Шпаргалка по "Программированию и компьютерам"

1. Программы и схемы программ. Стандартные схемы программ, базис класса ССП

Описать процесс - значит определить последовательность состояний заданной информационной среды. Если мы хотим, чтобы по заданному описанию требуемый процесс порождался автоматически на компьютере, необходимо, чтобы это описание было формализованным. Такое описание называется программой.

Программы и схемы программ

Схемы программ - это математические модели программ, описывающие строение программы, или точнее строение множества программ, где конкретные операции и функции заменены абстрактными функциональными и предикатными символами. Следующий пример программ вычисления факториала n! и переворачивания слов поясняет различие между программами и их схемой S₁.

 

begin integer x, y;   begin integer x, y;   begin

ввод(x);    ввод(x);    ввод(x);

y:=1;     y:=ε;     y:=a;

L: if x=0 then goto L1;  L: if x=0 then goto L1;  L: if p(x) then goto L1;

y:=x*y;     y:=CONSCAR(x, y);   y:=g(x, y);

x:=x-1;     x:=CDR(x);    x:=h(x);

goto L;     goto L;     goto L;

L1: вывод(y);   L1: вывод(y);   L1: вывод(y);

end     end     end

 

Функция CONSCAR (суперпозиция функций CONS и CAR из языка Лисп) приписывает первую букву первого слова ко второму слову (т. е. CONSCAR(аб, в) = ав), а функция CAR стирает первую букву слова (т. е. CAR(аб) = б).

1.2. Стандартные схемы  программ

1.2.1. Базис класса стандартных схем программ

Стандартные схемы программ (ССП) характеризуются  базисом и структурой схемы.

Базис класса фиксирует символы, из которых строятся схемы, указывает их роль (переменные, функциональные символы и др.), задает вид выражений и операторов схем.

Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных множеств символов и множества операторов - слов, построенных из этих символов.

Множества символов полного базиса:

1. Х = {x, х₁, х₂..., у, у₁ у₂..., z, z₁, z₂...} - множество символов, называемых переменными;
2. F = {f⁽⁰⁾, f⁽¹⁾, f⁽²⁾..., g⁽⁰⁾, g⁽¹⁾, g⁽²⁾..., h⁽⁰⁾, h⁽¹⁾, h⁽²⁾...} - множество функциональных символов; верхний символ задает местность символа; нульместные символы называют константами и обозначают начальными буквами латинского алфавита a, b, c...;
3. Р = {р⁽⁰⁾, р⁽¹⁾, р⁽²⁾...; q⁽⁰⁾, q⁽¹⁾, q⁽²⁾...; } - множество предикатных символов; р⁽⁰⁾, q⁽⁰⁾ - ; нульместные символы называют логическими константами;
4. {start, stop, ...,:= и т. д.} - множество специальных символов.

Термами (функциональными выражениями) называются слова, построенные из переменных, функциональных и специальных символов по следующим правилам:

1. односимвольные слова, состоящие из переменных или констант, являются термами;
2. слово τ вида f⁽ⁿ⁾(τ₁, τ₂...τ_n), где τ₁, τ₂...τ_n - термы, является термом;
3. те и только те слова, о которых говорится в п.п. 1,2, являются термами.

Примеры термов: х, f⁽⁰⁾, а, f⁽¹⁾(х), g⁽²⁾(x, h⁽³⁾(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р⁽ⁿ⁾(τ₁, τ₂,...,τ_n). Примеры: p⁽⁰⁾,  p⁽⁰⁾(х), g⁽³⁾(x, y, z),  p⁽²⁾ (f⁽²(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

Множество операторов включает пять типов:

1. начальный оператор - слово вида start(х_1, х₂...х_к), где k ≥0, а х_1, х₂...х_к - переменные, называемые результатом этого оператора;
2. заключительный оператор - слово вида stop(τ_1, τ₂...τ_n), где n ≥0, а τ_1, τ₂...τ_n - термы; вхождения переменных в термы τ называются аргументами этого оператора;
3. оператор присваивания - слово вида х := τ, где х – переменная (результат оператора), а τ - терм; вхождения переменных в термы называются аргументами этого оператора;
4. условный оператор (тест) - логическое выражение; вхождения переменных в логическое выражение называются аргументами этого оператора;
5. оператор петли - односимвольное слово loop.

Среди операторов присваивания выделим случаи: когда τ - переменная, то оператор называется пересылкой (х:=у) и когда τ -константа, то оператор называется засылкой (х:=а).

Подклассы используют ограниченные базисы. Так, например, подкласс У₁ имеет базис:

{х₁, х₂}, {а, f⁽¹⁾}, {p⁽¹⁾}, {start, stop, (,),:=, ,}и множество операторов {start(х₁, х₂); х₁:= f(x₁), x₂=f(x₂), x₁:=а, х₂:= а, р(х₁), р(х₂), stop(х₁,х₂)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

 

2. Графовая форма представления ССП

Представим стандартную схему  программ как размеченный граф, вершинам которого приписаны операторы из некоторого базиса В.

Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф без свободных дуг и с вершинами следующих пяти видов:

1. Начальная вершина (ровно одна) помечена начальным о1ператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.
2. Заключительная вершина (может быть несколько). Помечена заключительным оператором. Из нее не выходит ни одной дуги.
3. Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.
4. Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).
5. Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.

Конечное множество переменных схемы S составляют ее память Х_S.

Из определения следует, что  один и тот же оператор может помечать несколько вершин схемы.

Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2...). Начальная вершина всегда помечается меткой 0.

Схема S называется правильной, если на каждой дуге заданы все переменные.

Пример правильной ССП S₁ в графовой форме приведен на рисунке 1.2, а.

Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы записаны внутри вершины.

 

3. Линейная форма представления ССП

Для использования линейной формы  СПП множество специальных символов расширим дополнительными символами {:, goto, if, then, else}. СПП в линейной форме представляет собой последовательность инструкций, которая строится следующим образом:

1. если выходная дуга начальной вершины с оператором start(х₁,..., х_n) ведет к вершине с меткой L, то начальной вершине соответствует инструкция:

0: start(х₁,..., х_n) goto L;

2. если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=τ, выходная дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:

L: x: =τ goto L1;

3. если вершина с меткой L - заключительная вершина с оператором stop(τ₁,...τ_m), то ей соответствует инструкция

L: stop(τ₁,..., τ_m);

4. если вершина с меткой L - распознаватель с условием р(τ₁,...τ_k), причем 1-дуга ведет к вершине с меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция

L: if  р(τ₁,...τ_k) then  L1 else L0;

5. если вершина с меткой L - петля, то ей соответствует инструкция

L: loop.

Обычно используется сокращенная  запись (опускание меток). Полная и сокращенная линейные формы ССП (рисунок 1.2, а) приведены ниже

0: start(х) goto 1,       start(х),

1: у: = а goto 2,       у: = а,

2: if р(х) then 5 else 3,    2:  if р(х) then 5 else 3,

3: у: = g(x,y) goto 4,      3:  у: = g(x,y),

4: х: = h(x) goto 2,       х: = h (x) goto 2,

5: stop(у).      5: stop(у).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Эквивалентность, пустота, тотальность, свобода схем программ

1.3. Свойства и  виды стандартных схем программ

1.3.1. Эквивалентность, тотальность,  пустота, свобода

ССП S в базисе В тотальна (пуста), если для любой интерпретации I базиса В программа (S, I) останавливается (зацикливается).

Стандартные схемы S₁ и S₂ в базисе В функционально эквивалентны (S₁ ~ S₂), если либо обе зацикливаются, либо обе останавливаются с одинаковым результатом, т. е. val (S₁, I) » val (S₂, I).

Примеры тотальных, пустых и эквивалентных схем S₂, S₃, S₄, S₅ приведены на рисунке 1.3.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1.3

Цепочкой стандартной  схемы (ЦСС) называют:

1. конечный путь по  вершинам схемы, ведущий от  начальной вершины к заключительной;

2. бесконечный путь по  вершинам, начинающийся начальной вершиной схемы.

В случае, когда вершина-распознаватель (v), то дополнительно указывается верхний индекс (1 или 0), определяющий 1-дугу или 0-дугу, исходящую из вершины.

 

Примеры цепочек схемы S₁ (рисунок 1.2,а):

(0, 1, 2¹, 5); (0, 1, 2⁰, 3, 4, 2⁰,3,4,2¹,5) и т. д.

Цепочкой операторов (ЦО) называется последовательность операторов, метящих вершины некоторой цепочки схемы.

Например для S₁: (start(х), у:=a, р¹(x), stop(у)) или (start(х), у:=a, р⁰(x), y:=g(x, y), x:=h(x), р⁰(x), y:=g(x, y), x:=h(x), р⁰(x), y:=g(x, y), x:=h(x), …)) и т. д.

Предикатные символы ЦО обозначаются так же, как вершины распознавателей в ЦСС.

Пусть S - ССП в базисе В, I - некоторая его интерпретация, (0, 1, к₂, к₃,…) - последовательность меток инструкций S, выписанных в том порядке, в котором эти метки входят в конфигурации протокола выполнения программы (S, I). Ясно, что эта последовательность – цепочка схемы S. Считают, что интерпретация I подтверждает (порождает) эту цепочку.

ЦСС в базисе В называют допустимой, если она подтверждается хотя бы одной интерпретацией этого базиса.

Не всякая ЦСС является допустимой. В схеме S₂ (рисунок 1.3,а) цепочки (0, 1, 2⁰, 5, 6¹, 7), (0, 1, 2¹, 3, 4⁰, 7) и все другие конечные цепочки не подтверждаются ни одной интерпретацией.

Свойство допустимости цепочек  играет чрезвычайно важную роль в  анализе ССП. В частности оно  определяет те случаи, когда стандартная  схема свободна.

ССП свободна, если все ее цепочки допустимы.

Допустимая цепочка  операторов - это цепочка операторов, соответствующая допустимой цепочке схемы. В тотальной схеме все допустимые цепочки (и допустимые цепочки операторов) конечны. В пустой схеме - бесконечны.

Рассмотренные свойства распространяются на все другие классы стандартных схем и образуют опорные пункты схематологии программирования.

 

5. Моделирование схем программ, одноленточные автоматы

Конечный одноленточный (детерминированный, односторонний) автомат обнаруживают ряд полезных качеств, используемых в теории схем программ для установления разрешимости свойств ССП.

Одноленточный конечный автомат (ОКА) над алфавитом V задается набором

A = { V, Q, R, q₀, #, I } и правилом функционирования, общим для всех таких автоматов. В наборе А

V - алфавит;

Q - конечное непустое множество состояний (QÇV=Æ);

R - множество выделенных заключительных состояний (RÍQ);

q₀ - выделенное начальное состояние;

I - программа автомата; 

# - «пустой» символ.

Программа автомата I представляет собой множество команд вида qа®q', в которой q,q'ÎQ, aÎV и для любой пары (q, a) существует единственная команда, начинающаяся этими символами.

Неформально ОКА можно представить  как абстрактную машину, похожую  на машину Тьюринга, но имеющую следующие  особенности:

1) выделены заключительные состояния;

2) машина считывает символы с  ленты, ничего не записывая  на нее;

3) на каждом шаге головка автомата, считав символ с ленты и  перейдя согласно программе в  новое состояние, обязательно  передвигается вправо на одну клетку;

4) автомат останавливается в  том и только в том случае, когда головка достигнет конца слова, т.е. символа #.

Говорят, что автомат допускает  слово a в алфавите V, если, начав работать с лентой, содержащей это слово, он останавливается в заключительном состоянии. Автомат A задает характеристическую функцию множества M_A допускаемых им слов в алфавите V, т. е. он распознает, принадлежит ли заданное слово множеству M_A если связать с остановкой в заключительном состоянии символ 1, а с остановкой в незаключительном состоянии – 0.