Algoritmos y estructuras de datos avanzado

Este curso capacita a desarrolladores que ya dominan estructuras lineales, mapas, árboles y recursión para resolver problemas algorítmicos de mayor complejidad aplicando los cuatro paradigmas fundamentales: programación dinámica, grafos, divide-y-vencerás y greedy. Dirigido a quienes necesitan prepararse para entrevistas técnicas de nivel avanzado, optimizar código en producción o abordar problemas de diseño algorítmico con criterio cuantitativo. Al finalizar, el participante será capaz de identificar el paradigma adecuado para un problema nuevo, diseñar la solución correspondiente, derivar su complejidad y validarla empíricamente comparando el comportamiento teórico con mediciones reales sobre entradas de tamaño creciente.

Al finalizar el curso, el participante será capaz de:

• Diseñar una solución con programación dinámica aplicando memoización o tabulación a un problema con subproblemas solapados, comparando el coste con la versión recursiva naive
• Modelar un problema como grafo eligiendo representación por lista o matriz de adyacencia, y aplicar BFS o DFS para resolverlo justificando la elección del recorrido
• Implementar un heap o cola de prioridad y justificar su elección frente a una lista ordenada para el caso de uso dado, comparando la complejidad de inserción y extracción
• Aplicar la técnica de dos punteros o ventana deslizante para reducir la complejidad de un problema sobre una secuencia de O(n²) a O(n), verificando la corrección en casos límite
• Diseñar un algoritmo divide-y-vencerás para un problema dado, identificar su recurrencia y derivar su complejidad aplicando el Teorema Maestro o sustitución
• Diseñar una solución greedy para un problema de optimización, verificar que la propiedad de elección local óptima se sostiene en el caso general y contraejemplificar un greedy incorrecto
• Evaluar empíricamente el rendimiento de dos algoritmos alternativos sobre entradas de tamaño creciente, relacionar los resultados con el análisis teórico y recomendar uno según el perfil de uso

1. Programación dinámica Subproblemas solapados y subestructura óptima como condiciones necesarias; memoización top-down con diccionario: almacenamiento en la primera llamada y reutilización en las siguientes; tabulación bottom-up: orden de relleno de la tabla desde los casos base; reducción de espacio cuando solo se necesitan los últimos k estados; problemas representativos: Fibonacci, escalera de peldaños, cambio de monedas, caminos en cuadrícula; comparativa de llamadas y tiempo entre versión naive y DP
2. Grafos: modelado y recorridos Grafo como abstracción de relaciones entre entidades: nodos, aristas y dirección; representación por lista de adyacencia frente a matriz de adyacencia: memoria O(V+E) vs. O(V²) y coste de consultar arista; BFS con cola: recorrido por niveles y garantía de camino mínimo en grafos no ponderados; DFS con pila o recursión: detección de ciclos y exploración en profundidad; criterios de selección entre BFS y DFS según la pregunta que responde el recorrido; aplicaciones: conectividad, camino mínimo en número de saltos, componentes conexas
3. Heaps, colas de prioridad y técnicas de optimización en secuencias Max-heap y min-heap: propiedad de heap, operaciones push y pop en O(log n), construcción en O(n) con heapify; cola de prioridad como abstracción sobre heap: uso en planificación y algoritmos de camino mínimo; módulo heapq de Python; técnica de dos punteros sobre arrays ordenados: invariante de extremos y corrección de la terminación; ventana deslizante para subsecuencias contiguas: invariante de la ventana, expansión y contracción, aplicaciones a suma mínima, longitud máxima y restricciones sobre caracteres
4. Divide-y-vencerás y algoritmos greedy Estructura de divide-y-vencerás: caso base, división en subproblemas independientes y combinación; recurrencias y Teorema Maestro: identificación de a, b y f(n), aplicación de los tres casos; mergesort y quicksort como casos prototípicos; cuándo divide-y-vencerás no mejora sobre la solución iterativa; paradigma greedy: elección local óptima en cada paso y propiedad de subestructura óptima; verificación de la propiedad voraz por intercambio; construcción de contraejemplos para greedy incorrectos; problemas representativos: selección de actividades, cambio de monedas, árbol recubridor mínimo con Kruskal
5. Evaluación empírica del rendimiento Discrepancia entre complejidad teórica y tiempo medido para entradas pequeñas: papel de las constantes ocultas; benchmarking con timeit: múltiples repeticiones, cálculo de media y desviación, efecto del garbage collector y la caché; diseño del experimento: tamaños de entrada representativos, entradas adversariales vs. promedio; relación entre curva empírica y función teórica; recomendación algorítmica basada en perfil de uso: listas pequeñas vs. grandes, operaciones dominantes, restricciones de memoria

• Python 3.11 o superior para implementar soluciones, estructuras y benchmarks
• pytest 8.x o superior para validar funciones con casos de prueba automatizados
• timeit (módulo estándar de Python) para medición de rendimiento
• heapq (módulo estándar de Python) para ejercicios de heap y cola de prioridad
• collections.deque (módulo estándar de Python) para BFS y ventana deslizante
• Entorno de desarrollo con soporte para ejecución y depuración paso a paso (VS Code o PyCharm)
• Git para versionar las soluciones y comparar iteraciones de código

→ AED02 — Algoritmos y estructuras de datos intermedio (Intermedio, 8h)

• Comparar soluciones algorítmicas alternativas justificando la elección según complejidad temporal, complejidad espacial y legibilidad
• Diseñar soluciones que usen mapas o conjuntos para reducir búsquedas repetidas
• Integrar árboles binarios básicos y aplicar recorridos preorden, inorden y postorden
• Diseñar soluciones recursivas para problemas descomponibles y compararlas con alternativas iterativas
• Depurar errores lógicos en algoritmos iterativos o recursivos identificando casos límite
• Integrar análisis de complejidad en la validación de una solución y detectar cuellos de botella