Se pretende aplicar la técnica memoización a la siguiente función recursiva:
int f( int x, int y ) {
if( x <= y ) return 1;
return x + f(x-1,y);
}
En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante? Temporal O(x-y) y espacial O(1) O(x-y), tanto temporal como espacial. Ninguna de las otras dos opciones es correcta.
La mejora que en general aporta la programación dinámica frente a la solución ingenua se consigue gracias al hecho de que ... El número de veces que se resuelven los subproblemas no tiene nada que ver con la eficiencia de los problemas resueltos mediante programación dinámica ... en la solución ingenua se resuelve pocas veces un número relativamente grande de subproblemas distintos. ... en la solución ingenua se resuelve muchas veces un número relativamente pequeño de subproblemas distintos.
El valor que se obtiene con el método voraz para el problema de la mochila discreta es ... ... una cota superior para el valor óptimo. ... una cota inferior para el valor óptimo que a veces puede ser igual a este. ... una cota inferior para el valor óptimo, pero que nunca coincide con este.
Un tubo de centímetros de largo se puede cortar en segmentos de 1 centímetro, 2 centímetros, etc. Existe una lista de los precios a los que se venden los segmentos de cada longitud. Una de las maneras de cortar el tubo es la que más ingresos nos producirá. Di cuál de estas tres afirmaciones es falsa. Hacer una evaluación exhaustiva ``de fuerza bruta'' de todas las posibles maneras de cortar el tubo consume un tiempo O(n!). Es posible evitar hacer la evaluación exhaustiva ``de fuerza bruta'' guardando, para cada posible longitud j < n el precio más elevado posible que se puede obtener dividiendo el tubo correspondiente. Hacer una evaluación exhaustiva ``de fuerza bruta'' de todas las posibles maneras de cortar el tubo consume un tiempo O(2^n).
Un informático quiere subir a una montaña y para ello decide que tras cada paso, el siguiente debe tomarlo en la dirección de máxima pendiente hacia arriba. Además, entenderá que ha alcanzado la cima cuando llegue a un punto en el que no haya ninguna dirección que sea cuesta arriba. ¿qué tipo de algoritmo está usando nuestro informático? un algoritmo de programación dinámica un algoritmo voraz. un algoritmo divide y vencerás.
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
unsigned f( unsigned x, unsigned v[] ) {
if (x==0)
return 0;
unsigned m = 0;
for ( unsigned k = 0; k < x; k++ )
m = max( m, v[k] + f( x-k, v ) );
return m;
}
¿Cuál es la mejor complejidad espacial que se puede conseguir? O(1) O(x^2) O(x).
En el método voraz ... ... es habitual preparar los datos para disminuir el coste temporal de la función que determina cuál es la siguiente decisión a tomar. ... el dominio de las decisiones sólo pueden ser conjuntos discretos o discretizables. ... siempre se encuentra solución pero puede que no sea la óptima.
La solución óptima al problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado ... ... se construye haciendo crecer un único árbol. ... puede construir un único árbol que va creciendo o bien construir un bosque de árboles que al final se injertan en un único árbol ... se construye haciendo crecer varios árboles que al final acaban injertados en un único árbol.
unsigned f( unsigned y, unsigned x){ // suponemos y >= x
if (x==0 || y==x) return 1;
return f(y-1, x-1) + f(y-1, x);
} O(y) O(x) O(x-y).
Supongamos que una solución recursiva a un problema de optimización muestra estas dos características: por un lado, se basa en obtener soluciones óptimas a problemas parciales más pequeños, y por otro, estos subproblemas se resuelven más de una vez durante el proceso recursivo. Este problema es candidato a tener una solución alternativa basada en ... ... un algoritmo del estilo de divide y vencerás. ... un algoritmo voraz. ... un algoritmo de programación dinámica.
¿Qué mecanismo se usa para acelerar el algoritmo de Prim? El TAD "Union-find" Mantener para cada vértice el vértice origen de la arista más corta hasta él. Mantener una lista de los arcos ordenados según su peso.
¿Cómo se vería afectada la solución voraz al problema de la asignación de tareas en el caso de que se incorporaran restricciones que contemplen que ciertas tareas no pueden ser adjudicadas a ciertos trabajadores ? Habría que replantearse el criterio de selección para comenzar por aquellos trabajadores con más restricciones en cuanto a las tareas que no pueden realizar para asegurar, al menos, una solución factible. Ya no se garantizaría la solución óptima pero sí una factible. La solución factible ya no estaría garantizada, es decir, pudiera ser que el algoritmo no llegue a solución alguna.
¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, un solución voraz óptima? El árbol de cobertura de coste mínimo de un grafo conexo El problema de la mochila discreta o sin fraccionamiento El problema de la mochila continua o con fraccionamiento.
Los algoritmos de programación dinámica hacen uso... ... de que la solución óptima se puede construir añadiendo a la solución el elemento óptimo de los elementos restantes, uno a uno. ... de que se puede ahorrar cálculos guardando resultados anteriores en un almacén ... de una estrategia trivial consistente en examinar todas las soluciones posibles.
De los problemas siguientes, indicad cuál no se puede tratar eficientemente como los otros dos El problema del cambio, o sea, el de encontrar la manera de entregar una cantidad de dinero usando el mínimo de monedas posibles El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y de sus valores El problema de cortar un tubo de forma que se obtenga el máximo beneficio posible.
En la solución al problema de la mochila continua, ¿por qué es conveniente la ordenación previa de los objetos? Para reducir la complejidad temporal en la toma de cada decisión de O(n) a O(1), donde n es el numero de objetos a considerar Porque si no se hace no es posible garantizar que la toma de decisiones siga un criterio voraz Para reducir la complejidad temporal en la toma de cada decisión de O(n^2) a O(nlogn), donde n es el numero de objetos a considerar.
Seleccione una: T(n) E O(n^2) T(n) E O(n!) T(n) E O(2^n).
Cuando la descomposición de los problemas da lugar a subproblemas de tamaño similar, ¿qué esquema promete ser más apropiado? El metodo voraz Divide y vencerás, siempre que se garantice que los problema no son del mismo tamaño Programación dinámica.
¿Como se vería afectada la solución voraz al problema de la asignación de tareas en el caso de que se incorporaran restricciones que contemplen que ciertas tareas no pueden ser adjudicadas a ciertos trabajadores? Ya no se garantizaría la solución óptima pero sí una factible Habría que replantearse el criterio de selecciones La solución factible ya no estaría garantizada, es decir, pudiera ser que el algoritmo o llegue a solución alguna.
Seleccione una: La estrategia voraz Programación dinámica Las dos estrategias citadas serían similares en cuanto a la eficiencia.
La solución de programación dinámica iterativa del problema de la mochila discreta... ... calcula menos veces el valor de la mochila que la correspondiente solución de programación dinámica recursiva ... tiene un coste temporal asintótico exponencial con respecto al número de objetos ... tiene la restricción de que los valores tienen que ser enteros positivos.
El problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo dirigido y ponderado... sólo se puede resolver con una estrategia voraz si existe una arista para cualquier par de vértices del grafo ... no se puede resolver en general con una estrategia voraz ... se puede resolver siempre con una estrategia voraz.
Seleccione una: O(1) O(y^2) O(y).
¿Cual de estas tres estrategias voraces obtiene un mejor valor para la mochila discreta? Meter primero los elementos de menor peso Meter primero los elementos de mayor valor específico o valor por unidad de peso Meter primero los elementos de mayor valor.
La eficiencia de los algoritmos voraces se basa en el hecho de que... ... antes de tomar una decisión de comprueba si satisface las restricciones del problema ... con antelación, las posibles decisiones se ordenan de mejor a peor ... las decisiones tomadas nunca se reconsideran.
¿Cual de los siguientes pares de problemas son equivalentes en cuanto al tipo de solución(óptima, factible, etc) aportada por el método voraz? El fontanero diligente y mochila continua El fontanero diligente y asignación de tareas El fontanero diligente y el problema del cambio.
Un algoritm recursivo basado en el esquema divide y vencerás... Las demás opciones son verdaderas ... nunca tendrá una complejidad exponencial ... será más eficiente cuanto más equitativa sea la división en subproblemas.
Dado un problema de optimización, el método voraz... Siempre obtiene una solución factible Siempre obtiene una solución óptima garantiza la solución óptima sólo para determinados problemas.
Si ante un problema de decisión existe un criterio de selección voraz entonces... la solución óptima está garantizada al menos una solución factible está garantizada Ninguna de las otras dos es cierta.
¿Cual de los siguientes pares de problemas son equivalente en cuanto al tipo de solución(óptima, factible, etc) aportada por el método voraz? El fontanero diligente y el problema del cambio La mochila continua y la asignación de tareas La mochila discreta y la asignación de tareas.
int f(int x, int y){
if (x<=y) return 1;
return x + f(x-1,y);
}
Seleccione una: O(1) O(x^2) O(x).
Seleccione una: int A[] [] int A[] int A.
Seleccione una La recursion puede ser infinita y por tanto es necesario organizarla según el esquema iterativo de programación dinámica Se repiten muchos cálculos y ello se puede evitar usando programación dinámica Se repiten muchos cálculos y ello se puede evitar haciendo uso de una estrategia voraz.
Seleccione una: int A[] int A[][] int A.
|
