- Артикул:00-01119671
- Автор: В. Е. Котов, В. К. Сабельфельд
- ISBN: 5-02-013974-2
- Тираж: 7250 экз.
- Обложка: Мягкая обложка
- Издательство: Наука (все книги издательства)
- Город: Москва
- Страниц: 248
- Формат: 60х90 1/16
- Год: 1991
- Вес: 310 г
Развернуть ▼
В книге проведено систематизированное изложение раздела теоретического программирования, изучающего неинтерпретированные модели программ - их схемы, отражающие структурные особенности программ и в определенной мере абстрагирующиеся от их функциональной сущности. Излагается теория схем программ, являющаяся математической базой для развития методов трансляции программ и создания новых конструкций в языках программирования.
Для специалистов в области информатики и прикладной математики.
Содержание
Предисловие
Глава 1. Вычислимость и разрешимость
§ 1. Вычислимые функции, алгоритмы
1.1. Функции
1.2. Словарные функции
1.3. Вычислимые функции и машины Тьюринга
1.4. Пример машины Тьюринга
1.5. Словарное представление машины Тьюринга
§ 2. Разрешимые н неразрешимые проблемы
2.1. Массовые алгоритмические проблемы
2.2. Проблема остановки
2.3. Проблема пустой ленты и метод сведения
2.4. Проблема зацикливания
Краткий обзор и комментарии
Глава 2. Графы и метод разметка
§ 1. Понятие графа
1.1. Определение графа
1.2. Связность и изоморфизм графов, деревья
§ 2. Метод разметки и задача глобального анализа
2.1. Неформальное введение
2.2. Формальная постановка задачи глобального анализа
§ 3. Решение задачи глобального анализа
3.1. Процесс разметки
3.2. Безопасность и единственность стационарной разметки
3.3. Точное решение задачи глобального анализа
Краткий обзор и комментарии
Глава 3. Конечные автоматы
§ 1. Одноленточные автоматы
1.1. Определенно автомата
1.2. Проблемы пустоты и эквивалентности
§ 2. Многоленточные автоматы
2.1. Определения
2.2. Свойства замкнутых диаграмм
2.3. Процедура распознавания
2.4. Предельная диаграмма
2.5. Решение двухленточной проблемы
§ 3. Двухголовочные автоматы
3.1. Определение и пример
3.2. Проблемы пустоты и эквивалентности
Краткий обзор и комментарии
Глава 4. Стандартные схемы программ
§ 1. Схемы программ
1.1. Программы
1.2. От программ к схемам программ
§ 2. Класс стандартных схем
2.1. Базис
2.2. Стандартная схема (графовая форма)
2.3. Стандартная схема (линейная форма)
2.4. Интерпретация, программа
2.5. Примеры программ
§ 3. Эквивалентность и главные свойства стандартных схем
3.1. Эквивалентность, тотальность, пустота, свобода
3.2. Свободные интерпретации
3.3. Согласованные свободные интерпретации
3.4. Основные теоремы о свободных интерпретациях
3.5. Определение логико-термальной эквивалентности и ее корректность
Краткий обзор и комментарии
Глава 5. Неразрешимые свойства стандартных схем
§ 1. Двоичный двухголовочный автомат
§ 2. Моделирование двоичного автомата стандартной схемой
Класс Р1, стандартных схем
Построение схемы, моделирующей автомат
§ 3. Теоремы о неразрешимых свойствах стандартных схем
3.1. Проблемы пустоты и эквивалентности
3.2. Проблема тотальности
3.3. Проблема свободы
Краткий обзор и комментарии
Глава 6. Логико-термальная эквивалентность стандартных схем
§ 1. Фрагменты и их преобразование
1.1. Фрагменты
1.2. Информационные маршруты, зацепленность и влияние
1.3. Формальные преобразования
§ 2. Инварианты н их представление в виде сетей
2.1. Функциональные сети
2.2. Полурешетка приведенных сетей
2.3. Нахождение инвариантов
§ 3. Алгоритм распознавания логико-термальной эквивалентности
3.1. Система эквивалентных преобразований
3.2. Приведение и согласование фрагментов
3.3. Полнота системы
Краткий обзор и комментарии
Глава 7. Разрешимые подклассы стандартных схем
§ 1. Свободные стандартные схемы
1.1. Проблемы пустоты и тотальности
1.2. Проблема изоморфизма
§ 2. Сквозные схемы
2.1. Определение сквозных схем
2.2. Обобщение инвариантов
2.3. Освобождение сквозных схем
2.4. Алгоритм распознавания эквивалентности сквозных схем
2.5. Корректность алгоритма
Краткий обзор и комментарии
Глава 8. Рекурсивные схемы
§ 1. Класс рекурсивных схем
1.1. Рекурсивное программирование
1.2. Определение рекурсивной схемы
1.3. Рекурсивная программа
§ 2. Проблемы трансляции
2.1. О сравнении классов схем
2.2. Трансляция стандартных схем в рекурсивные
2.3. Трансляция рекурсивных схем в стандартные
§ 3. Линейные унарные рекурсивные схемы
3.1. Проблема трансляции
3.2. Праволинейные унарные схемы
§ 4. Схемы с процедурами
4.1. Сравнение с классом рекурсивных схем
4.2. Частичная трансляция схем с процедурами
Краткий обзор и комментарии
Глава 9. Обогащенные схемы
§ 1. Классы обогащенных схем
1.1. Счетчики, магазины, массивы
1.2. Примеры обогащенных схем
§ 2. Проблемы трансляции
2.1. Счетчиковые и рекурсивные схемы
2.2. Счетчиковые и стандартные схемы
2.3. Счетчиковые и магазинные схемы
2.4. Магазинные схемы и схемы с массивами
2.5. Магазинные и рекурсивные схемы
2.6. Сравнительная схематология
Краткий обзор и комментарии
Глава 10. Схемы структурированных программ
§ 1. Структурированные схемы
1.1. Класс структурированных схем
1.2. Трансляция структурированных схем в стандартные
1.3. Трансляция стандартных схем в структурированные
§ 2. Структурированные схемы с логическими операциями
Список литературы