Teorema del programa estructurat

De Viquip??dia

El teorema del programa estructurat ??s un resultat de la teoria de llenguatges de programaci??. Aquest teorema estableix que tota funci?? computable pot ser implementada per un llenguatge de programaci?? que combini subrutines de nom??s 3 tipus. Aquestes 3 formes tamb?? anomenades estructures de control s??n:

Executar una subrutina i despr??s un altre (estructures de seq????ncia)
Executar una subrutina seleccionada d'entre 2 rutines possibles depenent d'un valor boolea (estructures de selecci?? com IF-THEN-ELSE)
Executar una subrutina durant el temps que una variable booleana sigui certa (estructures d'iteraci??, cicle o bucle)

Aquest teorema demostra que la instrucci?? GOTO no ??s estrictament necess??ria i que per a tot programa existeix un programa equivalent que no utilitza aquesta instrucci??.

El experts en computaci?? acrediten aquest teorema a un article escrit per Corrado B??hm i Giuseppe Jacopini. Tot i aix??, David Harel va rastrejar els or??gens d'aquest teorema fins arribar a la descripci?? de 1946 de la arquitectura de Von Neumann i el teorema formal de Kleene.

[edita] Enlla??os externs

Ashcroft, Edward, and Zohar Manna (1971). ??The translation of go to programs to 'while' programs??. Proceedings of IFIP Congress.
Bohm, Corrado, and Giuseppe Jacopini (May 1966). ??Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules??. Communications of the ACM 9 (5).
Harel, David (1980). ??On Folk Theorems??. Communications of the ACM 23.
Dijkstra, Edsger (1968). ??Go To Statement Considered Harmful??. Communications of the ACM 3 http://www.acm.org/classics/oct95/.