Теория вычислительных процессов
Конспект лекций
назад | вперед

Лекция 1
1. СХЕМЫ ПРОГРАММ
 1.1. Краткое математическое предисловие
   1.1.1. Функции и графы
   1.1.2. Вычислимость и разрешимость
   1.1.3. Программы и схемы программ

Лекция 2
 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. Логико-терминальная эквивалентность

Лекция 3
 1.4. Моделирование стандартных схем программ
   1.4.1. Одноленточные автоматы
   1.4.2. Многоленточные автоматы
   1.4.3. Двухголовочные автоматы
    1.4.3.1. Проблема пустоты и эквивалентности
    1.4.3.2. Двоичный двухголовочный автомат
    1.4.3.3. Построение схемы, моделирующей автомат

Лекция 4
 1.5. Рекурсивные схемы
   1.5.1. Рекурсивное программирование
   1.5.2. Определение рекурсивной схемы
 1.6. Трансляция схем программ
   1.6.1. О сравнении классов схем
   1.6.2. Схемы с процедурами

Лекция 5
 1.7 Обогащенные и структурированные схемы
   1.7.1 Классы обогащенных схем
   1.7.2. Трансляция обогащенных схем
   1.7.3. Структурированные схемы
 1.8. Вопросы для самоконтроля

Лекция 6
2. СЕМАНТИЧЕСКАЯ ТЕОРИЯ ПРОГРАММ
 2.1. Описание смысла программ
   2.1.1. Операционная семантика
   2.1.2. Аксиоматическая семантика
    2.1.2.1. Преобразователь предикатов
    2.1.2.2. Аксиоматическое определение операторов в терминах wp
   2.1.3. Денотационная семантика
   2.1.4. Декларативная семантика

Лекция 7
 2.2. Языки формальной спецификации

Лекция 8
 2.3. Верификация программ
   2.3.1. Методы доказательства правильности программ

   2.3.2. Использование утверждений в программах
   2.3.3. Правила верификации К. Хоара
 2.4. Вопросы и задания для самоконтроля

Лекция 9
3. ТЕОРЕТИЧЕСКИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

 3.1. Взаимодействующие последовательные процессы
   3.1.1. Определения
    3.1.1.1. Префиксы
    3.1.1.2. Рекурсия
    3.1.1.3. Выбор
    3.1.1.4. Взаимная рекурсия
   3.1.2. Законы
   3.1.3. Реализация процессов
   3.1.4. Протоколы
   3.1.5. Операции над протоколами
    3.1.5.1. Конкатенация
    3.1.5.2. Сужение
    3.1.5.3. Голова и хвост
    3.1.5.4. Звёздочка
    3.1.5.5. Порядок
    3.1.5.6. Длина
   3.1.6. Протоколы процесса
    3.1.6.1. 3аконы
    3.1.6.2. После
   3.1.7. Спецификации
    3.1.7.1. Соответствие спецификации
    3.1.7.2. Доказательства

Лекция 10
 3.2. Параллельные процессы
   3.2.1. Взаимодействие
    3.2.1.1. Законы
   3.2.2. Параллелизм
    3.2.2.1. Законы
    3.2.2.2. Реализация
    3.2.2.3. Протоколы
   3.2.3. Задача об обедающих философах
    3.2.3.1. Алфавиты
    3.2.3.2. Поведение
    3.2.3.3. Тупик!
    3.2.3.4. Доказательство беступиковости
    3.2.3.5. Бесконечный перехват
   3.2.4. Помеченные процессы
   3.2.5. Множественная пометка

Лекция 11
3.3. Взаимодействие - обмен сообщениями
3.3.1. Ввод и вывод
3.3.2. Взаимодействия
3.3.3. Подчинение


Лекция 12
 3.4. Разделяемые ресурсы
   3.4.1. Поочередное использование
   3.4.2. Общая память
   3.4.3. Кратные ресурсы
   3.4.4. Планирование ресурсов

Лекция 14
 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. Модель общей памяти
 3.7. Вопросы и задания для самоконтроля

Лекция 15
4. СЕТИ ПЕТРИ
 4.1. Введение в сети Петри
 4.2. Основные определения
   4.2.1. Теоретико-множественное определение сетей Петри

   4.2.2. Графы сетей Петри
   4.2.3. Маркировка сетей Петри
   4.2.4. Правила выполнения сетей Петри

Лекция 16
 4.3. Моделирование систем на основе сетей Петри
   4.3.1. События и условия
   4.3.2. Одновременность и конфликт
   4.3.3. Моделирование параллельных систем взаимодействующих процессов
    4.3.3.1. Моделирование последовательных процессов

    4.3.3.2. Моделирование взаимодействия процессов
    4.3.3.3. Задача о взаимном исключении
    4.3.3.4. Задача о производителе/потребителе
    4.3.3.5. Задача об обедающих философах


Лекция 17
 4.4. Анализ сетей Петри
   4.4.1. Свойства сетей Петри
   4.4.2. Методы анализа
    4.4.2.1. Дерево достижимости
    4.4.2.2. Анализ свойств сетей Петри на основе дерева достижимости
    4.4.2.3. Матричные уравнения
 4.5. Вопросы и упражнения для самоконтроля

Литература


назад | вперед