ALG-P2

¿Para qué se utiliza el TAD "Union-find" en el algoritmo de Kruskal?. Para comprobar si dos vértices son equivalentes. Para comprobar si un vértice ya ha sido visitado. Para comprobar si un arco forma ciclos.

Los algoritmos de programación dinámica hacen uso... ... 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 que la solución óptima se puede construir añadiendo a la solución el elemento óptimo de los elementos restantes, uno a uno.

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*(y-1) + f(x,y-2); } En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante?. Ninguna de las otras dos opciones es correcta. O(y - x), tanto temporal como espacial. Temporal O(x ⋅ y) y espacial 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(x ⋅ y). O(x). O(y).

¿Cuál 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 el problema del cambio. El fontanero diligente y la mochila continua. El fontanero diligente y la asignación de tareas.

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 a , donde 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) a O(1), donde n es el número de objetos a considerar.

La eficiencia de los algoritmos voraces se basa en el hecho de que... ...antes de tomar una decisión se comprueba si satisface las retricciones del problema. ...con antelación, las posibles decisiones se ordenan de mejor a peor. ...las decisiones tomadas nunca se reconsideran.

La solución óptima al problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado... ...debe construirlo arista a arista: vértice a vértice no puede ser. ...debe construirlo vértice a vértice: arista a arista no puede ser. ...puede construirlo tanto vértice a vértice como arista a arista.

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. Es posible evitar hacer la evaluación exhaustiva "de fuerza bruta'' guardando, para cada posible longitud 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!). Hacer una evaluación exhaustiva "de fuerza bruta'' de todas las posibles maneras de cortar el tubo consume un tiempo Θ(2^n).

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

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 temporal que se puede conseguir?. O(y). O(x). O(x ⋅ y).

¿Cuál de estas estrategias voraces obtiene siempre un mejor valor para la mochila discreta?. Ninguna de las otras dos opciones es cierta. Meter primero los elementos de mayor valor. Meter primero los elementos de mayor valor específico o valor por unidad de peso.

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 y = 1; y < x; y++) m = max(m, v[y] + f(x - y, v)); return m; } ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(x). O(x · y). O(1).

¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz óptima?. El problema de la mochila discreta o sin fraccionamiento. El árbol de cobertura de coste mínimo de un grafo conexo. El problema de la mochila continua con fraccionamiento.

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. ...se construye haciendo crecer varios árboles que al final acaban injertados en 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.

De los problemas siguientes, indicad cuál no se puede tratar eficientemente como los otros dos: El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y sus valores. El problema de cortar un tubo de forma que se obtenga el máximo beneficio posible. El problema del cambio, o sea, el de encontrar la manera de entregar una cantidad de dinero usando el mínimo de monedas posibles.

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 la restricción de que los valores de los objetos tienen que ser números discretos o discretizables. ...tiene la restricción de que los pesos de los objetos tienen que ser valores discretos o discretizables.

¿Qué mecanismo se usa para acelerar el algoritmo de Prim?. Mantener para cada vértice su "padre" más cercano. El TAD "Union-find". Mantener una lista de los arcos ordenados según su peso.

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, y - 2); } En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante?. O(y - x), tanto temporal como espacial. Temporal O(x · y) y espacial O(x). Ninguna de las otras dos opciones es correcta.

En el método voraz... ...siempre se encuentra solución pero puede que no sea la óptima. ...el dominio de las decisiones sólo pueden ser conjuntos discretos o discretizables. ...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.

Cuando se calculan los coeficientes binomiales usando la siguiente recursión, ¿qué problema se da y cómo se puede resolver?. Se repiten muchos cálculos y ello se puede evitar haciendo uso de una estrategia voraz. La recursión 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.

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. Para reducir la complejidad temporal en la toma de cada decisión: de O(n^2) a O(nlogn), 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.

La programación dinámica... ...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. ...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.

El valor que se obtiene con el método voraz para el problema de la mochila discreta es... ...una cota inferior para el valor óptimo, pero que nunca coincide con este. ...una cota inferior para el valor óptimo que a veces puede ser igual a este. ...una cota superior para el valor óptimo.

El problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado... ...se puede resolver siempre con una estrategia voraz. ...no se puede resolver en general con una estrategia voraz. ...sólo se puede resolver con una estrategia voraz si existe una arista para cualquier par de vértices del grafo.

La eficiencia de los algoritmos voraces se basa en el hecho de que... ...con antelación, las posibles decisiones se ordenan de mejor a peor. ...antes de tomar una decisión se comprueba si satisface las retricciones del problema. ...las decisiones tomadas nunca se reconsideran.

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) + y; } En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante?. O(x - y), tanto temporal como espacial. Ninguna de las otras dos opciones es correcta. Temporal O(x − y) y espacial O(1).

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 muchas veces un número relativamente pequeño de subproblemas distintos. ...en la solución ingenua se resuelve pocas veces un número relativamente grande 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.

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 y = 1; y < x; y++) m = max(m, v[y] + f(x - y, v)); return m; } ¿Cuál es la mejor complejidad temporal que se puede conseguir?. O(x). O(x^2). O(x · y).

¿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?. Programación dinámica. La estrategia voraz. Las dos estrategias citadas serían similares en cuanto a eficiencia.

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.

¿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?. La solución factible ya no estaría garantizada, es decir, pudiera ser que el algoritmo no llegue a solución alguna. 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.