Análisis y Diseño de Algoritmos (300CIG004)

 

Información Básica

  • Créditos: 3
  • Horas de Clase: 4 / semana
  • Horas de trabajo independiente: 5 / semana
  • Horas de Laboratorio al semestre:
  • Prerequisitos: Computabilidad y Lenguajes Formales(300CIG007)
  • Tipo de curso: Núcleo de Formación Fundamental.

Descripción del Curso

Este curso estudia técnicas bien conocidas en el diseño de algoritmos como dividir y conquistar, programación dinámica, la técnica voraz y backtracking. A los algoritmos desarrollados mediante estas técnicas, se les aplican los dos tipos de análisis fundamentales en algoritmia: el de corrección y el de eficiencia. Adicionalmente, el curso aborda el estudio de problemas intratables y las alternativas para su solución, como algoritmos aleatorizados, paralelos o probabilisticos. Finalmente se retoma la teoria de la NP-completitud en lo referente a realizar demostraciones por reducción.

Objetivos

Al finalizar el curso los participantes podrán:

  1. Utilizar las tecnicas de diseño para proponer soluciones eficaces y eficientes a problemas del mundo real.
    1. Modelar formalmente un problema real como un problema abstracto, algorítmico.
    2. Diseñar algoritmos que resuelvan problemas del mundo real, siguiendo técnicas de diseño como dividir y conquistar, backtracking, programación dinámica o algoritmos voraces.
    3. Aplicar algoritmos clásicos (como ordenamiento, búsqueda en grafos, hallar caminos mínimos en grafos, entre otros) al modelamiento de situaciones reales.
    4. Extender y adaptar algoritmos y estructuras de datos clásicas para dar solución a problemas planteados.
    5. Desarrollar soluciones para problemas algorítmicos intratables computacionalmente.
  2. Analizar rigurosamente el desempeno de algoritmos y de operaciones en estructuras de datos.
    1. Argumentar rigurosamente la corrección de los algoritmos clasicos estudiados y de los algoritmos propios.
    2. Analizar la complejidad temporal y espacial de algoritmos usando cotas superiores y cotas estrechas, para el mejor caso, el peor caso o el caso promedio.
    3. Escoger el algoritmo y estructura de datos más apropiados para usar en la solución de un problema determinado atendiendo a criterios de eficacia y eficiencia computacional.

Contenido

Capítulo 1: Introducción

Sesión Horas de Clase Tópicos Bibliografía
1 2 Presentación del curso, introducción al análisis y diseño de algoritmos, repaso de análisis de complejidad y demostraciones de corrección [1,cap 1]

Total de Horas: 2.

Capítulo 2: Técnicas de Diseno

Sesión Horas de Clase Tópicos Bibliografía
2 8 Dividir y conquistar: solución de ecuaciones de recurrencia. Teorema maestro. Ejemplos variados de aplicación de la técnica. [1,cap 4][1,cap 2][1,cap 7][3,cap ?][7,cap 3]
6 10 Programación dinámica. Ejemplos variados de aplicación de la técnica. [1,cap 15][6,cap 9][3,cap ?][7,cap 5]
11 10 Técnica voráz. Ejemplos variados de aplicación de la técnica. [3,cap ?][7,cap 4]

Total de Horas: 28.

Capítulo 3: Estructuras de Datos Eficientes

Sesión Horas de Clase Tópicos Bibliografía
16 2 Estructura Union-Find [1,cap 21]
17 2 Arboles de Busqueda [1,cap 12]
18 2 Arboles Rojo y Negro. Arboles B [1, cap 13][1,cap 18]
19 2 Heap Binomial [1,cap 19]

Total de Horas: 8.

Capítulo 4: Problemas Intratables

Sesión Horas de Clase Tópicos Bibliografía
20 10 Backtracking. Ejemplos variados de aplicación de la tecnica [7,cap 7][3,cap ?]
25 2 El metodo Simplex de programación lineal [1,cap 29]
26 4 Algoritmos de aproximación y aleatorizados [1,cap 35]

Total de Horas: 16.

Capítulo 4: Teoria de la NP-completitud

Sesión Horas de Clase Tópicos Bibliografía
28 6 Demostraciones de NP-completitud [1,cap 34][4,cap ?]

Total de Horas: 6.

Matriculación

  1. 2011-2:
  2. 2011-1:
  3. 2010-2:

Recursos

Ejemplos:

Demo PAPI

Bibliografía

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, Cambridge, MA, USA, 2001.
  2. G. Brassard and P. Bratley. Algorithmics: theory & practice. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1988.
  3. S. Dasgupta, C. H. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill Science/Engineering/Math, 2006.
  4. S. S. Skiena. The algorithm design manual. Springer-Verlag New York, Inc., New York, NY, USA, 1998.
  5. Garey, M. R. and Johnson D. S. Computers and intractability : a guide to the theory of NP-completeness. W.H. Freeman & Company, USA, 2003
  6. Maning C. D. and Schutze H. Foundations of Statistical Natural Language Proccessing. MIT Press, 2000.
  7. Horowitz E. Sahni S. Fundamentals of Computer Algorithms. Computer Science Press. 1978.

Instalaciones

Salón de clase con computador y proyector.