URSS.ru Магазин научной книги
Обложка Мельников О.И., Морозов А.А. Теория графов в алгоритмах и программах: Книга для учителей, для школьников... и не только!
Id: 289912
549 р.

Теория ГРАФОВ В АЛГОРИТМАХ И ПРОГРАММАХ:
Книга для учителей, для школьников... и не только! №175. Изд. стереотип.

Теория графов в алгоритмах и программах: Книга для учителей, для школьников... и не только! URSS. 2022. 200 с. ISBN 978-5-9519-3414-7.
Типографская бумага

Аннотация

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

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


Оглавление
top
Предисловие5
Глава 1. Отличительные черты PascalABC8
1.1. Комментарии и утверждения8
1.2. Типы данных и операторы10
1.3. Процедуры и функции18
1.4. Модули23
1.5. Рекурсивные процедуры и функции27
1.6. Указатели и динамические переменные35
1.7. Упражнения и задачи для самостоятельного решения38
Глава 2. Структуры данных40
2.1. Понятие стека40
2.2. Реализация стека в массиве43
2.3. Очередь48
2.4. Реализация очереди в массиве49
2.5. Связные списки53
2.6. Стек и очередь в виде линейных списков59
2.7. Упражнения и задачи для самостоятельного решения63
Глава 3. Понятие трудоемкости алгоритма66
Глава 4. Графы74
4.1. Определения, обозначения и примеры74
4.2. Структуры данных для представления графов80
4.3. Ввод данных, которые определяют граф85
4.4. Построение изображения графа90
4.5. Изоморфизм графов93
4.6. Поиск в ширину101
4.7. Расстояние между вершинами107
4.8. Определение связных компонент графа108
4.9. Диаметр, радиус и центр графа109
4.10. Распознавание двудольного графа113
4.11. Поиск в глубину115
4.12. Остовное дерево наименьшего веса126
4.13. Фундаментальное множество циклов139
4.14. Эйлеровы циклы143
4.15. Гамильтоновы циклы148
4.16. Упражнения и задачи для самостоятельного решения155
Глава 5. Ориентированные графы157
5.1. Топологическая сортировка вершин орграфа157
5.2. Все циклы в ориентированном графе167
5.3. Поиск кратчайших путей172
5.4. Кратчайшие пути между всеми парами вершин181
5.5. Транзитивное замыкание орграфа190
5.6. Упражнения и задачи для самостоятельного решения194
Приложение196
Рекомендуемая литература198

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

В недавно вышедшей из печати работе одного из авторов «Теория графов для учителей, для школьников... и не только» методам решения графовых задач отведено небольшое место. Это сделано сознательно, поскольку алгоритмы должны изучаться вместе с их реализацией на компьютере, а это предполагает использование языка программирования и неизбежно приводит к увеличению объема учебного материала. Насыщение издания сопутствующей информацией, которая вряд ли понадобится учителю математики, нецелесообразно. Изначально было задумано отдельное пособие, и вот оно перед вами.

В данной книге мы решили остановиться на языке Паскаль.

В школьной информатике он является наиболее широко распространенным на сегодняшний день языком программирования благодаря удобству и доступности систем программирования на нем.

Все рассматриваемые алгоритмы запрограммированы и протестированы в учебной среде программирования PascalABC. Но те же самые реализации сработают и в Интегрированной среде разработки PascalABC.NET.

Эту книгу можно использовать в качестве учебника при изучении алгоритмизации и программирования на углубленном уровне.

Конечно, есть и другие издания, посвященные обработке графов на основе Паскаля. Однако они не ориентированы на учителя информатики.

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

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

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

Четвертая глава посвящена алгоритмическому решению задач на неориентированных графах, пятая — на ориентированных.

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

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

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

В конце — список литературы, включающий работы по структурам данных и программированию на Паскале.

Доказательства теорем и корректности алгоритмов в нашей книге отсутствуют. Их можно найти в рекомендованной литературе.

Теперь о соглашениях, о которых надо упомянуть. Новые термины, а также отдельные слова или фразы, если надо подчеркнуть их особое значение или обратить на них внимание, выделены курсивом.

Стандартные элементы исходных программ, такие как идентификаторы и комментарии, набраны в полужирном начертании, служебные слова — в полужирном. Уделяя большое внимание положению служебных слов и отступов строк, мы стремились представить наши программы в наиболее ясной и лаконичной форме.

Авторы


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