Cuestionario 7,8 y 9

La obtención del término n-ésimo de Fibonacci usando una tabla para no repetir llamadas se basa en uno de los enfoques de la programación dinámica

Cuando se aplica en problemas de optimización, puede generar soluciones que no son óptimas.

Los algoritmos basados en este método suelen tener un orden de complejidad algorítmica alto

Hay problemas de optimización en los que no se cumple el principio de optimalidad de Bellman

Sus dos enfoques se basan en el principio de optimalidad de Bellman

Solo se aplica a problemas de optimización

Para obtener el optimo en una etapa no es necesaria obtener el optimo en las etapas previas

Cuando se aplica a problemas de optimizacion (segundo enfoque, de los dos posibles) cualquier subsolución de la solución optima, también ha de ser óptima

Se basa en el enfoque de la programación dinámica y consiste en evitar llamadas recúrsivas repetidas

Ninguna de las anteriores es cierta

La solución recursiva es mas eficiente que la iterativa

La solución recursiva vista en clase no genera llamadas recursivas repetidas

P (i, j) = pP (i − 1, j) + (1 − p)P (i, j − 1)

RESPUESTA VACÍA

RESPUESTA VACÍA 2

RESPUESTA VACÍA 3

La distancia y camino mínimo entre todos los pares de nodos, usando únicamente como nodos intermedios, nodos de númeración menor que k.

La distancia y camino mínimo entre todos los pares de nodos, usando únicamente como Nodo intermedio el nodo k.

La distancia y camino mínimo entre todos los pares de nodos, usando únicamente como nodos intermedios, nodos de númeración mayor o igual que k.

La distancia y camino mínimo entre todos los pares de nodos, usando únicamente como nodos intermedios, nodos de númeración menor o igual que k.

El elemento C(i,j) de la matriz resultado nos da el número de monedas necesario para obtener un cambio j usando única y exclusivamente la i-ésima moneda.

El elemento C(i,j) de la matriz resultado nos da el número de monedas necesario para obtener un cambio i usando única y exclusivamente la j-ésima moneda.

El elemento C(i,j) de la matriz resultado nos da el número de monedas necesario para obtener un cambio j usando única y exclusivamente las i primeras monedas

El elemento C(i,j) de la matriz resultado nos da el número de monedas necesario para obtener un cambio i usando única y exclusivamente las j primeras monedas

C(i,j) = min{C(i-1,j), 1 + C(i, j-V(i))}

C(i,j) = min{C(i-1,j), 1 + C(i-1, j-V(i))}

C(i,j) = min{C(i-1,j), C(i-1, j-V(i))}

C(i,j) = min{C(i-1,j), C(i, j-V(i))}

Si el elemento C(i,j) es igual al C(i-1, j) la moneda i no entra en la solución

Si el elemento C(i,j) es igual al C(i, j-1) la moneda i no entra en la solución

Si el elemento C(i,j) es igual al C(i,j-V(i)) la moneda i no entra en la solución

Si el elemento C(i,j) es igual al C(i-V(i), j) la moneda i no entra en la solución

El elemento C(i,j) de la matriz resultado nos da el valor máximo de la mochila para un volumen máximo de i, usando los j primeros materiales

El elemento C(i,j) de la matriz resultado nos da el valor máximo de la mochila para un volumen máximo de j, usando exclusivamente los i primeros materiales

El elemento C(i,j) de la matriz resultado nos da el valor máximo de la mochila para un volumen máximo de j, usando el material i

El elemento C(i,j) de la matriz resultado nos da el valor máximo de la mochila para un volumen máximo de i, usando el material j

C(i,j) = max{C(i-1, j), p(i)*v(i) + C(i, j - v(i))}

C(i,j) = max{C(i-1, j), C(i, j - v(i))}

C(i,j) = max{C(i-1, j), C(i - 1, j - v(i))}

C(i,j) = max{C(i-1, j), p(i)*v(i) + C(i - 1, j - v(i))}

Si C(i,j) es igual al C(i-1, j) el material i no entra en la solución

Si C(i,j) es igual al C(i, j-1) el material i no entra en la solución

Si C(i,j) es igual al C(i, j-v(i)) el material i no entra en la solución

Si C(i,j) es igual al C(i-v(i), j) el material i no entra en la solución

La solución ha de ser única

Cualquier subcamino del camino solución es optimo

Si hay varias soluciones, estas pueden tener un número distinto de etapas

Si hay varias soluciones, estas pueden tener distintas longitudes

El camino mínimo hasta el nodo i de la etapa n, se obtiene de obtener el mínimo de todos los caminos óptimos de los nodos de la etapa n-1 mas el peso del lado que enlaza el nodo de la etapa n-1 con el nodo i

El camino mínimo hasta el nodo i de la etapa n, se obtiene de obtener el camino optimo de cualquier nodo de la etapa n-1 mas el peso del lado que enlaza el nodo de la etapa n-1 con el nodo i

Todas las respuestas son falsa

El camino mínimo hasta el nodo i de la etapa n, se obtiene de obtener el maximo de todos los caminos óptimos de los nodos de la etapa n-1 mas el peso del lado que enlaza el nodo de la etapa n-1 con el nodo i

El algoritmo tiene un orden de complejidad cuadratico

La solución obtenida cumple el principio de optimalidad de Bellman

La solución siempre será única

Puede que la solución proprocionada no sea óptima

La solución tiene n-1 lados, siendo n el número de nodos

La solución obtenida siempre será optima

El algoritmo tiene un orden de complejidad muy alto y para valores de n altos es inviable

Puede tener varias soluciones

Se puede emplear para obtener todas las soluciones de un problema y por tanto se puede usar en problemas de optimización

Todos los caminos del árbol resultante dan lugar a una solución correcta

Cuando resuelve un problema de optimización, todas las soluciones obtenidas a lo largo de las etapas del algoritmo son óptimas

No es necesaria la división de la solución en etapas

El conjunto de posibles soluciones a evaluar ha de ser lo más pequeño posible pero ha de contener a todas las soluciones

En problemas de optimización el conjunto de posibles soluciones a evaluar puede que no contenga la solución optima

Cuando el conjunto de posibles soluciones sea excesivamente grande habrá que usar pruebas mas restrictivas que poden y reduzcan dicho conjunto lo antes posible

El tamaño del conjunto de posibles soluciones a explorar y la complejidad de las pruebas o condiciones son los aspecto mas influyentes en la eficacia del método

La condición para ver que dos reinas no se apuntan en diagonal se satisface cuando no se repiten números en el vector que contiene la solución

La versión que se ha visto en clase es de orden O(n²)

El vector solución será una permutación de los 8 primeros números

El vector solución puede tener valores repetidos

Es de orden O(nlogn)

Es de orden O(n)

Es de orden O(n!)

Es de orden O(n²)

El problema puede tener más de una solución

Para encontrar la solución optima hay que evaluar todas las soluciones

Si los elementos están ordenados ascendentemente, si un elemento no entra en la solución, el siguiente si podría entrar en la misma

Ordenando los elementos de menor a ascendente se obtiene un criterio mas eficiente al elegir los candidatos de la solución

Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de camino mas corto

Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de menos lados

Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de más lados

Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de camino más largo

Las condiciones para añadir un nodo son tres, que el nodo que selecciones no haya sido seleccionado antes, que este enlazado al último y que si es el último tiene que estar conectado al primero

RESPUESTA VACÍA 1

RESPUESTA VACÍA 2

RESPUESTA VACÍA 3

Si hay más de un material, el material más barato nunca entrará en la solución

Si en la solución optima hay dos materiales, éstos serán los dos más caros

En la solución al problema, la mochila no tiene porqué llenarse por completo

En la solución óptima siempre entrará el material más caro

El valor de la mochila en la solución obtenida puede ser mayor, igual o menor que si se resuelve con un algoritmo voraz para materiales particionables

El valor de la mochila en la solución obtenida es siempre igual que si se resuelve para un algoritmo voraz para materiales particionables

El valor de la mochila en la solución obtenida es siempre menor o igual que si se resuelve para un algoritmo voraz para materiales particionables

El valor de la mochila en la solución obtenida es siempre mayor que si se resuelve para un algoritmo voraz para materiales particionables

La función limite que se usa para la poda se obtiene resolviendo el problema de la mochila para materiales particionables usando un algoritmo voraz aplicado a las materiales aún no considerados

La función limite que se usa para la poda se obtiene resolviendo el problema de la mochila para materiales particionables usando un algoritmo voraz aplicado a las materiales ya considerados

La función limite que se usa para la poda se obtiene resolviendo el problema de la mochila para materiales particionables usando un algoritmo voraz aplicado a las materiales ya considerados pero para materiales no particionables usando el algoritmo voraz

La función limite que se usa para la poda se obtiene resolviendo el problema de la mochila para materiales no particionables usando un algoritmo voraz aplicado a las materiales aún no considerados

535

550

335

350

Para una misma entrada, producen siempre la misma salida

Siempre dan lugar a un error, aunque éste podría ser muy pequeño

Siempre dan una respuesta que es exacta o es muy aproximada a la solución correcta

Pueden producir una respuesta con una probabilidad de error menor que la probabilidad de que el equipo físico fallase cuando ejecuta un algoritmo

Si se admiten una pequeña probabilidad de error pueden ser mucho mas eficientes que algunos algoritmos deterministas

Para una misma entrada pueden producir distintas salidas en distintas ejecuciones

Pueden dar lugar a un callejón sin salida del cual no se obtenga solución alguna

La respuesta a un algoritmo probabilista es siempre probabilista (nunca es totalmente correcta)

Un algoritmo Las Vegas puede producir una salida de 3.1411

Un algoritmo de Montecarlo podría no generar una solución y llegar a un callejón sin salida

Un algoritmo probabilista numérico podría obtener el intervalo (3.009, 3.13)

Ninguna de las respuestas es correcta

Un algoritmo Montecarlo podría generar la salida 3.1415

Un algoritmo de las Vegas podría generar una solución y llegar a un callejón sin salida

Un algoritmo la Vegas puede producir una salida de 3.1412

Un algoritmo probabilista numérico podría generar el intervalo (3.1400, 3.1420)

El valor de la integral se obtiene multiplicando la longitud del intervalo por el valor medio de valores de la función, no de la x, comprendidos entre a y b

El método de la aguja de Buffon obtiene el valor de Pi con un margen de error muy pequeño aunque se realicen pocas pruebas

La única ventaja del algoritmo probabilista para integración numérica frente al determinista basado en el método de los trapecios se produce en integral de cuatro o mas dimensiones

El método probabilista de la integración numérica produce resultados mas precisos que cualquier método determinista independientemente del número de dimensiones de la integral

La probabilidad de error no depende del número de veces que se ejecute

Si se ejecuta 3 veces la probabilidad de error es de 1/3

Si se ejecuta 3 veces la probabilidad de error es de 1/8

Si se ejecuta 4 veces la probabilidad de error es de 1/4

Es de orden O(n³)

Es de orden O(n²)

Es de orden O(n)

Es de orden O(nlogn)

Se pueden obtener las 92 soluciones usando dicho algoritmo

Cuando se realiza una ejecución para obtener una posible solución, una vez que se coloca una reina, ésta ya no cambia de posición

Siempre produce una solución válida

Por término medio se necesitan 8 pruebas para obtener una solución válida

Puede que conduzca a un callejón sin salida y que no genere una solución

Es poco eficiente comparado con el determinista cuando el número de reinas es elevado

Se puede generar una solución donde una reina sea amenazada por otra

Si se genera una reina errónea, puede retroceder y probar otra reina