F. A. M.
Quiz by , created more than 1 year ago

Cuestionario 7, 8 y 9

118
0
0
F. A. M.
Created by F. A. M. almost 9 years ago
Close

Cuestionario 7,8 y 9

Question 1 of 35

1

¿Cuál de las siguientes afirmaciones sobre la programación dinámica es FALSA?

Select one of the following:

  • 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

Explanation

Question 2 of 35

1

¿Cuál de las siguientes afirmaciones sobre la programación dinámica es CIERTA?

Select one of the following:

  • 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

Explanation

Question 3 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la competición internacional es CIERTA?

Select one of the following:

  • 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

Explanation

Question 4 of 35

1

La formula usada para obtener P(i, j) para el problema de la competición internacional es:

Select one of the following:

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

  • RESPUESTA VACÍA

  • RESPUESTA VACÍA 2

  • RESPUESTA VACÍA 3

Explanation

Question 5 of 35

1

En el algoritmo de FLOYD (caminos mínimos entre todos los pares de nodos de un grafo), en la iteración k-ésima se obtiene:

Select one of the following:

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

Explanation

Question 6 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema del cambio, resuelto mediante programación dinámica, es CIERTA?

Select one of the following:

  • 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

Explanation

Question 7 of 35

1

La formula recursiva que se utiliza para obtener el valor de C(i, j) en el problema del cambio, usando programación dinámica es: (V(i) es el valor de la moneda i)

Select one of the following:

  • 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))}

Explanation

Question 8 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema del cambio, resuelto por programación dinámica es CIERTA en el caso de que haya una única solución?

Select one of the following:

  • 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

Explanation

Question 9 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila, resuelto mediante programación dinámica es CIERTA?

Select one of the following:

  • 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

Explanation

Question 10 of 35

1

La formula recursiva que se utiliza para obtener el valor de C(i,j) en el problema de la mochila, usando programación dinámica es: (p es precio de un material, v es volumen de un material y C es coste de la mochila)

Select one of the following:

  • 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))}

Explanation

Question 11 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila, resuelto mediante programación dinámica es CIERTA en el caso de que haya una única solución?

Select one of the following:

  • 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

Explanation

Question 12 of 35

1

¿Cual de las siguientes afirmaciones en el problema del Camino más corto en un grafo polietápico es CIERTA?

Select one of the following:

  • 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

Explanation

Question 13 of 35

1

En el problema del Camino más corto en un grafo polietápico, ¿cuál de las siguientes afirmaciones es CIERTA?

Select one of the following:

  • 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

Explanation

Question 14 of 35

1

¿Cual de las siguientes afirmaciones sobre el problema del viajante de comercio, resuelto mediante programación dinámica es CIERTA?

Select one of the following:

  • 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

Explanation

Question 15 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema del viajante de comercio, resuelto mediante programación dinámica es FALSA?

Select one of the following:

  • 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

Explanation

Question 16 of 35

1

¿Cuál de las siguientes afirmaciones sobre el backtracking es CIERTA?

Select one of the following:

  • 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

Explanation

Question 17 of 35

1

¿Cuál de las siguientes afirmaciones sobre el backtracking es FALSA?

Select one of the following:

  • 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

Explanation

Question 18 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de las 8 reinas es CIERTA?

Select one of the following:

  • 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

Explanation

Question 19 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de las 8 reinas es CIERTA?

Select one of the following:

  • Es de orden O(nlogn)

  • Es de orden O(n)

  • Es de orden O(n!)

  • Es de orden O(n²)

Explanation

Question 20 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la suma de los subconjuntos es FALSA?

Select one of the following:

  • 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

Explanation

Question 21 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos es CIERTA?

Select one of the following:

  • 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

Explanation

Question 22 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos es CIERTA?

Select one of the following:

  • 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

Explanation

Question 23 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?

Select one of the following:

  • 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

Explanation

Question 24 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?

Select one of the following:

  • 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

Explanation

Question 25 of 35

1

¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?

Select one of the following:

  • 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

Explanation

Question 26 of 35

1

Para el problema de la mochila para un volumen de 95...

Select one of the following:

  • 535

  • 550

  • 335

  • 350

Explanation

Question 27 of 35

1

¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas en general (númericos, MonteCarlo y Las Vegas), es CIERTA?

Select one of the following:

  • 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

Explanation

Question 28 of 35

1

¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas en general (númericos, MonteCarlo y Las Vegas), es FALSA?

Select one of the following:

  • 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)

Explanation

Question 29 of 35

1

¿Cuál de las siguientes afirmaciones será CIERTA si implementamos un algoritmo probabilista para obtener el valor de PI con 4 decimales (3.1416)?

Select one of the following:

  • 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

Explanation

Question 30 of 35

1

¿Cuál de las siguientes afirmaciones será FALSA si implementamos un algoritmo probabilista para obtener el valor de PI con 4 decimales (3.1416)?

Select one of the following:

  • 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)

Explanation

Question 31 of 35

1

¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas numéricos vistos es CIERTA?

Select one of the following:

  • 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

Explanation

Question 32 of 35

1

¿Cuál de las siguientes afirmaciones sobre el algoritmo MonteCarlo de VERIFICACIÓN DE MULTIPLICACIÓN DE MATRICES es CIERTA?

Select one of the following:

  • 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

Explanation

Question 33 of 35

1

¿Cuál de las siguientes afirmaciones sobre el algoritmo Montecarlo de VERIFICACIÓN DE MULTIPLICACIÓN DE MATRICES es CIERTA?

Select one of the following:

  • Es de orden O(n³)

  • Es de orden O(n²)

  • Es de orden O(n)

  • Es de orden O(nlogn)

Explanation

Question 34 of 35

1

¿Cuál de las siguientes afirmaciones sobre el algoritmo Las Vegas para el problema de las 8 reinas es FALSA?

Select one of the following:

  • 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

Explanation

Question 35 of 35

1

¿Cuál de las siguientes afirmaciones sobre el algoritmo Las Vegas para el problema de las 8 reinas es CIERTA?

Select one of the following:

  • 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

Explanation

Previous
Check answer
Next