Diseño de algoritmos
¿Por qué un programa que ordena un millón de datos tarda un segundo y otro, que hace lo mismo, tarda un día? ¿Cómo se demuestra que un algoritmo es correcto y no solo que «funciona en los ejemplos»? Este es un curso de nivel grado en ingeniería dedicado a diseñar y analizar algoritmos eficientes: aprenderás a medir su coste con recurrencias y el teorema maestro, a dominar las grandes técnicas de diseño —divide y vencerás, algoritmos voraces, programación dinámica y vuelta atrás—, a usar las estructuras de datos que las hacen rápidas (montículos y conjuntos disjuntos) y a resolver los problemas clásicos sobre grafos: recorridos, árboles de expansión mínima, caminos mínimos y flujo máximo. Cada algoritmo se acompaña de su demostración de corrección y de una medición empírica que confirma el análisis.
Qué incluye: 10 temas y 4 prácticas evaluables
- Módulo 1 · Análisis de algoritmos y divide y vencerás — Tema 1 Análisis de algoritmos: coste, corrección y medición · Tema 2 Recurrencias y el teorema maestro · Tema 3 Divide y vencerás · Práctica 1 · Medir y predecir: divide y vencerás bajo la lupa
- Módulo 2 · Estructuras de datos, grafos y algoritmos voraces — Tema 4 Montículos, conjuntos disjuntos y análisis amortizado · Tema 5 Grafos: representación y recorridos · Tema 6 Algoritmos voraces y su corrección · Tema 7 Árboles de expansión mínima y caminos mínimos · Práctica 2 · Redes eficientes: árboles de expansión y caminos mínimos
- Módulo 3 · Programación dinámica — Tema 8 Programación dinámica · Práctica 3 · De la recurrencia a la tabla: programación dinámica aplicada
- Módulo 4 · Flujo en redes y búsqueda exhaustiva — Tema 9 Flujo máximo y emparejamientos · Tema 10 Vuelta atrás: búsqueda exhaustiva con podas · Práctica 4 · Asignar y explorar: flujo máximo frente a vuelta atrás
Cada tema trae un PDF propio con el esquema de cada técnica, algoritmos en pseudocódigo y en Python, demostraciones de corrección y de coste comentadas y ejemplos resueltos paso a paso; un notebook de entrenamiento con ejercicios autocorregibles y su solución, y una autoevaluación que desbloquea lo siguiente. Las prácticas combinan implementación (ordenación y selección instrumentadas, montículos y union-find propios, Kruskal, Prim, Dijkstra y Bellman-Ford, tablas de programación dinámica con reconstrucción, Edmonds-Karp y vuelta atrás con podas), análisis formal (invariantes, recurrencias, argumentos de intercambio, subestructura óptima) y estudio experimental (tiempos y contadores en escala log-log frente a la predicción teórica).
Trabajarás en Python 3 con la biblioteca estándar, networkx para generar grafos y comprobar resultados y matplotlib para las gráficas, en local o en Google Colab. Dedicación estimada: 129 horas de temas y prácticas, más una hora de presentación (unas 10 horas semanales durante 13 semanas). Dirigido a estudiantes de ingeniería informática, matemáticas o titulaciones afines y a profesionales del software que quieran escribir código más rápido y razonar con rigor sobre él, también como preparación de entrevistas técnicas y programación competitiva. Requisitos: programación en Python (incluida la recursión), estructuras de datos básicas (listas, pilas, colas, árboles, tablas hash), matemática discreta (inducción, sumatorios, logaritmos) y nociones de grafos. Se complementa con el curso Teoría de la Complejidad Computacional, que estudia qué hacer cuando no existe un algoritmo eficiente.