Algoritmos Divide y Vencerás y Voraz

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando un algoritmo voraz se pretende conocer la dificultad del camino más favorable y para ello se va seleccionando una casilla escogida al azar de entre las tres posibles, hasta llegar al destino. ¿Qué podemos decir de este algoritmo?. Que aún siendo voraz existen otros criterios de selección con mejores resultados a priori. Que es voraz puesto que las decisiones no se replantean. Que no es voraz.

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando la técnica memoización se pretende conocer la dificultad del camino más favorable. ¿Cuál es la mejor complejidad espacial y temporal que se puede conseguir?. Espacial Θ(n) y temporal Θ(n⋅m). Espacial Θ(n)y temporal Θ(2^max(n,m)). Θ(n⋅m), tanto espacial como temporal.

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. En cuanto a la complejidad espacial y temporal, ¿Cuál de los siguientes esquemas algorítmicos resulta más eficiente para resolverlo?. Programación dinámica. Divide y vencerás. Ramificación y poda.

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur pero modificado de manera que el punto de partida es una casilla cualquiera (i,j) del mapa con nombre M (1 ≤ i ≤ n y 1 ≤ j ≤ m) y el destino en la casilla (n,m). Utilizando la técnica divide y vencerás se pretende conocer la dificultad del camino más favorable. ¿Cuál sería la recurrencia matemática más apropiada?. b. c. d.

En un mapa similar al del problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur se pretende conocer el número de caminos distintos que hay desde la casilla (1,1) hasta una casilla cualquiera (i,j) que pertenece al mapa. El mapa tiene n filas y m columnas ¿Cuál sería la recurrencia matemática más apropiada para abordarlo mediante Divide y vencerás?. a. b. c. d.

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando la técnica programación dinámica iterativa se pretende conocer la dificultad del camino más favorable. ¿Cuál es la mejor complejidad espacial y temporal que se puede conseguir?. Espacial Θ(min(n,m)) y temporal Θ(n⋅m). Θ(n+m), tanto espacial como temporal. Espacial Θ(n) y temporal Θ(n⋅m).

Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Se pretende encontrar el camino más favorable con la menor complejidad temporal posible. ¿Cuál sería la más ajustada para realizar todo el proceso?. O(n⋅m+m). O(n⋅m+n). O(n⋅m+n+m).

En un problema de optimización, si el dominio de las decisiones es un conjunto infinito. es probable que a través de programación dinámica se obtenga un algoritmo eficaz que lo solucione. una estrategia voraz puede ser la única alternativa. podremos aplicar el esquema vuelta atrás siempre que se trate de un conjunto infinito numerable.

Decid cuál de estas tres es la cota pesimista más ajustada al valor óptimo de la mochila discreta. El valor de una mochila que contiene todos los objetos restantes aunque se pase del peso máximo permitido. El valor de la mochila continua correspondiente. El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos.

La solución de programación dinámica iterativa del problema de la mochila discreta. ... tiene la restricción de que los pesos tienen que ser enteros positivos. ... tiene un coste temporal asintótico exponencial. ... calcula menos veces el valor de la mochila que la correspondiente solución de programación dinámica recursiva.

¿Qué tienen en común el algoritmo que obtiene el k-ésimo elemento más pequeño de un vector (estudiado en clase) y el algoritmo de ordenación Quicksort?. La división del problema en subproblemas. El número de llamadas recursivas que se hacen. La combinación de las soluciones a los subproblemas.

¿Para cuál de estos problemas de optimización se conoce una solución óptima voraz?. El problema de la mochila discreta. El problema de la asignación de coste mínimo de n tareas a n trabajadores cuando el coste de asignar la tarea i al trabajador j, cij está tabulado en una matriz. El árbol de recubrimiento mínimo para un grafo no dirigido con pesos.

Uno de estos tres problemas no tiene una solución trivial y eficiente que siga el esquema voraz. El problema de la mochila discreta sin limitación en la carga máxima de la mochila. El problema de la mochila continua. El problema del cambio sin restricciones en cuanto al número de monedas disponibles de cada clase.

¿Cuál de estas afirmaciones es falsa?. Todos los problemas de optimización tienen una solución voraz que es óptima sea cual sea la instancia a resolver. Hay problemas de optimización en los cuales el método voraz sólo obtiene la solución óptima para algunas instancias y un subóptimo para muchas otras instancias. Hay problemas de optimización para los cuales se puede obtener siempre la solución óptima utilizando una estrategia voraz.

Ante un problema que presenta una solución recursiva siempre podemos aplicar: Divide y vencerás. Programación Dinámica. Cualquiera de las dos anteriores.

Un problema se puede resolver por Divide y Vencerás siempre que: Cumpla el principio de optimalidad. Cumpla el teorema de reducción. Ninguna de las anteriores.

La serie de números de Fibonacci se define de la siguiente forma: Para implementar esta función podemos emplear... Divide y vencerás. Programación dinámica. Cualquiera de las dos anteriores.

La serie de números de Fibonacci se define de la siguiente forma: ¿Qué implementación de entre las siguientes supone el menor coste?. Divide y vencerás. Programación dinámica. Ambas tienen el mismo coste asintótico.

El problema de la mochila, ¿Puede solucionarse de forma óptima empleando la estrategia de divide y vencerás?. Sólo para el caso de la mochila con fraccionamiento. Sólo para el caso de la mochila sin fraccionamiento. Sí, se puede aplicar para ambos casos.

Para que un problema de optimización se pueda resolver mediante programación dinámica es necesario que: Cumpla el principio de optimalidad. Cumpla el teorema de reducción. Cumpla las dos anteriores.

Dada una solución recursiva a un problema, ¿Cómo podemos evitar la resolución de los mismos subproblemas muchas veces?. Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas pequeños. Resolver los subproblemas de menor a mayor y guardar su resultado en una tabla, inicializándola con los problemas pequeños. Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas más grandes.

Si aplicamos programación dinámica a un problema que también tiene solución por divide y vencerás podemos asegurar que…. El coste temporal se reduce y el espacial aumenta con respecto a la solución por DyV. El coste temporal aumenta y el espacial se reduce con respecto a la solución por DyV. Ninguna de las anteriores.

Cuándo utilizaremos Programación Dinámica en lugar de Divide y Vencerás?. Cuando se incrementa la eficacia. Cuando se incrementa la eficiencia. Cuando se reduce el coste espacial.

En programación dinámica, dónde almacenaremos los valores de los problemas resueltos?. En un vector unidimensional. En un vector bidimensional. Depende del problema.

Supongamos el problema de la mochila resuelto mediante Programación Dinámica y particularizado para n elementos y un peso máximo trasportable de P. ¿Es necesario calcular valores para toda la matriz auxiliar para obtener el resultado?. Si. No. Depende de los valores de n y P.

Un problema de optimización cuya solución se puede expresar mediante una secuencia de decisiones cumple el principio de optimalidad si, dada una secuencia óptima: Existe una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado. Existe al menos una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado. Cualquier subsecuencia de esa solución corresponde a la solución óptima de su subproblema asociado.

La programación dinámica, para resolver un problema, aplica la estrategia…. Se resuelven los problemas más pequeños y, combinando las soluciones, se obtienen las soluciones de problemas sucesivamente más grandes hasta llegar al problema original. Se descompone el problema a resolver en subproblemas más pequeños, que se resuelven independientemente para finalmente combinar las soluciones de los subproblemas para obtener la solución del problema original. Ninguna de las anteriores.

¿Qué esquema de programación es el adecuado para resolver el problema k-ésimo mínimo en un vector?. Programación Dinámica. Divide y Vencerás. Ninguno de los dos.

¿Con qué esquema de programación obtenemos algoritmos que calculan la distancia de edición entre dos cadenas?. Programación Dinámica. Divide y Vencerás. Ambos.

¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz (greedy) que es ó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.

Supongamos que un informático quiere subir a una montaña y como no es una persona normal 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 voraz. Un algoritmo divide y vencerás. Un algoritmo de programación dinámica.

La mejora que en general aporta la programación dinámica frente a la solución ingenua se consigue gracias al hecho de que... ... 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 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 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 número 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 (n log(n) ), donde n es el número de objetos a considerar.

Cuando la descomposición recursiva de un problema da lugar a subproblemas de tamaño similar, ¿qué esquema promete ser más apropiado?. El método voraz. Divide y vencerás, siempre que se garantice que los subproblemas no son del mismo tamaño. Programación dinámica.

En el método voraz... ... siempre se encuentra solución pero puede que no sea óptima. ... 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.

¿Cómo se vería afectada la solución voraz al problema de la asignación de tareas en el caso de que 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 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. La solución factible ya no estaría garantizada, es decir, pudiera ser que el algoritmo no llegue a solución alguna.

Sólo una de las tres afirmaciones siguientes es cierta. Cuál?. Mientras que el algoritmo de Prim va construyendo un único árbol de recubrimiento seleccionando aristas una a una, el algoritmo de Kruskal va construyendo un bosque que va uniendo añadiendo vértices hasta obtener un único árbol de recubrimiento. Los algoritmos de Prim y de Kruskal mantienen en todo momento un único árbol de recubrimiento, que crece añadiendo aristas o vértices. Mientras que el algoritmo de Prim va construyendo un único árbol de recubrimiento seleccionando vértices uno a uno, el algoritmo de Kruskal va construyendo un bosque que va uniendo añadiendo aristas, hasta obtener un único árbol de recubrimiento.

Qué diferencia (entre otras) hay entre el algoritmo de Prim y el de Kruskal?. El algoritmo de Prim es voraz y el de Kruskal no. El subgrafo que paso a paso va generando el algoritmo de Prim siempre contiene una única componente conexa mientras que el de Kruskal no tiene por qué. Aún siendo el grafo de partida totalmente conexo, el algoritmo de Kruskal garantiza la solución óptima mientras que el de Prim sólo garantiza un subóptimo.

Se pretende implementar mediante programación dinámica iterativa la función recursiva: 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); } ¿Cuál es la mejor estructura para el almacén?. a) int A. int A[]. int A [] [].

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 estructura para el almacén?. int A[]. int A. int A[] [].

¿Cuál de estas estrategias para calcular el n-ésimo elemento de la serie de Fibonacci (f(n) = f(n-1) + f(n-2) , f(1) = f(2) = 1) es más eficiente?. La estrategia voraz. Programación Dinámica. Las dos estrategias citadas serían similares en cuanto a eficiencia .

La solución recursiva ingenua a un determinado problema de optimización muestra estas dos características: por un lado, se basa en obtener soluciones optimas 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 voraz. Un algoritmo de programación dinámica. Un algoritmo de estilo Divide y Vencerás.

El problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo 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.

Si ante un problema de decisión existe un criterio de selección voraz entonces... al menos una solución factible está garantizada. la solución óptima está garantizada. ninguna de las otras dos opciones es cierta.

Se pretende implementar mediante programación dinámica iterativa la función recursiva: float f(unsigned x, int y){ if(y<0) return 0; float A= 0.0; if(v1[y] <= x) A= v2[y] + f(x-v1[y], y-1); float B = f(x, y-1); return min(A,2+B); } ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(x). O(y). O(xy).

¿Cuál 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 se 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.

Un tubo de n 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. Hace una evaluación exhaustiva "de fuerza bruta" de todas las posibles maneras de cortar el tubo consume un tiempo Θ(2^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 Θ(n!).

Se pretende implementar mediante programación dinámica iterativa la función recursiva: ¿Cuál es la mejor complejidad espacial que se puede conseguir? int f(int x, int y){ if(x <= y) return 1; return x + f(x-1, y); }. O(x^2). O(1). O(x).

Se pretende implementar mediante programación dinámica iterativa la función recursiva: 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); } ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(y^2). O(1). O(y). O(x^2).

Se pretende implementar mediante programación dinámica iterativa la función recursiva: 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); } ¿Cuál es la mejor complejidad temporal que se puede conseguir?. O(y). O(x*y). O(x).

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=1; 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(x^2). O(x). O(1).

La programación dinámica... En algunos casos se puede utilizar para resolver problemas de optimización con dominios continuos pero probablemente pierda su eficacia ya que puede disminuir drásticamente el número de subproblemas repetidos. Las otras dos opciones son ciertas. Normalmente se usa para resolver problemas de optimización con dominios discretizables puesto que las tablas se han de indexar con este tipo de valores.

Dado un problema de optimización, el método voraz... siempre obtiene una solución factible. siempre obtiene la solución óptima. garantiza la solución óptima sólo para determinados problemas.

Un algoritmo recursivo basado en el esquema divide y vencerás... Las demás opciones son verdaderas. ... será más eficiente cuanto más equitativa sea la división en subproblemas. ... nunca tendrá una complejidad exponencial.