Tecnología · 3o de Preparatoria

Ideas de aprendizaje activo

Programación Dinámica

La programación dinámica se presta maravillosamente al aprendizaje activo porque los estudiantes construyen intuición sobre la optimización al resolver problemas concretos. Al trabajar con subproblemas y estructuras, los estudiantes ven directamente cómo la memorización y la construcción de tablas evitan cálculos redundantes, haciendo el aprendizaje experiencial.

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

• 25–45 min
• Parejas → Toda la clase
• 4 actividades

Actividad 01

• Enseñanza entre Pares
• 30 min · Parejas

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.

¿Cómo la programación dinámica evita la recomputación de subproblemas ya resueltos?

Consejo de Facilitación

Para la actividad de Pares sobre Fibonacci, observe si los estudiantes identifican correctamente los cálculos repetidos en la versión recursiva antes de implementar la memoización.

Qué observar

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.

• Comprender
• Aplicar
• Analizar
• Crear
• Autogestión
• Habilidades de Relación

Actividad 02

• Sesión de Exploración al Aire Libre
• 45 min · Grupos pequeños

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.

¿De qué manera la memorización y la tabulación optimizan el rendimiento de algoritmos recursivos?

Consejo de Facilitación

Al trabajar en Grupos Pequeños con la Tabla de la Mochila 0/1, asegúrese de que cada rol esté activo y que el grupo discuta cómo cada entrada de la tabla se basa en las anteriores.

Qué observar

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.

• Recordar
• Comprender
• Analizar
• Conciencia Social
• Autoconciencia
• Toma de Decisiones

Actividad 03

• Sesión de Exploración al Aire Libre
• 35 min · Toda la clase

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.

¿Por qué la programación dinámica es esencial para resolver problemas de optimización complejos de manera eficiente?

Consejo de Facilitación

Durante la Clase Completa de Simulación de Multiplicación de Matrices, guíe a la clase para que reconozca patrones en la tabla de costos y cómo se derivan los valores óptimos de subproblemas más pequeños.

Qué observar

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.

• Recordar
• Comprender
• Analizar
• Conciencia Social
• Autoconciencia
• Toma de Decisiones

Actividad 04

• Sesión de Exploración al Aire Libre
• 25 min · Individual

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.

¿Cómo la programación dinámica evita la recomputación de subproblemas ya resueltos?

Qué observar

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.

• Recordar
• Comprender
• Analizar
• Conciencia Social
• Autoconciencia
• Toma de Decisiones

Algunas notas para enseñar esta unidad

Enfoque la enseñanza de la programación dinámica en la visualización de la estructura del problema y el flujo de soluciones. Use ejemplos guiados donde los estudiantes construyan tablas paso a paso, fomentando la discusión sobre por qué ciertos subproblemas se resuelven antes y cómo sus soluciones se combinan. Evite presentarla solo como una técnica de codificación; enfatice su poder para modelar y resolver problemas de optimización complejos.

Los estudiantes demostrarán comprensión al explicar cómo se identifican subproblemas superpuestos y subestructuras óptimas en problemas dados. Podrán justificar la elección de un enfoque de programación dinámica y trazar el llenado de una tabla para encontrar una solución óptima.

---

Cuidado con estas ideas erróneas

• Durante la actividad de Pares: Fibonacci Recursivo vs. Memoizado, los estudiantes pueden creer que la optimización solo es necesaria para problemas extremadamente grandes.

  Redirija a los estudiantes a comparar los tiempos de ejecución medidos para Fibonacci(30) en ambas versiones; pídales que discutan si la mejora observada justifica la complejidad adicional de la memoización incluso para tamaños moderados.

• Al construir la Tabla de la Mochila 0/1 en Grupos Pequeños, los estudiantes podrían pensar que el enfoque top-down es inherentemente superior.

  Después de completar la tabla bottom-up, plantee un escenario donde solo se necesite una subparte específica de la solución; discuta cómo un enfoque top-down con memoización podría ser más eficiente en ese caso particular.

• Durante la Simulación de Multiplicación de Matrices, los estudiantes podrían asumir que las decisiones óptimas para subproblemas se toman de forma aislada.

  Guíe la discusión sobre cómo el costo de multiplicar una cadena de matrices (A_i...A_j) depende de dónde se coloque el paréntesis final, vinculando explícitamente las soluciones óptimas de subproblemas (A_i...A_k) y (A_{k+1}...A_j) a la solución global.

---

Metodologías usadas en este resumen

• Enseñanza entre Pares
• Sesión de Exploración al Aire Libre