Segundo parcial

La eficiencia de los algoritmos voraces se basa en el hecho de que... las decisiones tomadas nunca se reconsideran. 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.

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( n*log(n) ), 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.

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.

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

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

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

La mejora que en general aporta la programación dinámica frente a la solución ingenua se consigue gracia 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.

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

Se pretende aplicar la técnica memoización a la siguiente función recursiva: (imagen) 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.

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(x^2). O(x). O(1).

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad temporal que se puede conseguir?. O(y). O(x*y). O(x).

¿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.

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. 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.

Los algoritmos de programación dinámica hacen uso ... ... 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. ... de que se puede ahorrar cálculos guardando resultados anteriores en un almacén.

(imagen). 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. Se repiten muchos cálculos y ello se puede evitar haciendo uso de una estrategia voraz.

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 superior para el valor óptimo. Una cota inferior para el valor óptimo que a veces puede ser igual a este.

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.

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

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

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

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(y^2). O(y). O(x^2).

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.

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad temporal que se puede conseguir?. O(y). O(x). O(x*y).

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad temporal que se puede conseguir?. O(x^2). O(x). O(x*y).

¿Cuál de estas estrategias para calcular el n-ésimo elemento de la serie 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.

Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(y^2). O(x^2). O(y).