Реферат Курсовая Конспект
Обогащенные и структурированные схемы - раздел Программирование, Математические основы программирования. Теория схем программ. Семантическая теория программ 1.7.1 Классы Обогащенных Схем Выделяют Следующие Классы Обогащенных ...
|
1.7.1 Классы обогащенных схем
Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами.
Классы счетчиковых и магазинных схем образован добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.
Счетчик — интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0.
Интерпретированные операторы имеют следующий вид:
c := c + 1 — оператор прибавления единицы;
c := c - 1 — оператор вычитания единицы;
c = 0 — условный оператор проверки равенства счетчика нулю.
При значении счетчика равном 0 оператор вычитания единицы не изменяет его, оно остается равным 0.
К интерпретированным операторам может быть добавлен оператор пересылки значения счетчика с2 := с1, который может быть получен при помощи стандартных операторов.
Рисунок 1.10
Магазин — неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина — это конечный набор элементов (d1,d2,…,dn) из области интерпретации, где dn — верхушка магазина.
Интерпретированные операторы имеют следующий вид:
М := x — запись в магазин;
х := М — выборка из магазина;
М = Æ — условный оператор проверки пустоты магазина,
где М – магазин, х — обычная переменная. Первый оператор меняет состояние (d1,d2,…,dn) магазина М на состояние (d1,d2,…,dn+1), где dn+1 — значение переменной х. После выполнения этого оператора элемент dn+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с (d1,d2,…,dn-1,dn) на (d1,d2,…,dn-1), при этом dn.1 становится новой верхушкой магазина. Если магазин М пуст, то применение второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор— предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = 0 равно 1, в противном случае — 0.
Класс схем с массивами — это расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними.
Массив — неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива — бесконечная последовательность (d1,d2,…,di,…) элементов из области интерпретациии.
Интерпретированные операторы имеют следующий вид:
А[c]:= x — запись в магазин;
х:= А[c] — выборка из магазина,
где А — массив, [c] — целое число, равное текущему значению счетчика с.
На рисунке 1.10. приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:
F(x), F(x)=ifp(x) thenx else f(x, F(g(x))).
1.7.2 Трансляция обогащенных схем
Диаграмма на рисунке 1.11 дает полную информацию о возможности трансляции одного класса схем в другой, классы имеют следующие обозначения:
Y — стандартные схемы; | Y(М) — магазинные схемы; |
Y(R) — рекурсивные схемы; | Y(А) — схемы с массивами; |
Y(с) — счетчиковые схемы; | Y(P) — схемы с процедурами. |
Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков не менее 2, т.е. класс Y(с) с одним счетчиком равномощен классу Y.
1.7.3. Структурированные схемы
Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил, в частности, отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла.
Класс cтруктурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y.
Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if , then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных оператора в базисе В: простой оператор, условный оператор и оператор цикла.
Простой оператор — это начальный (заключительный) оператор и оператор присваивания.
Условный оператор — это оператор вида
ifp then s1 else s0 end,
где p — логическое выражение, s1 ,s0 — последовательности (может быть, пустые) схемных операторов, среди которых нет ни начального, ни заключительного.
Операторы цикла имеют вид
while p dos endилиuntilp dos end,
где p,s имеют тот же смысл, что и выше.
Ниже приведен пример эквивалентных схем Y и Y(S).
Стандартная схема программ Y | Структурированная схема программ Y(S) |
start(х), 1: y := f(x), 2: ifp(y) then7 else 3, 3: y := f(y), 4: ifp(y) then 5 else 7, 5: ifp(x) then 6 else 7, 6: x := h(x) goto 5, 7: stop(х, y). | start(х), y := f(x), ifp(y) then else y := f(y), ifp(x) then while p(x) dox := h(x) end else end end, stop(х, y). |
Доказано, что класс Y мощнее класса Y(S), т.е. схемы Y(S) транслируемы в Y, но не наоборот.
Усилить класс Y(S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y(SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:
NOT p(x) AND q(y,x);
p(g(x, t)) OR q(h(x), x).
В этом случае справедлива
Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).
– Конец работы –
Эта тема принадлежит разделу:
Следуя А П Ершову мы употребляем термин теоретическое программирование в качестве названия математической дисциплины изучающей синтаксические... В настоящее время сложились следующие основные направления исследований... Математические основы программирования Основная цель исследований развитие математического аппарата...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Обогащенные и структурированные схемы
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов