Cuestiones
ayuda
option
Mi Daypo

TEST BORRADO, QUIZÁS LE INTERESEProgramación Dinámica y Algoritmos Voraces

COMENTARIOS ESTADÍSTICAS RÉCORDS
REALIZAR TEST
Título del test:
Programación Dinámica y Algoritmos Voraces

Descripción:
Algoritmia

Autor:
AVATAR

Fecha de Creación:
27/11/2018

Categoría:
Universidad

Número preguntas: 28
Comparte el test:
Facebook
Twitter
Whatsapp
Comparte el test:
Facebook
Twitter
Whatsapp
Últimos Comentarios
No hay ningún comentario sobre este test.
Temario:
¿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.
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.
Dada la suma de la recurrencia: (imagen) ¿cuál de las siguientes afirmaciones es cierta? T(n) ∈ Θ(n^2) T(n) ∈ Θ(n!) T(n) ∈ Θ(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? 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 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 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.
Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿Cuál es la mejor estructura para el almacén? int A int A[] int A [] [].
Se pretende implementar mediante programación dinámica iterativa la función recursiva: (imagen) ¿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 (imagen) es más eficiente? La estrategia voraz Programación Dinámica Las dos estrategias citadas serían similares en cuanto a eficiencia .
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 un 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.
De los problemas siguientes, indicad cuál no se puede tratar eficientemente como los otros dos: 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 El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y de sus valores.
La solución de programación dinámica iterativa del problema de la mochila discreta... ... calcula menos veces al 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 un á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: (imagen) ¿Cuál es la mejor complejidad espacial que se puede conseguir? O(1) O(y^2) O(y).
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 que a veces puede ser igual a este una cota inferior para el valor óptimo, pero que nunca coincide con este una cota superior para el valor óptimo.
¿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íficio o valor por unidad de pero 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.
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 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 muchas veces un número relativamente pequeño de subproblemas distintos.
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: (imagen) ¿Cuál es la mejor complejidad espacial que se puede conseguir? O(x^2) O(1) O(x).
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(1) O(y).
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.
Denunciar test Consentimiento Condiciones de uso