WorksheetsProgramación dinámica
Total questions: 10
Worksheet time: 5mins
Para resolver un problema, desarrollar un algoritmo utilizando PD es mejor que utilizando la técnica Greedy
Sí, siempre
No, nunca
No necesariamente
Los algoritmos greedy pertenecen a programación dinámica
¿Cuál de estas características/conceptos no corresponde a la PD?
La ecuación de recurrencia
La división del problema en subproblemas más pequeños
La memorización de soluciones
La aproximación de resultados
La ecuación de recurrencia en la programación dinámica ...
No se utiliza. Corresponde a División y conquista
Corresponde al pseudocódigo del problema
Nos permite calcular recursivamente un problema en base a sus subproblemas
Indica que problemas se memorizan
¿Cuáles propiedades requiere un problema para poder resolverse en forma óptima mediante programación dinámica?
subestructura óptima y elección greedy
subestructura óptima y memorizacion de resultados
subestructura óptima y problemas superpuestos
recurrencia y memorización
Todo problema que se puede resolver mediante programación dinámica tiene una complejidad temporal polinómica
Verdadero
Falso
El concepto "problemas superpuestos" ...
Refiere a que el mismo subproblema vuelve a aparecer en otra rama de la recursión
Refiere a que para resolver un problema se deben resolver 2 o mas subproblemas
Corresponde a la dimensionalidad del problema resuelto con programación dinámica
Corresponde a que la optimalidad de cada subproblema se superpone con la optimalidad global
¿Cuál de los siguientes problemas NO se resuelven con programación dinámica?
Problema de la mochila
Cambio mínimo
Maximización de intervalos con peso
Árbol recubridor mínimo
El problema de la mochila, de n elementos y capacidad W, utilizando programación dinámica se puede resolver ...
En forma pseudopolinomial con complejidad O(nW)
En forma polinomial con complejidad O(nW)
En forma exponencial con complejidad O(n!W)
No se puede resolver de forma optima con programación dinámica
En forma polinomial con complejidad O(n^2)
El problema de Intervalos con costos utilizando programación dinámica
Requiere ordenar los intervalos por tiempo de finalización
Tiene como caso base el valor 0 si no se consideran intervalos
En cada subproblema se evalua incluir o no un intervalo
Toda las opciones
Ninguna de las opciones
¿Cuál es el impacto de la técnica de memorización dentro de la programación dinámica?
Aumenta la complejidad temporal y espacial
Disminuye la complejidad temporal y aumenta la espacial
Disminuye la complejidad espacial y la temporal
Permite la resolución recursiva del problema
No tiene impacto, es un artilugio matemático para demostrar la optimalidad de la solución
