Optimización de rutas
Nombre: ___________________________
Fecha: ____________________________
Puntaje: __________________________
1.
¿Qué es la programación dinámica?
Una técnica que consiste en resolver problemas superponiendo subproblemas y almacenando sus soluciones para reutilizarlos
Una técnica que divide un problema en subproblemas independientes y los resuelve de forma recursiva sin repeticiones
Un algoritmo de ordenamiento
2.
¿Cuál es la propiedad que se refiere a que la solución óptima de un problema se puede construir a partir de soluciones óptimas de sus subproblemas? (escriba la palabra o frase corta)
Respuesta: ____________________________________________
3.
¿Cuál es la complejidad temporal del algoritmo de DP para encontrar el número de caminos en una cuadrícula de m x n sin obstáculos?
O(m*n)
O(m+n)
O(2^(m+n))
O(m^2*n)
4.
En una cuadrícula con obstáculos, la tabla DP se inicializa con 1 en la celda de inicio. Si esa celda es un obstáculo, ¿con qué valor se inicializa?
Se inicializa con -1
Se inicializa con 1
Se inicializa con 0
5.
Si una celda contiene un obstáculo, ¿cuál es el número de caminos desde el inicio hasta esa celda? (escriba el número)
Respuesta: ____________________________________________
6.
¿Cuál de los siguientes NO es un paso típico en el diseño de un algoritmo de programación dinámica?
Definir la estructura de subproblemas
Identificar subproblemas repetidos
Escribir la recurrencia
Implementar recursión sin memoización
7.
En una cuadrícula de 3x3 celdas (filas 0..2, columnas 0..2), ¿cuántos caminos hay desde (0,0) hasta (2,2) moviéndose solo hacia abajo y hacia la derecha?
4
9
6
3
8.
En una cuadrícula de 2x2 celdas, ¿cuántos caminos hay desde la esquina superior izquierda hasta la inferior derecha moviéndose solo abajo y derecha? (escriba el número)
Respuesta: ____________________________________________
9.
¿En qué orden se suele llenar la tabla DP en el problema de caminos en grid?
Columna por columna
Fila por fila
En orden inverso de diagonales
10.
Complete la frase: El principio de optimalidad de Bellman dice que cualquier subpolítica de una política óptima es también _____.
Respuesta: ____________________________________________
11.
En un videojuego, un personaje debe moverse desde la esquina superior izquierda a la inferior derecha esquivando enemigos. Los movimientos permitidos son solo derecha y abajo. ¿Qué técnica usarías para calcular la ruta más corta?
Búsqueda en anchura
Algoritmo A*
Algoritmo genético
Programación dinámica
12.
Si en la cuadrícula se permiten movimientos en las cuatro direcciones (arriba, abajo, izquierda, derecha), ¿sigue siendo aplicable directamente la programación dinámica?
Sí, con la misma recurrencia
No, se necesita otro método como BFS o Dijkstra
No, porque se formarían ciclos
Sí, pero hay que llenar la tabla en otro orden
13.
El número de subproblemas en un grid de m x n es del orden de: (escriba la expresión algebraica)
Respuesta: ____________________________________________
14.
¿Cuál es la principal ventaja de la programación dinámica sobre la fuerza bruta?
Evita recalcular subproblemas
Menor uso de memoria
Es más fácil de implementar
15.
Para el problema del número de caminos en un grid con obstáculos, ¿cuál es la recurrencia correcta?
Si la celda no es obstáculo, dp[i][j] = dp[i-1][j] + dp[i][j-1]; si es obstáculo, dp[i][j] = 0
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1
dp[i][j] = sumatoria de dp[i-1][j] y dp[i][j-1] sin importar obstáculos
dp[i][j] = dp[i-1][j] * dp[i][j-1]
16.
En una cuadrícula con costos no negativos, si una celda es obstáculo, el valor de dp[i][j] en el problema de camino de costo mínimo se establece como: (escriba la palabra en español)
Respuesta: ____________________________________________
17.
Para optimizar memoria en el problema de caminos en grid, ¿cuántas filas de la tabla DP se necesitan guardar simultáneamente?
m
1
2
18.
En un grid de 5x5 celdas (filas 0..4, columnas 0..4), ¿cuántos caminos hay de (0,0) a (4,4) sin obstáculos?
56
70
35
126
19.
En un grid unidimensional (solo una fila), el número de caminos de una celda a otra moviéndose siempre a la derecha es: (escriba el número)
Respuesta: ____________________________________________
20.
¿Cuál de los siguientes NO es un problema típico resuelto con programación dinámica?
Subsecuencia común más larga
Búsqueda binaria
Problema de la mochila