Теория вычислительных процессов и структур (190,00 руб.)

Стр.2

Стр.89

Стр.90

УДК 519.6(075) ББК 22.19я7 Е30 Печатается по решению редакционно-издательского совета Казанского национального исследовательского технологического университета Рецензенты: д-р техн. наук, проф. К. Х. Гильфанов канд. техн. наук, доц. М. П. Шлеймович Е30 Егоров Д. Л. Теория вычислительных процессов и структур : учебное пособие / Д. Л. Егоров; Минобрнауки России, Казан. нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ, 2018. – 92 с. ISBN 978-5-7882-2378-0 Представлены основы теории вычислительных процессов и структур, в том числе вопросы, связанные с представлением, анализом и моделированием вычислительных процессов, а также программ, которые их порождают, и устройств, на которых они выполняются. Рассмотрены основы теорий формальных языков, автоматов, схем программ и др. Предназначено для студентов, обучающихся по направлениям 01.03.02 «Прикладная математика и информатика», 02.03.03 «Математическое обеспечение и администрирование информационных систем», 09.03.01 «Информатика и вычислительная техника». Подготовлено на кафедре интеллектуальных систем и управления информационными ресурсами. УДК 519.6(075) ББК 22.19я7 ISBN 978-5-7882-2378-0 © Егоров Д. Л., 2018 © Казанский национальный исследовательский технологический университет, 2018 2

Стр.2

СОДЕРЖАНИЕ ВВЕДЕНИЕ ................................................................................................ 3 1. ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ ............................................... 5 1.1. Вычислительная система и вычислительный процесс ..................... 5 1.2. Виды вычислительных процессов...................................................... 6 1.3. Проблема организации совместной работы процессов ................... 7 2. ОСНОВЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ ........................... 9 2.1. Цепочки символов и их свойства ....................................................... 9 2.2. Формальные грамматики и формальные языки .............................. 13 2.3. Классификация языков Н. Хомского ............................................... 15 2.4. Пример построения формальной грамматики и порождения цепочки ...................................................................................................... 16 3. АВТОМАТНЫЕ МОДЕЛИ............................................................... 19 3.1. Конечные автоматы ........................................................................... 19 3.2. Автоматы с магазинной памятью ..................................................... 23 3.3. Машина Тьюринга ............................................................................. 25 3.4. Линейно-ограниченные автоматы .................................................... 29 4. МОДЕЛЬ ЦИФРОВОГО АВТОМАТА .......................................... 30 4.1. Основные понятия теории автоматов .............................................. 30 4.2. Способы задания автоматов ............................................................. 33 4.2.1. Аналитический способ ................................................................... 33 4.2.2. Табличный способ .......................................................................... 33 4.2.3. Графический способ ....................................................................... 36 4.2.4. Примеры графического и табличного задания автоматов Мили и Мура ............................................................................................. 37 5. СЕТИ ПЕТРИ ...................................................................................... 40 5.1. Концепция сети Петри ...................................................................... 40 5.2. Элементы сети Петри ........................................................................ 41 5.3. Теоретико-множественное определение сети Петри ..................... 42 5.4. Граф сети Петри ................................................................................. 44 5.5. Работа сети Петри .............................................................................. 44 5.6. Классификация сетей Петри ............................................................. 48 5.7. Анализ сетей Петри ........................................................................... 49 5.8. Задача достижимости ........................................................................ 51 5.9. Основы моделирования систем с помощью сетей Петри .............. 56 89

Стр.89

6. СХЕМЫ ПРОГРАММ ....................................................................... 64 6.1. Базис класса стандартных схем программ ...................................... 64 6.2. Способы представления стандартной схемы программы .............. 68 6.3. Интерпретированная стандартная схема программы ..................... 70 6.4. Протокол выполнения программы ................................................... 72 6.5. Свойства стандартных схем программ ............................................ 75 6.6. Цепочка стандартной схемы ............................................................. 76 6.7. Свободные интерпретации ............................................................... 77 7. ОПИСАНИЕ СИНТАКСИСА И СЕМАНТИКИ ЯЗЫКА ПРОГРАММИРОВАНИЯ ..................................................................... 79 7.1. Проблема точного описания языка программирования ................. 79 7.2. Определение синтаксиса языка программирования ....................... 80 7.2.1. Форма Бэкуса–Наура ...................................................................... 80 7.2.2. Синтаксические диаграммы Вирта ............................................... 81 7.2.3. Контекстные условия ..................................................................... 82 7.3. Определение семантики языка программирования ........................ 82 7.3.1. Грамматические модели ................................................................. 83 7.3.2. Операционная, аксиоматическая и денотационная семантики .. 84 ЛИТЕРАТУРА......................................................................................... 86 90

Стр.90