рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Стандартные схемы программ - раздел Программирование, Математические основы программирования. Теория схем программ. Семантическая теория программ 1.2.1. Базис Класса Стандартных Схем Программ Стандартные Схемы Прог...

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

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

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

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

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

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

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

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

Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).

Тестами (логическими выражениями) называются логические константы и слова вида р(n)1, τ2,...,τn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2) (f(2(x, y)). Допускается в функциональных и логических выражениях опускать индексы местности, если это не приводит к двусмысленности или противоречию.

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

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

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

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

1, х2}, {а, f(1)}, {p(1)},{start,stop, (,),:=, ,}и множество операторов {start1, х2); х1:= f(x1), x2=f(x2), x1:=а, х2:= а, р(х1), р(х2), stop12)}, т. е. схемы из этого подкласса используют две переменные, константу а, один одноместный функциональный символ, один предикатный символ и операторы указанного вида.

1.2.2. Графовая форма стандартной схемы

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

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

1. Начальная вершина (ровно одна) помечена начальным о1ператором. Из нее выходит ровно одна дуга. Нет дуг, ведущих к начальной вершине.

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

3. Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна дуга.

4. Вершина-распознаватель. Помечена условным оператором (называемым условием данной вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).

5. Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.

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

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

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

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

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

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

1.2.3. Линейная форма стандартной схемы

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

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

0:start(х1,..., хn) goto L;

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

L: x: =τgotoL1;

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

L:stop1,..., τm);

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

L: ifр(τ1,...τk)thenL1elseL0;

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

L: loop.

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

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

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

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

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

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

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

 
 

 


1.2.4. Интерпретация стандартных схем программ

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

Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области интерпретации D называется функция I, которая сопоставляет:

1. каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации D;

2. каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;

3. каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));

4. каждой логической константе р(0) - один символ множества { 0,1 };

5. каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).

Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной программой (СП).

Определим понятие выполнения программы.

Состоянием памяти программы (S,I) называют функцию W: XS ® D, которая каждой переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.

Значение терма τ при интерпретации I и состоянии памяти W (обозначим τI(W)) определяется следующим образом:

1) если τ=х, x – переменная, то τI(W) = W(x);

2) если τ=a, a – константа, то τI(W) = I(a);

3) если τ=f(n)(τ1, τ2..., τn), то τI(W)= I(f(n))(τ1I(W), τ2I(W),..., τnI(W)).

Аналогично определяется значение теста p при интерпретации I и состоянии памяти W или pI(W):

если p=р(n)1, τ2..., τn), то pI(W)= I(p(n))(τ1I(W), τ2I(W),... τnI(W)), n ≥0.

Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W - состояние ее памяти. Выполнение программы описывается конечной или бесконечной последовательностей конфигураций, которую называют протоколом выполнения программы (ПВП).

Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S,I) определяем следующим образом (ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui=(ki,Wi)):

U0=(0, W0), W0 – начальное состояние памяти схемы S при интерпретации I.

Пусть Ui=(ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если О - заключительный оператор stop1, τ2... τn), то Ui - последняя конфигурация, так что протокол конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность значений τ1I(W), τ2I(W),..., τnI(W) объявляют результатом val(S,I) выполнения программы (S,I). В противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая, (i+1)-я конфигурация Ui+1 = (ki+1, Wi+1), причем

а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

б) если О - оператор присваивания х:=τ, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L, Wi+1 = Wi, Wi+1(х) = τ1(Wi);

в) если О - условный оператор p и pI(Wi) = Δ, где Δ Î{0,1}, а выходящая из него дуга ведет к вершине с меткой L, то ki+1 = L и Wi+1 = Wi;

г) если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.

Таким образом, программа останавливается тогда и только тогда, когда протокол ее выполнения конечен. В противном случае программа зацикливается и результат ее выполнения не определен.

Рассмотрим две интерпретации СПП S1 (рисунок 1.2, а). Интерпретация (S1, I1) задана так:

  • область интерпретации D1 Í Nat - подмножество множества Nat целых неотрицательных чисел;
  • I1(x)=4; I1(y)=0; I1(a)=1;
  • I1(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2;
  • I1(h)=H, где H - функция вычитания единицы, т. е. H(d)= d-1;
  • I1(p)=P1, где P1 - предикат «равно 0», т.е. P1(d)=1, если d=0.

Программа (S1, I1) вычисляет 4! (рисунок 1.2,б).

Интерпретация (S1, I2) задана следующим образом:

  • область интерпретации D2=V*, где V={a,b,c}, V* - множество всех возможных слов в алфавите V.
  • I2(x)=abc;
  • I2(y)=e, где e - пустое слово;
  • I2(a)= e;
  • I2(g)=CONSTAR;
  • I2(h)=CDR;
  • I2(p)=P2, где P2 - предикат «равное e», т.е. P2(a)=1, если a=e.

Программа (S1, I2) преобразует слово abc в слово cba (рисунок 1.2, в).

ПВП (S1, I1) и (S1, I2) конечен, результат - 24 и - cba (таблица 1.1 и 1.2).

Таблица 1.1

Конфигурация U0 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13
Метка  
Значения х
  у

Таблица 1.2

Конфигурация U0 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12
Метка
Значения x abc abc abc abc bc bc bc c c c e e e
  у e e e a a a ba ba ba cba cba cba cba

– Конец работы –

Эта тема принадлежит разделу:

Математические основы программирования. Теория схем программ. Семантическая теория программ

Следуя А П Ершову мы употребляем термин теоретическое программирование в качестве названия математической дисциплины изучающей синтаксические.. В настоящее время сложились следующие основные направления исследований.. Математические основы программирования Основная цель исследований развитие математического аппарата..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Стандартные схемы программ

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Программа как формализованное описание процесса обработки данных
Целью программирования является описание процессов обработки данных (в дальнейшем - просто процессов). Данные - это представление фактов и идей в формализованном виде, пригодном для п

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

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

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

Рекурсивные схемы
1.5.1. Рекурсивное программирование Среди упомянутых выше методов формализации понятия вычислимой функции метод Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего

Трансляция схем программ
1.6.1. О сравнении класс сов схем. Программы для ЭВМ, будь-то программы, записанные на операторном языке, или программы на рекурсивном языке, универсальны в том смысле, что любую вычислиму

Обогащенные и структурированные схемы
1.7.1 Классы обогащенных схем Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами. Классы счетчиковых и магази

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

Преобразователь предикатов.
Э. Дейкстра рассматривает слабейшие предусловия, т.е. предусловия, необходимые и достаточные для гарантии желаемого результата. «Условие, характеризующее множество всех начальных состояний

Языки формальной спецификации.
Языки и методы формальной спецификации, как средство проектирования и анализа программного обеспечения появились более сорока лет назад. За это время было немало попыток разработать как универсальн

Методы доказательства правильности программ.
Как известно, универсальные вычислительные машины могут быть запрограммированы для решения самых разнородных задач - в этом заключается одна из основных их особенностей, имеющая огромную практическ

Правила верификации К. Хоара.
Сформулируем правила (аксиомы) К.Хоара, которые определяют предусловия как достаточные предусловия, гарантирующие, что исполнение соответствующего оператора при успешном завершении приведет к желае

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

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

Программирование параллельных вычислений
3.5.1. Основные понятия Исполнение процессов типичной параллельной программы прерывается значительно чаще, чем процессов, работающих в последовательной среде, так как процессы параллельной

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

Основные определения
4.2.1. Теоретико-множественное определение сетей Петри Пусть мультимножество это множество, допускающее вхождение нескольких экземпляров одного и того же элемента. Сеть

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

Then begin
X1:=X1*Y; end; X2:=X2*Y; Y:=Y-1; end; write(X1); write(X2); endРисунок 4.5.

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги