Also known as Böhm-Jacopini theorem, Dijkstra's theorem
theorem that a class of control flow graphs can compute any computable function if it combines subprograms only through sequence, selection, and iteration
Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления: последовательной (англ. 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 года. В статье также описывались методы преобразования неструктурированных алгоритмов в структурированные на примере созданного Бёмом языка программирования P′′. Спустя 2 года после публикации теоремы, в 1968 году вышла статья Эдсгера Дейкстры «Go To Statement Considered Harmful», в которой он критиковал использование оператора GOTO и высказывался в пользу улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма. Структурная теорема Бёма-Якопини не была началом структурного программирования. Эта теорема является научным положением, использованным Дейкстрой для обоснования его идеи об использовании в программах только управляющих структур: последовательных структур, ветвлений и циклов и не более того.
Abstract from DBpedia / Wikipedia · CC BY-SA
via Wikidata sitelinks · CC0
Discovered by embedding cosine similarity (sentence-transformers MiniLM, 384-dim).