Análisis y Diseño de Algoritmos

Información Básica

  • Código y Nombre: 300CIG004, Análisis y Diseño de Algoritmos.
  • Créditos y horas de contacto: 3 Créditos, 4 horas por semana.
  • Nombre del profesor o coordinador del curso: Juan Manuel Reyes.
  • Tipo de curso: Abierto.

Textos del Curso

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

Información Específica del Curso

  • Este curso tiene como objetivo estudiar 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 Específicos del Curso

Objetivos de aprendizaje:
  • Utilizar las técnicas de diseño para proponer soluciones eficaces y eficientes a problemas del mundo real.
  • Aplicar algoritmos clásicos (como ordenamiento, búsqueda en grafos, hallar caminos mínimos en grafos, entre otros) al modelamiento de situaciones reales.
  • Desarrollar soluciones para problemas algorítmicos intratables computacionalmente.
  • Analizar rigurosamente el desempeño de algoritmos y de operaciones en estructuras de datos.
  • Argumentar rigurosamente la corrección de los algoritmos clásicos estudiados y de los algoritmos propios.
  • 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.
Relación con los resultados de programa
Resultados de Programa
A B C D E F G H I J K
Relevancia 3 2 3 2 5 1

Escala: (1) baja relevancia - (5) alta relevancia.

Tópicos del Curso

  • Dividir y conquistar: solución de ecuaciones de recurrencia.
  • Teorema maestro.
  • Programación dinámica.
  • Técnica voraz.
  • Estructura Union-Find.
  • Árboles de Búsqueda.
  • Árboles Rojo y Negro. Arboles B.
  • Heap Binomial.
  • Backtracking.
  • El método Simplex de programación lineal.
  • Algoritmos de aproximación y aleatorizados.
  • Demostraciones de NP-completitud.
 
pregrados/dptoccomputacionyelectronica/anaydisenoalgoritmos.txt · Última modificación: 2014/07/15 15:52 por lsosorio
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki