Hispanopedia Wiki
Articulo de referencia

Teorema del programa estructurado

En la teoría de los lenguajes de programación , el teorema del programa estructurado , generalmente llamado teorema de Böhm-Jacopini , [ 1 ] [ 2 ] establece que una clase de gra...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de los lenguajes de programación , el teorema del programa estructurado , generalmente llamado teorema de Böhm-Jacopini , [ 1 ] [ 2 ] establece que una clase de grafos de flujo de control (históricamente llamados diagramas de flujo en este contexto) pueden calcular cualquier función computable utilizando solo las siguientes tres estructuras de control para combinar subprogramas ( instrucciones y bloques ): [ 3 ]

Secuencia
Ejecutar un subprograma y luego otro subprograma.
Selección
Ejecutar uno de dos subprogramas según el valor de una expresión booleana .
Iteración
Ejecutar repetidamente un subprograma mientras una expresión booleana sea verdadera.

En la siguiente sección se ofrecen definiciones más precisas.

El diagrama estructurado sujeto a estas restricciones, en particular la restricción de bucle que implica una única salida (como se describe más adelante en este artículo), puede, sin embargo, utilizar variables adicionales en forma de bits (almacenadas en una variable entera adicional en la prueba original) para realizar un seguimiento de la información que el programa original representa mediante la ubicación del programa. La construcción se basó en el lenguaje de programación P′′ de Böhm .

El teorema constituye la base de la programación estructurada , un paradigma de programación que prescinde de la instrucción goto y utiliza exclusivamente otras semánticas de control para la selección y la iteración.

Los flujos de control del teorema del programa estructurado (secuencia, selección y repetición) se representan mediante diagramas NS (azul) y diagramas de flujo (verde).

Origen y variantes

En 1964, Corrado Böhm definió un lenguaje de programación Turing-completo simple ( P′′ ), basado en secuencias e iteración . [ 4 ] En un artículo posterior, Böhm y Giuseppe Jacopini reiteraron este resultado. [ 5 ]

El teorema del programa estructurado se atribuye generalmente [ 6 ] a ese artículo de 1966. Harel escribió en 1980 que el artículo de Böhm-Jacopini gozaba de "popularidad universal" [ 6 ] , particularmente entre los defensores de la programación estructurada. Harel también señaló que "debido a su estilo bastante técnico, [el artículo de Böhm-Jacopini de 1966] aparentemente se cita con más frecuencia que se lee en detalle" [ 6 ] y, después de revisar una gran cantidad de artículos publicados hasta 1980, Harel argumentó que el contenido de la demostración de Böhm-Jacopini solía ser malinterpretado como un teorema popular que esencialmente contiene un resultado más simple, un resultado que a su vez puede rastrearse hasta el inicio de la teoría de la computación moderna en los artículos de von Neumann [ 7 ] y Kleene [ 8 ] .

Harel también escribe [ 6 ] que el nombre más genérico fue propuesto por HD Mills como "El teorema de la estructura" a principios de la década de 1970. [ 9 ]

La evolución del teorema fue la siguiente.

1. Böhm 1964 (Creación de programas / Computación)

Resultado
Cada función recursiva parcial puede ser calculada por un programa [ 10 ] utilizando únicamente secuencia e iteración . [ 4 ]
Notas
Este resultado se centra en la generación de programas . No se requiere selección : el comportamiento condicional se codifica mediante bucles. P′′ evita el flujo de control no estructurado a través del diseño del lenguaje, imponiendo la estructura en la fuente. Böhm reitera sus resultados en la parte 2 de Böhm-Jacopini (1966). [ 5 ]

2. Böhm-Jacopini 1966 (Transformación del programa)

Resultado
Todo diagrama de flujo ( grafo de flujo de control , CFG) puede transformarse en un programa estructurado utilizando únicamente secuencias e iteraciones . [ 5 ]
Notas
Esta versión del teorema se centra en la transformación de programas . Es relevante principalmente para la optimización de compiladores , más que para las decisiones de diseño de software. En la parte 1 de Böhm–Jacopini (1966), Jacopini demuestra que cualquier [ 11 ] grafo de flujo de control (CFG) puede reescribirse como un grafo estructurado, [ 12 ] usando solo selección , secuencia e iteración , mientras se conserva la estructura del programa original. [ 3 ] En la parte 2, Böhm muestra que la selección no es estrictamente necesaria: cualquier CFG puede transformarse usando solo secuencia e iteración .
La demostración de Jacopini procede por inducción sobre la estructura del diagrama de flujo. [ 6 ] Debido a que empleaba la coincidencia de patrones en grafos , la demostración no era realmente práctica como algoritmo de transformación de programas , y por lo tanto abrió la puerta a investigaciones adicionales en esta dirección. [ 13 ]

3. Teorema popular (Transformación mínima de bucle)

Resultado
Cada diagrama de flujo es equivalente a un programa while con una ocurrencia de while-do , siempre que se permitan variables adicionales. [ 14 ]
Notas
Esta versión del teorema simplifica la transformación de Böhm-Jacopini, reduciendo toda la iteración a un único bucle. La selección se reintroduce para mayor claridad, pero teóricamente es opcional.
El teorema popular reemplaza el flujo de control del programa original con un único whilebucle global que simula un contador de programa que recorre todas las etiquetas posibles (cajas del diagrama de flujo) en el programa no estructurado original. [ 3 ] Harel rastreó el origen de este teorema popular hasta dos artículos que marcan el comienzo de la computación. Uno es la descripción de la arquitectura de von Neumann de 1946 , que explica cómo funciona un contador de programa en términos de un bucle while. Harel señala que el único bucle utilizado por la versión popular del teorema de programación estructurada básicamente solo proporciona semántica operacional para la ejecución de un diagrama de flujo en una computadora von Neumann. [ 8 ] Otra fuente, aún más antigua, de la que Harel rastreó la versión popular del teorema es el teorema de la forma normal de Stephen Kleene de 1936. [ 8 ]
p := 1 mientras p > 0 hacer si p = 1 entonces realizar el paso 1 del diagrama de flujo p := número de paso sucesor resultante del paso 1 del diagrama de flujo ( 0 si no hay sucesor ) fin si si p = 2 entonces realizar el paso 2 del diagrama de flujo p := número de paso sucesor resultante del paso 2 del diagrama de flujo ( 0 si no hay sucesor ) fin si ... si p = n entonces realizar el paso n del diagrama de flujo p := número de paso sucesor resultante del paso n del diagrama de flujo ( 0 si no hay sucesor ) fin si fin mientras
Donald Knuth criticó esta forma de demostración, que da como resultado un pseudocódigo como el anterior, señalando que la estructura del programa original se pierde por completo en esta transformación. [ 15 ] De manera similar, Bruce Ian Mills escribió sobre este enfoque que «El espíritu de la estructura de bloques es un estilo, no un lenguaje. Al simular una máquina de von Neumann, podemos producir el comportamiento de cualquier código espagueti dentro de los límites de un lenguaje con estructura de bloques. Esto no impide que sea espagueti». [ 16 ]

4. Declaración sobre los libros de texto modernos

La programación estructurada se suele denominar

Resultado
Toda función recursiva parcial puede ser calculada por un programa estructurado utilizando secuencias ( selección ,) e iteración ; además, con codificaciones adecuadas del estado de control, basta con un solo bucle. [ 17 ]while
Notas
Esto combina:
  1. Böhm (1964) – quien demostró que para cada función recursiva parcial existe un programa (estructurado) P′′ que la calcula – estableciendo la existencia de un algoritmo en lugar de reescribir uno existente; [ 18 ]
  2. Böhm–Jacopini (1966) – que muestra que cualquier programa o diagrama de flujo existente puede reescribirse utilizando solo selección , secuencia e iteración (siendo la selección redundante); [ 5 ]
  3. El resultado del folclore de un solo bucle, que demuestra que la iteración se puede reducir a un solo bucle mediante la codificación explícita del estado de control.

5. Versión reversible

El Teorema del Programa Estructurado Reversible [ 19 ] es un concepto importante en el campo de la computación reversible . Postula que cualquier cálculo que se pueda realizar mediante un programa reversible también se puede lograr mediante un programa reversible utilizando únicamente una combinación estructurada de construcciones de flujo de control, como secuencias, selecciones e iteraciones. Cualquier cálculo que se pueda lograr mediante un programa tradicional irreversible también se puede lograr mediante un programa reversible, pero con la restricción adicional de que cada paso debe ser reversible y generar alguna salida adicional. [ 20 ] Además, cualquier programa reversible no estructurado también se puede realizar mediante un programa reversible estructurado con una sola iteración y sin ninguna salida adicional. Este teorema sienta las bases para la construcción de algoritmos reversibles dentro de un marco de programación estructurada.

Para el Teorema del Programa Estructurado, se conocen métodos de demostración tanto locales [ 5 ] como globales [ 21 ] . Sin embargo, para su versión reversible, si bien se reconoce un método de demostración global, aún no se conoce un enfoque local similar al empleado por Böhm y Jacopini [ 5 ] . Esta distinción pone de manifiesto los desafíos y matices que implica establecer los fundamentos de la computación reversible en comparación con los paradigmas de computación tradicionales.

Implicaciones y mejoras

La demostración de Böhm-Jacopini no resolvió la cuestión de si adoptar la programación estructurada para el desarrollo de software, en parte porque era más probable que la construcción oscureciera un programa que lo mejorara. Por el contrario, marcó el inicio del debate. La famosa carta de Edsger Dijkstra , «La instrucción Go To se considera perjudicial» , se publicó en 1968. [ 22 ]

Algunos académicos adoptaron un enfoque purista respecto al resultado de Böhm-Jacopini y argumentaron que incluso instrucciones como ` breakand` returndesde el medio de los bucles son una mala práctica, ya que no son necesarias en la demostración de Böhm-Jacopini; por lo tanto, abogaron por que todos los bucles tuvieran un único punto de salida. Este enfoque purista se materializa en el lenguaje de programación Pascal (diseñado entre 1968 y 1969), que hasta mediados de la década de 1990 fue la herramienta preferida para impartir clases introductorias de programación en el ámbito académico. [ 23 ]

Edward Yourdon señala que en la década de 1970 incluso existía una oposición filosófica a la transformación de programas no estructurados en estructurados mediante métodos automatizados, basada en el argumento de que era necesario pensar desde el principio como programadores estructurados. El contrapunto pragmático era que tales transformaciones beneficiaban a un gran número de programas existentes. [ 24 ] Entre las primeras propuestas para una transformación automatizada se encontraba un artículo de 1971 de Edward Ashcroft y Zohar Manna . [ 25 ]

La aplicación directa del teorema de Böhm-Jacopini puede resultar en la introducción de variables locales adicionales en el diagrama estructurado, y también puede resultar en cierta duplicación de código . [ 26 ] Este último problema se denomina problema del bucle y medio en este contexto. [ 27 ] Pascal se ve afectado por ambos problemas, y según estudios empíricos citados por Eric S. Roberts , los estudiantes de programación tuvieron dificultades para formular soluciones correctas en Pascal para varios problemas simples, incluyendo escribir una función para buscar un elemento en un arreglo. Un estudio de 1980 de Henry Shapiro citado por Roberts encontró que utilizando solo las estructuras de control proporcionadas por Pascal, la solución correcta fue dada por solo el 20% de los sujetos, mientras que ningún sujeto escribió código incorrecto para este problema si se le permitió escribir un retorno desde el medio de un bucle. [ 23 ]

En 1973, S. Rao Kosaraju demostró que es posible evitar la adición de variables adicionales en la programación estructurada, siempre que se permitan saltos de bucles de múltiples niveles y profundidad arbitraria. [ 1 ] [ 29 ] Además, Kosaraju demostró que existe una jerarquía estricta de programas, actualmente llamada jerarquía de Kosaraju , en la que para cada entero n , existe un programa que contiene un salto de bucle de múltiples niveles de profundidad n que no puede reescribirse como un programa con saltos de bucles de múltiples niveles de profundidad menor que n (sin introducir variables adicionales). [ 1 ] Kosaraju cita la construcción de salto de bucle de múltiples niveles en el lenguaje de programación BLISS . Los saltos de bucles de múltiples niveles, en forma de palabra clave, se introdujeron en la versión BLISS-11 de dicho lenguaje; el BLISS original solo tenía saltos de un solo nivel. La familia de lenguajes BLISS no proporcionaba un goto sin restricciones. El lenguaje de programación Java seguiría posteriormente este enfoque también. [ 30 ]leave label

Un resultado más sencillo del artículo de Kosaraju es que un programa es reducible a un programa estructurado (sin añadir variables) si y solo si no contiene un bucle con dos salidas distintas. Kosaraju definió la reducibilidad, en términos generales, como el cálculo de la misma función y el uso de las mismas "acciones primitivas" y predicados que el programa original, pero posiblemente utilizando diferentes estructuras de flujo de control. (Esta es una noción de reducibilidad más restringida que la que utilizó Böhm-Jacopini). Inspirado por este resultado, en la sección VI de su artículo, muy citado, que introdujo la noción de complejidad ciclomática , Thomas J. McCabe describió un análogo del teorema de Kuratowski para los grafos de flujo de control (GFC) de programas no estructurados, es decir, los subgrafos mínimos que hacen que el GFC de un programa sea no estructurado. Estos subgrafos tienen una descripción muy buena en lenguaje natural. Son:

  1. bifurcación fuera de un bucle (que no sea la prueba del ciclo del bucle)
  2. ramificándose en un bucle
  3. ramificarse en una decisión (es decir, en una "rama" condicional)
  4. ramificarse a partir de una decisión

McCabe descubrió que estos cuatro grafos no son independientes cuando aparecen como subgrafos, lo que significa que una condición necesaria y suficiente para que un programa sea no estructurado es que su CFG tenga como subgrafo uno de cualquier subconjunto de tres de estos cuatro grafos. También descubrió que si un programa no estructurado contiene uno de estos cuatro subgrafos, debe contener otro distinto del conjunto de cuatro. Este último resultado ayuda a explicar cómo el flujo de control de un programa no estructurado se enreda en lo que popularmente se denomina "código espagueti". McCabe también ideó una medida numérica que, dado un programa arbitrario, cuantifica cuán alejado está del ideal de ser un programa estructurado; McCabe llamó a su medida complejidad esencial . [ 31 ] La caracterización de McCabe de los grafos prohibidos para la programación estructurada puede considerarse incompleta, al menos si se consideran las estructuras D de Dijkstra como los bloques de construcción. [ 32 ]

Hasta 1990, se propusieron varios métodos para eliminar las instrucciones goto de los programas existentes, conservando la mayor parte de su estructura. Los distintos enfoques para este problema también propusieron varias nociones de equivalencia, más estrictas que la simple equivalencia de Turing, para evitar resultados como el teorema popular mencionado anteriormente. La rigurosidad de la noción de equivalencia elegida determina el conjunto mínimo de estructuras de flujo de control necesarias. El artículo de Lyle Ramshaw publicado en JACM en 1988 revisa el campo hasta ese momento y propone su propio método. [ 33 ] El algoritmo de Ramshaw se utilizó, por ejemplo, en algunos descompiladores de Java porque el código de la máquina virtual de Javabreak tiene instrucciones de salto con destinos expresados ​​como desplazamientos, pero el lenguaje Java de alto nivel solo tiene instrucciones multinivel continue. [ 34 ] [ 35 ] [ 36 ] Ammarguellat (1992) propuso un método de transformación que vuelve a imponer una única salida. [ 13 ]

Aplicación a COBOL

En la década de 1980, el investigador de IBM Harlan Mills supervisó el desarrollo de la COBOL Structuring Facility , que aplicaba un algoritmo de estructuración al código COBOL . La transformación de Mills implicaba los siguientes pasos para cada procedimiento.

  1. Identifique los bloques básicos del procedimiento.
  2. Asigne una etiqueta única a la ruta de entrada de cada bloque y etiquete las rutas de salida de cada bloque con las etiquetas de las rutas de entrada a las que se conectan. Use 0 para el retorno del procedimiento y 1 para la ruta de entrada del procedimiento.
  3. Divide el procedimiento en sus bloques básicos.
  4. Para cada bloque que sea destino de una sola ruta de salida, vuelva a conectar ese bloque a esa ruta de salida.
  5. Declara una nueva variable en el procedimiento (llamada L para referencia).
  6. En cada ruta de salida no conectada restante, agregue una instrucción que establezca L al valor de la etiqueta en esa ruta.
  7. Combine los programas resultantes en una instrucción de selección que ejecute el programa con la etiqueta de ruta de entrada indicada por L.
  8. Construye un bucle que ejecute esta instrucción de selección mientras L no sea 0.
  9. Construye una secuencia que inicialice L a 1 y ejecute el bucle.

Esta construcción se puede mejorar convirtiendo algunos casos de la instrucción de selección en subprocedimientos.

Véase también

Notas y referencias

  1. 1 2 3 Kozen y Tseng 2008 .
  2. ↑ Universidad de Buffalo 2004 .
  3. ^ Barendregt 2019 , pág . 12. 
  4. 1 2 Böhm 1964 .
  5. ^ Böhm y Jacopini 1966 .​​​​
  6. 1 2 3 4 5 Harel 1980 , pág. 381.
  7. ^ Burks, Goldstine y von Neumann 1947 .
  8. 1 2 3 Harel 1980 , pág. 383.
  9. ↑ Mills 1972 .
  10. ↑ El lenguaje P′′ es Turing-completo y cumple con los requisitos. Brainfuck , una bifurcación de P′′, también está estructurado por diseño.
  11. ↑ Böhm-Jacopini no exigieron explícitamente que los "programas" fueran de entrada única y salida única , con todos los nodos accesibles, pero su demostración se basaba en esto. Mills (1972 , p. 32) explicitó estos dos requisitos.
  12. ↑ Una gramática libre de contexto de entrada única y salida única (SESE) está "estructurada" si cada subgrafo es SESE.
  13. 1 2 Ammarguellat 1992 .
  14. ↑ Harel 1980 , pág. 380.
  15. ↑ Knuth 1974 , pág. 274.
  16. ↑ Mills 2005 , pág. 279.
  17. ↑ Greibach 1975 , Capítulo 4. Programas estructurados.
  18. ↑ Böhm 1964 , pág. 191, Resultado principal de este artículo.
  19. ↑ Yokoyama, Axelsen y Glück 2016 .
  20. ↑ Bennett 1973 .
  21. ↑ Cooper 1967 .
  22. ↑ Dijkstra 1968 .
  23. 1 2 Roberts 1995 .
  24. ↑ Yourdon 1979 , págs. 49–50.
  25. ↑ Ashcroft y Manna 1971 .
  26. ↑ Watt y Findlay 2004 , pág. 228.
  27. ↑ Louden y Lambert 2011 , págs. 422–423.
  28. ↑ Kosaraju 1974 .
  29. ↑ Kosaraju 1973 , [ 28 ] citado por Knuth 1974 .
  30. ^ Brender 2002 , págs .
  31. ↑ El artículo original es McCabe 1976. Para una exposición secundaria, véase Jorgensen 2002 .
  32. ↑ Williams 1983 , págs. 274–275.
  33. ↑ Ramshaw 1988 .
  34. ↑ Nolan 2004 .
  35. ↑ Proebsting y Watterson 1997 .
  36. ^ Maruyama, Ogawa y Matsuoka 1999 .

Bibliografía

  • Ammarguellat, Z. (1992). "Un algoritmo de normalización del flujo de control y su complejidad". IEEE Transactions on Software Engineering . 18 (3): 237– 251. doi : 10.1109/32.126773 .
  • Ashcroft, Edward; Manna, Zohar (1971). "La traducción de programas 'go to' a programas 'while'". Actas del Congreso IFIP .Republicado en Yourdon 1979 , págs.  51–61 .
  • Bennett, CH (noviembre de 1973). "Reversibilidad lógica de la computación". IBM Journal of Research and Development . 17 (6): 525– 532. doi : 10.1147/rd.176.0525 .
  • Böhm, Corrado (junio de 1962). "Machine a indirizzi, dotate di un numero minimo di istruzioni" . Rendiconti dell'Accademia Nazionale dei Lincei . Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII (en italiano). 32 : 923–930 .
  • Böhm, Corrado (1964). "Sobre una familia de máquinas de Turing y el lenguaje de programación relacionado" (PDF) . Boletín ICC . 3 : 185–194 .
  • Böhm, Corrado ; Jacopini, Giuseppe [en italiano] (junio de 1962). "Nuevas técnicas de programación simplificada de síntesis de máquinas universales de Turing" . Rendiconti dell'Accademia Nazionale dei Lincei . Classe di Scienze Fisiche, Matematiche e Naturali, Serie VIII (en italiano). 32 : 913-922 .
  • Brender, Ronald F. (2002). "El lenguaje de programación BLISS: una historia" (PDF) . Software: Practice and Experience . 32 (10): 955– 981. doi : 10.1002/spe.470 . S2CID 45466625 . 
  • Cooper, David C. (agosto de 1967). "La reducción de diagramas de flujo de Böhm y Jacopini" . Communications of the ACM . 10 (8): 463. doi : 10.1145/363534.363539 .
  • Dijkstra, Edsger (1968). "Ir a la declaración considerada perjudicial" . Communications of the ACM . 11 (3): 147– 148. doi : 10.1145/362929.362947 . S2CID 17469809 . Republicado en Yourdon 1979 , págs.  29-33 .
  • Greibach, Sheila A. (1975). Teoría de las estructuras de programas: esquemas, semántica, verificación . Lecture Notes in Computer Science. Vol.  36. Berlín, Heidelberg, Nueva York: Springer-Verlag. ISBN 978-3-540-07415-1. LCCN 75031780 . 
  • Harel, David (1980). "Sobre los teoremas populares" . Communications of the ACM . 23 (7): 379– 389. doi : 10.1145/358886.358892 . S2CID 16300625 . 
  • Jorgensen, Paul C. (2002). Pruebas de software: Un enfoque artesanal (2.ª  ed.). CRC Press. págs. 150–153 . ISBN  978-0-8493-0809-3.
  • Knuth, Donald (1974). "Programación estructurada con instrucciones go to". Computing Surveys . 6 (4): 261– 301. CiteSeerX 10.1.1.103.6084 . doi : 10.1145/356635.356640 . S2CID 207630080 .  Republicado en Yourdon 1979 , págs.  259–321
  • Kosaraju, S. Rao (mayo de 1973). "Análisis de programas estructurados". Actas del Quinto Simposio Anual de la ACM sobre Teoría de la Computación . ACM. págs. 240–252 . , "Análisis de programas estructurados". Journal of Computer and System Sciences . 9 (3): 232– 255. 1974 [1973]. doi : 10.1016/S0022-0000(74)80043-7 .
  • Kozen, Dexter ; Tseng, Wei-Lung Dustin (2008). "Matemáticas de la construcción de programas: el teorema de Böhm-Jacopini es falso, proposicionalmente" ( PDF) . MPC 2008. Lecture Notes in Computer Science. Vol.  5133. pp. 177–192 . CiteSeerX 10.1.1.218.9241 . doi : 10.1007/978-3-540-70594-9_11 . ISBN   978-3-540-70593-2.
  • Louden, Kenneth C.; Lambert, Kenneth A. (2011). Lenguajes de programación: Principios y prácticas (3.ª  ed.). Cengage Learning. ISBN 978-1-111-52941-3.
  • Maruyama, Fuyuhiko; Ogawa, Hirotaka; Matsuoka, Satoshi (1999). "Un algoritmo de descompilación eficaz para bytecodes de Java" (PDF) . www.openjit.org (en japonés) . Consultado el 12 de julio de 2025 .
  • McCabe, Thomas J. (diciembre de 1976). "Una medida de complejidad" . IEEE Transactions on Software Engineering . SE-2 (4): 315–318 . doi : 10.1109/tse.1976.233837 . S2CID 9116234 . 
  • Mills, H. (1972). Fundamentos matemáticos para la programación estructurada (Informe técnico). Gaithersburg, MD: IBM Federal Systems Division. pág.  62.
  • Mills, Bruce Ian (2005). Introducción teórica a la programación . Springer. pág.  279. ISBN 978-1-84628-263-8.
  • Nolan, Godfrey (2004). Descompilación de Java . Apress. pág.  142. ISBN 978-1-4302-0739-9.
  • Proebsting, Todd A.; Watterson, Scott A. (1997). "Krakatoa: Descompilación en Java" (PDF) . usenix.org . Consultado el 12 de julio de 2025 .
  • Ramshaw, L. (1988). "Eliminar las instrucciones goto mientras se preserva la estructura del programa" . Journal of the ACM . 35 (4): 893– 920. doi : 10.1145/48014.48021 . S2CID 31001665 . 
  • Roberts, E. (1995). "Salidas de bucle y programación estructurada: reabriendo el debate" (PDF) . Boletín ACM SIGCSE . 27 (1): 268– 272. Archivado (PDF) del original el 25 de julio de 2014.
  • Universidad de Buffalo (22 de noviembre de 2004). "CSE 111, otoño de 2004, TEOREMA DE BOEHM-JACOPINI" . Universidad de Buffalo. Archivado del original el 22 de noviembre de 2004. Consultado el 12 de julio de 2025 .
  • Watt, David Anthony ; Findlay, William (2004). Conceptos de diseño de lenguajes de programación . John Wiley & Sons. ISBN 978-0-470-85320-7.
  • Williams, MH (1983). "Esquemas de diagramas de flujo y el problema de la nomenclatura". The Computer Journal . 26 (3): 270– 276. doi : 10.1093/comjnl/26.3.270 .
  • Yokoyama, Tetsuo; Axelsen, Holger Bock; Glück, Robert (enero de 2016). "Fundamentos de los lenguajes de diagramas de flujo reversibles" . Theoretical Computer Science . 611 : 87–115 . doi : 10.1016/j.tcs.2015.07.046 .
  • Yourdon, EN , ed. (1979). Clásicos en ingeniería de software . Nueva York, NY: Yourdon Press. pp.  xi, 424. ISBN 978-0-917072-14-7. LCCN 79-63449 . 

Lecturas adicionales

  • DeMillo, Richard A .; Eisenstat, Stanley C.; Lipton, Richard J. (enero de 1980). "Compromisos espacio-temporales en programación estructurada: un teorema de incrustación combinatoria mejorado" . Journal of the ACM . 27 (1): 123–127 . doi : 10.1145/322169.322180 . S2CID 15669719 . 
  • Devienne, Philippe; Lebègue, Patrick; Routier, Jean-Christophe; Würtz, Jörg (febrero de 1994). «Una cláusula binaria de Horn es suficiente». Actas del 11.º Simposio sobre Aspectos Teóricos de la Informática (STACS '94) . Lecture Notes in Computer Science. Vol.  775. pp. 21–32 . CiteSeerX 10.1.1.14.537 . doi : 10.1007/3-540-57785-8_128 . ISBN   978-3-540-57785-0.
Lecturas relacionadas
6 articulos
Teoría de lenguajes de programaciónTeoría de lenguajes de programaciónLa teoría de lenguajes de programación ( PLT ) es una rama de la informática que se ocupa del diseño, implementación, análisis, caracterización y c...Gráfico de flujo de controlGráfico de flujo de controlEn informática , un gráfico de flujo de control ( GFC ) es una representación , mediante notación gráfica , de todos los caminos que se pueden reco...Diagrama de flujoDiagrama de flujoUn diagrama de flujo es un tipo de diagrama que representa un flujo de trabajo o un proceso . Un diagrama de flujo también se puede definir como un...{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }Función computableLas funciones computables son los objetos básicos de estudio en la teoría de la computabilidad . Las funciones computables son el análogo formaliza...Flujo de controlFlujo de controlEn software , el flujo de control describe cómo progresa la ejecución de un comando al siguiente. En muchos contextos, como el código máquina y un ...Declaración (informática)Declaración (informática)En programación informática , una declaración es una unidad sintáctica de un lenguaje de programación imperativo que expresa alguna acción a realiz...