F. A. M.
Test por , creado hace más de 1 año

Cuestionario 7, 8 y 9

118
0
0
F. A. M.
Creado por F. A. M. hace casi 9 años
Cerrar

Cuestionario 7,8 y 9

Pregunta 1 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 2 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 3 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 4 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

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

  • RESPUESTA VACÍA

  • RESPUESTA VACÍA 2

  • RESPUESTA VACÍA 3

Explicación

Pregunta 5 de 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:

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 6 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 7 de 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)

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 8 de 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?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 9 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 10 de 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)

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 11 de 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?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 12 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 13 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 14 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 15 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 16 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 17 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 18 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 19 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • Es de orden O(nlogn)

  • Es de orden O(n)

  • Es de orden O(n!)

  • Es de orden O(n²)

Explicación

Pregunta 20 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 21 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 22 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 23 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 24 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 25 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 26 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 535

  • 550

  • 335

  • 350

Explicación

Pregunta 27 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 28 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 29 de 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)?

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 30 de 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)?

Selecciona una de las siguientes respuestas posibles:

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

Explicación

Pregunta 31 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 32 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 33 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • Es de orden O(n³)

  • Es de orden O(n²)

  • Es de orden O(n)

  • Es de orden O(nlogn)

Explicación

Pregunta 34 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Pregunta 35 de 35

1

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

Selecciona una de las siguientes respuestas posibles:

  • 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

Explicación

Anterior
Revisar respuesta
Siguiente