Análisis y diseño de algoritmos

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.