|
Оглавление
От автора
Уважаемые коллеги! Графы часто встречаются в практических (и олимпиадных) задачах, и экономные алгоритмы их обработки всегда востребованы. Многие такие алгоритмы собраны в книге, которую вы держите в руках. Опыт преподавания свидетельствует, что вычислительные алгоритмы должны изучаться вместе с их реализациями на компьютере, что предполагает использование языка программирования высокого уровня. Ранее уже была издана наша книга «Теория графов в алгоритмах и программах» , где алгоритмы обработки графов представлены на языке Pascal, просто потому, что он широко распространен на школьном уровне. Однако уже достаточно давно большую известность получил имеющий много преимуществ язык программирования Python. Именно последние версии Python 3 применяются в настоящем издании при программном исполнении алгоритмов. Инструментальной системой программирования на Python мы избрали простую и удобную Интегрированную Среду Разработки (ИСР) Thonny, ориентированную на начинающих пользователей и вполне подходящую для наших целей. Сверх того, программы тестировались в среде разработки Spyder, специально предназначенной для организации научных расчетов с использованием Python для пользователей Windows (ее рекомендуется устанавливать в составе инструментального программного комплекса Anaconda).
Книга разделена на три главы. В первой, вводной, в общих чертах обсуждаются традиционные структуры данных, их аналоги и представления в Python и стандартные приемы работы с ними. Все это применяется в дальнейшем изложении. Основное содержание составляют две другие главы. В них разбираются базовые алгоритмы решения известных графовых задач вместе с оценкой их вычислительной сложности в зависимости от числа вершин и ребер (дуг) исходного графа. Сюда вошли также полные реализации всех алгоритмов на языке Python. Изложение учебного материала подробное, для лучшего его усвоения работа алгоритмов иллюстрируется примерами ручного выполнения, а соответствующие графы — рисунками. Во второй главе даны алгоритмы решения задач для неориентированных графов, в третьей — для ориентированных. Сравнительно с предыдущей книгой добавлен алгоритм решения одной задачи транспортных сетей. В конце глав предлагаются упражнения и задачи для самостоятельного решения. Читать материал надо в том порядке, в котором он излагается. Мы стремились изложитиь наши программы в простом и ясном стиле, присущем используемому языку программирования. Во многих случаях имеются дополнительные пояснения в комментариях. Доказательства теорем и корректности алгоритмов в пособии отсутствуют, их можно найти в рекомендуемой литературе. Перечень книг содержит работы по теории графов и программированию на языке Python.
Содержание книги дополняют несколько приложений: Приложение А. Здесь сосредоточены замечания по языку Python, которые помогут разобраться в деталях демонстрационных программ. Приложение Б. В нем обсуждаются практические вопросы рекурсивного программирования. Приложение В. В приложении рассматривается один комбинаторный алгоритм порождения всех перестановок n чисел 0, 1, …, n – 1. Приложение Г. Здесь разъясняется простой способ программного построения изображения графа. Приложение Д. В этом приложении уделено внимание понятию трудоемкости (сложности) вычислительных алгоритмов. Для первого знакомства с этой крайне важной темой материал излагается без излишней формализации. Приложение Е. В последнем приложении содержатся краткие сведения о математиках и программистах, чьи имена встречаются на страницах данной книги.
Вообще говоря, это пособие для тех, кто уже знаком с программированием. Его можно рассматривать как дополнительный учебный материал при обучении алгоритмизации и программированию на углубленном уровне и в первую очередь для наиболее подготовленных учащихся.
Несколько слов о соглашениях, принятых при оформлении. Новые термины и понятия, а также отдельные слова или фразы, когда надо подчеркнуть их значение или обратить на них особое внимание, выделены курсивом. Программные тексты и результаты выполнения программ оформлены моноширинным шрифтом. А служебные (зарезервированные) слова языка Python выделены полужирным. Вывод результатов размещается после знака >>> (три угловые скобки в отдельной строке). Авторы выражают признательность А. А. Буславскому за помощь при реализации алгоритма построения максимального потока в транспортной сети.
Об авторах
 Мельников Олег Исидорович Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.
 Морозов Алексей Алексеевич Старший преподаватель кафедры информатики и методики преподавания информатики физико-математического факультета Белорусского государственного педагогического университета. Научные интересы: дискретная математика, компьютерное моделирование, программирование. Автор и соавтор ряда учебных и учебно-методических пособий.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||