Характеристики

ISBN/ISSN 978-5-7782-0901-5
Год издания 2007
Автор Рабинович Е.В.
Вид издания уч
Кафедра ВТ
Типография НГТУ
Факультет АВТФ

Учебник подготовлен на основе Государственного образовательного стандарта дисциплины «Теория вычислительных процессов» по направлению 230100 – «Информатика и вычислительная техника», специальность 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем».
Учебник состоит из введения, четырех глав и списка литературы. Каждая глава содержит обширный методический аппарат, включающий перечень основных выводов и результатов, контрольные вопросы, задачи и задания.
В учебнике изложен теоретический материал по всем четырем основным темам курса: введение, схемы программ, семантическая теория программ, теоретические модели вычислительных процессов и сети Петри.
Материалы учебника включают анализ проблем теоретического программирования; рекомендации по практическому применению моделей программ и методов программирования; поясняющие примеры и иллюстрации.

Учебник подготовлен на основе Государственного образовательного стандарта дисциплины «Теория вычислительных процессов» по направлению 230100 – «Информатика и вычислительная техника», специальность 230105 – «Программное обеспечение вычислительной техники и автоматизированных систем».
Учебник состоит из введения, четырех глав и списка литературы. Каждая глава содержит обширный методический аппарат, включающий перечень основных выводов и результатов, контрольные вопросы, задачи и задания.
В учебнике изложен теоретический материал по всем четырем основным темам курса: введение, схемы программ, семантическая теория программ, теоретические модели вычислительных процессов и сети Петри.
Материалы учебника включают анализ проблем теоретического программирования; рекомендации по практическому применению моделей программ и методов программирования; поясняющие примеры и иллюстрации.



ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ    3
Программа как формализованное описание процесса обработки данных    5
Правильная программа и надежная программа    5
Глава 1. СХЕМЫ ПРОГРАММ    7
1.1. Краткое математическое предисловие    7
1.1.1. Функции и графы    7
1.1.2. Вычислимость и разрешимость    11
1.1.3. Программы и схемы программ    16
1.2. Стандартные схемы программ    17
1.2.1. Базис класса стандартных схем программ    17
1.2.2. Графовая форма стандартной схемы    18
1.2.3. Линейная форма стандартной схемы    19
1.2.4. Интерпретация стандартных схем программ    21
1.3. Свойства и виды стандартных схем программ    23
1.3.1. Эквивалентность, тотальность, пустота, свобода    23
1.3.2. Свободные интерпретации    25
1.3.3. Согласованные свободные интерпретации    27
1.3.4. Логико-термальная эквивалентность    29
1.4. Моделирование стандартных схем программ    31
1.4.1. Одноленточные автоматы    31
1.4.2. Многоленточные автоматы    33
1.4.3. Двухголовочные автоматы    34
1.5. Рекурсивные схемы    40
1.5.1. Рекурсивное программирование    40
1.5.2. Определение рекурсивной схемы    41
1.6. Трансляция схем программ    43
1.6.1. О сравнении классов схем    43
1.6.2. Схемы с процедурами    45
1.7. Обогащенные и структурированные схемы    46
1.7.1. Классы обогащенных схем    46
1.7.2. Трансляция обогащенных схем    48
1.7.3. Структурированные схемы    49
Основные выводы и результаты     50
Контрольные вопросы и задания    52
Глава 2. СЕМАНТИЧЕСКАЯ ТЕОРИЯ ПРОГРАММ    54
2.1. Описание смысла программ    54
2.1.1. Операционная семантика    55
2.1.2. Аксиоматическая семантика    59
2.1.3. Денотационная семантика    71
2.1.4. Декларативная семантика    75
2.2. Языки формальной спецификации.    75
2.3. Верификация программ    78
2.3.1. Методы доказательства правильности программ    78
2.3.2. Использование высказываний в программах    82
2.3.3. Правила верификации К. Хоара    84
Основные выводы и результаты    86
Контрольные вопросы и задания    88
Глава 3. ТЕОРЕТИЧЕСКИЕ МОДЕЛИ
ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ    90
3.1. Взаимодействующие последовательные процессы    90
3.1.1. Определения    90
3.1.2. Законы    95
3.1.3. Реализация процессов    96
3.1.4. Протоколы    97
3.1.5. Операции над протоколами    98
3.1.6. Протоколы процесса    101
3.1.7. Спецификации    102
3.2. Параллельные процессы    105
3.2.1. Взаимодействие    106
3.2.2. Параллелизм    107
3.2.3. Задача об обедающих философах    108
3.2.4. Помеченные процессы    112
3.2.5. Множественная пометка    113
3.3. Взаимодействие – обмен сообщениями    114
3.3.1. Ввод и вывод    115
3.3.2. Взаимодействия    116
3.3.3. Подчинение    116
3.4. Разделяемые ресурсы    118
3.4.1. Поочередное использование    118
3.4.2. Общая память    119
3.4.3. Кратные ресурсы    122
3.4.4. Планирование ресурсов    124
3.5. Программирование параллельных вычислений    127
3.5.1. Основные понятия    127
3.5.2. Многопоточная обработка    129
3.5.3. Условные критические участки    130
3.5.4. Мониторы    131
3.6. Модели параллельных вычислений    133
3.6.1. Процесс/канал    133
3.6.2. Обмен сообщениями    134
3.6.3. Параллелизм данных    135
3.6.4. Модель общей памяти    136
Основные выводы и результаты     136
Контрольные вопросы и задания    137
Глава 4. СЕТИ ПЕТРИ    139
4.1. Введение в сети Петри    139
4.2. Основные определения    140
4.2.1. Теоретико-множественное определение сетей Петри    140
4.2.2. Графы сетей Петри    141
4.2.3. Маркировка сетей Петри.    141
4.2.4. Правила выполнения сетей Петри    142
4.3. Моделирование систем на основе сетей Петри    143
4.3.1. События и условия    143
4.3.2. Одновременность и конфликт    145
4.3.3. Моделирование параллельных систем взаимодействующих процессов    145
4.4. Анализ сетей Петри    151
4.4.1. Свойства сетей Петри    152
4.4.2. Методы анализа.    153
Основные выводы и результаты     159
Контрольные вопросы и задания    160
Библиографический список    162

Данные подготавливаются.

Вернуться к списку