Теорема Бёма


Теорема Бёма

Теорема Бёма — Якопини — положение структурного программирования, согласно которому любой исполняемый алгоритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управления: последовательной (англ. 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/



Wikimedia Foundation. 2010.

Смотреть что такое "Теорема Бёма" в других словарях:

  • Теорема Лёба — Теорема Лёба  теорема в математической логике о взаимосвязи между доказуемостью утверждения и самим утверждением. Установлена математиком Мартином Хуго Лёбом в 1955 году. Теорема Лёба гласит, что во всякой теории, включающей аксиоматику… …   Википедия

  • ТЕОРЕМА — (от греч. theoreo – рассматриваю) научное положение. Философский энциклопедический словарь. 2010. ТЕОРЕМА (греч. ϑεώρημα, от ϑεωρέω – рассматриваю, исследу …   Философская энциклопедия

  • ТЕОРЕМА — (греч. theorema, от theorein рассматривать). Предложение, долженствующее быть подтвержденным; истина, требующая доказательства, преимущественно в математике. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. ТЕОРЕМА… …   Словарь иностранных слов русского языка

  • ТЕОРЕМА — Пифагора. Жарг. шк. Шутл. Учительница математики. ВМН 2003, 131. Теорема Пофигатора. Жарг. шк. Шутл. Теорема Пифагора. ВМН 2003, 108. Теорема Фаллоса. Жарг. студ. (матем.). Шутл. Теорема Фалеса. (Запись 2003 г.). Теорема хана банаха. Жарг. студ.… …   Большой словарь русских поговорок

  • теорема — См …   Словарь синонимов

  • ТЕОРЕМА — (греч. theorema от theoreo рассматриваю), в математике предложение (утверждение), устанавливаемое при помощи доказательства (в противоположность аксиоме). Теорема обычно состоит из условия и заключения. Напр., в теореме: если в треугольнике один… …   Большой Энциклопедический словарь

  • ТЕОРЕМА — ТЕОРЕМА, утверждение или предложение, которое доказывается логическими рассуждениями, основанными на фактах и АКСИОМАХ. см. также ВЕЛИКАЯ ТЕОРЕМА ФЕРМА …   Научно-технический энциклопедический словарь

  • ТЕОРЕМА — ТЕОРЕМА, теоремы, жен. (от греч. theorema, букв. зрелище) (научн.). Положение, справедливость которого устанавливается путем доказательств, основанных на аксиомах или на других, уже доказанных положениях (мат.). Доказать теорему. Пифагорова… …   Толковый словарь Ушакова

  • ТЕОРЕМА — «ТЕОРЕМА» (Теогеmа) Италия, 1968, 100 мин. Философская драма. Возможно, одна из самых противоречивых картин в истории мирового кино. Она вызвала взаимоисключающие трактовки, нападки на режиссера слева и справа, расколола представителей Ватикана… …   Энциклопедия кино

  • теорема — ы, ж. Следуя логике лотмановского подхода к искусству можно предложить понятие эротемы как структурно тематической единицы эроса (термин образован с тем же французским суффиксом ем , что и другие обозначения структурных единиц языка: лексема,… …   Исторический словарь галлицизмов русского языка

Книги

Другие книги по запросу «Теорема Бёма» >>