Teorema del programa estructurado

Teorema del programa estructurado

El teorema del programa estructurado es un resultado en la teoría de lenguajes de programación. Establece que toda función computable puede ser implementada en un lenguaje de programación que combine sólo tres estructuras lógicas. Esas tres formas (también llamadas estructuras de control) específicamente son:

  1. Secuencia: ejecución de una instrucción tras otra.
  2. Selección: ejecución de una de dos instrucciones (o conjuntos), según el valor de una variable booleana.
  3. Iteración: ejecución de una instrucción (o conjunto) mientras una variable booleana sea 'verdadera'. Esta estructura lógica también se conoce como ciclo o bucle.

Este teorema demuestra que la instrucción GOTO no es estrictamente necesaria y que para todo programa que la utilice existe otro equivalente que no hace uso de dicha instrucción.

Los científicos de la computación usualmente acreditan el teorema a un artículo de 1966 escrito por Corrado Böhm y Giuseppe Jacopini. Sin embargo, David Harel rastreó sus orígenes hasta la descripción de 1946 de la arquitectura de von Neumann y el teorema de la forma normal de Kleene.

La demostración de Böhm-Jacopini describe cómo construir diagramas de flujo estructurados a partir de cualquier digrama de flujo, usando los bits de una variable entera extra para dar seguimiento a la información que el programa original representa mediante puntos de entrada en el código. Esta construcción estuvo basada en el lenguaje de programación P′′ de Böhm. La demostración de Böhm-Jacopini no esclareció la cuestión sobre cuándo convendría usar programación estructurada para el desarrollo de software, en parte porque la construcción ofuscaba el código del programa en lugar de mejorarlo. Por otro lado, fue el punto de partida para iniciar el debate. Edsger Dijkstra escribió una importante carta titulada "La sentencia Go To considerada dañina" en el año 1968. Posteriores estudios agregaron aproximaciones más prácticas a la demostración de Böhm-Jacopini, que mantenían o mejoraban la claridad del programa original.[1]

Referencias

Enlaces externos

  • 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/. 

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Control del bucle while do — Saltar a navegación, búsqueda Controla el bucle while o bucle mientras es una estructura de la mayoría de los lenguajes de programación estructurados cuyo propósito es repetir un bloque de código mientras una condición se mantenga verdadera.… …   Wikipedia Español

  • Programación estructurada — Saltar a navegación, búsqueda La programación estructurada es una forma de escribir programas de ordenador (programación de computadora) de forma clara. Para ello utiliza únicamente tres estructuras: secuencia, selección e iteración; siendo… …   Wikipedia Español

  • Estructuras de control — En lenguajes de programación, las estructuras de control permiten modificar el flujo de ejecución de las instrucciones de un programa. Con las estructuras de control se puede: De acuerdo a una condición, ejecutar un grupo u otro de sentencias (If …   Wikipedia Español

  • GOTO — o GO TO (ir a en inglés) es una instrucción muy común en los lenguajes de programación con el objetivo de controlar el flujo del programa. El efecto de su versión más simple es transferir sin condiciones la ejecución del programa a la etiqueta o… …   Wikipedia Español

  • P′′ — Información general Paradigma Esotérico Apareció en 1964 Diseñado por Corrado Böhm Implementaciones …   Wikipedia Español

  • Bucle infinito — en programación es aquel ciclo que se repite de forma indefinida ya que su condición para finalizar nunca se cumple. Por definición un bucle debe contener condiciones que establezcan cuándo empieza y cuándo acaba, de manera que, mientras las… …   Wikipedia Español

  • Bucle for — Saltar a navegación, búsqueda El bucle for o ciclo for es una estructura de control en la que se puede indicar el número máximo de iteraciones. Está disponible en casi todos los lenguajes de programación imperativos. Contenido 1 Elementos del… …   Wikipedia Español

  • Bucle (programación) — Un bucle o ciclo, en programación, es una sentencia que se realiza repetidas veces a un trozo aislado de código, hasta que la condición asignada a dicho bucle deje de cumplirse. Generalmente,un bucle es utilizado para hacer una acción repetida… …   Wikipedia Español

  • Sistema — (Del gr. systema.) ► sustantivo masculino 1 Conjunto ordenado de normas o procedimientos que contribuyen a un fin o con que funciona o se hace funcionar una cosa: ■ sistema político; sistema educativo. SINÓNIMO modelo norma 2 Conjunto organizado… …   Enciclopedia Universal

  • Simulación — es la experimentación con un modelo de una hipótesis o un conjunto de hipótesis de trabajo. Thomas T. Goldsmith Jr. y Estle Ray Mann la define así: Simulación es una técnica numérica para conducir experimentos en una computadora digital. Estos… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”