Инструменты пользователя

Инструменты сайта


examination:c:question13

Любая простая программа функционально эквивалентна структурированной программе, составленной из элементарного базисного множества, последовательностей if,then,else; while,do с использованием функций и предикат исходной программы, а так же присвоений и проверок на дополнительном счетчике. Доказательство:

  1. Рассмотрим произвольную простую программу с произвольным числом функциональных и предикатных узлов, начинающихся с первого узла, соответствующего входной линии
  2. Зададим выходной линии №0
  3. Выходной линии каждого узла присваиваем № узла, стоящего следом за ним, если таковой имеется, в противном случае №0
  4. Для каждого функционального узла исходной программы, имеющего №i и выполняющего функцию L, а так же выходную линию j определим

Для каждого предикатного узла с №i

На основании этих определений построим по типу while do с телом цикла в виде вложенных структур разветвления if then else, пров. значения счетчика n от 1 до n. Каждая выходная линия, соответствующая истине, соединяется с узлом g, являющимся функциональным или предикатным узлом исходной программы.

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

examination/c/question13.txt · Последние изменения: 2014/01/15 12:09 (внешнее изменение)