Обложка Мельников О.И., Морозов А.А. Алгоритмы на графах: Использование языка Python
Id: 278173
456 руб.

Алгоритмы на графах:
Использование языка Python

URSS. 2022. 224 с. ISBN 978-5-9710-9235-3.

Аннотация

В настоящей книге достаточно популярно излагаются базовые алгоритмы на графах вместе с их реализациями на языке Python. Материал иллюстрирован большим числом примеров и рисунков, способствующих его усвоению.

Книга адресована прежде всего учителям информатики общеобразовательных учреждений (школ, гимназий, лицеев) и студентам соответствующих специальностей педагогических вузов, а также всем, кто интересуется прикладной теорией графов и программированием.... (Подробнее)


Оглавление
Оглавление3
От авторов5
Глава 1. Структуры данных9
Общие понятия11
1. Списки11
2. Списки со ссылками12
3. Стеки и очереди14
4. Двусторонняя очередь17
5. Двоичные деревья17
6. Структура данных «куча»19
Реализации в Python24
7. Списки и кортежи24
8. Стеки и очереди на основе списков list35
9. Очередь на основе списка со ссылками39
10. Очередь по приоритету на основе кучи41
Глава 2. Графы43
1. Общие понятия и обозначения45
2. Структуры данных для представления графов51
3. Ввод данных, которые задают граф57
4. Изоморфизм графов60
5. Поиск в ширину62
6. Расстояние между вершинами68
7. Выявление связных компонент графа68
8. Диаметр, радиус и центр графа70
9. Распознавание двудольного графа74
10. Поиск в глубину77
11. Остовное дерево наименьшего веса88
12. Фундаментальное множество циклов в графе101
13. Эйлеровы циклы105
14. Гамильтоновы циклы110
Глава 3. Ориентированные графы117
1. Топологическая сортировка вершин орграфа119
2. Все циклы в ориентированном графе129
3. Поиск кратчайших путей133
4. Кратчайшие пути между всеми парами вершин142
5. Транзитивное замыкание орграфа149
6. Максимальный поток в транспортной сети153
Приложения169
А. Справочные сведения из языка Python171
Б. Рекурсия187
В. Порождение перестановок197
Г. Построение изображения графа202
Д. Трудоемкость алгоритмов208
Е. Справочные сведения о математиках, упоминаемых в книге217
Рекомендуемая литература219

От автора

Уважаемые коллеги!

Графы часто встречаются в практических (и олимпиадных) задачах, и экономные алгоритмы их обработки всегда востребованы. Многие такие алгоритмы собраны в книге, которую вы держите в руках.

Опыт преподавания свидетельствует, что вычислительные алгоритмы должны изучаться вместе с их реализациями на компьютере, что предполагает использование языка программирования высокого уровня. Ранее уже была издана наша книга «Теория графов в алгоритмах и программах» , где алгоритмы обработки графов представлены на языке Pascal, просто потому, что он широко распространен на школьном уровне. Однако уже достаточно давно большую известность получил имеющий много преимуществ язык программирования Python. Именно последние версии Python 3 применяются в настоящем издании при программном исполнении алгоритмов.

Инструментальной системой программирования на Python мы избрали простую и удобную Интегрированную Среду Разработки (ИСР) Thonny, ориентированную на начинающих пользователей и вполне подходящую для наших целей. Сверх того, программы тестировались в среде разработки Spyder, специально предназначенной для организации научных расчетов с использованием Python для пользователей Windows (ее рекомендуется устанавливать в составе инструментального программного комплекса Anaconda).

Книга разделена на три главы. В первой, вводной, в общих чертах обсуждаются традиционные структуры данных, их аналоги и представления в Python и стандартные приемы работы с ними. Все это применяется в дальнейшем изложении.

Основное содержание составляют две другие главы. В них разбираются базовые алгоритмы решения известных графовых задач вместе с оценкой их вычислительной сложности в зависимости от числа вершин и ребер (дуг) исходного графа. Сюда вошли также полные реализации всех алгоритмов на языке Python. Изложение учебного материала подробное, для лучшего его усвоения работа алгоритмов иллюстрируется примерами ручного выполнения, а соответствующие графы — рисунками. Во второй главе даны алгоритмы решения задач для неориентированных графов, в третьей — для ориентированных. Сравнительно с предыдущей книгой добавлен алгоритм решения одной задачи транспортных сетей. В конце глав предлагаются упражнения и задачи для самостоятельного решения. Читать материал надо в том порядке, в котором он излагается.

Мы стремились изложитиь наши программы в простом и ясном стиле, присущем используемому языку программирования. Во многих случаях имеются дополнительные пояснения в комментариях.

Доказательства теорем и корректности алгоритмов в пособии отсутствуют, их можно найти в рекомендуемой литературе. Перечень книг содержит работы по теории графов и программированию на языке Python.

Содержание книги дополняют несколько приложений:

Приложение А. Здесь сосредоточены замечания по языку Python, которые помогут разобраться в деталях демонстрационных программ.

Приложение Б. В нем обсуждаются практические вопросы рекурсивного программирования.

Приложение В. В приложении рассматривается один комбинаторный алгоритм порождения всех перестановок n чисел 0, 1, …, n – 1.

Приложение Г. Здесь разъясняется простой способ программного построения изображения графа.

Приложение Д. В этом приложении уделено внимание понятию трудоемкости (сложности) вычислительных алгоритмов. Для первого знакомства с этой крайне важной темой материал излагается без излишней формализации.

Приложение Е. В последнем приложении содержатся краткие сведения о математиках и программистах, чьи имена встречаются на страницах данной книги.

Вообще говоря, это пособие для тех, кто уже знаком с программированием. Его можно рассматривать как дополнительный учебный материал при обучении алгоритмизации и программированию на углубленном уровне и в первую очередь для наиболее подготовленных учащихся.

Несколько слов о соглашениях, принятых при оформлении. Новые термины и понятия, а также отдельные слова или фразы, когда надо подчеркнуть их значение или обратить на них особое внимание, выделены курсивом. Программные тексты и результаты выполнения программ оформлены моноширинным шрифтом. А служебные (зарезервированные) слова языка Python выделены полужирным. Вывод результатов размещается после знака >>> (три угловые скобки в отдельной строке).

Авторы выражают признательность А. А. Буславскому за помощь при реализации алгоритма построения максимального потока в транспортной сети.


Об авторах
Мельников Олег Исидорович
Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.
Морозов Алексей Алексеевич
Старший преподаватель кафедры информатики и методики преподавания информатики физико-математического факультета Белорусского государственного педагогического университета. Научные интересы: дискретная математика, компьютерное моделирование, программирование. Автор и соавтор ряда учебных и учебно-методических пособий.