sábado, 14 de junio de 2008

Al-Khorezmi: Un Matemático Olvidado


Introducción.
Muchos se preguntarán quién es Al-Khorezmi. Posiblemente adivinen su origen árabe, pero Al-Khorezmi debiera ser tan conocido como Pitágoras o Euclides. Gracias a él, la matemática moderna usa el sistema numérico actual, proveniente de la India. Mas aún, las palabras guarismo (cifra, número) y algoritmo provienen de su nombre, que en árabe significa, "el de Khorezm" por su lugar de origen. Un algoritmo, según el diccionario de la Real Academia, es una secuencia o conjunto ordenado de operaciones o pasos que permite hallar la solución de un problema (otra acepción es un método y notación en las distintas formas del cálculo). Aunque los algoritmos datan de tiempos babilónicos y los griegos diseñaron algoritmos aún famosos (por ejemplo, el de Euclides para calcular el máximo común divisor de dos números), fue Al-Khorezmi el primero que diseñó algoritmos pensando en su eficiencia, en particular, para el cálculo de raíces de ecuaciones. La algoritmia es uno de los pilares fundamentales de la ciencia de la computación, ni siquiera soñada mil años atrás.

Hay muchas variantes para el nombre de Al-Khorezmi al usar el alfabeto latino, tales como al-Khwarizmi, Al-Khawarizmi, Al-Khawaritzmi o al-Khowarizmi. Hemos elegido usar la más simple, lo que no significa que es necesariamente la mejor.

Su vida.
Muhammad ibn Musa abu Djafar Al-Khorezmi nació alrededor del 780 DC (otros citan 800 DC) en Khorezm, al sur del Mar de Aral (hoy Khiva, Uzbekistán), que había sido conquistado 70 años antes por los árabes. Su nombre ya dice mucho, pues significa "Mohamed, hijo de Moisés, padre de Jafar, el de Khorezm". Su fama debió ser muy grande para que todo el mundo lo conociera por su lugar de origen. Hacia el 820, Al-Khorezmi fue llamado a Bagdad por el califa abasida Al-Mamun, segundo hijo de Harun ar-Rashid, por todos conocido gracias a las "Mil y unas Noches". Al-Mamun continuó el enriquecimiento de la ciencia árabe y de la Academia de Ciencias creada por su padre, llamada la Casa de la Sabiduría, lo que traería importantes consecuencias en el desarrollo de la ciencia en Europa, principalmente a través de España. Poco se sabe de su vida, pero realizó viajes a Afganistán, el sur de Rusia y Bizancio (hoy Turquía). Falleció en Bagdad hacia el 850 DC (también se menciona 840 DC).

Su Obra.
La mayoría de sus diez obras son conocidas en forma indirecta o por traducciones hechas más tarde al latín (muchas de ellas en Toledo) y de algunas sólo se conoce el título. Al-Khorezmi fue un recopilador de conocimiento de los griegos y de la India, principalmente matemáticas, pero también astronomía (incluyendo el calendario Judío), astrología, geografía e historia. Su trabajo más conocido y usado fueron sus Tablas Astronómicas, basadas en la astronomía india. Incluyen algoritmos para calcular fechas y las primeras tablas conocidas de las funciones trigonométricas seno y cotangente. Lo más increíble es que no usó los números negativos (que aún no se conocían), ni el sistema decimal ni fracciones, aunque sí el concepto del cero. Su Aritmética, traducida al latín como "Algoritmi de numero Indorum" introduce el sistema numérico indio (sólo conocido por los árabes unos 50 años antes) y los algoritmos para calcular con él. Finalmente tenemos el Algebra, una introducción compacta al cálculo, usando reglas para completar y reducir ecuaciones. Además de sistematizar la resolución de ecuaciones cuadráticas, también trata geometría, cálculos comerciales y de herencias. Quizás éste es el libro árabe más antiguo conocido y parte de su título "Kitab al-jabr wa'l-muqabala" da origen a la palabra álgebra. Aunque los historiadores no se han puesto de acuerdo en la mejor traducción del título, éste significa "El libro de restaurar e igualar" o "El arte de resolver ecuaciones".

Su impacto.
El trabajo de Al-Khorezmi permitió preservar y difundir el conocimiento de los griegos (con la notable excepción del trabajo de Diofanto) e indios, pilares de nuestra civilización. Rescató de los griegos la rigurosidad y de los indios la simplicidad (en vez de una larga demostración, usar un diagrama junto a la palabra "Mira"). Sus libros son intuitivos y prácticos y su principal contribución fue simplificar las matemáticas a un nivel entendible por no expertos. En particular muestran las ventajas de usar el sistema decimal indio, un atrevimiento para su época, dado lo tradicional de la cultura árabe. La exposición clara de cómo calcular de una manera sistemática a través de algoritmos diseñados para ser usados con algún tipo de dispositivo mecánico similar a un ábaco, más que con lápiz y papel, muestra la intuición y el poder de abstracción de Al-Khorezmi. Hasta se preocupaba de reducir el número de operaciones necesarias en cada cálculo. Por esta razón, aunque no haya sido él el inventor del primer algoritmo, merece que este concepto esté asociado a su nombre. Al-Khorezmi fue sin duda el primer pensador algorítmico.

Capítulo 1 - Conceptos Básicos: Definición de algoritmo.

Un algoritmo es un conjunto finito de instrucciones no ambiguas y efec­tivas que indican cómo resolver un problema, producen al menos una salida, reciben cero o más entradas y, para ejecutarse, necesitan una cantidad finita de recursos.


Una instrucción es no ambigua cuando la acción a ejecutar está perfecta­mente definida, por ejemplo, instrucciones del tipo:



x <-- log(0) ó x<-- (10 o 35)/3


no pueden formar parte de un algoritmo.


Una instrucción es efectiva cuando se puede ejecutar en un intervalo finito de tiempo, por ejemplo, las instrucciones



x <— 2 + 8, mensaje <— Une('Hola', 'Mundo')



son efectivas, mientras que



x <— cardinalidad(números naturales)




no lo es.



Si un conjunto de instrucciones tiene todas las características de un al­goritmo, excepto ser finito en tiempo se le denomina proceso computational. Los sistemas operativos son el mejor ejemplo de proceso computacional, pues están diseñados para ejecutar tareas mientras las haya pendientes, y cuando éstas se terminan, el sistema operativo entra en un estado de espera, hasta que llegan más, pero nunca termina.



Se asume que un problema tiene solución algorítmica si además de que el algoritmo existe, su tiempo de ejecución es razonablemente corto. Por ejem­plo, es posible diseñar un algoritmo para jugar ajedrez que triunfe siempre: el algoritmo elige la siguiente tirada examinando todas las posibles secuencias de movimientos desde el tablero actual hasta uno donde sea claro el resultado y elige la tirada que le asegure el triunfo; el pequeño inconveniente de este algoritmo es que dicho espacio de búsqueda se ha estimado en 100040 tableros por lo que puede tardarse miles de años en tomar una decisión. Por lo tanto, para fines prácticos se considera que si un problema tiene una solución que toma años en computar, dicha solución no existe.



Considérese ahora el problema de ordenar un conjunto de valores, si el conjunto tiene 2 elementos es más fácil resolverlo que si tiene 20, análoga­mente un algoritmo que resuelva el problema tardará más tiempo mientras más grande sea el conjunto y requerirá una cantidad de memoria mayor para almacenar los elementos del conjunto.



En general la cantidad de recursos que consume un algoritmo para re­solver un problema se incrementa conforme crece el tamaño del problema. Dependiendo del problema en particular, uno o varios de sus parámetros será elegido como tamaño del problema. Haciendo una cuidadosa observación, es relativamente fácil efectuar una elección atinada.



En la Figura 1 se presenta una serie de problemas y una sugerencia acerca del parámetro que se puede elegir como tamaño del problema.

Referencias: http://docencia.izt.uam.mx/pece/pagina_academica/AA/

Capítulo 1 - Introducción.

En las Ciencias de la Computación cuando se dice que un problema tiene solución, significa que existe un algoritmo susceptible de implantarse en una computadora, capaz de producir la respuesta correcta para cualquier instancia del problema en cuestión.

Para ciertos problemas es posible encontrar más de un algoritmo capaz de resolverlos, lo cual nos enfrenta al problema de escoger alguno de ellos. La tarea de decidir cuál de ellos es el mejor debe basarse en criterios acordes a nuestros intereses. En la mayoría de los casos la elección de un buen algoritmo está orientada hacia la disminución del costo que implica la solución del problema; bajo este enfoque es posible dividir los criterios en dos clases:

a) Criterios orientados a minimizar el costo de desarrollo: claridad, sencillez y facilidad de implantación, depuración y mantenimiento.
b) Criterios orientados a disminuir el costo de ejecución: tiempo de procesador y cantidad de memoria utilizados.

Si el programa que implanta el algoritmo se va a ejecutar unas cuantas veces, el costo de desarrollo es dominante, en este caso se debe dar más peso a los primeros criterios. Por el contrario, si el programa se va a utilizar frecuentemente, dominará el costo de ejecución, y por ende, se debe elegir un algoritmo que haga uso eficiente de los recursos de la computadora, es decir, se le debe evaluar prioritariamente bajo los criterios de la segunda clase. En cualquier caso, ninguno de los criterios de evaluación debe eliminarse por completo; pues, por ejemplo, si se implanta un sistema con algoritmos muy eficientes pero confusos, puede suceder que después no sea posible darle el mantenimiento adecuado.

Los recursos que consume un algoritmo pueden estimarse mediante he­rramientas teóricas y constituyen, por lo tanto, una base confiable para la elección de un algoritmo. En las Ciencias de la Computación, la actividad dedicada a determinar la cantidad de recursos que consumen los algoritmos se le denomina análisis de algoritmos.

La primera sección de este capítulo presenta los conceptos que nos permi­tirán introducir después, en secciones posteriores, las técnicas utilizadas para la medición de los recursos que consume un algoritmo y las bases teóricas sobre las que estas se fundamentan.

Referencias: http://docencia.izt.uam.mx/pece/pagina_academica/AA/

Análisis de Algoritmos - Prefacio

El concepto de algoritmo es de importancia central en las ciencias de la computación; matemáticos y científicos de la computación lo han definido en forma diferente. La palabra proviene del nombre de un matemático y as­trónomo medieval de Uzbekistán, Mohammed ibn-Musa al-Khwarizmi, quien dio las reglas para efectuar las 4 operaciones aritméticas básicas (suma, resta, multiplicación y división) en el siglo IX.

El astrónomo medieval se estableció en Bagdad en la "Casa del Conoci­miento" {Bait al-Hikma); escribió dos libros que jugaron un papel importante en la historia de las matemáticas, uno de los cuales concierne al arte indio de contar. Cuando su obra apareció traducida al latín en Europa, los lec­tores empezaron a atribuirle no sólo el libro sino, también, un esquema de numeración que hace uso de numerales indios, esto último se le atribuyó erró­neamente. La nueva notación se convirtió en la de al-Khwarizmi, y en forma descuidada fue nombrada "algorismi" y, finalmente, "algorism" o "algorithm". Esta palabra, originalmente derivada del nombre al-Khwarizmi, ahora signi­fica, más ampliamente, cualquier regla particular de proceder u operar (tal como lo es el método euclidiano para encontrar el máximo común divisor de dos enteros). A partir de entonces y hasta nuestros días, la palabra, por todo lo que representa, ha motivado muchos estudios de tipo teórico tanto en matemáticas como en computación.

En la primera parte de este curso se introducen los conceptos básicos para el análisis de algoritmos; se propone un procedimiento para estimar la cantidad de recursos que un algoritmo consume cuando se ejecuta en una computadora. Lo anterior nos permite conocer su valor práctico, es decir, determinar si existe una solución algorítmica eficiente para un problema en particular. Enseguida, se da importancia a la velocidad de crecimiento de la demanda de recursos por un algoritmo, conforme el tamaño del problema que resuelve se incrementa. El procedimiento presentado nos permite comparar y evaluar los costos de algoritmos tanto iterativos como recursivos.

En la segunda parte del curso nos avocamos al estudio de las principales técnicas de diseño de algoritmos. Para cada una de ellas se caracterizan los problemas a los que la técnica se puede aplicar, se presenta el método general y se dan algunos ejemplos.

Finalmente, la tercera parte del curso está enfocada al estudio de la teo­ría en torno a los problemas cuya solución algorítmica no se conoce o la conocida requiere tantos recursos que en términos prácticos no resuelve mas que problemas triviales. La teoría presentada permite identificar estos pro­blemas así como también encontrar soluciones aproximadas (no óptimas pero aceptables).
.