DA - Programacion Dinamica

En el diseño de algoritmos basados en Programación Dinámica, ¿cuál de las siguientes afirmaciones es falsa?: Mediante el uso de la memorización se evitan repeticiones en el cálculo de los subproblemas. Mediante el enfoque ascendente se transforman algoritmos recursivos en iterativos. La técnica puede aplicarse cuando no hay solapamiento entre los subproblemas.

Si un problema concreto es resuelto mediante un algoritmo usando programación dinámica: El orden de complejidad será polinomial. La memoria necesaria está en orden de n2 a lo sumo. Deben conocerse las soluciones para los caso 0, 1 ó los k menores. Ninguna es cierta.

El orden de complejidad del problema de la mochila, siendo n el número de objetos y M su capacidad, resuelto con programación dinámica es de: O(M*n). O(n^2). O(M^2). O(M*n^2).

El problema del viajante de comercio puede ser resuelto eficazmente mediante: Vuelta atrás. Programación Dinámica. Divide y Vencerás. Todas son ciertas.

La solución del problema de la Mochila con programación dinámica necesita actualizar una matriz atendiendo a la siguiente función. Para una celda dada, su valor: Será el dado por la función atendiendo al valor de x_n. Será el máximo de los dos valores. Será el mínimo de los dos valores. Ninguna es cierta.

En el diseño de algoritmos basados en Programación Dinámica, la definición recursiva de la solución proporciona, de forma directa, una implementación recursiva del problema. que siempre mejora la eficiencia del algoritmo de fuerza bruta. que siempre iguala la eficiencia del algoritmo de fuerza bruta. que puede mejorar la eficiencia del algoritmo de fuerza bruta. Ninguna es cierta.

A la hora de resolver el problema de los caminos mínimos mediante el algoritmo de Floyd se utiliza: "n" representa el número de nodos "p" representa el número de nodos intermedios en el camino. un array tridimensional de dimensiones n*n*p. un array bidimensional de dimensiones n*n que actualizará p veces. un array bidimensional de dimensiones n*p que se actualizará n veces. Todas las soluciones resuelven el problema con la misma eficiencia.

La Programación Dinámica: se aplica a problemas DyV en los que hay solapamiento entre subproblemas. reduce el número de subproblemas mediante memorización. no necesariamente tiene que eliminar la recursividad del problema original. aplica el enfoque ascendente para resolver los subproblemas más pequeños.

El problema de la mochila resuelto con PD mediante una matriz n*M: "n" es el número de objetos "M" es la capacidad de la mochila. puede suponer un problema en memoria si hay muchos objetos o la mochila es muy grande. se ejecutan en orden lineal. no siempre da la mejor solución.