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

Оглавление

Предисловие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Авторы

Об авторах

Мельников Олег Исидорович

Олег Исидорович МЕЛЬНИКОВ

Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Автор и соавтор книг: «Лекции по теории графов» (М.: URSS); «Exercises in graph theory»; «Информатика. Методы алгоритмизации»; «Занимательные задачи

по теории графов»; «Математика для экономистов на базе “Mathcad”», «Обучение дискретной математике» (М.: URSS). Лауреат Государственной премии Республики Беларусь.

@@@ Есть фото

Морозов Алексей Алексеевич

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