Программирование — это новый вид универсально^ деятельности. Человек должен вложить в ЭВМ все, что видит, слышит, знает, и научить ее всему, что делает сам. Об этом приходится время от времени вспоминать, для того чтобы не суживать чрезмерно кругозор при занятии программированием. М. Нива в своей научной переписке как-то указал, что над многими информати-ками довлеет наивное заблуждение, связанное с кажущейся простотой основных структур программирования: им кажется, что сравнительно небольшое количество универсальных методов позволяет им наытп ключ к решению практически любой «реальной» задачи программирования. Сходную мысль высказывал Э. Дейк-стра: воюя с теми, кто оценивает продуктивность программиста по числу написанных команд, он отмечал, что при грамотном программировании на тысячу строк программного текста надо написать в десять раз больше рассуждений и доказательств, гарантирующих всеобщую применимость программы.
Все три высказанных тезиса некоторым образом фокусируются на материале этой-книги. Важнейшим свойством информационной модели или управляющей системы является ее структура, или, говоря математическим языком, совокупность бинарных отношений па наборах элементарных единиц данных и действий. Этн структуры данных и структуры действий являются по выражению А. А, Берса единственными ипостасями программ и обрабатываемой ими информации, в которых они могут существовать в воображении программиста и во чреве компьютера.
Вот почему графы являются основной конструкцией для программиста. Графы обладают огромной, неисчерпаемой изобразительной силой, соразмерной масштабу задачи программирования.
ОГЛАВЛЕНИЕ
От редактора ......;,,,.,, 5
Предисловие ,,,,,,,,,,,, 5 7
Глава 1. Основные понятия . . , , , , s , 9
§ 1. Основные определения теории графов ... 9
§ 2. Графы как модели программ, данных и процессов 19
§ 3. Графы как объекты обработки информации . . 26
Библиографический комментарий...... 32
Глава 2. Глобальный анализ графов.....» 33
§ 1. Нумерации, выявляющие логическую структуру
графа............ 33
§ 2. Логический анализ управляющих графов. Линейные компоненты и компоненты сильной связности 52 , § 3. Гамаки, полугамаки и шлейфы , . , 76
§ 4. Интервалы и сводимые графы...... 83
§ 5. Контуры в орграфах....., . , 105
Библиографический комментарий...... 118
Глава 3. Итеративные алгоритмы глобального анализа
графов. Пути и покрытия ........ 121
§ 1. Итеративный алгоритм Килдала ..... 121
* § 2. Пути в орграфах......... 130
§ 3. Пути, удовлетворяющие дополнительным ограничениям. Покрытия......... 138
§ 4. Отыскание доыинаторов в орграфе , 150
Библиографический комментарий......165
Глава 4. Оптимизационные задачи на графах , , i 166
§ 1. Построение оптимальных нумераций . , 166
§ 2. Конструирование оптимальных деревьев ... 192
§ 3. Балансированные деревья...... 214
Библиографический комментарий ,,.... 239
Глава 5. Разрезания и раскраска графов i * * 241
| 1. Разрезания графов......... 241
§ 2. Раскраска графов......... 278
Библиографический комментарий...... 292
Глава 6. Применение теории графов в программирова-
нии
294
5 1. Анализ я тестирЪвавие программ. Вычисление
характеристик программ....... 294
§ 2. Применение методов теории графов к организации вычислительного процесса ..... 309
5 3. Применение деревьев для организации больших
массивов информации ........ 325
Библиографический комментарий ,,,... 340
Список литературы.....,..... 342
Предметный указатель .......... 350
