Теорема Бёма

Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления: последовательной (англ. sequence), ветвлений (англ. selection) и повторов или циклов (англ. repetition, cycle).

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

• Например:

          Подпрограмма 1  /* последовательное выполнение инструкций 1, 2 ..N…...*/ 
             Инструкция 1;
             Инструкция 2;
             ... 
             Инструкция N;
          Конец  Подпрограммы 1.

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

• Например:

          Подпрограмма 2     /* ветвлений – Выбор инструкции  согласно условию */   
             Если условие 1 то Инструкция 1;       /* выполняется, если истинно условие 1 */  
 
             Если условие 2 то Инструкция 2;       /* выполняется, если истинно условие 2 */ 
              ...
             Иначе Инструкция N;                   /* выполняется, если не ни одно из условий не является  истинным */ .
          Конец  Подпрограммы 2.

3. В циклах инструкции повторяются до тех пор пока не изменится некое условие, например значение логической переменной.

• Например:

             Подпрограмма 3  /* цикл */  
                Пока условие N выполнить Инструкция N  /*  цикл повторяется пока верно условие N */ 
                Инструкция N + 1                       /* выход из цикла по нарушению условия N */  
             Конец  Подпрограммы 3

Теорема была сформулирована и доказана итальянскими математиками Коррадо Бёмом (англ. Corrado Böhm) и Джузеппе Якопини (Giuseppe Jacopini) в их статье 1966 года^[1]. В статье также описывались методы преобразования неструктурированных алгоритмов в структурированные на примере созданного Бёмом языка программирования P′′.

Публикация теоремы была толчком к началу дебатов о структурном программировании. Спустя 2 года вышла статья Эдсгера Дейкстры «Go To Statement Considered Harmful»^[2], в которой он критиковал использование оператора GOTO и высказывался в пользу улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма.

Примечания

1. ↑ Bohm, Corrado; and Giuseppe Jacopini (May 1966). «Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules». Communications of the ACM 9 (5): 366–371. DOI:10.1145/355592.365646.
2. ↑ Dijkstra, Edsger (1968). «Go To Statement Considered Harmful». Communications of the ACM 11 (3): 147–148. DOI:10.1145/362929.362947. http://www.acm.org/classics/oct95/