Математика | ||||
Евстигнеев В. А. Применение теорий графов в программировании./Под ред. Л. П. Ершова.— М.: Наука. Главная редакция физико-математической литературы, 1985—352 с. Книга посвящена вопросам использования методов теории графов для исследования структуры сложных программ, определения их параметров, ворифнкации, организации хранения и поиска информации, распределения памяти и для решения дру-1их вопросов, возникающих в системном программировании и смежных областях. | ||||
ОТ РЕДАКТОРА Программирование — это новый вид универсально^ деятельности. Человек должен вложить в ЭВМ все, что видит, слышит, знает, и научить ее всему, что делает сам. Об этом приходится время от времени вспоминать, для того чтобы не суживать чрезмерно кругозор при занятии программированием. М. Нива в своей научной переписке как-то указал, что над многими информати-ками довлеет наивное заблуждение, связанное с кажущейся простотой основных структур программирования: им кажется, что сравнительно небольшое количество универсальных методов позволяет им наытп ключ к решению практически любой «реальной» задачи программирования. Сходную мысль высказывал Э. Дейк-стра: воюя с теми, кто оценивает продуктивность программиста по числу написанных команд, он отмечал, что при грамотном программировании на тысячу строк программного текста надо написать в десять раз больше рассуждений и доказательств, гарантирующих всеобщую применимость программы. Все три высказанных тезиса некоторым образом фокусируются на материале этой-книги. Важнейшим свойством информационной модели или управляющей системы является ее структура, или, говоря математическим языком, совокупность бинарных отношений па наборах элементарных единиц данных и действий. Этн структуры данных и структуры действий являются по выражению А. А, Берса единственными ипостасями программ и обрабатываемой ими информации, в которых они могут существовать в воображении программиста и во чреве компьютера. Вот почему графы являются основной конструкцией для программиста. Графы обладают огромной, неисчерпаемой изобразительной силой, соразмерной масштабу задачи программирования. ОГЛАВЛЕНИЕ От редактора ......;,,,.,, 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 Цена: 75руб. |
||||