Unidad de Aprendizaje
"Análisis de algoritmos"
18-19/2 Enero - Junio 2019
ESCOM IPN - ISC Plan 2009
18-19/2 Enero - Junio 2019
ESCOM IPN - ISC Plan 2009
Baase, S. Van Gelder, A. (2001). Algoritmos Computacionales (3ª Ed.). México: Editorial Pearson. ISBN-13: 978-0201612448.
Brassard, G. (1997). Fundamentos de Algoritmia. España: Prentice Hall. ISBN: 848966000X.
Cormen, T. Leiserson, Ch. Rivest R. (2003). Introduction to algorithms (2nd. Ed.) Estados Unidos de América: MIT press. ISBN-13: 978- 0072970548.
*Individuales **En equipo
Pruebas a posteriori (análisis empirico de los algoritmos). Con base en el archivo de entrada proporcionado que tiene 10,000,000 números diferentes; ordenarlo bajo los siguientes métodos de ordenamiento y comparar experimentalmente las complejidades de estos:
Con base en el ordenamiento obtenido a partir del archivo de entrada de la practica 01 que tiene 10,000,000 de números diferentes. Realizar la búsqueda de elementos bajo 3 métodos de búsqueda, realizar el análisis teórico y experimental de las complejidades; así como encontrar las cotas de los algoritmos. Estudiar tambien posibles mejoras de implementar los algoritmos mediante hilos.
Presentación de la Unidad de Aprendizaje (Introducción, unidades tematicas, formato de las evaluaciónes, tareas, practicas y acuerdos)
Objetivo de la unidad: Determinar la complejidad espacial y temporal de algoritmos iterativos y recursivos, con base en las notaciones O mayúscula, o minúscula, omega y theta.
En 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. El análisis de algoritmos es una parte importante de la Teoría de Complejidad computacional, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes.
La función complejidad, f(n); donde n es el tamaño del problema, da una medida de la cantidad de recursos que un algoritmo necesitará al implantarse y ejecutarse en alguna computadora. La cantidad de recursos que consume un algoritmo crece conforme el tamaño del problema se incrementa, la función complejidad es monótona creciente f(n) > f(m) si n > m con respecto al tamaño del problema.
El comportamiento de un algoritmo puede variar notablemente para diferentes instancias. Suelen estudiarse tres casos para un mismo algoritmo: caso mejor, caso peor, caso medio. El peor caso indica el mayor tiempo obtenido, teniendo en consideración todas las entradas posibles, el mejor caso indica el menor tiempo obtenido, teniendo en consideración todas las entradas posibles y el caso medio indica el tiempo medio obtenido, considerando todas las entradas posibles.
El costo para obtener una solución de un problema concreto aumenta con el tamaño n del problema. Para valores suficientemente pequeños de n, el coste de ejecución de cualquier algoritmo es pequeño, incluyendo los algoritmos ineficientes; i.e. la elección del algoritmo no es un problema crítico para problemas de pequeño tamaño. El análisis de algoritmos se realiza para valores grandes de n. Para lo cual se considera el comportamiento de sus funciones de complejidad para valores grandes de n, es decir se estudia el comportamiento asintótico de f(n), lo cual permite conocer el comportamiento en el límite del coste cuando n crece.
El análisis de complejidad de los algoritmos no recursivos (iterativos) se realiza bajo los principios del peor caso y generalmente devolverá la cota superior ajusta del orden de este. En principio se considera válido cuando solo se desea obtener una cota para valores grandes de n, basándose en que se cumple el principio de invarianza del análisis asintótico. Para los algoritmos iterativos es únicamente necesario conocer los órdenes de complejidad O de las tres estructuras de control que todo algoritmo iterativo puede emplear.
El análisis de complejidad de los algoritmos no recursivos (iterativos) se realiza bajo los principios del peor caso y generalmente devolverá la cota superior ajusta del orden de este. En principio se considera válido cuando solo se desea obtener una cota para valores grandes de n, basándose en que se cumple el principio de invarianza del análisis asintótico. Para los algoritmos iterativos es únicamente necesario conocer los órdenes de complejidad O de las tres estructuras de control que todo algoritmo iterativo puede emplear.
Objetivo de la unidad: Implementar algoritmos en un lenguaje de programación de alto nivel, con base en las estrategias de diseño y técnicas de programación utiles en la optimizaciónd e soluciones a problemas computacionales.
El método divide y vencerás consiste en descomponer el problema en una serie de subproblemas de menor tamaño, al resolver estos subproblemas usando siempre la misma técnica, las soluciones parciales se combinan para obtener la solución del problema original.
La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas. Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Un problema tiene subproblemas superpuestos si se usa un mismo subproblema para resolver diferentes problemas mayores.
Los algoritmos ávidos o voraces (Greedy Algorithms) son algoritmos que toman decisiones de corto alcance, basadas en información inmediatamente disponible, sin importar consecuencias futuras. Suelen ser bastante simples y se emplean sobre todo para resolver problemas de optimización, como por ejemplo, encontrar la secuencia óptima para procesar un conjunto de tareas por un computador, hallar el camino mínimo de un grafo, etc.
A menudo sucede que los datos a procesar no se descomponen lógicamente en registros independientes que representen pequeñas partes identificables. Este tipo de datos se caracteriza fácilmente por el hecho de que se pueden escribir en forma de cadenas: series lineales (por lo regular muy largas) de caracteres. Las cadenas son evidentemente el centro de los sistemas de tratamiento de texto, que proporcionan una gran variedad de posibilidades para la manipulación de textos. El empate de cadenas implica la implementación de algoritmos de búsqueda de subcadenas y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Por otro lado un "trie" es una estructura de datos de tipo árbol que permite la recuperación de conjunto de claves, donde una clave es una secuencia de símbolos pertenecientes a un alfabeto. Las claves son almacenadas en las hojas del árbol y los nodos internos son pasarelas para guiar la búsqueda. El árbol se estructura de forma que cada letra de la clave se sitúa en un nodo de forma que los hijos de un nodo representan las distintas posibilidades de símbolos diferentes que pueden continuar al símbolo representado por el nodo padre. Por tanto la búsqueda en un trie se hace de forma similar a como se hacen las búsquedas de cadenas en un diccionario.
Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmo determinista, a partir de unos mismos datos se puede obtener distintas soluciones y, en algunos casos, soluciones erróneas. A un algoritmo probabilista se le puede permitir calcular una solución equivocada, con una probabilidad pequeña. Estos algoritmos son útiles cuando la solución determinista es tardada y de un orden de complejidad no polinomial para tamaños de problema grandes.
Objetivo de la unidad: Identificar los problemas de mayor reto para la computación, .
Los problemas computacionales los podemos dividir en dos conjuntos (Tratables: Problemas para los cuales existe un algoritmo de complejidad polinomial e Intratables: Problemas para los que no se conoce ningún algoritmo de complejidad polinomial). A los problemas tratables se les conoce también como problemas P (de orden polinomial). Asimismo a los problemas no tratables se les llama también NP (de orden no determinístico polinomial).