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).

.

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