Introducción a algoritmos. Eficiencia. Análisis asintótico de la eficiencia temporal en programas iterativos. Resolución de recurrencias. Análisis asintótico de la eficiencia temporal en funciones recursivas. Técnicas de diseño de algoritmos. Caracterización del tipo de problema, esquema algorítmico, problemas representativos: Divide y conquista, Greedy, Programación dinámica y backtracking. Algoritmos de ordenamiento. Algoritmos cuadráticos y NlogN. Algoritmos sobre grafos. Algoritmos clásicos: recorrido en grafos, algoritmo de Dikjstra, Algoritmo de Floyd, algoritmo de Prim, algoritmo de Kruskal, componentes conectadas. Problemas NP-hard. Problemas clásicos y algoritmos de aproximación: El problema del viajante, recubrimiento de vértices, coloreo de un grafo. Bibliografía básica Brassard, G.; Bratley, P. Prentice-Hall. Fundamentos de Algoritmia. 1997 Cormen, T.; Lieserson, C.; Rivest, R. “Introduction to Algorithms” Ed. The MIT Press. 2009. |