Análisis y Diseño de Algoritmos — Programa del curso
Docente: Gerson Garrido
1. Descripción
En Estructuras de Datos ustedes construyeron herramientas y usaron algoritmos como Dijkstra o Huffman sin demostrar que funcionan. Este curso responde tres preguntas que quedaron abiertas: ¿cómo se diseña un algoritmo para un problema nuevo?, ¿cómo se demuestra que siempre da la respuesta correcta? y ¿cómo se reconoce un problema para el que quizá no exista ningún algoritmo rápido?
Cada semana combina demostración e implementación. En teoría se diseña el algoritmo y se demuestra. En el laboratorio se recibe un problema escrito en palabras, se decide qué técnica le sirve y se implementa en C++ hasta que pase el juez del curso. Se organiza en cuatro partes:
- Demostrar y dividir — correctitud, recurrencias y divide y vencerás.
- Greedy y grafos — argumentos de intercambio, árboles de expansión mínima y DFS.
- Programación dinámica — subproblemas, secuencias, árboles y caminos mínimos.
- Flujo e intratabilidad — flujo máximo, reducciones, NP-completitud y qué hacer con un problema difícil.
Los apuntes son el texto del curso, y cada capítulo abre con una ruta de lectura: qué leer antes de clase, qué se explica en clase y qué repasar después. El libro de Jeff Erickson es la lectura gratuita de apoyo y CLRS es la referencia para quien quiera profundizar. Los términos técnicos siguen la guía de estilo, y el glosario reúne los principales.
2. Carga horaria
| Componente | Horas/semana | Formato |
|---|---|---|
| Teoría | 4 h | Dos sesiones de 2 h (Sesión A y Sesión B) |
| Laboratorio | 2 h | Una sesión |
3. Resultados de aprendizaje
Al finalizar el curso, el estudiante será capaz de:
- Demostrar que un algoritmo es correcto, con invariantes, inducción y argumentos de intercambio.
- Plantear y resolver la recurrencia del costo de un algoritmo recursivo.
- Diseñar algoritmos con divide y vencerás, greedy y programación dinámica, y justificar por qué la técnica elegida sirve.
- Modelar un problema escrito en palabras como un problema de grafos o de flujo.
- Aplicar y demostrar los algoritmos clásicos de árboles de expansión mínima, caminos mínimos, componentes fuertemente conexas y flujo máximo.
- Implementar en C++ una solución que cumpla los límites de tiempo, usando la biblioteca estándar.
- Demostrar que un problema es NP-completo con una reducción, y explicar qué significa eso en la práctica.
- Elegir una estrategia para un problema difícil: un caso especial, búsqueda con poda, aproximación o un solucionador.
4. Bibliografía
Texto del curso: los apuntes, un capítulo por semana. No se requiere comprar ningún libro.
Lectura gratuita de apoyo: Jeff Erickson, Algorithms, 1.ª edición, 2019. Licencia CC BY 4.0.
Referencia: Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms, 4.ª edición, MIT Press, 2022.
5. Calendario
Este es el calendario oficial del curso. Cada semana enlaza a su guía con objetivos, temas y actividades de laboratorio. Los temas marcados con ✂️ se pueden comprimir o pasar a lectura autónoma si se pierden clases por feriados. Las semanas 8 y 16 son de exámenes y no tienen clases regulares. En las semanas con práctica, la práctica ocupa la sesión de laboratorio y el problema de esa semana queda como ejercicio opcional.
| Sem. | Sesión A (2 h) | Sesión B (2 h) | Laboratorio (2 h) | Práctica o examen |
|---|---|---|---|---|
| 1 | Presentación · Demostrar un algoritmo: invariantes e inducción | Matching estable: Gale-Shapley | Asignar postulantes a carreras | |
| 2 | Recurrencias y teorema maestro | Mergesort demostrado · Contar inversiones | Comparar rankings | |
| 3 | Selección en tiempo lineal | Karatsuba · Par más cercano | El par más cercano | |
| 4 | Cota inferior para ordenar · ✂️ Quicksort aleatorizado, con intuición | Greedy: selección de intervalos y argumentos de intercambio | Práctica 1 · Opcional: horarios y aulas | Práctica 1 |
| 5 | Huffman demostrado · Minimizar el retraso máximo | Dijkstra demostrado | Rutas con a lo sumo k peajes | |
| 6 | Árboles de expansión mínima: propiedad del corte, Kruskal y Prim | DFS: orden topológico y componentes fuertemente conexas | Diseñar una red · Los prerrequisitos de una malla | |
| 7 | Programación dinámica: de la memoización a la tabla · Mochila | Distancia de edición y subsecuencia común más larga | Práctica 2 · Opcional: comparar dos textos | Práctica 2 |
| 8 | Examen parcial (semanas 1 a 7) | |||
| 9 | Programación dinámica sobre intervalos y sobre DAG | Programación dinámica sobre árboles | Optimizar sobre una jerarquía | |
| 10 | Bellman-Ford como programación dinámica | Floyd-Warshall · ✂️ Programación dinámica con máscaras de bits | Arbitraje con tipos de cambio | |
| 11 | Flujo máximo: Ford-Fulkerson | Teorema de flujo máximo y corte mínimo · Edmonds-Karp | Práctica 3 · Opcional: capacidad de una red | Práctica 3 |
| 12 | Matching bipartito · Caminos disjuntos | Modelar con flujo: asignación y selección de proyectos | Asignar estudiantes a secciones | |
| 13 | P, NP y reducciones polinomiales | Conjunto independiente, cobertura de vértices y SAT | Resolver sudokus con un solucionador SAT | |
| 14 | NP-completitud: Cook-Levin enunciado y reducciones desde 3-SAT | Más reducciones: coloreo y suma de subconjuntos | Práctica 4 · Opcional: ¿fácil o difícil? | Práctica 4 |
| 15 | Qué hacer con un problema difícil: poda y aproximación | ✂️ Programación lineal como idea · Repaso | El viajero: exacto frente a heurística | |
| 16 | Examen final (todo el curso) |
6. Prácticas
Hay cuatro prácticas individuales, en las semanas 4, 7, 11 y 14. Cada una ocupa la sesión de
laboratorio de su semana y combina una demostración escrita con un problema en C++. El
formato y las reglas están en practicas/README.md.
Los laboratorios sirven para practicar: el juez da la respuesta de inmediato, y preparan las prácticas y los exámenes.
7. Políticas
- Trabajo: individual. Se puede discutir ideas, pero cada estudiante escribe su propio código y sus demostraciones, y debe poder explicarlos.
Herramientas permitidas
En este curso no se usa IA generativa en ningún trabajo: laboratorios, prácticas ni exámenes. Las demás herramientas se permiten en laboratorios y prácticas, dentro del entorno del curso.
| Herramienta | ¿Se permite? |
|---|---|
Mensajes del compilador, gdb, valgrind y sanitizers |
Sí |
| Documentación oficial (cppreference, manuales del entorno) y búsqueda en la web | Sí, para consultar el lenguaje y la biblioteca. Copiar una solución ajena es plagio |
| Autocompletado del editor que no genera soluciones enteras (nombres, firmas, paréntesis) | Sí |
| Correctores de ortografía, traductores y herramientas de accesibilidad | Sí |
| Formateadores de código y linters | Sí |
| IA generativa para pedir explicaciones, sin que escriba código | No |
| IA generativa que escribe código o demostraciones | No |
Cómo se declara lo usado: al final de la entrega, una nota breve con la documentación y las páginas consultadas, salvo las del compilador y el editor. Cualquier entrega puede llevar una explicación oral: quien entrega debe poder explicar cualquier parte de su código y de su demostración.
8. Entorno de trabajo
Todo se hace en un mismo entorno, con el compilador de C++, gdb, valgrind, make, Git, el
juez del curso y un solucionador SAT ya instalados. Se abre con GitHub Codespaces o con Docker.
Instrucciones en labs/README.md.