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

...