Análisis y diseño de Algoritmos
Objetivo: Presentar las técnicas para analizar y diseñar algoritmos y revisar la teoría computacional relacionada con la clasificación de problemas.
En este curso se revisará el proceso de análisis de algoritmos así como las técnicas utilizadas para diseñar algoritmos eficientes. En la primera parte se introducirán algunos conceptos matemáticos necesarios para el análisis de algoritmos. Se revisarán los modelos computacionales más utilizados y se definirá de manera breve lo que se entiende por complejidad computacional. En la segunda parte se ejemplificará la complejidad de los algoritmos mediante el análisis de algoritmos típicos como ordenamiento, búsquedas, algoritmos sobre gráficas, etc. En la tercera parte se presentarán técnicas de diseño de algoritmos generales como programación dinámica, algoritmos ávidos y métodos branch-and-bound. Finalmente, en la cuarta parte se presentarán algunos resultados que determinan las clases de complejidad. Se introducirá la clasificación de los problemas de decisión, los problemas difíciles y los problemas completos, los problemas polinomiales y no-polinomiales.
Contenido:
1. El papel de la teoría en las ciencias de la computación
a) Historia breve sobre la Teoría de la Computación
b) Preliminares matemáticos
c) El rango de crecimiento de las funciones
d) Modelos computacionales
e) Complejidad computacional
2. Análisis de Algoritmos
a) Historia breve sobre la Teoría de la Computación
b) Ecuaciones de recurrencia
c) Métodos de búsqueda
d) Métodos de ordenamiento
e) Estructuras de datos elementales y tablas de dispersión
f ) Arboles rojinegros y estructuras aumentadas
g) Algoritmos elementales sobre teoría de gráficas
3. Técnicas para Diseño de Algoritmos
a) Algoritmos de Fuerza Bruta
b) Divide y Vencerás
c) Programación Dinámica
d) Algoritmos ávidos
e) Backtracking
f ) Branch-and-bound
4. Complejidad computacional
a) Lenguajes y problemas
b) Recursos acotados
c) Clasificación de los problemas de decisión
d) Problemas difíciles y problemas completos
e) Problemas P y NP
Bibliografia:
1. A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Analysis and Design of Computer
Algorithms. Addisson-Wesley. Reading, Mass. ISBN: 0201000296. 1974.
2 A.V. Aho, and J.D. Ullman, Foundations of Computer Science (Principles of
Computer Science Series). W H Freeman & Co. ISBN: 0716782847. 1995.
3. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to
Algorithms (MIT Electrical Engineering and Computer Science Series). The MIT
Press, ISBN: 0262031418. 1990. (Libro de Texto).
4. Garey, M. and Johnson, D.S., Computers and untractability: A guide to the theory
of NP-completeness. W H Freeman & Co.; ISBN: 0716710455. 1979.
5. Graham, R., Knuth, D. E. and Patashnik, O. Concrete Mathematics. Addison-
Wesley, 1989.
6. Savage, John, E. Models of Computation: Exploring the Power of Computing.
Addisson-Wesley. Reading, Mass. 1998. ISBN: 0201895390.
