Ciencias de la Computación (plan 2013) 2023-1

Quinto Semestre, Análisis de Algoritmos

En este curso aprenderemos a analizar pero sobre todo a diseñar algoritmos. El enfoque particular del curso se centra en dos aspectos:

1. nos enfocaremos en los paradigmas de diseño, en lugar de la alternativa usual que suele ser agrupar los algoritmos por objeto de aplicación (gráficas, cadenas, números, p. ej.). En particular ilustraremos los paradigmas resolviendo problemas sobre objetos discretos.

2. Haremos énfasis en el papel de la recursión como técnica fundamental de diseño.

Temario

1. Introducción

   1. Qué es el análisis y qué es el diseño de algoritmos.

   2. Primeros problema de ejemplo: recurrencias lineales; máximo común divisor

   3. Propiedades necesarias: corrección y complejidad.

   4. Notación asintótica.

   5. Uso de inducción para análisis.

   6. Uso de recursión para diseño.

   7. Árboles de recursión.

   8. Equivalencia entre algoritmos iterativos y recursivos.

   9. Invariantes y análisis formal.

2. Divide y vencerás

   1. Definición.

   2. Caso de estudio 1. MergeSort

   3. Caso de estudio 2. QuickSort

   4. Caso de estudio 4. Pareja de puntos más cercana.

   5. Caso de estudio 3. Transformada rápida de Fourier

      1. FFT y convolución: aplicaciones.

   6. Paralelismo inherente en algoritmos divide y vencerás.

3. Algoritmos greedy

   1. Definición.

   2. Caso de estudio 1. Calendarización de intervalos.

   3. Caso de estudio 2. Rutas más cortas en gráficas.

   4. Caso de estudio 3. Árboles generadores de peso mínimo.

   5. Caso de estudio 4. Ordenación de enteros en tiempo lineal.

   6. Notas sobre problemas de optimización en gráficas perfectas.

   7. Matroides y algoritmos greedy*.

4. Programación dinámica

   1. Árboles de recursión con tareas repetidas.

   2. Memorización como primera optimización.

   3. Programación dinámica como segunda optimización.

   4. Caso de estudio 1. Multiplicación de cadenas de matrices.

   5. Caso de estudio 2. Rutas más cortas en gráficas con pesos negativos.

   6. Caso de estudio 3. Distancia de edición, alineación de secuencias, y problemas similares.

   7. Caso de estudio 4. Subsucesión común más larga.

   8. Paralelismo inherente en la programación dinámica.

5. Flujo en redes

   1. Definición

   2. Lema de flujo mínimo/corte máximo

   3. Algoritmo de Ford/Fulkenson.

   4. Caso de estudio 1. Emparejamiento bipartito.

   5. Caso de estudio 2. Conectividad de gráficas y trayectorias disjuntas.

   6. Caso de estudio 3. Segmentación de imágenes.

   7. Caso de estudio 4. Selección de proyectos.

6. Más allá de algoritmos secuenciales (opcional).

   1. NP-Dureza y reducciones

   2. Heurísticas de aproximación

   3. Algoritmos paralelos

   4. Algoritmos probabilistas.

Bibliografía

El libro principal será

Algorithm Design. John Kleinberg y Eva Tardos.

También utilizarémos los libros de algoritmos de Skienna y de Cormen et. al.

Contacto

El profesor David Flores se puede contactar en la oficina 118 del Departamento de Matemáticas de la Facultad de Ciencias, previa cita.