Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Вступний розділ цієї статті ймовірно несповна підсумовує ключові тези її вмісту Будь ласка допоможіть розширити вступ до

Базові алгоритмічні структури

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

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

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

Теорема Бьома — Якопіні

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

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

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

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

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

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

Базова структура «слідування»

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

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

дія 2

. . . . . . . . .

дія n

image

Базова структура «розгалуження»

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

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

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

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

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

      то дії

 

image

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

  то дії 1

  інакше дії 2

 

image

вибір
 вибір

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

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

.  .  .  .  .  .  .  .  .  .  .

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

 

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

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

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

  .  .  .  .  .  .  .  .  .  .  .

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

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

 

image

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

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

  то y: = sin (x)

image

 якщо a> b

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

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

image

 вибір

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

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

  при n = 3: y: = 0

 

image

 вибір

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

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

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

image

Базова структура «повторення»

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

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

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

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

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


пц поки умова

  тіло циклу

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

 кц

image

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


пц

  тіло циклу

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

 поки умова кц

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

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

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

  тіло циклу

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

 кц

image

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

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

  S: = S + A [i]

  i: = i + 1

 кц

image

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

  x [i]: = i * i * i

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

 кц

image

Наслідки та уточнення

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

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

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

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

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

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

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

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

Див. також

Примітки

  1. BöhmCorrado; JacopiniGiuseppe (1 травня 1966). . Communications of the ACM (EN) . doi:10.1145/355592.365646. Архів оригіналу за 26 червня 2020. Процитовано 7 січня 2020.
  2. W, DijkstraEdsger (1 березня 1968). . 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). . Communications of the ACM (EN) . doi:10.1145/358886.358892. Архів оригіналу за 26 червня 2020. Процитовано 8 січня 2020.
  5. Ammarguellat, Z. (1992-03). . IEEE Transactions on Software Engineering. Т. 18, № 3. с. 237—251. doi:10.1109/32.126773. ISSN 2326-3881. Архів оригіналу за 6 квітня 2019. Процитовано 8 січня 2020.
  6. . web.archive.org. 3 липня 2007. Архів оригіналу за 3 липня 2007. Процитовано 8 січня 2020.
  7. (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 (ред.). . Mathematics of Program Construction (англ.). Springer Berlin Heidelberg. с. 177—192. doi:10.1007/978-3-540-70594-9_11. ISBN . Архів оригіналу за 8 березня 2021. Процитовано 8 січня 2020.
  10. Kosaraju, S. Rao (1 грудня 1974). . 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). . 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). . Journal of the ACM (JACM) (EN) . doi:10.1145/48014.48021. Архів оригіналу за 26 червня 2020. Процитовано 8 січня 2020.
  14. (PDF). Архів оригіналу (PDF) за 4 березня 2016.
  15. (PDF). Архів оригіналу (PDF) за 3 березня 2016.

Посилання

  • DeMillo, Richard A. (1980). Space-Time Trade-Offs in Structured Programming: An Improved Combinatorial Embedding Theorem. Journal of the ACM. 27 (1): 123—127. doi:10.1145/322169.322180.
  • Devienne, Philippe (1994). One binary horn clause is enough. Lecture Notes in Computer Science. Т. 775. с. 19—32. doi:10.1007/3-540-57785-8_128. ISBN .
  • http://www.cs.uwlax.edu/~riley/CS421/lect8_boehm.ppt [ 26 липня 2011 у Wayback Machine.] a slightly more detailed explanation of the construction used in the folk theorem's proof, with a concrete example of transformed program
  • Структурные модели алгоритмов в задачах прикладного программирования. I. Формальные алгоритмические структуры [ 1 листопада 2019 у Wayback Machine.] / Шинкаренко В. И., Ильман В. М., Скалозуб В. В. // Кибернетика и системный анализ. — 2009. — № 3. — С. 3-14.
  • Дискретні та алгоритмічні структури в інструментарії програмної інженерії: навч. посіб. [ 24 серпня 2020 у Wayback Machine.] / В. В. Скалозуб, В. М. Ільман, Ю. М. Івченко, В. О. Андрющенко ; Дніпропетр. нац. ун-т залізн. трансп. ім. акад. В. Лазаряна. — Дніпропетровськ: ДНУЗТ ім. акад. В. Лазаряна, 2016. — 254 с. — ISBN 978-966-8471-73-5.
  • Введение в информатику. Базовые алгоритмические структуры [ 23 грудня 2019 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Vstupnij rozdil ciyeyi statti jmovirno nespovna pidsumovuye klyuchovi tezi yiyi vmistu Bud laska dopomozhit rozshiriti vstup dodavshi stislij oglyad najvazhlivishih aspektiv statti kviten 2021 Bazovi algoritmichni strukturi ce osnovni strukturni elementi za dopomogoyu yakih stvoryuyut algoritm dlya rozv yazuvannya pevnoyi zadachi Isnuyut tri osnovni bazovi algoritmichni strukturi sliduvannya linijna rozgaluzhennya ta povtorennya za dopomogoyu poyednannya yakih mozhe buti predstavleno logichnu strukturu bud yakogo algoritmu Osnovna osoblivist bazovih algoritmichnih struktur ce yih povnota tobto cih struktur dostatno dlya stvorennya najskladnishogo algoritmu ta nayavnist u kozhnoyi z nih odnogo vhodu ta odnogo vihodu Grafichni zobrazhennya struktur nazivayut blok shemami Teorema Boma YakopiniTeorema Boma Yakopini polozhennya strukturnogo programuvannya zgidno z yakim vikonuvanij algoritm mozhna vtiliti z vikoristannyam lishe troh konkretnih struktur keruvannya poslidovnogo vikonannya angl Sequence poslidovne vikonannya odniyeyi komandi pidprogrami a potim inshoyi komandi pidprogrami rozgaluzhen angl Selection vikonannya odniyeyi z dvoh komand pidprogram zalezhno vid znachennya logichnogo virazu vibir povtoren cikliv angl Iteration povtorne vikonannya komandi pidprogrami poki logichnij viraz ye istinnim iteraciya Cyu teoremu sformulyuvali ta doveli italijski matematiki Korrado Bom i Dzhuzeppe Yakopini Giuseppe Jacopini v yihnij statti 1966 roku de opisano metodi peretvorennya nestrukturovanih algoritmiv na strukturovani na prikladi stvorenoyi Bomom movi programuvannya P Cherez 2 roki pislya publikaciyi teoremi 1968 roku vijshla stattya Edsgera Dejkstri Go To Statement Considered Harmful v yakij vin kritikuvav vikoristannya operatora GOTO j vislovlyuvavsya na korist polipshennya stilyu programnogo kodu za rahunok vikoristannya struktur keruvannya ta vidmovi vid inshih instrukcij sho keruyut vikonannyam algoritmu Strukturna teorema Boma Yakopini bula pochatkom strukturnogo programuvannya paradigmi programuvannya yaka viklyuchaye komandi bezumovnogo perehodu goto j vikoristovuye viklyuchno pidprogrami poslidovne vikonannya rozgaluzhennya vibir i cikli iteraciyi Cya teorema ye naukovim polozhennyam yake Dejkstra zastosuvav dlya obgruntuvannya jogo ideyi pro vikoristannya v programah lishe troh struktur keruvannya poslidovnogo vikonannya rozgaluzhen i cikliv Dovedennya v praci Boma ta Yakopini provedeno za indukciyeyu v strukturi blok shemi Oskilki v grafah vikoristovuvalosya zistavlennya zi zrazkom dovedennya zaproponovane Bomom i Yakopini ne bulo dijsno praktichnim yak algoritm peretvorennya programi do strukturovanogo viglyadu i takim chinom vidkrilo dveri dlya dodatkovih doslidzhen u comu napryamku Bazova struktura sliduvannya Struktura sliduvannya linijna poslidovne vikonannya ce algoritmichna struktura yaka zabezpechuye otrimannya rezultatu shlyahom odnorazovogo vikonannya poslidovnosti dij nezalezhno vid parametriv vhidnih danih ta promizhnih rezultativ Diyi v takih strukturah vikonuyutsya poslidovno odna za odnoyu tobto linijno Algoritmichna mova Blok shema diya 1 diya 2 diya nBazova struktura rozgaluzhennya Rozgaluzhennya umova struktura viboru vibir dij u razi vikonannya abo nevikonannya zadanoyi umovi Zabezpechuye zalezhno vid rezultatu perevirki umovi tak chi ni vibir odnogo z alternativnih shlyahiv roboti algoritmu Kozhen iz shlyahiv vede do zagalnogo vihodu tozh robota algoritmu prodovzhitsya nezalezhno vid togo yakij shlyah bude obrano Rozgaluzhennya buvayut povnimi i nepovnimi Povne rozgaluzhennya ce rozgaluzhennya v yakomu pevni diyi viznacheno j u razi vikonannya i v razi nevikonannya umovi Nepovne rozgaluzhennya ce rozgaluzhennya v yakomu diyi viznacheno lishe v razi vikonannya abo v razi nevikonannya umovi Struktura rozgaluzhennya isnuye v chotiroh osnovnih variantah yaksho to yaksho to inakshe vibir vibir inakshe Algoritmichna mova Blok shema yaksho to yaksho umova to diyi yaksho to inakshe yaksho umova to diyi 1 inakshe diyi 2 vibir vibir pri umova 1 diyi 1 pri umova 2 diyi 2 pri umova N diyi N vibir inakshe vibir pri umova 1 diyi 1 pri umova 2 diyi 2 pri umova N diyi N inakshe diyi N 1 Prikladi strukturi rozgaluzhennya Algoritmichna mova Blok shema yaksho x gt 0 to y sin x yaksho a gt b to a 2 a b 1 inakshe b 2 b vibir pri n 1 y sin x pri n 2 y cos x pri n 3 y 0 vibir pri a gt 5 i i 1 pri a 0 j j 1 inakshe i 10 j 0Bazova struktura povtorennya Povtorennya cikli struktura povtorennya struktura v yakij peredbacheno povtorennya deyakoyi komandi chi poslidovnosti seriyi komand Za dopomogoyu ciyeyi strukturi opisuyut odnotipni diyi sho povtoryuyutsya dekilka raziv Taki algoritmi zabezpechuyut vikonannya dovgoyi poslidovnosti dij zapisanih porivnyano korotkoyu poslidovnistyu komand Vikoristannya cikliv dozvolyaye u povnij miri realizuvati shvidkodiyu komp yuteriv Povtorennya zabezpechuye bagatorazove vikonannya deyakoyi sukupnosti dij yaku nazivayut tilom ciklu Osnovni riznovidi cikliv navedeno v tablici Algoritmichna mova Blok shema Cikli z umovoyu Vkazuye na neobhidnist vikonuvati seriyu komand tilo ciklu doti poki vikonuyetsya umova zapisana pislya slova poki Cikl z peredumovoyu pc poki umova tilo ciklu poslidovnist dij kc Cikl z pislyaumovoyu pc tilo ciklu poslidovnist dij poki umova kc Cikl z parametrom Vkazuye na neobhidnist vikonuvati tilo ciklu dlya vsih znachen deyakoyi zminnoyi lichilnika parametra ciklu v zadanomu diapazoni pc dlya i vid i1 do i2 tilo ciklu poslidovnist dij kc Prikladi struktur povtorennya Algoritmichna mova Blok shema pc poki i lt 5 S S A i i i 1 kc pc dlya i vid 1 do 5 x i i i i y i x i 2 kcNaslidki ta utochnennyaTeorema Boma Yakopini ne rozv yazuye pitannya pro te chi slid zastosovuvati strukturne programuvannya dlya rozrobki programnogo zabezpechennya pochasti tomu sho konstrukciya shvidshe za vse zatinyuye programu nizh polipshuye yiyi Navpaki ce stalo signalom do pochatku obgovorennya Znamenitij list Edsgera Dejkstri Go To Statement Considered Harmful 1968 roku poklav pochatok cij diskusiyi Deyaki naukovci vikoristovuvali puristskij pidhid do rezultatu Boma Yakopini j stverdzhuvali sho navit taki instrukciyi yak break i return zi seredini cikliv ye poganoyu praktikoyu oskilki voni ne potribni v dovedenni Boma Yakopini j tomu voni obstoyuvali sho vsi cikli povinni mati yedinu tochka vihodu Cej puristskij pidhid vtileno v movi programuvannya Pascal rozrobleno v 1968 1969 rokah yaka do seredini 1990 h rokiv bula najkrashim instrumentom dlya navchannya osnov programuvannya Edvard Yudon zaznachaye sho v 1970 h rokah bula navit filosofska opoziciya peretvorennyu nestrukturovanih program na strukturovani za dopomogoyu avtomatizovanih zasobiv gruntovana na argumenti sho potribno vid samogo pochatku dumati v stili strukturovanogo programuvannya Pragmatichnim kontrapunktom bulo te sho taki peretvorennya prinesli korist velikij kilkosti nayavnih program Sered pershih propozicij z avtomatizovanogo peretvorennya bula stattya Edvarda Eshkrofta i Zohara Manni opublikovana 1971 roku Pryame zastosuvannya teoremi Boma Yakopini mozhe prizvesti do dodavannya do strukturovanoyi programi dodatkovih lokalnih zminnih a takozh do deyakogo dublyuvannya kodu Ostannye pitannya v comu konteksti nazivayut problemoyu ciklu z polovinoyu Na Paskal vplivayut obidvi ci problemi i zgidno z empirichnimi doslidzhennyami na yaki posilayetsya Erik S Roberts uchnyam yaki navchayutsya programuvannya dosit skladno formulyuvati pravilni rozv yazki na Paskali dlya kilkoh prostih zavdan vklyuchno z napisannyam funkciyi dlya poshuku elementa v masivi Doslidzhennya provedene 1980 roku Genri Shapiro ta citovane Robertsom pokazalo sho z vikoristannyam lishe struktur keruvannya nadanih Paskalem pravilnij rozv yazok znajshli lishe 20 viprobovuvanih u toj chas yak zhoden z viprobuvanih ne napisav nepravilnogo kodu dlya ciyeyi zadachi yaksho jomu bulo dozvoleno napisati vihid iz seredini ciklu 1973 roku S Rao Kosaradzhu doviv sho mozhlivo unikati dodavannya dodatkovih zminnih v strukturnu programu yaksho dopuskayutsya bagatorivnevi vihodi dovilnoyi glibini z cikliv Krim togo Kosaradzhu doviv sho isnuye stroga iyerarhiya program nini zvana iyerarhiyeyu Kosaradzhu v yakij dlya kozhnogo cilogo chisla n isnuye programa yaka mistit bagatorivnevij vihid glibini n yakij nemozhlivo perepisati yak programu z bagatorivnevimi vihodami glibini menshe n bez uvedennya dodatkovih zminnih Kosaradzhu posilayetsya na bagatorivnevu konstrukciyu vihodu v movi programuvannya Bagatorivnevi vihodi u formi klyuchovogo slova leave label faktichno vvedeno u versiyi BLISS 11 ciyeyi movi v originalnij BLISS buli lishe odnorivnevi vihodi Mova programuvannya Java piznishe bude dotrimuvatisya cogo pidhodu Prostishij rezultat zi statti Kosaradzhu polyagaye v tomu sho programa zvoditsya do strukturovanoyi programi bez dodavannya zminnih todi j lishe todi koli vona ne mistit ciklu z dvoma riznimi vihodami Kosaradzhu viznachav u principi redukovani yak obchislennya tiyeyi zh funkciyi j vikoristannya tih zhe primitivnih dij ta predikativ sho j u vihidnij programi ale mozhlivo z vikoristannyam riznih struktur keruvannya Nathnennij cim rezultatom u svoyij statti de vin vvodiv ponyattya ciklomatichnoyi skladnosti Tomas Dzh Makkejb opisav analog teoremi Kuratovskogo dlya grafiv potokiv keruvannya CFG nestrukturovanih program tobto minimalni pidgrafi yaki roblyat CFG programi nestrukturovanimi Ci pidgrafi mayut duzhe horoshij opis prirodnoyu movoyu rozgaluzhennya poza ciklom krim ciklichnoyi perevirki ciklu rozgaluzhennya v cikli perehid v rishennya tobto u vidgaluzhennya if vidgaluzhennya rishennya Makkejb faktichno viyaviv sho ci chotiri grafi ne ye nezalezhnimi pri vidobrazhenni yak pidgrafi a ce oznachaye sho neobhidnoyu i dostatnoyu umovoyu dlya nestrukturovanoyi programi ye nayavnist v yiyi pidgrupi odniyeyi z pidmnozhin bud yakogo z troh z cih chotiroh grafiv Vin takozh viyaviv sho yaksho nestrukturovana programa mistit odin z cih chotiroh pidgrafiv vona povinna mistiti she odin vidminnij vid naboru z chotiroh Cej ostannij rezultat dopomagaye poyasniti yak potik keruvannya nestrukturovanoyu programoyu zaplutuyetsya v tak zvanomu kodi spagetti Makkejb takozh rozrobiv chislovu miru yaka z oglyadu na dovilnu programu kilkisno viznachaye naskilki vona daleka vid idealu strukturovanoyi programi Makkejb nazvav svoyu miru istotnoyu skladnistyu Do 1990 roku bulo zaproponovano dosit bagato metodiv dlya viklyuchennya komandi bezumovnogo perehodu goto z nayavnih program za zberezhennya bilshoyi chastini yihnoyi strukturi Rizni pidhodi do ciyeyi zadachi takozh zaproponuvali kilka ponyat ekvivalentnosti yaki ye bilsh strogimi nizh prosto ekvivalentnist Tyuringa shob uniknuti vihodu Strogist obranogo ponyattya ekvivalentnosti diktuye minimalnij nabir neobhidnih struktur keruvannya potokami U statti JACM 1988 roku napisanij Lajlom Ramshou oglyanuto situaciyu do cogo momentu a takozh zaproponovano vlasnij metod Algoritm Ramshou vikoristovuvavsya napriklad u deyakih dekompilyatorah Java oskilki v kodi virtualnoyi mashini Java ye instrukciyi rozgaluzhennya z cilovimi znachennyami virazhenimi u viglyadi zsuviv ale v movi Java visokogo rivnya ye lishe bagatorivnevi operatori break i continue Ammargellat 1992 zaproponuvav metod peretvorennya yakij zvoditsya do primusu do yedinogo vihodu Div takozhStrukturne programuvannya Algoritmichna mova Blok shema Potik keruvannya Metodi rozrobki algoritmiv Teoriya algoritmiv Spisok algoritmiv Strukturi danih Programuvannya Movna konstrukciya programuvannya PrimitkiBohmCorrado JacopiniGiuseppe 1 travnya 1966 Communications of the ACM EN doi 10 1145 355592 365646 Arhiv originalu za 26 chervnya 2020 Procitovano 7 sichnya 2020 W DijkstraEdsger 1 bereznya 1968 Communications of the ACM EN doi 10 1145 362929 362947 Arhiv originalu za 8 chervnya 2020 Procitovano 7 sichnya 2020 prutzkow com Arhiv originalu za 7 listopada 2019 Procitovano 7 sichnya 2020 HarelDavid 1 lipnya 1980 Communications of the ACM EN doi 10 1145 358886 358892 Arhiv originalu za 26 chervnya 2020 Procitovano 8 sichnya 2020 Ammarguellat Z 1992 03 IEEE Transactions on Software Engineering T 18 3 s 237 251 doi 10 1109 32 126773 ISSN 2326 3881 Arhiv originalu za 6 kvitnya 2019 Procitovano 8 sichnya 2020 web archive org 3 lipnya 2007 Arhiv originalu za 3 lipnya 2007 Procitovano 8 sichnya 2020 PDF Arhiv originalu PDF za 25 lipnya 2014 Yourdon Edward 1979 Classics in software engineering New York Yourdon Press Kozen Dexter Tseng Wei Lung Dustin 2008 Audebaud Philippe red Mathematics of Program Construction angl Springer Berlin Heidelberg s 177 192 doi 10 1007 978 3 540 70594 9 11 ISBN 978 3 540 70594 9 Arhiv originalu za 8 bereznya 2021 Procitovano 8 sichnya 2020 Kosaraju S Rao 1 grudnya 1974 Journal of Computer and System Sciences T 9 3 s 232 255 doi 10 1016 S0022 0000 74 80043 7 ISSN 0022 0000 Arhiv originalu za 8 kvitnya 2019 Procitovano 8 sichnya 2020 Brender Ronald F 2002 The BLISS programming language a history Software Practice and Experience angl T 32 10 s 955 981 doi 10 1002 spe 470 ISSN 1097 024X Procitovano 8 sichnya 2020 McCabe T J 1976 12 IEEE Transactions on Software Engineering T SE 2 4 s 308 320 doi 10 1109 TSE 1976 233837 ISSN 2326 3881 Arhiv originalu za 9 chervnya 2020 Procitovano 8 sichnya 2020 RamshawLyle 1 zhovtnya 1988 Journal of the ACM JACM EN doi 10 1145 48014 48021 Arhiv originalu za 26 chervnya 2020 Procitovano 8 sichnya 2020 PDF Arhiv originalu PDF za 4 bereznya 2016 PDF Arhiv originalu PDF za 3 bereznya 2016 PosilannyaDeMillo Richard A 1980 Space Time Trade Offs in Structured Programming An Improved Combinatorial Embedding Theorem Journal of the ACM 27 1 123 127 doi 10 1145 322169 322180 Devienne Philippe 1994 One binary horn clause is enough Lecture Notes in Computer Science T 775 s 19 32 doi 10 1007 3 540 57785 8 128 ISBN 978 3 540 57785 0 http www cs uwlax edu riley CS421 lect8 boehm ppt 26 lipnya 2011 u Wayback Machine a slightly more detailed explanation of the construction used in the folk theorem s proof with a concrete example of transformed program Strukturnye modeli algoritmov v zadachah prikladnogo programmirovaniya I Formalnye algoritmicheskie struktury 1 listopada 2019 u Wayback Machine Shinkarenko V I Ilman V M Skalozub V V Kibernetika i sistemnyj analiz 2009 3 S 3 14 Diskretni ta algoritmichni strukturi v instrumentariyi programnoyi inzheneriyi navch posib 24 serpnya 2020 u Wayback Machine V V Skalozub V M Ilman Yu M Ivchenko V O Andryushenko Dnipropetr nac un t zalizn transp im akad V Lazaryana Dnipropetrovsk DNUZT im akad V Lazaryana 2016 254 s ISBN 978 966 8471 73 5 Vvedenie v informatiku Bazovye algoritmicheskie struktury 23 grudnya 2019 u Wayback Machine

Дата публікації:
Топ