Теория вычислительных процессов

Введение

1 Схемы программ

1.1 Предварительные математические сведения

1.1.1 Функции и графы

1.1.2 Вычислимость и разрешимость

1.1.3 Программы и схемы программ

1.2 Стандартные схемы программ

1.2.1 Базис класса стандартных схем программ

1.2.2 Графовая форма стандартной схемы

1.2.3 Линейная форма стандартной схемы

1.2.4 Интерпретация стандартных схем программ

1.3 Свойства и виды стандартных схем программ

1.3.1 Эквивалентность, тотальность, пустота, свобода

1.3.2 Свободные интерпретации

1.3.3 Согласованные свободные интерпретации

1.3.4 Логико-термальная эквивалентность

1.4 Моделирование стандартных схем программ

1.4.1 Одноленточные автоматы

1.4.2 Многоленточные автоматы

1.4.3 Двухголовочные автоматы

1.4.4 Двоичный двухголовочный автомат

1.5 Рекурсивные схемы

1.5.1 Рекурсивное программирование

1.5.2 Определение рекурсивной схемы

1.6 Трансляция схем программ

1.6.1 О сравнении класс сов схем

1.6.2 Схемы с процедурами

1.7 Обогащенные и структурированные схемы

1.7.1 Классы обогащенных схем

1.7.2 Трансляция обогащенных схем

1.7.3 Структурированные схемы

Контрольные вопросы

2 Семантическая теория программ

2.1 Описание смысла программ

2.2 Операционная семантика

2.3 Аксиоматическая семантика

2.3.1 Преобразователь предикатов

2.3.2 Аксиоматическое определение операторов языка программирования

2.4 Денотационная семантика

2.5 Декларативная семантика

2.6 Языки формальной спецификации

2.7 Верификация программ

2.7.1 Методы доказательства правильности программ

2.7.2 Использование утверждений в программах

2.7.3 Правила верификации К. Хоара

Контрольные вопросы

3 Теоретические модели вычислительных процессов

3.1 Взаимодействующие последовательные процессы

3.1.1 Базовые определения

3.1.2 Законы взаимодействия последовательных процессов

3.1.3 Реализация процессов

3.1.4 Протоколы поведения процесса

3.1.5 Операции над протоколами

3.1.6 Протоколы процесса

3.1.7 Спецификации

3.2 Параллельные процессы

3.2.1 Взаимодействие процессов

3.2.2 Параллелизм

3.2.3 Задача об обедающих философах

3.2.4 Помеченные процессы

3.2.5 Множественная пометка

3.3 Взаимодействие – обмен сообщениями

3.3.1 Ввод и вывод

3.3.2 Взаимодействия

3.3.3 Подчинение

3.4 Разделяемые ресурсы

3.4.1 Поочередное использование

3.4.2 Общая память

3.4.3 Кратные ресурсы

3.4.4 Планирование ресурсов

3.5 Программирование параллельных вычислений

3.5.1 Основные понятия

3.5.2 Многопоточная обработка

3.5.3 Условные критические участки

3.5.4. Мониторы

3.6 Модели параллельных вычислений

3.6.1 Процесс/канал

3.6.2 Обмен сообщениями

3.6.3 Параллелизм данных

3.6.4 Общей памяти

Контрольные вопросы

4 Моделирование взаимодейстия процессов. Сети Петри

4.1 Введение в сети Петри

4.2 Основные определения

4.2.1 Теоретико-множественное определение сетей Петри

4.2.2 Графы сетей Петри

4.2.3 Маркировка сетей Петри

4.2.4 Правила выполнения сетей Петри

4.3 Моделирование систем на основе сетей Петри

4.3.1 События и условия

4.3.2 Одновременность и конфликт

4.4 Моделирование параллельных систем взаимодействующих процессов

4.4.1. Моделирование последовательных процессов

4.4.2 Моделирование взаимодействия процессов

4.4.3 Задача о взаимном исключении

4.4.4 Задача о производителе/потребителе

4.4.5 Задача об обедающих философах

4.5 Анализ сетей Петри

4.5.1 Свойства сетей Петри

4.5.2 Методы анализа

4.5.3 Анализ свойств сетей Петри на основе дерева достижимости

4.5.3 Матричные уравнения