El Teorema De Böhm-Jacopini

El teorema de Böhm-Jacopini

El teorema de Böhm-Jacopini es un enunciado que data de los años 60, en el que se prueba formalmente que cualquier algoritmo puede prescindir desaltos incondicionales. Se trata de consideraciones del pasado, que hoy en día no tienen utilidad directa aunque su importancia histórica es indiscutible.

A finales de los años 60 se inició una pequeña revolución en el mundo de la programación que daría paso a la programación estructurada.

En aquella época, parece ser que se alzaron muchas voces en contra de la que hoy conocemos como "programación desestructurada". Por lo visto, cada uno programaba como buenamente podía, sin demasiado orden ni criterio, y principalmente, la programación estaba llena de saltos incondicionales (tipo goto) que hacían muy muy difícil sacar conclusiones acerca de los algoritmos, como por ejemplo, simplemente saber si funcionaban correctamente. Una de esas voces, por ejemplo, fue Edsger Dijkstra, que con su conocido artículo del 68 GoTo Statement Considered Harmful (La sentencia GoTo se considera dañina) empezaba a poner en evidencia los problemas que estaban surgiendo, a pesar de que él decía que no era su intención inicial.

En el principio de todo aquello, que culminó con la programación estructurada que nos ha llegado hasta hoy parece ser que se dio importancia clave a la publicación en 1966 del conocido como teorema de la estructura o de Böhm-Jacopini en honor de Corrado Böhm y Giuseppe Jacopini.

Básicamente, este teorema nos dice que:

Todo algoritmo propio puede ser expresado en términos de sólo tres tipos de estructura:

secuencial (es decir, poner instrucciones en orden, una detrás de otra, y que sean ejecutadas en ese orden)

condicional (es decir, hacer una cosa en función de una concidición -con estructuras como if, o if/else o switch)

repetitiva (es decir, hacer una cosa varias veces, con bucles)

Se define como algoritmo propio aquel que nos da unas ciertas garantías de calidad en su construcción. El teorema viene a decir que todo algoritmo bien construido se puede expresar siempre sólo con bloques secuenciales de instrucciones, condiciones y bucles, sin necesidad de recurrir a saltos incondicionales.

Edsger Dijkstra (1930-2002)

Contribuyó a la demostración formal de programas y a la teoría de grafos. También se le atribuye la invención del semáforo como mecanismo de exclusión mutua.

Dijkstra ha pasado a la historia probablemente por el conocido algoritmo que lleva su nombre, referente a la obtención de árboles de peso mínimo.

No obstante, las contribuciones de Dijskrta a la informática son muchas y variadas.

Se le considera uno de los promotores de la programación estructurada, debido a sus artículos e intervenciones en defensa de las estructuras y contra el salto incondicional (Go To Statement Considered Harmful).

También contribuyó en las teorías de demostración formal de algoritmos.

En cuanto a los sistemas operativos, se le considera el inventor del semáforo y contribuyó al desarrollo de los monitores, mecanismos utilizados por los sistemas operativos para gestionar el acceso concurrente a los recursos por parte de los procesos.

Niklaus Wirth

Un ingeniero de nacionalidad suiza y premio Turing en 1984 que ejerció de ingeniero jefe en el desarrollo de nada más y nada menos que 8 lenguajes de programación además de desarrollar algunos textos fundamentales en la enseñanza de la programación.

Niklaus Wirth nació el 15 de febrero de 1934 en Winterthur, en el cantón de Zúrich (Suiza) que en 1959 terminó sus estudios universitarios obteniendo el título de Ingeniero en Electrónica por el Instituto Federal de Tecnología de Suiza (ETHZ). Al año siguiente, Wirth marchó a Canadá y obtuvo un Master of Science en la Universidad de Laval y en 1963 obtuvo el Doctorado en la prestigiosa Universidad de California - Berkeley desde donde saltaría a la Universidad de Stanford para impartir clases como profesor auxiliar hasta volver como profesor a la Universidad de Zúrich y, en 1968, pasar a impartir clase al Instituto Federal de Tecnología de Suiza, institución a la que permanecería adscrito hasta su jubilación como docente en 1999.

Tras acceder al ETH y obtener una plaza de profesor, Wirth se tomaría 2 años sabáticos (el primero en 1976 y el segundo en 1984) para marchar de nuevo a Estados Unidos y entrar en una las mayores incubadoras de ideas tecnológicas del mundo, el prestigioso Xerox PARC de Palo Alto (California).

Con este curriculum académico tan impresionante y dos estancias en el prestigioso Xerox PARC, Niklaus Wirth se convirtió en un afamado profesor de universidad que lideró proyectos de diseño de lenguajes de programación, compiladores, sistemas operativos y sistemas hardware en los que destacaba una seña indiscutible: la búsqueda de la simplicidad, un factor que se plasmó en muchos de sus trabajos y libros que se utilizan en para enseñar programación hoy en día, como por ejemplo "Algoritmos + Estructuras de datos = Programas" (1975) o "Desarrollo de un programa por refinamiento sucesivo" (1971).

En nuestra profesión, precisión y perfección no son un lujo prescindible, son una simple necesidad

En el campo de los lenguajes de programación, Wirth ejerció de jefe de diseño de múltiples lenguajes de programación: Euler, ALGOL W, Pascal, Modula, Modula-2 , Oberon, Oberon 2, Oberon-07.

Además de recibir el prestigioso premio Turing en 1984, Niklaus Wirth ha sido galardonado también con los siguientes premios.

Emanuel R. Piore Award or achievement in the field of Information Processing contributing to the advancement of science and the bettermentof society del IEEE (1983)

Computer Pioneer Award del IEEE (1987)

Miembro honorífico de la Academia Nacional de Ingeniería de Estados Unidos (1994)

En el año 1999, Niklaus Wirth se jubiló como Catedrático del Insituto Federal de Tecnología de Suiza (ETHZ) pero sigue en activo, por ejemplo, trabajando en Oberon-07.

Diagramas Nassi-Shneiderman

Un diagrama Nassi-Shneiderman es una representación gráfica de un algoritmo para programación estructurada. Desarrollados en 1972 por Isaac Nassi y Ben Shneiderman, estos diagramas también son conocidos como estructogramas debido a que muestran las estructuras de un programa.

Siguiendo un diseño de arriba a abajo, el problema en cuestión es reducido en subproblemas cada vez menores, hasta que sólo comandos y estructuras de control permanecen. Los diagramas Nassi-Shneiderman reflejan esta descomposición de una forma clara y simple, usando cajas anidadas para representar subproblemas.

Comandos

Es sólo eso, un comando. Hay tres tipos de ellos, todos representados por un rectángulo con una expresión en su interior:

Comando normal: Cuando usted asigna un valor a una variable, como c = a + b ó voto = "Juánita Pérez". Por favor, note que el signo igual (=) es usado para asignación, si usted desea comparar algo, úselo dos veces, ==. Usted podría también no asignar un valor a una variable y sólo describir una acción, como "agregue azúcar al té".

Comando leer: Úselo cuando necesite que el usuario ingrese algo como un número o un texto. Estos comandos asignan el valor que el usuario ingresa a una variable. Por ejemplo, Leer x (Read x en inglés), luego de su ejecución la variable x contendrá el valor entregado por el usuario.

Comando escribir: Simplemente muestra el valor de una variable en pantalla al usuario.

Iteraciones

A veces se necesita repetir ciertas acciones, para esto existen las iteraciones o loops y existen dos tipos distintos de ellas:

Mientras hacer: Hace y repite ciertas operaciones mientras una condición es verdadera, si en algún momento es falsa, avanzará a la próxima operación. Siempre revisa la condiciónantes de ejecutar las operaciones en su interior. Un ejemplo no muy ambientalista puede ser: Mientras hayan árboles en el bosque, cortar uno, llevarlo al aserradero. Esto sería representado de la siguiente forma:

Como puede apreciar esta iteración contiene solo dos comandos normales, puede sin embargo, contener cualquier operación sin limitaciones de combinación o cantidad.

Hacer Mientras: Es similar a mientras hacer, pero la condición es revisada después que las operaciones interiores son realizadas. De esta forma iterará mientras la condición sea verdadera. Imagine por un momento que usted vuela a una isla tropical, usted ya se encuentra a bordo del avión y empieza a buscar su asiento, esta situación se puede representar con el siguiente algoritmo:

Primero usted lee el número de su asiento en su ticket, después se mueve y lee el número del asiento que tiene en frente, luego repite estas acciones mientras no encuentre el asiento que le corresponde.

Decisiones

Si existen dos (o más) formas de hacer algo, o hablando de forma más general, usted necesita estar seguro que una cierta condición se cumple para tomar diferentes acciones

...