|
Оглавление
Предисловие
В недавно вышедшей из печати работе одного из авторов «Теория графов для учителей, для школьников... и не только» методам решения графовых задач отведено небольшое место. Это сделано сознательно, поскольку алгоритмы должны изучаться вместе с их реализацией на компьютере, а это предполагает использование языка программирования и неизбежно приводит к увеличению объема учебного материала. Насыщение издания сопутствующей информацией, которая вряд ли понадобится учителю математики, нецелесообразно. Изначально было задумано отдельное пособие, и вот оно перед вами. В данной книге мы решили остановиться на языке Паскаль. В школьной информатике он является наиболее широко распространенным на сегодняшний день языком программирования благодаря удобству и доступности систем программирования на нем. Все рассматриваемые алгоритмы запрограммированы и протестированы в учебной среде программирования PascalABC. Но те же самые реализации сработают и в Интегрированной среде разработки PascalABC.NET. Эту книгу можно использовать в качестве учебника при изучении алгоритмизации и программирования на углубленном уровне. Конечно, есть и другие издания, посвященные обработке графов на основе Паскаля. Однако они не ориентированы на учителя информатики. Как построена книга? Она разделена на пять глав. В первой в кратких и общих чертах описаны составляющие языка PascalABC, которые в дальнейшем используются при составлении демонстрационных программ, включая сюда процедуры и функции, рекурсию, указатели и динамические переменные. Во второй главе довольно подробно обсуждаются вопросы программной реализации динамических структур данных и стандартные приемы работы со стеками, очередями и линейными связными списками. В небольшой третьей главе мы знакомим читателя с важнейшим понятием сложности вычислительного алгоритма. Определение нестрогое, без излишней формализации. Думается, однако, что этого вполне достаточно для первого знакомства. Четвертая глава посвящена алгоритмическому решению задач на неориентированных графах, пятая — на ориентированных. Кроме всего прочего, здесь применяются такие универсальные приемы решения комбинаторных задач, как полный перебор вариантов и элементы исчерпывающего поиска. Изложение подробное, для лучшего усвоения материала алгоритмы иллюстрируются примерами исполнения, а графы — рисунками. Вместе с тем оценивается время обработки графа в зависимости от числа его вершин и ребер (дуг). Как обычно, для закрепления пройденного материала предлагаются упражнения и задачи для самостоятельного решения, различные по типу и сложности. В небольшом приложении содержатся сведения о математиках и программистах, чьи имена встречаются на страницах книги. В конце — список литературы, включающий работы по структурам данных и программированию на Паскале. Доказательства теорем и корректности алгоритмов в нашей книге отсутствуют. Их можно найти в рекомендованной литературе. Теперь о соглашениях, о которых надо упомянуть. Новые термины, а также отдельные слова или фразы, если надо подчеркнуть их особое значение или обратить на них внимание, выделены курсивом. Стандартные элементы исходных программ, такие как идентификаторы и комментарии, набраны в полужирном начертании, служебные слова — в полужирном. Уделяя большое внимание положению служебных слов и отступов строк, мы стремились представить наши программы в наиболее ясной и лаконичной форме. Авторы Об авторах
 Мельников Олег Исидорович Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.
 Морозов Алексей Алексеевич Старший преподаватель кафедры информатики и методики преподавания информатики физико-математического факультета Белорусского государственного педагогического университета. Научные интересы: дискретная математика, компьютерное моделирование, программирование. Автор и соавтор ряда учебных и учебно-методических пособий.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||