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