Структурированные схемы
Возрастающая сложность программ привлекает все большее внимание к проблемам технологии программирования. Технологические соображения заставили, в первую очередь, пересмотреть принципы организации программ, их структуру. Дейкстра первым высказался против неупорядоченного использования переходов на метки, которое может привести и фактически приводит к переусложнению структуры программы, затрудняющему ее понимание и декомпозицию на более простые фрагменты. Реализуя концепцию так называемого структурированного программирования, он предложил, отказаться от использования переходов и ограничиться более дисциплинирующими средствами управления вычислениями, такими, как условные операторы и операторы цикла.
Класс 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) thenelse 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).
Дата добавления: 2015-07-18; просмотров: 930;