Análisis y diseño de Algoritmos
Objetivo: Presentar las técnicas para analizar y diseñar algoritmos y revisar la teoría computacional relacionada con la clasificación de problemas.
1. Introducción
1. Motivación.
2 Algoritmos.
Parte uno: Fundamentos
2. Nociones matemáticas y terminología
1) Análisis de algoritmos
2) Diseño de algoritmos
3) Ejemplos básicos
3. Crecimiento de funciones
1) Notación asintótica
2) Las funciones más comunes
4. Divide y vencerás y métodos para resolver recurrencias
1. Dos problemas que se resuelven usando divide y vencerás:
1 El problema del sub-arreglo máximo
2. Multiplicación de matrices: algoritmo de Strassen
2. El método de sustitución para resolver recurrencias
3. Árbol de recursión para resolver recurrencias
4. El método maestro
5. Análisis probabilístico y algoritmos aleatorizados
1. Un problema que se resuelve usando algoritmos aleatorizados
2. Variables indicadoras
3. Algoritmos aleatorizados y su análisis
Parte dos: Ordenación y Estadísticas de órden
6. Algoritmos básicos de ordenación
1) Heapsort
2) Quicksort
7. Ordenación en tiempo lineal
1) Cota inferior de ordenación
2) Counting sort, bucket sort, radix sort
8. Medianas y otras estadísticas de orden
1. Mínimo y máximo
2. i-ésima estadística de órden en tiempo linea
Parte tres: Estructura de datos
9. Árboles binarios de búsqueda (Binary Search Trees)
1) Operaciones básicas
2) BST construidos aleatoriamente
10. Red-black Trees
1) Propiedades
2) Operaciones básicas
11. Estructuras de datos dinámicas (augmenting data structures)
1. Estadísticas de orden dinámicas
2. Cómo aumentar una estructura de datos
3. Una estructura de datos dinámica: Árboles de intervalos
Parte cuatro: Técnicas avanzadas de diseño y análisis
12. Programación dinámica
1. Dos problemas que se resuelven usando programación dinámica:
1 Rod cutting
2. Multiplicación de cadenas de matrices
2. El método de la programación dinámica
3. Subsecuencia común más larga
13. Algoritmos glotones (greedy algorithms)
1. Un problema que se resuelve usando algoritmos glotones: el problema de
la selección de actividades
2. Los algoritmos glotones
3. Códigos de Huffman
14. Análisis amortizado (*Opcional)
1. Análisis agregado (aggregate analysis)
2. El método de la contabilidad (the accounting method) y el método de el potencial
(the potential method)
3. Tablas dinámicas
Parte cinco: Algoritmos en gráficas
15. Algoritmos elementales en gráficas
1. BFS, DFS
2. Topological sort
3. Componentes conexas
16. Árboles generadores de peso mínimo
1. Propiedades
2. Algoritmo de Prim y Kruskal
17. Caminos más cortos
1. Caminos más cortos desde una sola fuente
1. Algoritmo de Bellman-Ford y Dijkstra
2. Caminos más cortos para todas las parejas
1. Algortimo de Floyd-Warshall y de Johnson
Bibliografía básica:
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.
* Jon Kleinberg and Eva Tardos. 2005. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA
* Alfred V. Aho and John E. Hopcroft. 1974. The Design and Analysis of Computer Algorithms (1st ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.
Bibliografía complementaria:
* Robert Sedgewick, Kevin Wayne. 2011. Algorithms, Fourth Edition (4th ed.). Addison-Wesley Professional.
* George Heineman, Gary Pollice, and Stanley Selkow. 2008. Algorithms in a Nutshell. O'Reilly Media, Inc..
* Thomas H. Cormen. 2013. Algorithms Unlocked (1 ed.). The MIT Press.
* Peter Brass. 2008. Advanced Data Structures (1 ed.). Cambridge University Press, New York, NY, USA.
