Структурна теорема Бьома — Якопіні

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Вступний розділ цієї статті, ймовірно, несповна підсумовує ключові тези її вмісту. Будь ласка, допоможіть розширити вступ, додавши стислий огляд найважливіших аспектів статті. (квітень 2021)

Базові алгоритмічні структури — це основні структурні елементи, за допомогою яких створюють алгоритм для розв'язування певної задачі. Існують три основні (базові) алгоритмічні структури: слідування (лінійна), розгалуження та повторення, за допомогою поєднання яких може бути представлено логічну структуру будь-якого алгоритму.

Основна особливість базових алгоритмічних структур — це їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму, та наявність у кожної з них одного входу та одного виходу. Графічні зображення структур називають блок-схемами.

Теорема Бьома — Якопіні[ред. | ред. код]

Теорема Бьома — Якопіні — положення структурного програмування, згідно з яким виконуваний алгоритм можна втілити з використанням лише трьох конкретних структур керування:

  • послідовного виконання (англ. Sequence) — послідовне виконання однієї команди (підпрограми), а потім іншої команди (підпрограми);
  • розгалужень (англ. Selection) — виконання однієї з двох команд (підпрограм) залежно від значення логічного виразу (вибір);
  • повторень (циклів) (англ. Iteration) — повторне виконання команди (підпрограми), поки логічний вираз є істинним (ітерація).

Цю теорему сформулювали та довели італійські математики Коррадо Бьом і Джузеппе Якопіні (Giuseppe Jacopini) в їхній статті 1966 року[1], де описано методи перетворення неструктурованих алгоритмів на структуровані на прикладі створеної Бьомом мови програмування P′′.

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

Структурна теорема Бьома — Якопіні була початком структурного програмування — парадигми програмування, яка виключає команди безумовного переходу (goto) й використовує виключно підпрограми, послідовне виконання, розгалуження (вибір) і цикли (ітерації). Ця теорема є науковим положенням, яке Дейкстра застосував для обґрунтування його ідеї про використання в програмах лише трьох структур керування: послідовного виконання, розгалужень і циклів[3].

Доведення в праці Бьома та Якопіні проведено за індукцією в структурі блок-схеми[4]. Оскільки в графах використовувалося зіставлення зі зразком, доведення, запропоноване Бьомом і Якопіні не було дійсно практичним як алгоритм перетворення програми до структурованого вигляду, і, таким чином, відкрило двері для додаткових досліджень у цьому напрямку[5].

Базова структура «слідування»[ред. | ред. код]

Структура слідування (лінійна, послідовне виконання) — це алгоритмічна структура, яка забезпечує отримання результату шляхом одноразового виконання послідовності дій, незалежно від параметрів вхідних даних та проміжних результатів. Дії в таких структурах виконуються послідовно, одна за одною, тобто лінійно.

Алгоритмічна мова Блок-схема
дія 1

дія 2

. . . . . . . . .

дія n


Базова структура «розгалуження»[ред. | ред. код]

Розгалуження (умова, структура вибору) — вибір дій у разі виконання або невиконання заданої умови. Забезпечує, залежно від результату перевірки умови (так чи ні), вибір одного з альтернативних шляхів роботи алгоритму. Кожен із шляхів веде до загального виходу, тож робота алгоритму продовжиться незалежно від того, який шлях буде обрано.

Розгалуження бувають повними і неповними.

Повне розгалуження — це розгалуження, в якому певні дії визначено й у разі виконання, і в разі невиконання умови. Неповне розгалуження — це розгалуження, в якому дії визначено лише в разі виконання (або в разі невиконання) умови.

Структура розгалуження існує в чотирьох основних варіантах:

  • якщо то;
  • якщо то-інакше;
  • вибір;
  • вибір-інакше.
Алгоритмічна мова Блок-схема
якщо … то …
 якщо умова

      то дії

 


якщо … то …інакше …
 якщо умова

  то дії 1

  інакше дії 2

 


вибір
 вибір

  при умова 1: дії 1

  при умова 2: дії 2

.  .  .  .  .  .  .  .  .  .  .

  при умова N: дії N

 

вибір … інакше …
 вибір

  при умова 1: дії 1

  при умова 2: дії 2

  .  .  .  .  .  .  .  .  .  .  .

  при умова N: дії N

 інакше дії N + 1

 


Приклади структури розгалуження

Алгоритмічна мова Блок-схема
 якщо x> 0

  то y: = sin (x)


 якщо a> b

  то a: = 2 * a;  b: = 1

  інакше b: = 2 * b


 вибір

  при n = 1: y: = sin (x)

  при n = 2: y: = cos (x)

  при n = 3: y: = 0

 


 вибір

  при a> 5: i: = i + 1

  при a = 0: j: = j + 1

 інакше i: = 10;  j: = 0


Базова структура «повторення»[ред. | ред. код]

Повторення (цикли, структура повторення) — структура, в якій передбачено повторення деякої команди чи послідовності/серії команд. За допомогою цієї структури описують однотипні дії, що повторюються декілька разів. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд. Використання циклів дозволяє у повній мірі реалізувати швидкодію комп'ютерів.

Повторення забезпечує багаторазове виконання деякої сукупності дій, яку називають тілом циклу. Основні різновиди циклів наведено в таблиці:

Алгоритмічна мова Блок-схема
Цикли з умовою

Вказує на необхідність виконувати серію команд (тіло циклу) доти,
поки виконується умова, записана після слова поки.

Цикл з передумовою


пц поки умова

  тіло циклу

  (послідовність дій)

 кц


Цикл з післяумовою


пц

  тіло циклу

  (послідовність дій)

 поки умова кц

Цикл з параметром

Вказує на необхідність виконувати тіло циклу для всіх значень
деякої змінної-лічильника (параметра циклу) в заданому діапазоні.

 пц для i від i1 до i2

  тіло циклу

  (послідовність дій)

 кц


Приклади структур повторення

Алгоритмічна мова Блок-схема
 пц поки i <= 5

  S: = S + A [i]

  i: = i + 1

 кц


 пц для i від 1 до 5

  x [i]: = i * i * i

  y [i]: = x [i] / 2

 кц


Наслідки та уточнення[ред. | ред. код]

Теорема Бьома — Якопіні не розв'язує питання про те, чи слід застосовувати структурне програмування для розробки програмного забезпечення, почасти тому, що конструкція швидше за все «затінює» програму, ніж поліпшує її. Навпаки, це стало сигналом до початку обговорення. Знаменитий лист Едсгера Дейкстри «Go To Statement Considered Harmful» 1968 року поклав початок цій дискусії[6].

Деякі науковці використовували пуристській підхід до результату Бьома — Якопіні й стверджували, що навіть такі інструкції, як break і return зі середини циклів, є поганою практикою, оскільки вони не потрібні в доведенні Бьома — Якопіні, й тому вони обстоювали, що всі цикли повинні мати єдину точка виходу. Цей пуристський підхід втілено в мові програмування Pascal (розроблено в 1968—1969 роках), яка до середини 1990-х років була найкращим інструментом для навчання основ програмування[7].

Едвард Юдон зазначає, що в 1970-х роках була навіть філософська опозиція перетворенню неструктурованих програм на структуровані за допомогою автоматизованих засобів, ґрунтована на аргументі, що потрібно від самого початку думати в стилі структурованого програмування. Прагматичним контрапунктом було те, що такі перетворення принесли користь великій кількості наявних програм[8]. Серед перших пропозицій з автоматизованого перетворення була стаття Едварда Ешкрофта і Зохара Манни, опублікована 1971 року.

Пряме застосування теореми Бьома — Якопіні може призвести до додавання до структурованої програми додаткових локальних змінних, а також до деякого дублювання коду. Останнє питання в цьому контексті називають проблемою циклу з половиною. На Паскаль впливають обидві ці проблеми, і, згідно з емпіричними дослідженнями, на які посилається Ерік С. Робертс, учням, які навчаються програмування, досить складно формулювати правильні розв'язки на Паскалі для кількох простих завдань, включно з написанням функції для пошуку елемента в масиві. Дослідження, проведене 1980 року Генрі Шапіро та цитоване Робертсом, показало, що з використанням лише структур керування, наданих Паскалем, правильний розв'язок знайшли лише 20 % випробовуваних, у той час як жоден з випробуваних не написав неправильного коду для цієї задачі, якщо йому було дозволено написати вихід із середини циклу[7].

1973 року С. Рао Косараджу довів, що можливо уникати додавання додаткових змінних в структурну програму, якщо допускаються багаторівневі виходи довільної глибини з циклів[9][10]. Крім того, Косараджу довів, що існує строга ієрархія програм, нині звана ієрархією Косараджу, в якій для кожного цілого числа n існує програма, яка містить багаторівневий вихід глибини n, який неможливо переписати як програму з багаторівневими виходами глибини менше n (без уведення додаткових змінних)[9]. Косараджу посилається на багаторівневу конструкцію виходу в мові програмування BLISS. Багаторівневі виходи у формі ключового слова leave label фактично введено у версії BLISS-11 цієї мови; в оригінальній BLISS були лише однорівневі виходи. Мова програмування Java пізніше буде дотримуватися цього підходу[11]. Простіший результат зі статті Косараджу полягає в тому, що програма зводиться до структурованої програми (без додавання змінних) тоді й лише тоді, коли вона не містить циклу з двома різними виходами. Косараджу визначав, у принципі, редуковані як обчислення тієї ж функції й використання тих же «примітивних дій» та предикатів, що й у вихідній програмі, але, можливо, з використанням різних структур керування. Натхненний цим результатом, у своїй статті, де він вводив поняття цикломатичної складності, Томас Дж. Маккейб описав аналог теореми Куратовського для графів потоків керування (CFG) неструктурованих програм, тобто мінімальні підграфи, які роблять CFG програми неструктурованими. Ці підграфи мають дуже хороший опис природною мовою:

  • розгалуження поза циклом (крім циклічної перевірки циклу)
  • розгалуження в циклі
  • перехід в рішення (тобто у «відгалуження» if)
  • відгалуження рішення

Маккейб фактично виявив, що ці чотири графи не є незалежними при відображенні як підграфи, а це означає, що необхідною і достатньою умовою для неструктурованої програми є наявність в її підгрупі однієї з підмножин будь-якого з трьох з цих чотирьох графів. Він також виявив, що якщо неструктурована програма містить один з цих чотирьох підграфів, вона повинна містити ще один відмінний від набору з чотирьох. Цей останній результат допомагає пояснити, як потік керування неструктурованою програмою заплутується в так званому «коді спагетті». Маккейб також розробив числову міру, яка, з огляду на довільну програму, кількісно визначає, наскільки вона далека від ідеалу структурованої програми; Маккейб назвав свою міру істотною складністю[12].

До 1990 року було запропоновано досить багато методів для виключення команди безумовного переходу goto з наявних програм за збереження більшої частини їхньої структури. Різні підходи до цієї задачі також запропонували кілька понять еквівалентності, які є більш строгими, ніж просто еквівалентність Тюрінга, щоб уникнути виходу. Строгість обраного поняття еквівалентності диктує мінімальний набір необхідних структур керування потоками. У статті JACM 1988 року, написаній Лайлом Рамшоу, оглянуто ситуацію до цього моменту, а також запропоновано власний метод[13]. Алгоритм Рамшоу використовувався, наприклад, у деяких декомпіляторах Java, оскільки в коді віртуальної машини Java є інструкції розгалуження з цільовими значеннями, вираженими у вигляді зсувів, але в мові Java високого рівня є лише багаторівневі оператори break і continue[14][15]. Аммаргеллат (1992) запропонував метод перетворення, який зводиться до примусу до єдиного виходу[5].

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ BöhmCorrado; JacopiniGiuseppe (1 травня 1966). Flow diagrams, turing machines and languages with only two formation rules. Communications of the ACM (EN) . doi:10.1145/355592.365646. Архів оригіналу за 26 червня 2020. Процитовано 7 січня 2020.
  2. ↑ W, DijkstraEdsger (1 березня 1968). Letters to the editor: go to statement considered harmful. Communications of the ACM (EN) . doi:10.1145/362929.362947. Архів оригіналу за 8 червня 2020. Процитовано 7 січня 2020.
  3. ↑ Авачева Т. Г., Пруцков А. В. Современный взгляд на концепцию структурного программирования. prutzkow.com. Архів оригіналу за 7 листопада 2019. Процитовано 7 січня 2020.
  4. ↑ HarelDavid (1 липня 1980). On folk theorems. Communications of the ACM (EN) . doi:10.1145/358886.358892. Архів оригіналу за 26 червня 2020. Процитовано 8 січня 2020.
  5. ↑ а б Ammarguellat, Z. (1992-03). A control-flow normalization algorithm and its complexity. IEEE Transactions on Software Engineering. Т. 18, № 3. с. 237—251. doi:10.1109/32.126773. ISSN 2326-3881. Архів оригіналу за 6 квітня 2019. Процитовано 8 січня 2020.
  6. ↑ Go To Statement Considered Harmful. web.archive.org. 3 липня 2007. Архів оригіналу за 3 липня 2007. Процитовано 8 січня 2020.
  7. ↑ а б Loop Exits and Structured Programming: Reopening the Debate (PDF). Архів оригіналу (PDF) за 25 липня 2014.
  8. ↑ Yourdon, Edward (1979). Classics in software engineering. New York : Yourdon Press.
  9. ↑ а б Kozen, Dexter; Tseng, Wei-Lung Dustin (2008). Audebaud, Philippe (ред.). The Böhm–Jacopini Theorem Is False, Propositionally. Mathematics of Program Construction (англ.). Springer Berlin Heidelberg. с. 177—192. doi:10.1007/978-3-540-70594-9_11. ISBN 978-3-540-70594-9. Архів оригіналу за 8 березня 2021. Процитовано 8 січня 2020.
  10. ↑ Kosaraju, S. Rao (1 грудня 1974). Analysis of structured programs. Journal of Computer and System Sciences. Т. 9, № 3. с. 232—255. doi:10.1016/S0022-0000(74)80043-7. ISSN 0022-0000. Архів оригіналу за 8 квітня 2019. Процитовано 8 січня 2020.
  11. ↑ Brender, Ronald F. (2002). The BLISS programming language: a history. Software: Practice and Experience (англ.). Т. 32, № 10. с. 955—981. doi:10.1002/spe.470. ISSN 1097-024X. Процитовано 8 січня 2020.
  12. ↑ McCabe, T. J. (1976-12). A Complexity Measure. IEEE Transactions on Software Engineering. Т. SE-2, № 4. с. 308—320. doi:10.1109/TSE.1976.233837. ISSN 2326-3881. Архів оригіналу за 9 червня 2020. Процитовано 8 січня 2020.
  13. ↑ RamshawLyle (1 жовтня 1988). Eliminating go to's while preserving program structure. Journal of the ACM (JACM) (EN) . doi:10.1145/48014.48021. Архів оригіналу за 26 червня 2020. Процитовано 8 січня 2020.
  14. ↑ https://www.usenix.org/legacy/publications/library/proceedings/coots97/full_papers/proebsting2/proebsting2.pdf (PDF). Архів оригіналу (PDF) за 4 березня 2016.
  15. ↑ http://www.openjit.org/publications/pro1999-06/decompiler-pro-199906.pdf (PDF). Архів оригіналу (PDF) за 3 березня 2016.

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Структурна_теорема_Бьома_—_Якопіні&oldid=37879801