Теория вычислительных процессов |
Лекция 5 |
Лекция 5
1.7 Обогащенные и структурированные схемы
1.7.1 Классы обогащенных схем
Выделяют следующие классы обогащенных схем: класс счетчиковых схем, класс магазинных схем, класс схем с массивами.
Классы счетчиковых и магазинных схем образованы добавлением в базис ССП счетного множества счетчиков и магазинов с их интерпретированными операторами.
Счетчик - интерпретированная переменная, у которой областью значений является множество Nat; начальное значение счетчика равно 0. Интерпретированные операторы имеют следующий вид:
с:= с + 1 - оператор прибавления единицы;
с:= с - 1 - оператор вычитания единицы;
с = 0 - условный оператор проверки равенства счетчика нулю.
При значении счетчика равном 0 оператор вычитания единицы не изменяет его. Оно остается равным 0.
К интерпретированным операторам может бьrrъ добавлен оператор пересылки значения счетчика с2:= с1, который может быть получен при помощи стандартных операторов.
Магазин - неинтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина - это конечный набор элементов (d1,d2,...,dn) из области интерпретации, где dn - верхушка магазина.
Интерпретированные операторы имеют следующий вид:
М:= х - запись в магазин;
х:= М - выборка из магазина;
М = 0 - условный оператор проверки пустоты магазина,
где М - магазин, х - обычная переменная. Первый оператор меняет состояние (d1,d2,.. .,dn) магазина М на состояние (d1,d2,.. .,dn+1), где dn+1 - значение переменной х. После выполнения этого оператора элемент dn+1 становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которого меняется с (d1,d2,...,dn-1,dn) на (d1,d2,...,dn-1), при этом dn-1 становится новой верхушкой магазина. Если магазин М пуст, то применение второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор - предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М равно 1, в противном случае - 0.
Класс схем с массивами - это расширение класса счетчиковых схем засчет добавления счетного множества массивов и операторов над ними.
Массив - неинтерпретированная переменная сложной структуры. При выполнении интерпретированной схемы состояние массива - бесконечная последовательность (d1,d2,...,di,...) элементов из области интерпретации.
Интерпретированные операторы имеют следующий вид:
А[с]:= х - запись в магазин;
х:= А[ с] - выборка из магазина,
где А - массив, [с] - целое число, равное текущему значению счетчика с.
На рисунке 1.11 приведены четыре схемы: стандартная (а), счетчиковая (б), магазинная (в) и схема с массивами (г). Все они эквивалентны друг другу и рекурсивной схеме:
F(x), F(x)=if р(х) then х else [(х, F(g(x))).
Рис. 1.11.
Диаграмма на рис. 1.12. дает полную информацию о возможности трансляции одного класса схем в другой. Классы имеют следующие обозначения:
Y - стандартные схемы; Y(М) - магазинные схемы;
Y(R) - рекурсивные схемы; Y(А) - схемы с массивами;
Y( с) - счетчиковые схемы; Y(Р) - схемы с процедурами.
Рис. 1.12.
Диаграмма показывает, что классы Y(М) и Y(А) являются универсальными в том смысле, что схемы всех других классов транслируемы в них. В то же время, в класс Y не транслируются схемы ни одного другого класса. Следует отметить, что класс Y(с) достигает полной мощности при количестве счетчиков неменее 2, т.е. класс Y( с) с одним счетчиком равномощен классу Y.
Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотретъ принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла.
Класс структурированных схем Y(S) определяется в том же (полном) базисе В, который был введен для ССП Y.
Различие между Y и Y(S) проявляется на уровне структур схем. Вместо специальных символов Y вводятся специальные символы: if , then, else, while, do, end. Вместо инструкций с метками вводятся три типа схемных операторов в базисе В: простой оператор, условный оператор и оператор цикла.
Простой оператор - это начальный (заключительный) оператор и оператор присваивания.
Условный оператор - это оператор вида
if p then g1 else g0 end,
где p - логическое выражение, g1, g0 - последовательности (может быть, пустые) операторов, среди которых нет ни начального, ни заключительного.
Операторы цикла имеют вид
while p do g end
или
until p do g end,
где p и g имеют тот же смысл, что и выше.
Ниже приведен пример эквивалентных схем Y и Y(S).
Стандартная схема программы Y
Структурированная схема программ Y(S)
Структурированные программы универсальны в том смысле, что набора предоставленных им средств достаточно для описания любой вычислимой функции. Задача автоматического преобразования стандартных схем в структурированные имеет отрицательное решение. Доказано, что класс Y мощнее класса Y(S), т.е. схемы Y(S) транслируемы в Y, но не наоборот.
Усилить класс Y(S) можно за счет усложнения логических выражений в условных операторах и операторах цикла Y(SL), введением символов логических операций NOT, OR, AND и атомарных формул, которыми являются логические выражения в старом смысле, например:
NOT р(х) AND q(y,x);
p(g(x, t)) OR q(h(x), х).
.В этом случае справедлива
Теорема (Ашкрофт - Манн) Класс стандартных схем Y транслируем в класс схем с логическими операциями Y(SL).
1.8. Вопросы для самоконтроля
1. Пусть V*n - множество всех наборов из n слов в алфавите V. Покажите, что между наборами из V*n и числами существует взаимно-однозначное соответствие. Закодировать числами пары слов в алфавите {а, Ь}.
2. Покажите, что множество {anbn I n>=1} слов в алфавите {а, Ь} разрешимо.
3. Покажите, что область определения любой вычислимой функции - перечислимое множество.
4. Покажите, что непустое множество перечислимо тогда и только тогда, когда оно является областью значений некоторой частичной вычислимой функции.
5. Покажите, что проблема остановки машины Тьюринга является частично разрешимой.
6. Постройте одноленточный автомат над алфавитом {а, Ь, с}, допускающий следующие множества слов: {a n bb I n >=0}, { a nсb mI n>= 1, m >=1}.
7. Постройте двухголовочный автомат, который устанавливает равенство пары слов в алфавите {0, 1} с точностью до перестановки некоторой единственной пары соседних символов.
8. Докажите, что отношение функциональной эквивалентности стандартных схем программ является математическим отношением эквивалентности.
9. Чем отличается определяемый функциональный символ от просто функционального символа в рекурсивной схеме?
10. Постройте протокол исполнения рекурсивной схемы:
F(a), F(x) = if p(х) then f(x) else F(F(g(x))) при интерпретации I: I(а) = 7, I(p)(d) = 1, при d>=10 I(p)(d) = 0, при d < 10, I(f)(d) = d - 1, I(g)(d) = d+2.
11. Определите понятие цепочки рекурсивной схемы, понятие допустимой цепочки, свободной рекурсивной схемы.
12. В каких случаях возможна трансляция схем?
13. Что представляет собой структурированная схема с усложненными логическими выражениями?
назад | содержание | вперед