Programación dinámica

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