Algoritmos

El Correcto y Completo Desarrollo de un Algoritmo.
por M. en C. Eduardo René Rodríguez Ávila. Sección de Estudios de Posgrado e Investigación UPIICSA
A Patricia Prieto Corona, por permitirme compartir esta clase con ella.

Presentación.
“En el Gran Templo de Benares, bajo el domo que marca el centro del mundo, descansa un plato de bronce en el que están fijas tres agujas de diamante, cadauna de un cúbito de largo y tan delgadas como el cuerpo de una abeja. En una de estas agujas Dios colocó sesenta y cuatro discos de oro puro, el disco más largo descansa sobre el plato y sobre éste está uno más pequeño y así sucesivamente hasta la punta. Esta es la Torre de Brahma. Día y noche, incesantemente, los sacerdotes transfieren los discos de una aguja a otra, de acuerdo a fijas e inmutablesleyes que requieren que el sacerdote en turno no mueva mas que un disco a la vez y que el disco se coloque en un aguja de tal forma que no haya un disco más pequeño bajo éste. Cuando los sesenta y cuatro discos hayan sido transferidos de la aguja donde Dios los colocó a una de las otras, los brahmanes se convertirán en polvo, y con un trueno el mundo se desvanecerá.” Edouard Lucas, 1883. Nadiesabe si la leyenda anterior es verdadera o no, pero ésta inspiró al francés Edouard Lucas a desarrollar el conocido juego “Las Torres de Hanoi”. Esta historia será el vehículo que nos introducirá en uno de los más interesantes y apasionantes temas de la teoría de la computación: el desarrollo de algoritmos.

Los algoritmos y su historia.
Los algoritmos no son sólo una curiosidad académica uobjeto de estudio de una ciencia. Son la base de todo proceso metódico, formal o informal, y los encontramos por todas partes con múltiples nombres: receta, proceso, método, técnica, procedimiento, fórmula, rutina, conjuro. Un diccionario común [1] [2] [3] describirá como algoritmo al conjunto de símbolos y procedimientos usados en la realización de un cálculo. Descripciones similares se encuentranincluso en los diccionarios especializados [4] [5] El desarrollo de la informática y computación han hecho que el término adquiera cierto nivel de cotidianidad, sin que eso implique la pérdida de la rigurosidad requerida para dar a una serie de pasos el apelativo de algoritmo. Para muchos será una palabra más, producto de nuestra era tecnológica, pero su origen se remonta muy atrás en el tiempo. Unode los más grandes matemáticos árabes del siglo IX de nuestra era, Abu ‘Abd Allah Muhhamad ibn Musa al-Khwarizmi (literalmente: Padre de Abdullah, Mohamed, hijo de Moisés,

nativo de Khwarizm hoy Khiwa) con su obra “Kitab al-jabr wa’l-muqabala” (Reglas de Ecuaciones y Restauración), ayudó a difundir las matemáticas árabes por el mundo occidental a tal grado que del título de su obra se hadesprendido el término álgebra (al-jabr). Con el paso del tiempo y por defectos de pronunciación, su nombre se difundió simplemente como Al-Juarismi y de éste los términos guarismo y algorismo (usados para referirse a cualquier método de cómputo usando la notación arábiga de numeración). El término algorismo también fue corrompido en su pronunciación hasta derivar uno más difundido en latín comoalgoritmus, empleado desde el siglo XVII por los matemáticos para referirse a procedimientos de cálculo. Finalmente, la palabra que conocemos no apareció en un diccionario sino hasta la edición de 1957 del “Webster´s New World Dictionary”. Las matemáticas son, en cierto sentido, una colección de algoritmos. La aparición de las computadoras, propiciada por la necesidad y propósito de realizar cálculos yconteos, obligó a mucha gente a hablar de métodos y procedimientos para describir los programas que para ellas se elaboraban; programas que eran en sí la representación de un procedimiento matemático, de un algoritmo. La escritura de programas es entonces la elaboración o implementación de algoritmos, aunque claro no podemos afirmar que hacer matemáticas sea sólo hacer programas. Al final,...