Diseño de Algoritmos I

Los objetivos del curso son:

1) Diseño y análisis de buenos algoritmos para resolver problemas importantes y fundamentales en varias áreas de la computación.
2) Estudio de las técnicas de diseño de estos algoritmos, las cuales permiten resolver otros problemas.
3) Introducción a la teoría de complejidad computacional, la cual permite clasificar los problemas de acuerdo al grado de dificultad (en tiempo de ejecución) que resulta al resolverlos algorítmicamente.

Programa:

-Notación Asintótica.
-Análisis de algoritmos. Análisis del peor caso, caso promedio y análisis amortizado. Ejemplos prácticos de cálculo de la complejidad en tiempo. Verificación de la correctitud de algoritmos.
-Estructuras de datos avanzadas.
-Algoritmos Voraces (Greedy). Arbol mínimo cobertor. Implementación con componentes conexas. El concepto de Matroide y su relación con algoritmos greedy. Caminos mínimos, el problema de la mochila, Secuenciación de procesos.
-Divide and Conquer:
Multiplicación de enteros grandes. Búsqueda Binaria. Merge Sort.
Quicksort. Búsqueda de la mediana en orden lineal. Multiplicación de
matrices.
-Programación Dinámica: Coeficiente binomial. Campeonato
mundial. El problema de la mochila. Caminos mínimos. Multiplicación
encadenada de matrices. Funciones con memoria.
-Recorridos en grafos:
DFS, BFS. Técnicas de enumeración implícita: Backtraking y Branch and
Bound.
-Teoría de la complejidad computacional de problemas.: Máquinas de Turing. Tesis de Churh-Turing. Clases de problemas P, NP, NP-completos.

Material opcional:
-Flujo máximo en Redes.
-Apareamiento Máximo en Grafos Bipartitos.
-String Matching.
-Algoritmos Geométricos.
-Algoritmos Probabilísticos Numéricos.
-Heurísticas y Algoritmos Aproximados.

Programa detallado de CI-5651 (Diseño de Algoritmos I)