Яндекс.Метрика
Programmer

Песни о Паскале | Книга «Графомания»


Обновлено 2022-11-18

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

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


Аннотация


Рассмотрены алгоритмы на графах и множествах. Неформальное изложение алгоритмов сопровождает работающий код c контрольными примерами, доведенными до числа. Код воплощен на объектно-ориентированном языке программирования Delphi. Подробно описана техника программирования задач, а листинги детально прокомментированы. Книга может служить дополнением к учебникам по дискретной математике, а также справочником по алгоритмам. Будет полезна студентам, аспирантам и программистам, решающим практические задачи на графах.

Предисловие


Графомания — мучительная хворь, симптом которой выражен в неодолимой тяге к маранию бумаги. Замечено, что поражает она организмы, ослабленные математикой. Иначе чем ещё объяснить обилие книг под общим названием «Теория графов»? Почти все они сочинены математиками для математиков, и лишь немногие доступны простым смертным: инженерам, студентам, и любознательным пенсионерам. И поскольку эти книги от математиков, там тоже не обходится без теорем и доказательств. Впрочем, отбросим иронию, и воздадим хвалу всем талантам, коим мы обязаны этим украшением дискретной математики, тесно примыкающим к информатике и программированию.

Однако, в конечном счёте, любую теорию прилагают к практике. И тогда то, что родилось в голове математика, попадает в голову программиста, становясь (если повезёт) работающей программой. На этом пути программист одолевает массу своих проблем: ищет оптимальные структуры данных, строит иерархию объектов, процедур и функций. При всём уважении к математике, он вынужден направлять усилия не на теоремы и доказательства, а на эти технические детали. Разумеется, что программисту надо ясно представлять воплощаемый в программу алгоритм, понимать идеи, лежащие в его основе, и без математической литературы ему не обойтись. И всё же книга, задуманная программистом для программистов, ему не повредит. Итак, цель этой книги в том, чтобы ознакомить программиста с идеями решений задач на графах, а также с техникой кодирования этих задач. Идеи излагаются неформально, без теорем и доказательств (взамен чего даются ссылки на литературу). Потому книгу можно трактовать и как популярную теорию графов.

И всё же программирование, как и математика, — дисциплина строгая и точная. Потому словесные пояснения и рисунки здесь дополнены работающим, практически «боевым» кодом. Этот подробно прокомментированный код подкрепляет пояснения: так, детали, не вполне понятные в словесном изложении, могут проясниться читателю при изучении листингов. По этой причине при написании кода автор стремился сделать его в первую очередь понятным и наглядным, отдавая эффективности второе место (но не последнее).

Код написан на языке Pascal, точнее, на том его диалекте, что нынче зовётся Delphi. И тому есть, по меньшей мере, две причины. Во-первых, язык Pascal распространён в образовании, стало быть, многим знаком. К тому же он так прост, что листинг поймёт и тот, кто пишет на других языках. Во-вторых, Delphi-версия языка обладает мощным объектно-ориентированным аппаратом, как нельзя лучше подходящим для воплощения излагаемых идей. Уверен, что при должном понимании материала книги, читатель без особого труда переведёт код на любой нужный ему язык. Замечу, кстати, что задачи на графах — те ещё загогулины, — дают прекрасный полигон для обретения опыта объектно-ориентированного программирования (ООП). Почему бы не воспользоваться этим полигоном?

В тщетных попытках объять необъятное, автор смог представить здесь лишь часть наиболее популярных алгоритмов на графах; перечень этих задач и сопутствующего материала дан в таблице:


Содержание материала Главы
Знакомство с объектами, отношениями и множествами 2
Представление объектов в языке Delphi 3 — 5
Представление множеств, операции с множествами 6, 7
Понятие о сложности (трудоёмкости) алгоритмов 8
Задачи на множествах:
  • разбиение множества на подмножества;
  • задача о наименьшем разбиении (ЗНР);
  • задача о наименьшем покрытии (ЗНП).
 9 — 11
Представление отношений графами 12
Программная реализация, ввод и вывод графов 13
Группа задач на достижимость:
  • взаимная достижимость вершин;
  • кратчайшие пути между вершинами;
  • выделение сильно связанных компонент.
 14 — 16
Группа задач на размещение:
  • независимые вершины и клики;
  • доминирующие множества;
  • раскраски;
  • центры;
  • p-центры;
  • p-медианы.
 17 — 22
Остовные деревья 23
Группа задач о потоках:
  • максимальный поток в сети;
  • поток, ограниченный сверху и снизу;
  • минимальная стоимость потока.
 24 — 26
Паросочетания:
  • паросочетание в двудольном графе;
  • паросочетание в произвольном графе;
  • алгоритм Эдмондса (Edmonds).
 27 — 29
Цикл Эйлера и задача почтальона:
  • на неориентированном графе;
  • на орграфе.
 30, 31
Задачи Гамильтона и коммивояжёра:
  • разомкнутая задача Гамильтона;
  • замкнутая задача Гамильтона (контур);
  • комбинирование методов для задач Гамильтона;
  • задачи коммивояжёра.
 32 — 35