Teorí­a de Algoritmos 
CI-7621


 


A continuación se listan los temas que se pretenden cubrir (no necesariamente en el orden en que se listan).

Elementos de Algoritmia:
Definiciones básicas. Medidas de complejidad. El peor caso, el caso promedio, análisis amortizado. Notación asintótica. Corrección de algoritmos.

Métodos de la Matemática:
Sumas, recurrencias, combinatoria y su uso en el análisis de algoritmos.

Elementos para el Diseño de Algoritmos.
Estructuras de Datos:
heaps, heaps binomiales, Arboles AVL, estructuras para conjuntos de conjuntos, etc.
Estrategias:
"Greedy", "Backtracking", divide y conquistarás, programación dinámica, "Brach-and-Bound".

Popurrí de Algoritmos.
Dependiendo del número de semanas que tengamos antes de finalizar el trimestre, estudiaremos y analizaremos algunos o todos de los siguientes tipos de algoritmos: Algoritmos de Optimización Combinatoia, algoritmos paralelos, algoritmos probabilí­sticos ,Heurísticas y algoritmos de Aproximació.n

Complejidad Computacional:
Las clases P, NP, PESPACIO y otras. Problemas NP-completos, NP-Hard. Reducciones. 

Bibliografía:
(B): Guilles Brassard y P. Bratley. Fundamentos de Algoritmia. Prentice Hall. 1997. cota: QA9.58 B73
(S): Robert Sedgewick. Algorithms in C++. Addison-Wesley. 1992. cota: NUL RES QA76.73 C15S435
(C): Thomas Cormen, Charles Leirserson and Ronald Rivest. Introduction to Algorithms. McGraw Hill. 1998 (última edición). cota: QA76.6 C662
(M): Michael Sipser. Introduction to the Theory of Computation. PWS Publishing Company. 1997. cota: QA267 S56
(A): Aho, Hopcroft, Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1976. cota: QA76.6 A36
(G): Garey, Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman&Co., 1979. cota: QA76.6 G35
(P): Christos H. Papadimitriou y Kenneth Steiglizt. “Combinatorial Optimization: Algorithms and Complexity”. Prentice may. 1982. Nueva publicación de Dover Piblications 1998 ISBN 0-486-40258-4. cota: QA402.5 P37
(V): V. Vazirani. "Approximation Algorithms". Springer. 2004
(M1):  R. Motwani, P. Raghaban. "Randomized Algorithms". Cambridge University Press. 1995
(H): J. Hromkovic. Design and Analysis of Randomized Algorithms. Springer 2005
(H1): J. Hromkovic. Theoretical Computer Science. Springer 1998

Actividades en los trimestres:


Ir al comienzo