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

Оглавление 

1 

Министерство образования и науки Российской Федерации 
Сибирский федеральный университет 
 
 
 
 
 
А. С. Кузнецов, Р. Ю. Царев, А. Н. Князьков 
 
 
ТЕОРИЯ  
ВЫЧИСЛИТЕЛЬНЫХ  
ПРОЦЕССОВ 
 
 
Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебника для студентов высших учебных заведений, обучающихся по специальностям: 230105.65 «Программное 
обеспечение вычислительной техники и автоматизированных систем», 080801.65 «Прикладная информатика 
(в экономике)», 230700.62 «Прикладная информатика» 
(рег. № 493 от 12.01.2015 г.) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Красноярск 
СФУ 
2015 

Оглавление 
 

2 

УДК 004.384(07) 
ББК 32.971.3я73 
        К891 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Кузнецов, А. С.  
К891           Теория вычислительных процессов : учеб. / А. С. Кузнецов,  
Р. Ю. Царев, А. Н. Князьков. – Красноярск : Сиб. федер. ун-т, 2015. – 
184 c. 
ISBN 978-5-7638-3193-1 
 
Приведены сведения о семантике языков программирования и теории 
схем программ, даны основные понятия и определения теории параллельных 
процессов, их протоколов и интерфейсов, изложены принципы построения сетей 
Петри. 
Особое внимание уделено вопросам разработки параллельных программ с 
использование различных библиотек функций, реализующих системные вызовы 
в рамках операционной системы Linux. 
Предназначен для студентов, обучающихся по специальностям 230105.65 
«Программное обеспечение вычислительной техники и автоматизированных систем», 080801.65 «Прикладная информатика (в экономике)», 230700.62 «Прикладная информатика»  всех форм обучения. 
 
 
   Электронный вариант издания см.: 
           http://catalog.sfu-kras.ru 
УДК 004.384(07) 
ББК 32.971.3я73
 
ISBN 978-5-7638-3193-1                                                          © Сибирский федеральный  
                                                                                                         университет, 2015 

Оглавление 

3 

 
ОГЛАВЛЕНИЕ 
 
ВВЕДЕНИЕ .......................................................................................................... 6 
 
1. СЕМАНТИЧЕСКАЯ  ТЕОРИЯ  ПРОГРАММ ............................................. 8 
1.1. Описание смысла программ ................................................................... 8 
1.1.1. Операционная семантика ............................................................. 9 
1.1.2. Аксиоматическая семантика ...................................................... 13 
1.1.3. Денотационная семантика ......................................................... 17 
1.2. Языки формальной спецификации ...................................................... 21 
1.3. Верификация программ ........................................................................ 23 
 
2. СХЕМЫ  ПРОГРАММ ................................................................................. 31 
2.1. Множества и графы .............................................................................. 31 
2.2. Вычислимость и разрешимость ........................................................... 33 
2.3. Программы и схемы программ ............................................................ 36 
2.3.1. Стандартные схемы программ .................................................. 37 
2.3.2. Графовая форма стандартной схемы ........................................ 38 
2.3.3. Линейная форма стандартной схемы ....................................... 39 
2.3.4. Интерпритация стандартных схем программ .......................... 40 
2.4. Свойства и виды стандартных схем программ .................................. 42 
2.4.1. Эквивалентность, тотальность, пустота, свобода ................... 42  
2.4.2. Свободные интерпретации ........................................................ 43 
2.4.3. Согласованные свободные интерпретации ............................. 45 
2.4.4. Логико-термальная эквивалентность ....................................... 46 
2.5. Рекурсивные схемы ............................................................................... 47 
2.6. Трансляция схем программ .................................................................. 50 
2.7. Обогащенные и структурированные схемы ....................................... 53 
2.7.1. Трансляция обогащенных схем ................................................ 55 
2.7.2. Структурированые схемы ......................................................... 55 
 
3. ТЕОРЕТИЧЕСКИЕ  ОСНОВЫ   
    ВЫЧИСЛИТЕЛЬНЫХ  ПРОЦЕССОВ ....................................................... 58 
3.1. Взаимодействующие вычислительные процессы ............................... 58 
3.1.1. Префиксы ..................................................................................... 59 
3.1.2. Протоколы ................................................................................... 63  
3.1.3. Спецификации ............................................................................. 66 
3.2. Параллельные процессы ........................................................................ 69 

Оглавление 
 

4 

3.3. Взаимодействие между процессами  
       посредством обмена сообщениями ...................................................... 74 
3.4. Разделяемые ресурсы ............................................................................. 77 
3.5. Программная реализация параллельных вычислений ....................... 84 
3.6. Модели параллельных вычислений ..................................................... 89 
3.6.1. Процесс/канал .............................................................................. 89 
3.6.2. Обмен сообщениями ................................................................... 90 
3.6.3. Параллелизм данных .................................................................. 98 
3.6.4. Общая память .............................................................................. 98 
 
4. СЕТИ  ПЕТРИ .............................................................................................. 100 
4.1. Основные сведения ............................................................................. 100 
4.1.1. Формальное определение сети Петри ..................................... 100 
4.1.2. Графическое представление сетей Петри ............................... 101 
4.1.3. Маркировка сетей Петри .......................................................... 102 
4.1.4. Правила выполнения сетей Петри ........................................... 102 
4.2. Моделирование систем на основе сетей Петри ................................ 104 
4.2.1. События и условия .................................................................... 105 
4.2.2. Одновременность и конфликт ................................................. 106 
4.3. Моделирование взаимодействующих процессов  
       параллельных систем .......................................................................... 109 
4.3.1. Задача о взаимном исключении ............................................... 109 
4.3.2. Задача о производителе и потребителе ................................... 111 
4.3.3. Задача об обедающих философах ........................................... 113 
4.3.4. Задача о чтении и записи .......................................................... 115 
4.3.5. Р- и V-системы ........................................................................... 116 
4.3.6. Моделирование последовательных процессов ...................... 117 
4.3.7. ЭВМ с конвейерной обработкой ............................................. 121 
4.4. Анализ сетей Петри ............................................................................. 124 
4.4.1. Свойства сетей Петри ............................................................... 124 
4.4.2. Покрывающее дерево ............................................................... 127 
4.4.3. Анализ свойств сетей Петри  
          на основе покрывающего дерева ............................................. 130 
 
5. КОНЕЧНЫЕ  АВТОМАТЫ ....................................................................... 132 
5.1. Конечные распознаватели .................................................................. 133 
5.2. Таблица переходов .............................................................................. 135 
5.3. Концевые маркеры, выходы из распознавания  
       и пустая цепочка .................................................................................. 136 
5.4. Эквивалентность состояний ............................................................... 141 
5.5. Проверка эквивалентности двух состояний ..................................... 144 

Оглавление 

5 

5.6. Недостижимые состояния ................................................................... 148 
5.7. Приведенные автоматы ....................................................................... 149 
5.8. Получение минимального автомата .................................................. 151 
5.9. Недетерминированные автоматы ....................................................... 154 
5.10. Эквивалентность недетерминированных  
         и детерминированных конечных распознавателей ........................ 158 
 
6. АВТОМАТЫ  С  МАГАЗИННОЙ  ПАМЯТЬЮ ...................................... 163 
6.1. Некоторые обозначения для множеств цепочек .............................. 170 
6.2. Пример распознавания множества МП-автоматом.......................... 173 
6.3. Расширенные операции над магазином ............................................ 175 
6.4. Перевод с помощью МП-автоматов .................................................. 178 
 
ЗАКЛЮЧЕНИЕ ............................................................................................... 182 
 
БИБЛИОГРАФИЧЕСКИЙ  СПИСОК .......................................................... 183 

Введение 
 

6 

 
ВВЕДЕНИЕ 
 
 
Теоретическое программирование – математическая дисциплина, 
изучающая семантические и синтаксические аспекты языков программирования и программ, их структуру, возможности преобразования, процесс 
разработки и работы в рамках какой-либо среды исполнения. Программа        
в этом случае рассматривается и как некий абстрактный объект. 
В настоящее время в теоретическом программировании сложилось 
несколько направлений. Большинство из них, в общем, соответствуют         
названиям разделов данного учебника. 
В первой главе рассматривается семантика программы или конкретных языковых конструкций как для программиста, так и для вычислительной машины, на которой может выполняться программа. Приводятся формальные методы описания семантики, методы преобразования программ,  
а также доказательства утверждений о программах. 
Во второй главе основное внимание уделяется теории схем программ, т. е. изучению их структурных свойств и преобразований, которые 
отличают их от прочих способов реализации алгоритмов. Во главу угла 
ставится схема – математическая модель программы, в которой отражается 
ее устройство и взаимодействие составляющих ее компонентов. 
Третья глава дает представление о теории параллельных вычислений 
(моделях, структурах и операционных системах, а также способах описания протоколов процессов и операций над ними). Разделяются взаимодействующие последовательные процессы, параллельные и чередующиеся. На 
примерах показывается их использование. В частности, особое внимание 
уделяется известной задаче об обедающих философах. Известно несколько 
способов организации взаимодействия процессов, которые также описаны 
в третьей главе настоящего учебника. Один из важнейших вопросов при 
взаимодействии процессов – планирование ресурсов. Ему тоже уделено 
немало внимания. Приводятся сведения по программной реализации параллельных вычислений в рамках ОС Linux на языке программирования Си.  
Отметим, что используется компилятор этого языка из коллекции GCC. Описаны самые популярные модели параллельных вычислений и приведены аспекты программной реализации одной из этих моделей, поддержка которой 
существует в ОС Linux, а именно библиотека сокетов, которая позволяет 
взаимодействовать не только параллельным процессам и потокам, работающим на одной ЭВМ, но и сложным по топологии глобальным сетям. 

Введение 

7 

В четвертой главе приводятся основы специальной теории сетей,  
а именно сетей Петри (определение сети Петри, ее структуры, свойств  
и способов задания). В основном рассматриваются маркированные сети 
Петри как инструмент анализа и моделирования систем. Изложение теоретического материала сопровождается иллюстрациями. Особое внимание 
уделяется практическим примерам реализации на основе сетей Петри общеизвестных задач и вычислительных структур. Дается алгоритм построения покрывающего дерева, на основе которого можно выполнить анализ 
ряда свойств сети Петри. 
В пятой и шестой главах рассматриваются некоторые аспекты теории конечных автоматов. Конечный автомат как простейшая из моделей 
теории автоматов служит основой для изучения всех остальных автоматов. 
Показано, как задается конечный автомат. Определено понятие эквивалентности конечных автоматов и состояний, а также обозначены условия, 
при которых выполняется эквивалентность. Описан процесс получения 
минимального автомата. 
Шестая глава развивает идеи конечных автоматов. В ней представлены автоматы с магазинной памятью (или памятью, организованной в виде стека). Благодаря дополнительному механизму хранения информации 
данный класс автоматов обладает более широкими возможностями. Описано, какие элементы определяют автомат с магазинной памятью. Приведены примеры распознавания цепочек и перевода с помощью автоматов         
с магазинной памятью. Показано, что операции над магазином могут быть 
расширены по усмотрению программиста. 

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

8 

 
1. СЕМАНТИЧЕСКАЯ  ТЕОРИЯ  ПРОГРАММ 
 
 
1.1. Описание смысла программ 
 
Термин «процесс» в применении к вычислительным машинам трактуется по-разному. Наиболее распространенное определение следующее: 
процесс – это программа, находящаяся на стадии выполнения. Программы 
могут создаваться вручную, хотя, надо отметить, что для разработки некоторых фрагментов могут использоваться автоматизированные средства. 
Так создаются, например, элементы пользовательского интерфейса или 
часть компонентов трансляторов программ. 
В любом случае для написания программ используются определенные полностью или частично формальные методы. Чаще всего – языки 
программирования. Под описанием языка обычно подразумевается однозначное определение его синтаксиса, то есть описание каждой отдельной 
языковой конструкции и их совокупности, а также, по возможности, однозначное описание его семантики, т. е. смысла, придаваемого каждой такой 
конструкции. 
Сведения о синтаксисе и семантике языка программирования необходимы как его пользователю, в качестве которого выступает программист, так и разработчику транслятора для этого языка. Программист использует такого рода информацию для разработки правильных программ, 
зная заранее, к какому результату могут привести те или иные конструкции, используемые в программе. В то же время разработчику транслятора 
корректные определения необходимы для того, чтобы осуществить правильную реализацию языка программирования. 
Механизм формальных грамматик достаточно давно зарекомендовал 
себя простым и удобным способом описания синтаксиса языка в целом       
и отдельных конструкций. Это может быть сделано перечислением множества правил вывода предложений языка, часто для этого используются так 
называемые Бэкуса – Наура формы (БНФ). 
Описание семантики языка в большинстве случаев осуществляется 
приведением нескольких простых примеров и кратким поясняющим текстом. Смысл этого текста чаще всего неоднозначен, так что различные читатели могут понимать его по-разному. Программист может получить 
ошибочное представление о том, что именно будет делать написанная им 
программа при выполнении, а разработчик может реализовать какую-либо 

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

9 

языковую конструкцию иначе, чем разработчики других реализаций того 
же языка. Как и для синтаксиса, нужен какой-то метод, позволяющий дать 
удобочитаемое, точное и лаконичное определение семантики языка. 
Задача определения семантики языка программирования рассматривается теоретиками давно, но до сих пор не найдено удовлетворительного 
универсального решения. Было разработано множество различных методов формального определения семантики. 
 
1.1.1. Операционная семантика 

Операционная семантика сводится к описанию смысла программы 
посредством выполнения ее конструкций на реальной или виртуальной 
вычислительной машине. Смысл конструкции определяется изменениями, 
произошедшими в состоянии машины после выполнения данной конструкции (оператора). 
Допустим, что состояние компьютера – это значения всех его регистров и ячеек памяти, в том числе коды условий и регистры состояний. Если 
просто записать состояние компьютера, выполнить машинную команду, 
смысл которой нужно определить, затем записать новое состояние машины, 
а затем сравнить два полученных состояния, то семантика выполняемой 
команды станет понятной: она представляется изменением в состоянии 
машины, вызванным выполнением команды. 
Описание смысла операторов языков программирования высокого 
уровня с помощью операционной семантики требует создания реального 
или виртуального компьютера. Аппаратное обеспечение компьютера является чистым интерпретатором его машинного языка. Интерпретатор любого языка программирования можно разработать с помощью программных 
инструментов, которые для данного языка становятся виртуальной машиной. Будем считать такой интерпретатор «чистым». Семантику языка  программирования высокого уровня можно описать, используя «чистый» интерпретатор данного языка. Однако налицо две проблемы. Во-первых, 
сложность и индивидуальные особенности аппаратного обеспечения           
и операционного окружения, используемых для запуска чистого интерпретатора, затрудняют понимание выполняемых действий. Во-вторых, выполненное таким образом семантическое описание будет доступно только для 
пользователей с абсолютно идентичной конфигурацией вычислительной 
машины и одинаковой операционной системой. 
Для борьбы с этими проблемами можно заменить реальную машину 
неким виртуальным компьютером низкого уровня. Регистры, оперативную 
память, информацию о состоянии и последовательность выполнения операторов – все это можно смоделировать, написав соответствующие программы. Набор команд такой идеализированной виртуальной машины