4143020
Question 1
Question
¿Cuál de las siguientes afirmaciones sobre la programación dinámica es FALSA?
Answer
-
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
Question 2
Question
¿Cuál de las siguientes afirmaciones sobre la programación dinámica es CIERTA?
Answer
-
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
Question 3
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la competición internacional es CIERTA?
Answer
-
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
Question 4
Question
La formula usada para obtener P(i, j) para el problema de la competición internacional es:
Answer
-
P (i, j) = pP (i − 1, j) + (1 − p)P (i, j − 1)
-
RESPUESTA VACÍA
-
RESPUESTA VACÍA 2
-
RESPUESTA VACÍA 3
Question 5
Question
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:
Answer
-
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.
Question 6
Question
¿Cuál de las siguientes afirmaciones sobre el problema del cambio, resuelto mediante programación dinámica, es CIERTA?
Answer
-
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
Question 7
Question
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)
Answer
-
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))}
Question 8
Question
¿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?
Answer
-
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
Question 9
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la mochila, resuelto mediante programación dinámica es CIERTA?
Answer
-
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
Question 10
Question
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)
Answer
-
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))}
Question 11
Question
¿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?
Answer
-
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
Question 12
Question
¿Cual de las siguientes afirmaciones en el problema del Camino más corto en un grafo polietápico es CIERTA?
Answer
-
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
Question 13
Question
En el problema del Camino más corto en un grafo polietápico, ¿cuál de las siguientes afirmaciones es CIERTA?
Answer
-
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
Question 14
Question
¿Cual de las siguientes afirmaciones sobre el problema del viajante de comercio, resuelto mediante programación dinámica es CIERTA?
Answer
-
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
Question 15
Question
¿Cuál de las siguientes afirmaciones sobre el problema del viajante de comercio, resuelto mediante programación dinámica es FALSA?
Answer
-
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
Question 16
Question
¿Cuál de las siguientes afirmaciones sobre el backtracking es CIERTA?
Answer
-
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
Question 17
Question
¿Cuál de las siguientes afirmaciones sobre el backtracking es FALSA?
Answer
-
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
Question 18
Question
¿Cuál de las siguientes afirmaciones sobre el problema de las 8 reinas es CIERTA?
Answer
-
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
Question 19
Question
¿Cuál de las siguientes afirmaciones sobre el problema de las 8 reinas es CIERTA?
Answer
-
Es de orden O(nlogn)
-
Es de orden O(n)
-
Es de orden O(n!)
-
Es de orden O(n²)
Question 20
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la suma de los subconjuntos es FALSA?
Answer
-
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
Question 21
Question
¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos es CIERTA?
Answer
-
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
Question 22
Question
¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos es CIERTA?
Answer
-
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
Question 23
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?
Answer
-
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
Question 24
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?
Answer
-
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
Question 25
Question
¿Cuál de las siguientes afirmaciones sobre el problema de la mochila para materiales no particionables, resuelto por Backtracking es CIERTA?
Answer
-
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
Question 26
Question
Para el problema de la mochila para un volumen de 95...
Answer
-
535
-
550
-
335
-
350
Question 27
Question
¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas en general (númericos, MonteCarlo y Las Vegas), es CIERTA?
Answer
-
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
Question 28
Question
¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas en general (númericos, MonteCarlo y Las Vegas), es FALSA?
Answer
-
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)
Question 29
Question
¿Cuál de las siguientes afirmaciones será CIERTA si implementamos un algoritmo probabilista para obtener el valor de PI con 4 decimales (3.1416)?
Answer
-
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
Question 30
Question
¿Cuál de las siguientes afirmaciones será FALSA si implementamos un algoritmo probabilista para obtener el valor de PI con 4 decimales (3.1416)?
Answer
-
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)
Question 31
Question
¿Cuál de las siguientes afirmaciones sobre los algoritmos probabilistas numéricos vistos es CIERTA?
Answer
-
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
Question 32
Question
¿Cuál de las siguientes afirmaciones sobre el algoritmo MonteCarlo de VERIFICACIÓN DE MULTIPLICACIÓN DE MATRICES es CIERTA?
Answer
-
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
Question 33
Question
¿Cuál de las siguientes afirmaciones sobre el algoritmo Montecarlo de VERIFICACIÓN DE MULTIPLICACIÓN DE MATRICES es CIERTA?
Answer
-
Es de orden O(n³)
-
Es de orden O(n²)
-
Es de orden O(n)
-
Es de orden O(nlogn)
Question 34
Question
¿Cuál de las siguientes afirmaciones sobre el algoritmo Las Vegas para el problema de las 8 reinas es FALSA?
Answer
-
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
Question 35
Question
¿Cuál de las siguientes afirmaciones sobre el algoritmo Las Vegas para el problema de las 8 reinas es CIERTA?
Answer
-
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
Want to create your own Quizzes for free with GoConqr? Learn more.