Введение
Часть 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. Алгоритм генерации -арных деревьев; 2.3.5. Алгоритм генерации корневых деревьев; 2.3.6. Алгоритм генерации свободных деревьев; 2.3.7. Генерация равновероятных деревьев; 2.3.8. Алгоритм прямой генерации равновероятных упорядоченных корневых деревьев; 2.3.9. Алгоритм генерации по номеру равновероятных -арных деревьев.
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. Алгоритм Шпекенмейера для задачи .
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. -упорядоченные грамматики; 8.4.3. Сильно ациклические грамматики; 8.4.4. Вычислители для грамматик общего вида; 8.4.5. Восходящее вычислений для S-атрибутных грамматик.
8.5. L-АТРИБУТНЫЕ ГРАММАТИКИ
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. РАМ И ПОНЯТИЕ NP-ПОЛНОТЫ
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. СПИСОК NP-ПОЛНЫХ ЗАДАЧ
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. Рисование деревьев.
БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ
СПИСОК ЛИТЕРАТУРЫ
Предметный указатель