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

Оглавление 

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. Операционная семантика 

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

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

10 

можно создать так, чтобы семантику каждой отдельной команды было легко понять и описать. Кроме того, семантика значительно упрощается, поскольку понятным становится изменение ее состояния. 
Использование операционного метода для полного описания семантики языка программирования L требует создания двух компонентов. 
Во-первых, для преобразования языка L в операторы выбранного 
языка низкого уровня понадобится транслятор. 
Во-вторых, для языка низкого уровня понадобится разработать виртуальную машину, состояние которой изменяется с помощью команд, полученных после трансляции операторов языка высокого уровня. Как отмечалось выше, изменения состояния этой виртуальной машины определяют 
смысл данного оператора. 
Операционную семантику конструкции while языка Си можно описать в терминах следующих простых команд. 

Оператор языка Си 
Операционная семантика 
while (expr){ 
 
 
loop:  
if expr1 = 0 goto out_loop 
... 
 
 
 
 
 
… 
} 
 
 
 
 
 
 
goto loop 
out_loop: 

Считается, что человек, читающий подобное описание, сам становится «виртуальной машиной» и предполагается способным правильно 
«выполнить» команды описания семантики и распознать эффект такого 
«выполнения» команды. 
Примерами низкоуровневого языка, который можно применять для 
операционной семантики, являются элементы следующего списка операторов, соответствующих простым управляющим операторам типичного 
языка программирования: 

identifier := variable 
identifier:= identifier + 1 
goto metka 
if variable relop variable goto metka 

Здесь relop – один из операторов сравнения из набора {= , !=, >, <, 
>=, <=}, identifier – идентификатор, a variable – переменная или константа. 
Перечисленные операторы просты и легки для понимания и реализации. 
Отчасти обобщим приведенные выше три оператора присваивания, 
что позволит описать более общие арифметические выражения и операторы присваивания. Например: 

identfier := variable bin_op variable  
identifier := un_op variable 

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

11 

Здесь bin_op – бинарный оператор, a un_op – унарный оператор. Немного усложнят сделанное обобщение типы данных и необходимость их 
автоматического преобразования. Чтобы описать семантику, например, 
указателей, массивов, структур, процедур и функций, понадобится ввести 
некоторое количество новых достаточно простых команд. 
Чтобы описать операционную семантику функций, рассмотрим следующую систему равенств: 

f1(p1, p2, ..., pk) = E1, 
f2(p1, p2, ..., pk) = E2, 
. . . . . . . . . . . . .  
fm(p1, p2, ..., pk) = Em. 

Здесь в левых частях равенств указаны определяемые функции            
с формальными параметрами p1, p2, ..., pk. В правых частях указаны выражения, содержащие тела этих функций с аргументами, задаваемых некоторыми выражениями, зависящими от входных параметров p1, p2, ..., pk. 
Операционная семантика интерпретирует эти равенства как систему 
подстановок. Под подстановкой <S, E, T> терма T в выражение E вместо 
символа S (например, идентификатора) понимается переписывание выражения E с заменой каждого вхождения в него символа S на выражение T. 
Каждое равенство fi(p1, p2, ..., pk) = Ei задает в параметрической форме множество правил подстановок: 

<p1, p2, ..., pk; fi(T1, T2, ..., Tk) → Ei; T1, T2, ..., Tk>. 

Здесь T1, T2, ... , Tk – это фактические аргументы конкретной функции. Это 
правило позволяет допустить замену вхождения левой его части в какоелибо выражение на его правую часть. 
Интерпретация системы равенств для получения значений определяемых функций в рамках операционной семантики производится следующим образом. 
Предположим, задан набор входных данных d1, d2, ..., dk. Сначала 
осуществляется подстановка этих данных в левые и правые части равенств. 
При этом по возможности выполняются предопределенные операции,             
а также выписываются получаемые в результате этого равенства. 
На последующих шагах просматриваются правые части получаемых 
равенств. Если правая часть является каким-либо значением, то оно – значение функции из левой части данного равенства. В противном случае 
правая часть является выражением, содержащим вхождения каких-либо 
определяемых функций с наборами аргументов. 
Если для такого вхождения соответствующая функция с данным набором аргументов имеется в левой части какого-либо из полученных ра

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

12 

венств, то либо вместо этого вхождения подставляется вычисленное значение правой части этого равенства, либо изменения вообще не производятся. 
Если эта функция с заданным набором аргументов не является левой 
частью никакого из полученных равенств, то формируется новое равенство, которое дописывается к уже имеющемуся набору. Формирование равенства получается из исходного равенства для данной функции, только 
вместо его параметров подставляются аргументы функции. 
Описанные шаги выполняются до тех пор, пока все определяемые 
функции не будут иметь вычисленные значения. 
Рассмотрим систему равенств, определяющую функцию FIBON(n), 
которая вычисляет значение числа Фибоначчи по его номеру. 

FIBON (1) = 1, 
FIBON (2) = 1 
FIBON (n)=FIBON (n–1) + FIBON (n–2). 

Для вычисления значения FIBON (4) выполняются следующие 4 шага. 

1-й шаг:  
 
 
 
          2-й шаг: 
FIBON(1)=1, 
 
 
 
FIBON(1)=1, 
FIBON(2)=1, 
. 
 
 
FIBON(2)=1, 
FIBON(4)=FIBON(3)+FIBON(2). 
FIBON(4)=FIBON(3)+FIBON(2), 
 
 
 
 
 
 
FIBON(3)=FIBON(2)+FIBON(1). 
 
3-й шаг: 
 
 
 
         4-й шаг: 
FIBON(1)=1, 
 
 
 
FIBON(1)=1, 
FIBON(2)=1, 
 
 
 
FIBON(2)=1, 
FIBON(4)=FIBON(3)+FIBON(2),    FIBON(4)=3, 
FIBON(3)=2. 
 
 
 
FIBON(3)=2. 

Фактически первым и до сих пор самым значительным использованием операционной семантики было описание семантики языка программирования PL/I. Разработанная виртуальная машина и правила трансляции 
языка PL/I были названы общим именем Vienna Definition Language (VDL) 
в честь города, в котором они были созданы в лабораториях корпорации IBM. 
Операционная семантика эффективна лишь до тех пор, пока описание языка остается простым и неформальным. Описание машины и транслятора VDL языка PL/I получилось очень сложным, так что практическим 
целям оно не служит. 
Проблема операционной семантики заключается в том, что она зависит от алгоритмов, а не от гораздо более строгих математических методов. 
Так получается, что операторы одного языка программирования описываются с помощью операторов другого языка программирования, только