Lenguajes y Fundamentos de Programación · LNG-301

Algoritmos avanzados y complejidad

Programación dinámica, algoritmos voraces y grafos ponderados con análisis asintótico y medición real.

Bajo demanda Especialización 7 módulos · 37 clases

Formato asíncrono Desarrollo Python, JupyterLab

DESARROLLO JUPYTER

Lo que aprenderás

Identificar subestructura óptima y solapamiento de subproblemas para decidir si cabe programación dinámica.
Convertir una recursión exponencial en memoizada y después en tabla iterativa reduciendo memoria.
Demostrar cuándo una estrategia voraz es óptima y construir el contraejemplo cuando no lo es.
Implementar Dijkstra con montículo binario y Bellman-Ford para aristas de peso negativo.
Calcular árboles de recubrimiento mínimo con Kruskal y conjuntos disjuntos con compresión de caminos.
Aplicar el teorema maestro y el análisis amortizado al coste de algoritmos divide y vencerás.
Contrastar la cota asintótica con tiempos medidos y explicar las divergencias por constantes y caché.

Contenido del curso

7 módulos · 37 clases en vídeo · práctica guiada en cada módulo

Módulo 1 · Marco de análisis 5 clases

Repaso exigente de notación asintótica: O, Omega y Theta
Modelo de coste y qué esconde la constante
Banco de pruebas del curso: generar entradas y medir
Teorema maestro con ejemplos resueltos
Análisis amortizado: el caso del array dinámico

Módulo 2 · Divide y vencerás 5 clases

Esquema general y condiciones de aplicación
Multiplicación rápida y Karatsuba
Selección del k-ésimo elemento en tiempo lineal esperado
Par de puntos más cercano en el plano
Cuándo la recursión no compensa: umbral de corte

Módulo 3 · Programación dinámica 6 clases

De la recursión ingenua a la memoización
Tabulación y reducción del espacio a una fila
Mochila 0-1 y variantes con restricciones
Distancia de edición y alineamiento de secuencias
Subsecuencia común más larga con reconstrucción
Cortes y particiones: multiplicación de matrices

Módulo 4 · Algoritmos voraces 5 clases

Propiedad de elección voraz y subestructura óptima
Planificación de intervalos y demostración de optimalidad
Codificación de Huffman paso a paso
Cambio de moneda: cuándo lo voraz falla
Construir el contraejemplo antes de escribir código

Módulo 5 · Grafos ponderados 6 clases

Dijkstra con montículo binario y su coste real
Bellman-Ford y detección de ciclos negativos
Floyd-Warshall para todos los pares
Kruskal con conjuntos disjuntos y compresión de caminos
Prim y comparación práctica con Kruskal
Flujo máximo: intuición y algoritmo de Edmonds-Karp

Módulo 6 · Límites y aproximación 5 clases

Clases P y NP explicadas sin formalismo excesivo
Reducciones entre problemas conocidos
Heurísticas y algoritmos de aproximación con garantía
Búsqueda local y cuándo basta con una solución buena
Criterio para decidir cuánto optimizar

Módulo 7 · Proyecto de cierre 5 clases

Enunciado: planificación de rutas con ventanas de tiempo
Modelar el problema como grafo ponderado
Solución exacta y su límite práctico
Solución aproximada y comparación de calidad
Informe de resultados con mediciones y conclusiones

Requisitos

Dominio de estructuras de datos básicas: listas, tablas hash, árboles y grafos.
Python fluido, incluyendo recursión, generadores y uso de la biblioteca estándar.
Haber trabajado antes con notación O grande, aunque sea de forma intuitiva.
Basta con un navegador: las prácticas se ejecutan en cuadernos de JupyterLab.

Descripción

Hay problemas que no se resuelven escribiendo más código, sino cambiando de enfoque: una planificación con restricciones, un reparto de recursos, una ruta óptima sobre una red con costes. Quien solo conoce fuerza bruta se estrella contra el tamaño de la entrada, y quien aplica recetas sin entender la propiedad que las sostiene obtiene resultados incorrectos que parecen razonables.

El curso trabaja tres familias en profundidad. Cada técnica se presenta con el argumento que la justifica, se implementa en un cuaderno de JupyterLab y se somete a medición sobre entradas crecientes para contrastar la cota teórica con el tiempo real. Se incluyen casos donde la intuición falla: voraces que no son óptimos, memoización que consume demasiada memoria y grafos con pesos negativos.

El resultado es capacidad para atacar problemas de optimización que aparecen en planificación, logística, compiladores y sistemas distribuidos, y para argumentar la elección ante un equipo. Encaja de forma natural con los cursos de concurrencia y de construcción de compiladores, donde varias de estas técnicas reaparecen aplicadas a la asignación de recursos y al análisis de programas.

¿Para quién es este curso?

Desarrolladores con experiencia que abordan problemas de optimización y planificación en producción.
Personas que preparan procesos de selección técnica exigentes con ronda de algoritmia.
Perfiles de desarrollo que necesitan justificar ante su equipo por qué una solución escala y otra no.