Análisis y Diseño de Algoritmos
Calendario
Cada semana: una sesión de teoría (2 h) y un laboratorio (2 h). Los temas marcados con ✂️ pueden pasar a lectura autónoma si se pierden clases.
Demostrar y dividirGreedy y grafosProgramación dinámicaFlujo e intratabilidad
- 01
Demostrar un algoritmo
Demostrar y dividir- Teoría
- Presentación · Demostrar un algoritmo: invariantes e inducción · Matching estable: Gale-Shapley
- Laboratorio
- Asignar postulantes a carreras
- 02
Recurrencias y mergesort
Demostrar y dividir- Teoría
- Recurrencias y teorema maestro · Mergesort demostrado · Contar inversiones
- Laboratorio
- Comparar rankings
- 03
Más divide y vencerás
Demostrar y dividir- Teoría
- Selección en tiempo lineal · Karatsuba · Par más cercano
- Laboratorio
- El par más cercano
- 04
- Teoría
- Cota inferior para ordenar · Quicksort aleatorizado, con intuición · Greedy: selección de intervalos y argumentos de intercambio
- Laboratorio
- Práctica 1 · Opcional: horarios y aulas
Práctica 1ApuntesDiapositivasCódigo - 05
Huffman y Dijkstra, demostrados
Greedy y grafos- Teoría
- Huffman demostrado · Minimizar el retraso máximo · Dijkstra demostrado
- Laboratorio
- Rutas con a lo sumo k peajes
- 06
Árboles de expansión mínima y DFS
Greedy y grafos- Teoría
- Árboles de expansión mínima: propiedad del corte, Kruskal y Prim · DFS: orden topológico y componentes fuertemente conexas
- Laboratorio
- Diseñar una red · Los prerrequisitos de una malla
- 07
Programación dinámica
Programación dinámica- Teoría
- Programación dinámica: de la memoización a la tabla · Mochila · Distancia de edición y subsecuencia común más larga
- Laboratorio
- Práctica 2 · Opcional: comparar dos textos
Práctica 2ApuntesDiapositivasCódigo - 08
- 09
Más programación dinámica
Programación dinámica- Teoría
- Programación dinámica sobre intervalos y sobre DAG · Programación dinámica sobre árboles
- Laboratorio
- Optimizar sobre una jerarquía
- 10
- Teoría
- Bellman-Ford como programación dinámica · Floyd-Warshall · Programación dinámica con máscaras de bits
- Laboratorio
- Arbitraje con tipos de cambio
- 11
Flujo máximo
Flujo e intratabilidad- Teoría
- Flujo máximo: Ford-Fulkerson · Teorema de flujo máximo y corte mínimo · Edmonds-Karp
- Laboratorio
- Práctica 3 · Opcional: capacidad de una red
Práctica 3ApuntesDiapositivasCódigo - 12
Modelar con flujo
Flujo e intratabilidad- Teoría
- Matching bipartito · Caminos disjuntos · Modelar con flujo: asignación y selección de proyectos
- Laboratorio
- Asignar estudiantes a secciones
- 13
P, NP y reducciones
Flujo e intratabilidad- Teoría
- P, NP y reducciones polinomiales · Conjunto independiente, cobertura de vértices y SAT
- Laboratorio
- Resolver sudokus con un solucionador SAT
- 14
NP-completitud
Flujo e intratabilidad- Teoría
- NP-completitud: Cook-Levin enunciado y reducciones desde 3-SAT · Más reducciones: coloreo y suma de subconjuntos
- Laboratorio
- Práctica 4 · Opcional: ¿fácil o difícil?
Práctica 4ApuntesDiapositivasCódigo - 15
- Teoría
- Qué hacer con un problema difícil: poda y aproximación · Programación lineal como idea · Repaso
- Laboratorio
- El viajero: exacto frente a heurística
- 16