Home Teaching - Algorithms November 30, 2022   

Análisis y Diseño de Algoritmos

Objetivo general
  • El objeto de estudio de este curso son los algoritmos. Por un lado, veremos las medidas convencionales para determinar la eficiencia de ellos. Por otra parte, repasaremos una serie de algoritmos representativos, a los cuales les aplicaremos estas medidas, incursionaremos en los principios de su diseño, y nos planearemos si es posible mejorarlos. Es prerrequisito para este curso haber aprobado matemáticas discretas.
Contenido temático
  • Fundamentos del análisis de la eficiencia de algoritmos
  • Fuerza bruta y búsqueda exhaustiva
  • Decrementa y vencerás
  • Divide y vencerás
  • Transforma y vencerás
  • Compromisos temporales y espaciales
  • Programación dinámica
  • Algoritmos voraces (greedy)
  • Mejora iterativa
  • Limitaciones de los algoritmos
  • Enfrentando las limitaciones de los algoritmos
Lineamientos de evaluación
  • Tareas y trabajos de investigación, 40%
  • Examenes (1 parcial y 1 final), 30%
  • Proyecto final, 30%
Bibliografía
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms. The MIT Press; 3rd edition (July 31, 2009), ISBN-10: 0262033844.
  • Robert Sedgewick and Kevin Wayne. Algorithms. Addison-Wesley Professional; 4th edition (March 19, 2011), ISBN-10: 032157351X.
  • S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani. Algorithms. McGraw-Hill; 1st edition (September 13, 2006), ISBN-10: 0073523402.

Material de clase
Sesión Fecha Tema Material
10/01/18 Presentación del curso
1 10/01/18 Introducción al análisis y diseño de algoritmos
2 15/01/18 Conceptos fundamentales del análisis de algoritmos
3 17/01/18 Conceptos fundamentales del análisis de algoritmos II
4 22/01/18 Análisis matemático de algoritmos no recursivos
5 24/01/18 Análisis matemático de algoritmos recursivos
6 29/01/18 Algoritmos de fuerza bruta
7 31/01/18 Algoritmos de búsqueda exhaustiva
8 07/02/18 Algoritmos de búsqueda en grafos, DFS
9 12/02/18 Algoritmos de búsqueda en grafos, BFS
10 19/02/18 Algoritmos decrementa y vencerás
11 21/02/18 Algoritmos decrementa y vencerás II
- 28/02/18 Examen parcial .
12 07/03/18 Algoritmos divide y vencerás
13 12/03/18 Algoritmos transforma y vencerás
14 14/03/18 Compromiso tiempo-espacio
15 21/03/18 Algoritmos codiciosos (greedy)
16 09/04/18 Mejora iterativa
17 11/04/18 Cotas inferiores, árboles de decisión, problemas P, NP y NP-completos .
18 16/04/18 Branch & Bound y algoritmos aproximados para problemas NP-duros .
- 18/04/18 Examen final .
- 25/04/18 Entrega del proyecto final.



® 2015 Eduardo Rodriguez-Tello