Objetivo
Análisis y Diseño de Algoritmos
¡Nuevo!
Invierno 2005
Arturo Díaz Pérez
adiaz@cs.cinvestav.mx
Objetivo
La teoría de las ciencias de la computación trata cualquier objeto computacional para el cual se puede crear un buen modelo. La investigación en modelos formales de computación se inició en los 30's y 40's por Turing, Post, Kleene, Church y otros. En los 50's y 60's los lenguajes de programación, compiladores y sistemas operativos estaban en desarrollo, por lo tanto, se convirtieron tanto en el sujeto como la base para la mayoría del trabajo teórico. El poder de las computadoras en este periodo estaba limitado por procesadores lentos y por pequeñas cantidades de memoria. Así, se desarrollaron teorías (modelos, algoritmos y análisis) para hacer un uso eficiente de ellas. Esto dio origen al desarrollo del área que ahora se conoce como "Algoritmos y Estructuras de Datos". Al mismo tiempo se hicieron estudios para comprender la complejidad inherente en la solución de algunos problemas. Esto dio origen a lo que se conoce como la jerarquía de problemas computacionales y al área de "Complejidad Computacional".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.
1. El papel de la teoría en las ciencias de
la computación
1.1 Historia breve sobre
la Teoría de la Computación
1.2 Preliminares matemáticos
1.3 El rango de crecimiento
de las funciones
1.3 Modelos computacionales
1.4 Complejidad computacional
2. Análisis de Algoritmos
2.1 Ecuaciones de recurrencia
2.2 Métodos de búsqueda
2.3 Métodos de ordenamiento
2.4 Estructuras de datos
elementales y tablas de dispersión
2.5 Arboles rojinegros y
estructuras aumentadas
2.6 Algoritmos elementales
sobre teoría de gráficas
3. Técnicas para Diseño de Algoritmos
3.1 Algoritmos de Fuerza
Bruta
3.2 Divide y Vencerás
3.3 Programación
Dinámica
3.4 Algoritmos ávidos
3.5 Backtracking
3.4 Branch-and-bound
4. Complejidad computacional
4.1 Lenguajes y problemas
4.2 Recursos acotados
4.3 Clasificación
de los problemas de decisión
4.4 Problemas difíciles
y problemas completos
4.5 Problemas P y NP
[Aho95] Aho, A. V. and Ullman, J. D. Foundations of Computer Science (Principles of Computer Science Series). W H Freeman & Co. ISBN: 0716782847. 1995.
[Cormen90] 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)
[Garey79] Garey, M. and Johnson, D. S, Computers and untractability: A guide to the theory of NP-completeness. W H Freeman & Co.; ISBN: 0716710455. 1979.
[Graham89] Graham, R., Knuth, D. E. and Patashnik, O. Concrete Mathematics. Addison-Wesley, 1989.
[Savage98] Savage, John, E. Models of Computation: Exploring the
Power of Computing. Addisson-Wesley. Reading, Mass. 1998. ISBN: 0201895390.
| Examen Parcial No. 1 | 10 % |
| Examen Parcial No. 2 | 15 % |
| Examen Parcial No. 3 | 15 % |
| Examen Parcial No. 4 | 10 % |
| Programa No. 1 | 10 % |
| Programa No. 2 | 10 % |
| Programa No. 3 | 10 % |
| Programa No. 4
(Proyecto de Investigación) |
20 % |
Información adicional: adiaz@cs.cinvestav.mx