Tecnología · 3o de Preparatoria · Pensamiento Computacional y Algoritmos Complejos · I Bimestre

Programación Dinámica

Los estudiantes resuelven problemas de optimización utilizando programación dinámica, identificando subproblemas superpuestos y estructuras óptimas.

• Aprendizajes Esperados SEP
• SEP EMS: Optimización de Procesos Computacionales
• SEP EMS: Algoritmos y Programación

Acerca de este tema

La programación dinámica permite resolver problemas de optimización complejos al identificar subproblemas superpuestos y estructuras óptimas. Los estudiantes dividen un problema grande en subproblemas más pequeños que se resuelven una sola vez y se almacenan para reutilizarse, evitando la recomputación costosa de algoritmos recursivos. En el plan SEP de Preparatoria, este tema integra el pensamiento computacional con algoritmos eficientes, alineado con estándares de optimización de procesos computacionales.

Los alumnos exploran técnicas como la memorización en enfoques top-down y la tabulación bottom-up, aplicándolas a ejemplos clásicos como la secuencia de Fibonacci, el problema de la mochila o la multiplicación de cadenas de matrices. Estas estrategias reducen la complejidad exponencial a polinomial, preparando a los estudiantes para desafíos reales en programación y ciencias de la computación.

El aprendizaje activo beneficia este tema porque los estudiantes construyen tablas de estados colaborativamente, implementan código y comparan rendimientos cronometrados. Estas prácticas convierten conceptos abstractos en experiencias tangibles, fortaleciendo la comprensión de la optimalidad y fomentando habilidades de depuración y análisis.

Preguntas Clave

1. ¿Cómo la programación dinámica evita la recomputación de subproblemas ya resueltos?
2. ¿De qué manera la memorización y la tabulación optimizan el rendimiento de algoritmos recursivos?
3. ¿Por qué la programación dinámica es esencial para resolver problemas de optimización complejos de manera eficiente?

Objetivos de Aprendizaje

• Calcular la solución óptima para problemas de optimización utilizando el enfoque de programación dinámica, demostrando la aplicación de subproblemas superpuestos.
• Comparar la eficiencia de un algoritmo recursivo simple con su contraparte de programación dinámica (memorización o tabulación) para la secuencia de Fibonacci.
• Diseñar un algoritmo de programación dinámica para resolver un problema de optimización dado, identificando la relación de recurrencia y la estructura óptima.
• Explicar cómo la memorización y la tabulación evitan la recomputación de subproblemas en algoritmos recursivos.

Antes de Empezar

Recursividad

Por qué: Los estudiantes deben comprender cómo funcionan las funciones que se llaman a sí mismas para poder aplicar y optimizar con programación dinámica.

Algoritmos Básicos y Estructuras de Datos

Por qué: Es necesario tener una base en la creación y análisis de algoritmos, así como en el uso de estructuras como arreglos o listas para almacenar resultados.

Vocabulario Clave

Programación Dinámica	Una técnica algorítmica que divide un problema complejo en subproblemas más pequeños y superpuestos, resolviendo cada subproblema solo una vez y almacenando sus resultados para su uso futuro.
Memorización (Top-Down)	Un enfoque de programación dinámica donde la solución se calcula de forma recursiva, pero los resultados de las llamadas a funciones se almacenan (memorizan) para evitar recalcularlos.
Tabulación (Bottom-Up)	Un enfoque de programación dinámica donde la solución se construye de forma iterativa, comenzando con los casos base más pequeños y construyendo progresivamente hacia la solución del problema principal.
Subproblemas Superpuestos	Subproblemas que aparecen múltiples veces en la descomposición recursiva de un problema más grande, lo que hace que su resolución repetida sea ineficiente sin técnicas de optimización.
Estructura Óptima	La propiedad de un problema de optimización donde una solución óptima para el problema general contiene soluciones óptimas para sus subproblemas.

Cuidado con estas ideas erróneas

Idea errónea común

La programación dinámica solo sirve para problemas muy grandes.

Qué enseñar en su lugar

Es útil desde problemas medianos porque el ahorro en recomputación es notable incluso en tamaños moderados. Actividades de comparación de tiempos de ejecución en pares ayudan a los estudiantes a medir directamente la mejora y cuestionar su idea inicial.

Idea errónea común

Siempre es mejor el enfoque bottom-up que top-down.

Qué enseñar en su lugar

Ambos son válidos según el problema; top-down evita calcular subproblemas innecesarios. Simulaciones grupales de tablas incompletas muestran ventajas contextuales, aclarando que la elección depende de la estructura del problema.

Idea errónea común

Los subproblemas óptimos se resuelven independientemente sin conexión.

Qué enseñar en su lugar

Dependen unos de otros en una estructura específica. Construir tablas colaborativamente visualiza estas dependencias, ayudando a los estudiantes a ver cómo las soluciones parciales construyen la global mediante discusión guiada.

Ideas de aprendizaje activo

Enseñanza entre Pares: Fibonacci Recursivo vs. Memoizado

Los estudiantes escriben funciones recursivas para Fibonacci y las modifican con un diccionario para memorización. Comparan el número de llamadas a la función usando contadores. Discuten el ahorro computacional observado.

30 min·Parejas

Grupos Pequeños: Tabla de la Mochila 0/1

En grupos, construyen una tabla dinámica para el problema de la mochila con pesos y valores dados. Llenan la matriz fila por fila considerando decisiones óptimas. Verifican la solución final contra enfoques greedy.

45 min·Grupos pequeños

Clase Completa: Simulación de Multiplicación de Matrices

Proyecta un problema de cadenas de matrices; la clase llena una tabla de costos colectivamente. Identifican subproblemas superpuestos en voz alta. Calculan el orden óptimo paso a paso.

35 min·Toda la clase

Individual: Optimización Manual de Sendero Más Corto

Cada estudiante resuelve un grafo pequeño con programación dinámica bottom-up, dibujando la tabla de distancias mínimas. Marca las dependencias entre celdas. Comparte su tabla con un compañero para validación.

25 min·Individual

Conexiones con el Mundo Real

• Los ingenieros de software utilizan programación dinámica para optimizar la asignación de recursos en sistemas de redes, como en el enrutamiento de paquetes de datos para minimizar la latencia en servicios de streaming como Netflix.
• Los científicos de datos aplican programación dinámica en algoritmos de bioinformática para alinear secuencias de ADN o proteínas, buscando la máxima similitud entre ellas, lo cual es crucial para la investigación genética y el desarrollo de fármacos.
• Los analistas financieros emplean programación dinámica para resolver problemas de optimización de carteras de inversión, buscando la combinación de activos que maximice el retorno esperado para un nivel de riesgo dado.

Ideas de Evaluación

Verificación Rápida

Presente a los estudiantes el problema de calcular el n-ésimo número de Fibonacci. Pida que escriban el pseudocódigo para una solución recursiva simple y luego modifiquenlo para incluir memorización, explicando dónde se almacenan y recuperan los resultados.

Boleto de Salida

Entregue a cada estudiante una tarjeta con la descripción de un problema de optimización (ej. problema de la suma de subconjuntos). Pida que identifiquen si el problema tiene subproblemas superpuestos y estructura óptima, y que propongan si la programación dinámica sería un enfoque adecuado, justificando brevemente.

Pregunta para Discusión

Plantee la siguiente pregunta al grupo: '¿Por qué un algoritmo recursivo sin optimización para calcular la secuencia de Fibonacci hasta un número grande (ej. 40) es significativamente más lento que uno que utiliza tabulación?'. Guíe la discusión para que resalten la recomputación de los mismos valores.

Preguntas frecuentes

¿Qué es la programación dinámica en preparatoria?

Es una método para optimizar algoritmos recursivos al resolver y almacenar subproblemas superpuestos una vez. En el currículo SEP, se aplica a problemas como Fibonacci o mochila, reduciendo complejidad de exponencial a polinomial. Los estudiantes aprenden a detectar estructuras óptimas para eficiencia computacional real.

¿Cómo evita la programación dinámica la recomputación?

Usa memorización o tabulación para guardar resultados de subproblemas ya calculados. En recursión top-down, un caché evita llamadas repetidas; bottom-up llena tablas sistemáticamente. Esto optimiza rendimiento, clave en problemas complejos del plan SEP de Tecnología.

¿Cuál es la diferencia entre memorización y tabulación?

La memorización es top-down: resuelve recursivamente y almacena en un diccionario solo lo necesario. La tabulación es bottom-up: construye una tabla completa desde subproblemas pequeños. Ambas logran optimalidad; las actividades prácticas ayudan a elegir según el contexto del problema.

¿Cómo usar aprendizaje activo para enseñar programación dinámica?

Implementa actividades como construir tablas en grupos para la mochila o comparar códigos Fibonacci en pares, midiendo tiempos reales. Estas experiencias hacen visible el ahorro computacional y las dependencias de subproblemas. Discusiones posteriores consolidan la comprensión, alineando con estándares SEP de pensamiento computacional.