Los algoritmos son una parte fundamental de las ciencias de la computación. El desempeño de un programa depende de: (1) la elección de sus algoritmos y (2) de la adecuación y efectividad de la implementación de estos. El buen diseño de los algoritmos es por lo tanto crucial para el desempeño de todos los sistemas de software. Por otra parte, el estudio de algoritmos proporciona una mayor comprensión de la naturaleza intrínseca de los problemas así como de sus posibles soluciones de manera independiente al lenguaje o paradigma de programación, del hardware utilizado o de cualquier otro aspecto de la implementación.
El objetivo de este curso es el obtener una comprensión profunda de algunos algoritmos clásicos y de su desempeño real asi como el aprender a resolver eficientemente un problema algorítmico.Referencias:
Introduction to Algorithms
Cormen,T., Leiserson, C., Rivest R. and Stein, C.
The MIT Press.
Algorithm Design
Kleinberg Jon and Tardos Éva
Cornell University.
Temario:
| Sesión | Fecha | Tema | Slides | Referencia útil | Tareas |
|---|---|---|---|---|---|
| 1 | 11.08 | Introducción, políticas del curso y algunos ejemplos |  |
||
| 2 | 13.08 | Recurrencias | |
||
| 3 | 18.08 | Recurrencias | |||
| 4 | 20.08 | Recurrencias | |
||
| 5 | 25.08 | Recurrencias | |||
| 6 | 01.09 | Stable Marriage Problem y Conjuntos Disjuntos | |
|
|
| 7 | 03.09 | Introducción a Gráficas | |
|
|
| 8 | 08.09 | Recorridos en gráficas: Depth-First Search y Topological Sort | |
|
|
| 9 | 10.09 | Plática del Prof. Dr. Juraj Hromkovic | |||
| 10 | 15.09 | Recorridos en gráficas: Breadth-First Search | |
||
| 11 | 17.09 | Minimum Spanning Trees: introducción y algoritmo de Boruvka | |
|
|
| 12 | 22.09 | Minimum Spanning Trees: algoritmos de Kruskal y Prim | |
||
| 13 | 29.09 | Caminos más cortos: algoritmos de Bellman-Ford y Dijkstra | |
|
|
| 14 | 01.10 | Caminos más cortos: heurísticas (algoritmo A*) | |
||
| 15 | 06.10 | Caminos más cortos desde todas las fuentes: algoritmo de Floyd-Warshall | |
|
|
| 16 | 08.10 | Introducción a Geometría Computacional y Slow Convex Hull | |
||
| 17 | 13.10 | Convex Hull: Un algoritmo iterativo | |
||
| 18 | 15.10 | Intersección de Segmentos de Recta | |
||
| 19 | 20.10 | Triangulación de Polígonos: Problema de la Galeria de Arte | |
Referencia | |
| 20 | 22.10 | Partición en Polígonos Monotonos | |
||
| 21 | 27.10 | Diagrama de Voronoi: Un algoritmo incremental | |