F. A. M.
Quiz von , erstellt am more than 1 year ago

Cuestionario 7, 8 y 9

118
0
0
F. A. M.
Erstellt von F. A. M. vor fast 9 Jahre
Schließen

Cuestionario 7,8 y 9

Frage 1 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 2 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 3 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 4 von 35

1

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

Wähle eine der folgenden:

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

  • RESPUESTA VACÍA

  • RESPUESTA VACÍA 2

  • RESPUESTA VACÍA 3

Erklärung

Frage 5 von 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:

Wähle eine der folgenden:

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

Erklärung

Frage 6 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 7 von 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)

Wähle eine der folgenden:

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

Erklärung

Frage 8 von 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?

Wähle eine der folgenden:

  • 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

Erklärung

Frage 9 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 10 von 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)

Wähle eine der folgenden:

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

Erklärung

Frage 11 von 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?

Wähle eine der folgenden:

  • 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

Erklärung

Frage 12 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 13 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 14 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 15 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 16 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 17 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 18 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 19 von 35

1

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

Wähle eine der folgenden:

  • Es de orden O(nlogn)

  • Es de orden O(n)

  • Es de orden O(n!)

  • Es de orden O(n²)

Erklärung

Frage 20 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 21 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 22 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 23 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 24 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 25 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 26 von 35

1

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

Wähle eine der folgenden:

  • 535

  • 550

  • 335

  • 350

Erklärung

Frage 27 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 28 von 35

1

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

Wähle eine der folgenden:

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

Erklärung

Frage 29 von 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)?

Wähle eine der folgenden:

  • 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

Erklärung

Frage 30 von 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)?

Wähle eine der folgenden:

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

Erklärung

Frage 31 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 32 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 33 von 35

1

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

Wähle eine der folgenden:

  • Es de orden O(n³)

  • Es de orden O(n²)

  • Es de orden O(n)

  • Es de orden O(nlogn)

Erklärung

Frage 34 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Frage 35 von 35

1

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

Wähle eine der folgenden:

  • 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

Erklärung

Vorherige
Antwort prüfen
Nächste