Теорема Бёма — Якопини

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Структурная теорема Бёма-Якопини не была началом структурного программирования. Эта теорема является научным положением, использованным Дейкстрой для обоснования его идеи об использовании в программах только управляющих структур: последовательных структур, ветвлений и циклов и не более того[3].

Примечания

[править | править код]
  1. Bohm, Corrado; and Giuseppe Jacopini. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules (англ.) // Communications of the ACM : journal. — 1966. — May (vol. 9, no. 5). — P. 366—371. — doi:10.1145/355592.365646. Архивировано 5 марта 2016 года.
  2. Dijkstra, Edsger. Go To Statement Considered Harmful (англ.) // Communications of the ACM : journal. — 1968. — Vol. 11, no. 3. — P. 147—148. — doi:10.1145/362929.362947. Архивированная копия. Дата обращения: 3 июля 2007. Архивировано 3 июля 2007 года.
  3. Авачева Т. Г., Пруцков А. В. Современный взгляд на концепцию структурного программирования // Cloud of Science. — 2019. — Т. 6, № 4. Архивировано 7 ноября 2019 года.