Оглавление

Введение

Часть I. Обработка и визуализация графов

ГЛАВА 1. ГРАФЫ И СЕТИ

1.1. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ

1.1.1.Обыкновенные графы и их свойства; 1.1.2. Деревья и их основные свойства; 1.1.3. Хордальные графы и их классификация; 1.1.4. Алгоритмы распознавания и раскраски; 1.1.5. Кратчайшие цепи; 1.1.6. Задача о минимальной связке.

1.2. ОРГРАФЫ И СЕТИ

1.2.1. Орграфы; 1.2.2. Кратчайшие пути; 1.2.3. Генерация путей; 1.2.4. Генерация контуров; 1.2.5. Сети и задачи о потоках; 1.2.6. Алгоритм Форда-Фалкерсона; 1.2.7. Алгоритмы Диница и Карзанова; 1.2.8. Изображение графов и сетей.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 2. ОРИЕНТИРОВАННЫЕ ДЕРЕВЬЯ

2.1. ОРДЕРЕВЬЯ И ИХ СВОЙСТВА

2.1.1. Корневые деревья; 2.1.2. Бинарные деревья; 2.1.3. Представление деревьев; 2.1.4. Перечисление и подсчет деревьев.

2.2. ОБХОДЫ ГРАФОВ И ДЕРЕВЬЕВ В ГЛУБИНУ И ШИРИНУ

2.2.1. Разметки, нумерации, обходы, укладки; 2.2.2. Базисные нумерации; 2.2.3. Обходы в ширину и глубину; 2.2.4. Остовный лес обхода в глубину и глубинное остовное дерево; 2.2.5. Рекурсивный алгоритм обхода графа в глубину; 2.2.6. Общий алгоритм обхода графа с запоминанием дуг; 2.2.7. Общий алгоритм обхода графа с запоминанием его вершин; 2.2.8. Алгоритм обхода графа в ширину с использованием внешней очереди; 2.2.9. Алгоритм обхода графа в ширину с использованием внутренней очереди; 2.2.10. Алгоритм обхода графа в ширину без использования дополнительной памяти; 2.2.11. Алгоритм обхода в ширину графа с циклическими списками дуг; 2.2.12. Способы прохождения бинарных деревьев; 2.2.13. Алгоритм обхода бинарного дерева в глубину с внешним стеком; 2.2.14. Алгоритм обхода в глубину прошитого бинарного дерева; 2.2.15. Замечания; 2.2.16. Алгоритм обхода бинарного дерева в глубину без использования дополнительной памяти; 2.2.17. Обход в глубину произвольных деревьев и лесов; 2.2.18. Алгоритм обхода графа в глубину без использования дополнительной памяти; 2.2.19. Алгоритм прямой нумерации вершин графа; 2.2.20. Алгоритм базисных нумераций графа; 2.2.21. Алгоритм обхода графа в глубину с двусторонним прохождением дуг графа; 2.2.22. Алгоритм обхода графа в глубину с двусторонним прохождением дуг и распределенной реализацией стека; 2.2.23. Алгоритм обхода графа в глубину с двусторонним прохождением дуг и без использования дополнительной памяти; 2.2.24. Алгоритм обхода в глубину графа, представленного в виде массива дуг, с двусторонним прохождением дуг графа.

2.3. ГЕНЕРАЦИЯ ДЕРЕВЬЕВ

2.3.1. Алгоритм генерации упорядоченных деревьев; 2.3.2. Алгоритм генерации бинарных деревьев; 2.3.3. Алгоритм генерации бинарных деревьев заданной высоты; 2.3.4. Алгоритм генерации $k$-арных деревьев; 2.3.5. Алгоритм генерации корневых деревьев; 2.3.6. Алгоритм генерации свободных деревьев; 2.3.7. Генерация равновероятных деревьев; 2.3.8. Алгоритм прямой генерации равновероятных упорядоченных корневых деревьев; 2.3.9. Алгоритм генерации по номеру равновероятных $k$-арных деревьев.

2.4. КАРКАСЫ

2.4.1. Задача об отыскании оптимального каркаса; 2.4.2. Алгоритмы перечисления всех каркасов; 2.4.3. Поиск каркасов с заданными свойствами.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 3. БЕСКОНТУРНЫЕ ГРАФЫ

3.1. ОСНОВНЫЕ СВОЙСТВАМ И АЛГОРИТМЫ

3.1.1. Основные свойства и подклассы; 3.1.2. Топологическая сортировка; 3.1.3. Кратчайшие пути; 3.1.4. Критический путь; 3.1.5. Путевое покрытие.

3.2. ТРАНЗИТИВНОЕ ЗАМЫКАНИЕ И ТРАНЗИТИВНАЯ РЕДУКЦИЯ

3.2.1. Необходимые определения; 3.2.2. Алгоритм Уоршалла; 3.2.3. Общая форма алгоритма Уоршалла; 3.2.4. Алгоритмы Горальчиковой-Коубека и Симона; 3.2.5. Алгоритм Жомард-Мину; 3.2.6. Быстрый алгоритм слияния списков; 3.2.7. Определение транзитивного замыкания и транзитивной редукции при неполностью известной матрице смежности; 3.2.8. Замыкание относительно множества вершин.

3.3. КОНГРУЭНТНОЕ ЗАМЫКАНИЕ ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ

3.3.1. Задача нахождения конгруэнтного замыкания; 3.3.2. Быстрый алгоритм конгруэнтного замыкания; 3.3.3. Ациклическое конгруэнтное замыкание; 3.3.4. Уточнение алгоритма быстрого конгруэнтного замыкания; 3.3.5. Случай единственной эквивалентности; 3.3.6. Симметричное конгруэнтное замыкание; 3.3.7. Унификация; 3.3.8. Проверка эквивалентности выражений; 3.3.9. Проверка свойства соединения без потерь.

3.4. НАХОЖДЕНИЕ БЛИЖАЙШИХ ПРЕДКОВ

3.4.1. Постановка проблемы; 3.4.2. Общий вид быстрого алгоритма для статических деревьев; 3.4.3. Сжатое дерево; 3.4.4. Сбалансированное бинарное дерево; 3.4.5. Быстрый алгоритм для задачи с соединением корней; 3.4.6. Более быстрый алгоритм для задачи с соединением корней; 3.4.7. Заключительные замечания.

3.5. ГРАФ ГЕРЦА

3.5.1. Бикомпоненты и граф Герца; 3.5.2. Матричный алгоритм отыскания бикомпонент; 3.5.4. Пошаговая форма алгоритма Тарьяна; 3.5.5. Алгоритм Фараджева; 3.5.6. Алгоритм Касьянова.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 4. СВОДИМЫЕ И РЕГУЛЯРИЗУЕМЫЕ ГРАФЫ

4.1. КЛАСС СВОДИМЫХ ГРАФОВ

4.1.1. Уграф, фрагменты и подфрагменты; 4.1.2. Альты, гамаки и интервалы; 4.1.3. Отношения обязательного предшествования и обязательной преемственности; 4.1.4. $F$-лучи, $F$-области и правильная нумерация; 4.1.5. Фактор-уграфы; 4.1.6. Интервальное представление уграфа; 4.1.7. Интервально-сводимые уграфы; 4.1.8. Регуляризуемые уграфы; 4.1.9. Аранжировка и аранжируемые графы; 4.1.10. Разборные уграфы; 4.1.11. Алгоритм проверки сводимости графа; 4.1.12. Упрощенный вариант алгоритма; 4.1.13. Порядок втягивания вершин; 4.1.14. Преобразование несводимых графов; 4.1.15. Преобразования расщепления; 4.1.16. Стандартное преобразование.

4.2. РАЗРУШЕНИЕ КОНТУРОВ В СВОДИМЫХ ГРАФАХ

4.2.1. Постановка задачи; 4.2.2. Необходимые определения; 4.2.3. Потокая сеть для G; 4.2.4. Определение мощности минимального множества разрывающих дуг; 4.2.5. Нахождение минимального множества вершин, разрезающего циклы; 4.2.6. Приближенный алгоритм нахождения множества разрывающих дуг; 4.2.7. Алгоритм Бергера-Шора; 4.2.8. Алгоритм Шамира.

4.3. АНАЛИЗ ЦИКЛИЧЕСКОЙ СТРУКТУРЫ И ЦИКЛИЧЕСКИ СВОДИМЫЕ ГРАФЫ

4.3.1. Понятие цикла в уграфе; 4.3.2. Достоверные частотные отношения; 4.3.3. Участки повторяемости; 4.3.4. Циклические участки графа; 4.3.5. Циклически сводимые графы; 4.3.6. Полные D-последовательности; 4.3.7. Связь со сводимыми графами; 4.3.8. Алгоритм Шпекенмейера для задачи $FVS$.

4.4. ПЕРЕЧИСЛЕНИЕ ПУТЕЙ

4.4.1. Сильные и слабые укладки; 4.4.2. Построение укладок; 4.4.3. Постановка задачи перечисления; 4.4.4. Формальная постановка задачи; 4.4.5. Алгоритмы перечисления путей; 4.4.6. Алгоритмы прямого потокового анализа.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 5. ВИЗУАЛИЗАЦИЯ

5.1. ЗАДАЧА И МЕТОДЫ ВИЗУАЛИЗАЦИИ

5.1.1. Рисование графов на плоскости; 5.1.2. Ортогональные изображения; 5.1.3. Использование физических аналогий; 5.1.4. Трехмерные представления; 5.1.5. Изображение помеченных графов.

5.2. ПЛАНАРНЫЕ ГРАФЫ И ИХ ИЗОБРАЖЕНИЯ

5.2.1. Планарные графы и их свойства; 5.2.2. Рисование деревьев; 5.2.3. Рисование последовательно-параллельных графов; 5.2.4. Рисование бесконтурных графов; 5.2.5. Переход к планарному графу; 5.2.6. Выпуклые представления; 5.2.7. Методы, основанные на канонических упорядочениях.

5.3. ПОУРОВНЕВОЕ РИСОВАНИЕ ОРИЕНТИРОВАННЫХ ГРАФОВ

5.3.1. Общая схема поуровневого подхода; 5.3.2. Распределение вершин по уровням; 5.3.3. Определение порядка вершин на уровне; 5.3.4. Определение координат вершин на уровне; 5.3.5. Предварительные преобразования графа.

5.4. ИЕРАРХИЧЕСКИЕ ГРАФЫ И ГРАФОВЫЕ МОДЕЛИ

5.4.1. Иерархические графы; 5.4.2. Изображения иерархических графов; 5.4.3. Иерархические графовые модели; 5.4.4. Использование инвариантных свойств для задания семантики модели; 5.4.5. Трансформационный подход к заданию семантики графовой модели.

5.5. СИСТЕМЫ ВИЗУАЛИЗАЦИИ ГРАФОВ И ГРАФОВЫХ МОДЕЛЕЙ

5.5.1. Вопросы визуализации и визуальной обработки; 5.5.2. Системы визуализации и графовые редакторы; 5.5.3. Графовые библиотеки; 5.5.4. Система HIGRES.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

Часть II. Применение графов и граф-моделей

ГЛАВА 6. ИНФОРМАЦИОННЫЕ ДЕРЕВЬЯ

6.1. ОДНОМЕРНЫЕ СТРУКТУРЫ ДАННЫХ

6.1.1. Деревья сортировки; 6.1.2. АВЛ-деревья; 6.1.3. Балансированные по весу деревья (ВВ-деревья); 6.1.4. Выровненные деревья; 6.1.5. 1-2-братские деревья; 6.1.6. 2-3-деревья; 6.1.7. Кучи; 6.1.8. В-деревья; 6.1.9. Другие страничные деревья.

6.2. МНОГОМЕРНЫЕ СТРУКТУРЫ ДАННЫХ

6.2.1. Многомерное дерево сортировки; 6.2.2. Многомерные В-деревья; 6.2.3. Деревья множественных атрибутов; 6.2.4. Парадигмы для МАТ-структур.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 7. СИНТАКСИЧЕСКИЕ ДЕРЕВЬЯ

7.1. СИНТАКСИС ЯЗЫКА И ЗАДАЧА ФАЗЫ АНАЛИЗА

7.1.1. Синтаксис языка, лексемы, понятия и атрибуты; 7.1.2. Схема процесса трансляции; 7.1.3. Лексический, синтаксический и контекстный анализ.

7.2. ПОРОЖДАЮЩИЕ ГРАММАТИКИ

7.2.1. Цепочки и языки; 7.2.2. Грамматики составляющих; 7.2.3. Контекстно-свободные языки; 7.2.4. Эквивалентные преобразования грамматик.

7.3. ЛЕКСИЧЕСКИЙ АНАЛИЗ

7.3.1. Распознаватели; 7.3.2. Функции лексического анализа; 7.3.3. Реализация лексического анализатора.

7.4. СИНТАКСИЧЕСКИЙ АНАЛИЗ

7.4.1. Стратегии разбора; 7.4.2. Автоматы с магазинной памятью; 7.4.3. Нисходящий МП-распознаватель; 7.4.4. $LL$-грамматики и $LL$-распознаватель; 7.4.5. Восходящий МП-распознаватель; 7.4.6. Грамматики предшествования; 7.4.7. Горизонтальный разбор; 7.4.8. Алгоритм Эрли; 7.4.9. $LR$-грамматики; 7.4.10. $LR$-анализатор; 7.4.11. Обработка синтаксических ошибок.

7.5. ПЕРЕВОД И КОНСТРУКТОРЫ АНАЛИЗАТОРОВ

7.5.1. Понятие перевода, СУ-схемы и преобразователя; 7.5.2. Конструктор лексических анализаторов; 7.5.3. Конструкторы синтаксических анализаторов; 7.5.4. Конструктор $LL$-преобразователя; 7.5.5. Конструктор $LR$-преобразователя; 7.5.6. Использование конструкторов.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 8. КОНТЕКСТНЫЙ АНАЛИЗ

8.1. ЗАДАЧА КОНТЕКСТНОГО АНАЛИЗА

8.1.1. Атрибуты абстрактной программы; 8.1.2. Области видимости и идентификация; 8.1.3. Атрибутная индукция.

8.2. АТРИБУТНЫЕ ГРАММАТИКИ

8.2.1. Определение атрибутных грамматик; 8.2.2. Пример атрибутной грамматики; 8.2.3. Атрибутное вычисление.

8.3. КОНСТРУИРОВАНИЕ АБСТРАКТНЫХ СИНТАКСИЧЕСКИХ ПРЕДСТАВЛЕНИЙ

8.3.1. Абстрактное синтаксическое дерево и построение дерева выражения; 8.3.2. Дэги выражений; 8.3.3. Метод нумерации для конструирования вершин в дэге.

8.4. ОСНОВНЫЕ ПОДКЛАССЫ АТРИБУТНЫХ ГРАММАТИК И ВЫЧИСЛЕНИЙ

8.4.1. Чисто синтезированные грамматики; 8.4.2. $l$-упорядоченные грамматики; 8.4.3. Сильно ациклические грамматики; 8.4.4. Вычислители для грамматик общего вида; 8.4.5. Восходящее вычислений для S-атрибутных грамматик.

8.5. -АТРИБУТНЫЕ ГРАММАТИКИ

8.5.1. Порядок обхода в глубину и $L$-атрибутные грамматики; 8.5.2. Трансляционные схемы; 8.5.3. Удаление левой рекурсии из трансляционной схемы; 8.5.4. Конструирование предсказывающего транслятора; 8.5.5. Удаление встроенных действий из трансляционных схем; 8.5.6. Наследуемые атрибуты на стеке разбора; 8.5.7. Восходящий разбор и трансляция с синтезируемыми атрибутами; 8.5.8. Замена наследуемых атрибутов синтезированными; 8.5.9. Пример атрибутной грамматики, трудной для обработки; 8.5.10. Рекурсивные вычислители и обходы слева направо; 8.5.11. Другие обходы рекурсивных вычислителей.

8.6. РАСПРЕДЕЛЕНИЕ ПАМЯТИ ПОД АТРИБУТЫ

8.6.1. Вводные замечания; 8.6.2. Распределение памяти под атрибуты во время трансляции; 8.6.3. Удаление копирований; 8.6.4. Распределение памяти во время конструирования транслятора; 8.6.5. Пример генерации промежуточного представления; 8.6.6. Неперекрывающиеся времена существования.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 9. КОДОГЕНЕРАЦИЯ

9.1. ЗАДАЧА КОДОГЕНЕРАЦИИ И ОБЪЕКТНАЯ МАШИНА

9.1.1. Задача кодогенерации; 9.1.2. Вход кодогенератора; 9.1.3. Трехадресные представления; 9.1.4. Объектные программы; 9.1.5. Управление памятью; 9.1.6. Выбор команд; 9.1.7. Распределение регистров; 9.1.8. Выбор порядка вычисления; 9.1.9. Архитектура объектной машины; 9.1.10. Стоимость команды.

9.2. УПРАВЛЕНИЕ ПАМЯТЬЮ ПЕРИОДА ИСПОЛНЕНИЯ

9.2.1. Вводные замечания; 9.2.2. Статическое распределение; 9.2.3. Стековое распределение; 9.2.4. Адресация периода исполнения для имен.

9.3. ЛИНЕЙНЫЕ УЧАСТКИ И УПРАВЛЯЮЩИЕ ГРАФЫ

9.3.1. Линейные участки и их выделение; 9.3.2. Преобразования на линейных участках; 9.3.3. Информация о последующем использовании; 9.3.4. Управляющие графы и представление лучей.

9.4. ПРОСТОЙ КОДОГЕНЕРАТОР

9.4.1. Вводные замечания; 9.4.2. Дескрипторы регистров и адресов; 9.4.3. Алгоритм кодогенерации; 9.4.4. Функция нахождения места размещения; 9.4.5. Генерация кода для операторов других типов; 9.4.6. Условные операторы.

9.5. РАСПРЕДЕЛЕНИЕ И ПРИСВАИВАНИЕ РЕГИСТРОВ

9.5.1. Глобальное распределение регистров; 9.5.2. Счетчики использований; 9.5.3. Присваивание регистров для внешних циклов; 9.5.4. Распределение регистров путем раскраски графа.

9.6. ПРЕДСТАВЛЕНИЕ ЛУЧЕЙ ДЭГАМИ И ГЕНЕРАЦИЯ КОДА ПО ДЭГУ

9.6.1. Представление линейных участков в виде дэгов; 9.6.2. Конструирование дэга луча; 9.6.3. Применение дэгов; 9.6.4. Массивы, указатели и вызовы функций; 9.6.5. Генерация кода по дэгу; 9.6.6. Задача переупорядочения; 9.6.7. Эвристическое упорядочение для дэгов; 9.6.8. Оптимальное упорядочение деревьев; 9.6.9. Алгоритм разметки; 9.6.10. Генерация кода по помеченному дереву; 9.6.11. Многорегистровые операции; 9.6.12. Алгебраические свойства; 9.6.13. Общие подвыражения.

9.7. АЛГОРИТМ КОДОГЕНЕРАЦИИ, ОСНОВАННЫЙ НА ДИНАМИЧЕСКОМ ПРОГРАММИРОВАНИИ

9.7.1. Класс регистровых машин; 9.7.2. Принцип динамического программирования и непрерывное вычисление; 9.7.3. Непрерывное вычисление; 9.7.4. Алгоритм динамического программирования.

9.8. ПОКАДРОВАЯ ОПТИМИЗАЦИЯ

9.8.1. Понятие покадровой оптимизации; 9.8.2. Избыточные загрузки и запоминания; 9.8.3. Недостижимый код; 9.8.4. Оптимизации потока управления; 9.8.5. Алгебраические упрощения; 9.8.6. Понижение силы операции; 9.8.7. Использование машинных идиом.

9.9. ГЕНЕРАЦИЯ КОДОГЕНЕРАТОРОВ

9.9.1. Генерация кода и переписывание деревьев; 9.9.2. Поиск по образцу при разборе; 9.9.3. Процедуры семантической проверки; 9.9.4. Покрывающие деревья; 9.9.5. Система BEG.

9.10. ГЕНЕРАЦИЯ ОПТИМАЛЬНОГО КОДА ДЛЯ СТЕКОВЫХ МАШИН

9.10.1. Стековая машина и корневые деревья; 9.10.2. Стековые вычисления; 9.10.3. Коммутативные операции; 9.10.4. Ассоциативные коммутативные операции.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 10. ПОТОКОВЫЙ АНАЛИЗ ПРОГРАММ

10.1. АНАЛИЗ ПОТОКА УПРАВЛЕНИЯ

10.1.1. Представление множеств исполнений; 10.1.2. Структуризация; 10.1.3. Нахождение свойств операторов и переходов; 10.1.4. Выбор порядка обработки операторов.

10.2. ГАМАЧНОЕ ПРЕДСТАВЛЕНИЕ УГРАФОВ

10.2.1. Иерархия вложенных альтов; 10.2.2. Нумерации $K$ и $L$; 10.2.3. Алгоритм $K$-нумерации; 10.2.4. Алгоритм $L$-нумерации; 10.2.5. Свойства нумераций $K$ и $L$; 10.2.6. Алгоритм выделения гамаков.

10.3. ОТНОШЕНИЯ ОБЯЗАТЕЛЬНОГО ПРЕДШЕСТВОВАНИЯ И ОБЯЗАТЕЛЬНОЙ ПРЕЕМСТВЕННОСТИ

10.3.1. Отношение доминирования и их свойства; 10.3.2. Семидоминаторы; 10.3.3. Алгоритм Ленгауэра-Тарьяна; 10.3.4. Реализация операций LINK и EVAL; 10.3.5. Общий вид алгоритма Ленгауэра-Тарьяна; 10.3.6. Микродеревья и их использование; 10.3.7. Линейный алгоритм Бухбаума-Каплана-Роджерс; 10.3.8. Инкрементальное вычисление доминаторных деревьев; 10.3.9. Алгоритм нахождения доминаторов в сводимом уграфе.

10.4. СТРУКТУРНАЯ СЛОЖНОСТЬ ПРОГРАММ

10.4.1. Понятие сложности программы; 10.4.2. Цикломатическая мера Мак-Кейба; 10.4.3. Другие меры сложности, основанные на уграфе; 10.4.4. Декомпозация уграфов.

10.5. ПОТОКОВЫЙ АНАЛИЗ ПРОГРАММ

10.5.1. Задача анализа потока данных; 10.5.2. Метод разметки; 10.5.3. Примеры задач анализа свойств состояний; 10.5.4. Алгоритм нахождения стационарной разметки; 10.5.5. Факторизация; 10.5.6. Свойства схем анализа свойств состояний.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 11. ПРЕОБРАЗОВАНИЕ ПРОГРАММ

11.1. УНИФИКАЦИЯ И СИСТЕМЫ ПЕРЕПИСЫВАНИЯ ТЕРМОВ

11.1.1. Задача унификации; 11.1.2. Унификация как решение множества урвнений; 11.1.3. Мультиуравнения и алгоритмы их решения; 11.1.4. Улучшение алгоритма унификации при обработке неунифицируемых данных; 11.1.5. Алгоритм проверки унифицируемости, основанный на представлении термов дэгами; 11.1.6. Линейный алгоритм унификации Патерсона-Вегмана; 11.1.7. Алгоритм Уэ; 11.1.8. Сравнение алгоритмов унификации; 11.1.9. Эквациональные спецификации; 11.1.10. Понятие системы переписывания термов; 11.1.11. Свойство Черча-Россера, конфлюэнтность, нетеровость и полнота системы переписывания термов; 11.1.12. Локальная конфлюэнтность и критические пары; 11.1.13. Построение полных СПТ для эквациональных теорий; 11.1.14. Методы доказательства нетеровости, основанные на упорядочении; 11.1.15. Алгоритм Кнута-Бендикса.

11.2. ПРОМЕЖУТОЧНЫЕ ПРЕДСТАВЛЕНИЯ ПРОГРАММ

11.2.1. Требования к промежуточному представлению; 11.2.2. Граф зависимостей по данным; 11.2.3. Зависимость по управлению; 11.2.4. Граф программных зависимостей; 11.2.5. Построение графа зависимостей; 11.2.6. Иерархический граф заданий; 11.2.7. Построение ИГЗ.

11.3. ОПЕРАТОРНЫЕ МОДЕЛИ ПРОГРАММ

11.3.1. Семантические и формальные схемы программ; 11.3.2. Класс крупноблочных схем программ; 11.3.3. Важные подклассы и их свойства; 11.3.4. Перераспределение памяти; 11.3.5. Схемы с распределенной памятью; 11.3.6. Схематизация программ; 11.3.7. Схемы с косвенной адресацией; 11.3.8. Корректные псевдораскраски; 11.3.9. Модель аннотированных программ; 11.3.10. Преобразования программ.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 12. ПРОЧИЕ ГРАФ-МОДЕЛИ

12.1. ДИАГРАММЫ БИНАРНЫХ РЕШЕНИЙ

12.1.1. Упорядоченные диаграммы бинарных решений и логические фрагменты; 12.1.2. Конструирование и манипуляция; 12.1.3. Представление математических объектов; 12.1.4. Другие применения.

12.2. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВА

12.2.1. Основные определения; 12.2.2. Параметры чу-множеств;
12.2.3. Частично упорядоченные множества и графы; 12.2.4. Решетки, подрешетки и полурешетки; 12.2.5. Теорема о неподвижной точке; 12.2.6. Кодирование частичных порядков; 12.2.7. Прозрачные частичные порядки и их применения; 12.2.8. Чу-множества и модели параллельных программ и процессов.

12.3. СЕТИ ПЕТРИ

12.3.1. События и условия; 12.3.2. Определение сети Петри; 12.3.3. Основные свойства сетей Петри; 12.3.4. Ограниченность и безопасность сети; 12.3.5. Классы языков сетей Петри; 12.3.6. Подклассы сетей Петри; 12.3.7. Обобщения сетей Петри; 12.3.8. Регулярные сети; 12.3.9. Иерархические сети.

12.4. ГРАФЫ АДРЕСУЕМЫХ ДАННЫХ

12.4.1. Граф данных; 12.4.2. Реализация графов данных; 12.4.3. Относительная адресация; 12.4.4. Вложения графов.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

Часть III. Приложения

ПРИЛОЖЕНИЕ 1. РАМ, ВУ-ЯЗЫК И СПИСОК $NP$-ПОЛНЫХ ЗАДАЧ

1.1. РАМ И ПОНЯТИЕ -ПОЛНОТЫ

1.1.1. Равнодоступная адресная машина; 1.1.2. Вычислительная
сложность РАМ-программ; 1.1.3. Свойства РАМ, связь РАМ с другими моделями вычислений; 1.1.4. Труднорешаемые и $NP$-полные задачи.

1.2. ЯЗЫК ВЫСОКОГО УРОВНЯ

1.2.1.Структуры данных; 1.2.2. Структуры действий; 1.2.3. Дополнительные средства.

1.3. СПИСОК -ПОЛНЫХ ЗАДАЧ

1.3.1.Покрытия и разбиения; 1.3.2. Подграфы и изоморфизм; 1.3.3. Расположения, укладки и нумерации; 1.3.4. Остовные деревья; 1.3.5. Разрезы и связность; 1.3.6. Пути; 1.3.7. Сети; 1.3.8. Множества и разбиения; 1.3.9. Хранение и поиск; 1.3.10. Программы и схемы; 1.3.11. Автоматы и языки; 1.3.12. Логика; 1.3.13. Игры и головоломки; 1.3.14. Алгебра и теория чисел; 1.3.15. Математическое программирование; 1.3.16. Теория расписаний; 1.3.17. Разные задачи.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 2. ХАРАКТЕРИСТИКИ РАЗМЕЩЕНИЙ ГРАФОВ

2.1. РАЗМЕР ОБЛАСТИ РАЗМЕЩЕНИЯ

2.1.1. Деревья; 2.1.2. Планарные графы; 2.1.3. Графы общего вида.

2.2. ОЦЕНКА ВЕЛИЧИНЫ УГЛОВ

2.3. ЧИСЛО СГИБОВ

2.4. СВЯЗЬ РАЗНЫХ ХАРАКТЕРИСТИК

2.4.1. Связь между размером и отношением сторон при изображении деревьев; 2.4.2. Связь между размером области и величины углового разрешения для планарных графов.

2.5. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ

2.5.1. Проверка планарности и вложения; 2.5.2. Прямолинейные и полилинейные изображения планарных графов; 2.5.3. Изображения графов с заданной степенью вершин; 2.5.4. Рисование деревьев.

БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ

СПИСОК ЛИТЕРАТУРЫ

Предметный указатель