Centro de Investigación y de Estudios Avanzados del
Instituto Politécnico Nacional

Análisis de Algoritmos


Datos generales
Nombre Completo del Programa de Posgrado: Maestría en Ciencias en Ingeniería Eléctrica
Nombre Completo del Curso: Análisis de Algoritmos
Tipo de curso: Formativo
Créditos: 8
Número de Horas:
  • Teóricas: 60 Presenciales
  • Prácticas: 20 No presenciales
Profesores que impartirán el curso: Andrés Méndez Vázquez
General


Específicos
1. Introducción
1.1. El papel de los algoritmos en la computación
1.2. Funciones asintóticas
1.3. El método de divide y vencerás
1.4. Recurrencias para resolver complejidades
1.5. Análisis probabilístico y algoritmos aleatorizados
2. Ordenamientos
2.1. Heapsort
2.2. Quicksort
2.3. Cotas de ordenamiento por comparación
2.4. Ordenamientos en tiempo linear
3. Estructuras de datos básicas
3.1. Revisión de estructuras básicas
3.2. Hash Tables
3.3. Arboles de búsqueda binaria
3.4. Árboles Rojo-Negros
4. Técnicas Avanzadas
4.1. Programación dinámica
4.2. Algoritmos voraces
4.3. Análisis amortizado
5. Estructura de datos avanzadas
5.1. Skip Lists
5.2. B-Trees
5.3. Heaps de Fibonacci
6. Algoritmos gráficos
6.1. Algoritmos gráficos elementales
6.2. Árboles de expansión mínima
6.3. Algoritmos single-source shortest paths
6.4. Algoritmos all-source shortest paths
6.5. Algoritmos de flujo máximo
7. Tópicos selectos
7.1. Algoritmos multi-thread
7.2. Algoritmos de matrices
7.3. Algoritmos para string-matching
7.4. Geometría computacional
8. NP-Completnes
8.1. Definiciones
8.2. Codificaciones
8.3. Verificación en tiempo polinomial
8.4. NP-hard
8.5. Pruebas de NP-Complete
8.6. Una familia de problemas NP-Complete
9. Resolviendo NP-Completnes
9.1. Backtracking
9.2. Branch and Bound
9.3. Algoritmos de aproximación
  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Third Edition (MIT Press, 2009).
  2. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, First Edition (McGraw-Hill Education, 2006).
  3. Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, New York, NY, USA.
  4. R. Sedgewick, K. Wayne, Algorithms (Addison-Wesley Professional, 2011).
  5. Russ Miller and Laurence Boxer. 2005. Algorithms Sequential and Parallel: A Unified Approach (Charles River Media Computer Engineering (Hardcover)). Charles River Media, Inc., Rockland, MA, USA.
  6. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. 2008. Computational Geometry: Algorithms and Applications (3rd edition). Telos, Santa Clara, CA, USA
  • Tareas 0%
  • Exámenes (2 parciales y un final) 0%
  • Proyecto Final 0%
  • Total 0%
  • Conocimientos:
  • Habilidades:
  • Actitudes y valores:
Centro de Investigación y de Estudios Avanzados del Instituto Politécnico Nacional
Av. del Bosque 1145, colonia el Bajío, CP 45019, Zapopan , Jalisco, México.
Tel: (33) 3777-3600 Fax: (33) 3777-3609