Teorema lui Böhm-Jacopini

Teorema Böhm-Jacopini , enunțată în 1966 ^[1] de informaticieni Corrado Böhm și Giuseppe Jacopini , este o teoremă teoretică a computerului care afirmă că orice algoritm poate fi implementat în faza de programare (în diagrama de flux , pseudocod sau cod sursă ) folosind doar trei structuri numite structuri de control : secvență, selecție și iterație , care trebuie aplicate recursiv compoziției instrucțiunilor elementare (de exemplu, instrucțiuni executabile cu modelul de bază al mașinii Turing ).

Istorie

Lucrarea care afirmă acest rezultat a fost realizată de cei doi autori de la Institutul pentru aplicații de calcul , al cărui ambii erau cercetători, ca parte a unei colaborări cu Centrul Internațional de Calcul UNESCO , care avea sediul la același institut. Rolul celor doi autori este specificat în introducerea articolului. ^[2]

Structuri

Secvenţă

Secvența sau blocul reprezintă listarea normală a instrucțiunilor care trebuie executate una după alta în ordinea în care au fost scrise de programator .

Selecție (sau condiționată)

Selecția este alegerea dintre două căi de urmat succesiv, care depinde de o condiție care poate fi adevărată sau falsă. În limbajele de programare, această structură este de obicei definită cu utilizarea cuvintelor cheie, cum ar fi if ... then ... else . Condiția poate fi o variabilă de computer booleană simplă, adică o variabilă care poate avea doar valorile „adevărat” și „fals”. În practica de programare, sunt utilizate în mod normal construcții selective, cum ar fi if (a > 10) în care expresia dintre paranteze este o expresie booleană . Cu toate acestea, acest construct poate fi considerat o abreviere a unei secvențe de atribuții preliminare încheiate printr-o selecție pe o variabilă booleană simplă. În practică , ele sunt , de asemenea folosite pentru a selecta mai mult de două moduri, cum ar fi cel implicat în operatorul ?: Limbajul C , istoric cu trei căi IF de Fortran 2 (afirmatii de genul: IF(numero)100,200,300 ) și diferitele selectorii cu mai multe moduri ca o formă antică GOTO a FORTRAN 2 și construcții precum cea a lui C bazată pe switch și case . Și toate aceste construcții pot fi ușor reduse la o selecție dihotomică de bază.

Buclă (sau iterație)

Bucla, numită și iterație , este un bloc de instrucțiuni care sunt executate în mod repetat până când o anumită condiție își schimbă starea. În practică, se utilizează diferite tipuri de bucle: cele cu clauza pe condiția din cap, cele cu clauza în coadă, cele cu clauza în mijloc și cele care implică derularea unei secvențe enumerative (strict numerice sau nu). Pentru implementare folosim cuvinte cheie precum: while ... do . Toate aceste construcții pot fi, de asemenea, reduse la o construcție de bază.

Dovada teoremei

Dovada teoremei lui Böhm și Jacopini are loc prin inducerea structurală a diagramei de flux . ^[3] Folosind cuplarea tiparului în grafice, dovada lui Böhm și Jacopini nu a fost foarte utilă ca algoritm de transformare a programului, dar a deschis ușa pentru cercetări suplimentare în această direcție. ^[4]

Urmări

Această teoremă prezintă și un interes teoretic, întrucât limbajele de programare tind să se echipeze cu mai multe tipuri de instrucțiuni de anvergură pentru a evita programatorilor să se ocupe de instrucțiuni foarte minuscule și, prin urmare, dispersive în ceea ce privește stăpânirea scopurilor algoritmului (totuși, există sunt limbaje minimaliste, cum ar fi Brainfuck , care aderă la litera teoremei). Valoarea sa trebuie văzută în capacitatea sa de a oferi indicații generale pentru proiectarea de noi limbaje și strategii de programare. Într-adevăr, a contribuit la critica utilizării imprudențiale go to instrucțiunilor go to accesare și la definirea liniilor directoare de programare structurată care au avut loc în jurul anului 1970 .

Notă

^ C. Bohm și G. Jacopini, Diagramele de flux, mașini și limbi Turing cu numai două reguli de formare ( PDF ), în Comunicări ale ACM , vol. 9, nr. 5, mai 1966, pp. 366–371, DOI : 10.1145 / 355592.365646 . Adus la 5 august 2015.
^ În această lucrare, diagramele de flux sunt introduse prin metoda ostensivă; acest lucru se face pentru a evita definițiile care cu siguranță nu ar fi de mare folos. În prima parte (scrisă de G. Jacopini), sunt studiate metodele de normalizare a diagramelor, care permit descompunerea lor în diagrame de bază de trei tipuri (primul rezultat) sau de două tipuri (al doilea rezultat). În a doua parte a lucrării (de C. Böhm), sunt raportate unele rezultate ale unei lucrări anterioare și rezultatele primei părți a lucrării sunt apoi utilizate pentru a demonstra că fiecare mașină Turing este reductibilă sau într-o sensul determinat este echivalent cu un program scris într-un limbaj care admite ca reguli de formare doar compoziția și iterația.
^ David Harel , Despre teoremele populare ( PDF ), în Comunicări ale ACM , vol. 23, n. 7, 1980, pp. 379–389, DOI : 10.1145 / 358886.358892 .
^ Z. Ammarguellat, Un algoritm de normalizare a fluxului de control și complexitatea acestuia , în IEEE Transactions on Software Engineering , vol. 18, nr. 3, 1992, pp. 237-251, DOI : 10.1109 / 32.126773 .

linkuri externe

( RO ) Teorema Böhm - Jacopini este falsă, propozițional ( PDF ), pe cs.cornell.edu .

Portal IT

Portalul de matematică

[1] C. Bohm și G. Jacopini, Diagramele de flux, mașini și limbi Turing cu numai două reguli de formare ( PDF ), în Comunicări ale ACM , vol. 9, nr. 5, mai 1966, pp. 366–371, DOI : 10.1145 / 355592.365646 . Adus la 5 august 2015.

[2] În această lucrare, diagramele de flux sunt introduse prin metoda ostensivă; acest lucru se face pentru a evita definițiile care cu siguranță nu ar fi de mare folos. În prima parte (scrisă de G. Jacopini), sunt studiate metodele de normalizare a diagramelor, care permit descompunerea lor în diagrame de bază de trei tipuri (primul rezultat) sau de două tipuri (al doilea rezultat). În a doua parte a lucrării (de C. Böhm), sunt raportate unele rezultate ale unei lucrări anterioare și rezultatele primei părți a lucrării sunt apoi utilizate pentru a demonstra că fiecare mașină Turing este reductibilă sau într-o sensul determinat este echivalent cu un program scris într-un limbaj care admite ca reguli de formare doar compoziția și iterația.

[3] David Harel , Despre teoremele populare ( PDF ), în Comunicări ale ACM , vol. 23, n. 7, 1980, pp. 379–389, DOI : 10.1145 / 358886.358892 .

[4] Z. Ammarguellat, Un algoritm de normalizare a fluxului de control și complexitatea acestuia , în IEEE Transactions on Software Engineering , vol. 18, nr. 3, 1992, pp. 237-251, DOI : 10.1109 / 32.126773 .

[1]

[2]

[3]

[4]