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 astró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 Conocimiento" {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 lectores 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 significa, 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 teorí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 problemas así como también encontrar soluciones aproximadas (no óptimas pero aceptables).
.
Referencias: http://docencia.izt.uam.mx/pece/pagina_academica/AA/
No hay comentarios:
Publicar un comentario