Análisis de algoritmos 2020-1

Grupo a cargo del profesor David Flores.

Ayudante José Nieves Morán.

Presentación

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 algortimos 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. Propiedades necesarias: corrección y complejidad.
    3. Notación asintótica.
    4. Uso de inducción para análisis.
    5. Uso de recursión para diseño.
    6. Árboles de recursión.
    7. Equivalencia entre algoritmos iterativos y recursivos.
    8. Invariantes y análisis formal.
  2. Objetos de estudio
    1. Enteros.
    2. Relaciones,
    3. Árboles y Gráficas.
    4. Objetos geométricos.
  3. Divide y vencerás
    1. Definición.
    2. Caso de estudio 1. MergeSort
    3. Caso de estudio 2. QuickSort
    4. Caso de estudio 3. Pareja de puntos más cercana.
    5. Caso de estudio 4. Transformada rápida de Fourier
      1. FFT y convolución: aplicaciones.
    6. Paralelismo inherente en algoritmos divide y vencerás.
  4. 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*.
  5. 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 entre todos los pares de vértices.
    6. Caso de estudio 3. Distancia de edición, alineación de secuencias, y problemas similares.
    7. Caso de estudio 4. Subsuseción común más larga.
    8. Paralelismo inherente en la programación dinámica.
  6. 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.

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.

Evaluación

La evaluación será:

  • max{tareas*0.6+ exámenes*0.4, tareas*0.4+exámenes*0.6}

Contacto

El grupo de correo del curso está en

https://groups.google.com/d/forum/algoritmos-2020-1

La oficina del profesor es la 118 del Departamento de Matemáticas.

La carpeta compartida con recursos electrónicos está en: