Cuestiones
ayuda
option
Mi Daypo

TEST BORRADO, QUIZÁS LE INTERESERecopilación de preguntas (2)

COMENTARIOS ESTADÍSTICAS RÉCORDS
REALIZAR TEST
Título del test:
Recopilación de preguntas (2)

Descripción:
Algoritmia

Autor:
AVATAR

Fecha de Creación:
07/01/2019

Categoría:
Universidad

Número preguntas: 40
Comparte el test:
Facebook
Twitter
Whatsapp
Comparte el test:
Facebook
Twitter
Whatsapp
Últimos Comentarios
No hay ningún comentario sobre este test.
Temario:
Dado el problema del laberinto con tres movimientos, ¿se puede aplicar un esquema de programación dinámica para obtener un camino de salida? No, con este esquema se puede conocer el número total de caminos distintos que conducen a la salida pero no se puede saber la composición de ninguno de ellos. Si, en caso de existir con este esquema siempre se puede encontrar un camino de salida No, para garantizar que se encuentra un camino de salida hay que aplicar métodos de búsqueda exhaustiva como vuelta atrás o ramificación y poda.
En ausencia de cotas optimistas y pesimistas, la estrategia de vuelta atrás... ... debe recorrer siempre todo el árbol. ... no se puede usar para resolver problemas de optimización. ... no recorre todo el árbol si hay manera de descartar subárboles que representan conjuntos de soluciones no factibles.
Decid cuál de estas tres es la cota optimista más ajustada al valor óptimo de la mochila discreta: El valor de una mochila que contiene todas los objetos aunque se pase del peso máximo permitido. El valor de la mochila continua correspondiente. El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos.
El coste temporal asintótico de insertar un elemento en un vector ordenado de forma que continue ordenado es: Ω(n^2) O(n) O(log n).
¿En ramificación y poda, tiene sentido utilizar la cota optimista de los nodos como criterio para ordenar la lista de nodos vivos? Sí, en el caso de que se ordene la lista de nodos vivos, siempre debe hacerse según el criterio de la cota optimista. No, la cota optimista sólo se utiliza para determinar si una n-tupla es prometedora. Sí, aunque no es una garantía de que sea una buena estrategia de búsqueda.
¿Qué estrategia de búsqueda es a priori más apropiada en un esquema de vuelta atrás? Explorar primera los nodos que están más completados. En el esquema de vuelta atrás no se pueden definir estrategias de búsqueda. Explorar primero los nodos con mejor cota optimista.
Sea la siguiente relación de recurrencia: (imagen) Las otras dos opciones son ambas ciertas g(n) = log n g(n) = √n.
Si f ∈ Ω(g1) y f ∈ Ω(g2) entonces: f ∈ Ω(g1+g2) f ∉ Ω(mín(g1,g2)) f ∈ Ω(g1*g2).
(imagen) O(n^2) O(n) O(log n).
El esquema de vuelta atrás... Se puede aplicar a cualquier tipo de problema aunque el coste temporal es elevado. Las otras dos opciones son ambas verdaderas. Garantiza que encuentra la solución Óptima & cualquier problema de selección discreta.
En el esquema de ramificación y poda, ¿qué estructura es la más adecuada si queremos realizar una exploración por niveles? Cola de prioridad Pila Cola.
¿Qué nos proporciona la media entre el coste temporal asintótico (o complejidad temporal) en el peor caso y el coste temporal asintótico en el mejor caso? Nada de interés El coste temporal promedio El coste temporal asintótico en el caso medio.
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de programación dinámica. En cuanto a la complejidad temporal, ¿cuál es la mejora de la versión recursiva con memoización frente a la recursiva ingenua que se obtiene a partir del esquema divide y vencerás? La mejora no está garantizada puesto que la versión recursiva con memoización podría ser peor que la obtenida a partir del esquema divide y vencerás. De una complejidad exponencial que se obtendría con la ingenua se reduciría a polinómica con la de memoización. De una complejidad cuadrática que se obtendría con la ingenua se reduciría a lineal con la de memoización.
¿Qué complejidad se obtiene a partir de la relación de recurrencia T(n) = 8T(n/2) + n^3 con T(1) = O(1)? O(n^3 log n) O(n^3) O(n log n).
(imagen) La complejidad temporal exacta es Θ(n^2) La complejidad temporal en el mejor de los casos es Ω(n) La complejidad temporal en el mejor de los casos es Ω(1).
El esquema voraz... Las otras dos opciones son ambas falsas. Garantiza encontrar una solución a cualquier problema, aunque puede que no sea óptima. Puede que no encuentre una solución pero si lo hace se garantiza que es óptima.
Cuando la descomposición de un problema de lugar a subproblemas de tamaño similar al original, muchos de los cuales se repiten, ¿qué esquema es a priori más apropiado? Ramificación y poda. Divide y vencerás. Programación dinámica.
(imagen) La complejidad temporal en el peor de los casos es O(n^2) La complejidad temporal en el peor de los casos es O(2^n) La complejidad temporal en el mejor de los casos es Ω(n^2).
(imagen) Θ(n) Θ(n^2) Θ(n x m).
Dado el problema del laberinto con tres movimientos, se pretende conocer la longitud del camino de salida más corto. Para ella se aplica el esquema voraz con un criterio de selección que consiste en elegir primero el movimiento "Este" siempre que la casilla sea accesible. Si no lo es se descarta ese movimiento y se prueba con "Sureste" y por último, si este tampoco es posible, se escoge el movimiento "Sur". ¿Qué se puede decir del algoritmo obtenido? Que es un algoritmo voraz pero sin garantía de solucionar el problema… Que en realidad no es un algoritmo voraz pues el criterio de selección no lo es. Que en realidad no es un algoritmo voraz pues las decisiones que se toman no deberían reconsiderarse.
Si el coste temporal de un algoritmo es T(n), ¿cuál de las siguientes situaciones es imposible? T(n) ∈ Θ(n) y T(n) ∈ Ω(n^2) T(n) ∈ O(n) y T(n) ∈ Θ(n) T(n) ∈ Ω(n) y T(n) ∈ Θ(n^2).
Se desea resolver el problema de la potencia enésima (x^n), asumiendo que n es par y que se utilizará la siguiente recurrencia: pot.(x, n) = pot.(x, n/2) * pot.(x, n/2); ¿Qué esquema resulta ser más eficiente en cuanto al coste temporal? En este caso tanto programación dinámica como divide y vencerás resultan ser equivalentes en cuanto a la complejidad temporal. Programación dinámica. Divide y vencerás.
De las siguientes afirmaciones marca la que es verdadera. El esquema de vuelta atrás no es compatible con el uso conjunto de cotas pesimistas y optimistas. Las cotas pesimistas no son compatibles con un esquema de vuelta atrás. En un esquema de vuelta atrás, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles.
Dado un problema de minimización resuelto mediante un esquema de ramificación y poda, ¿qué propiedad cumple una cota optimista? Asegura un ahorro en la comprobación de todas las soluciones factibles. Siempre es mayor o igual que la mejor solución pasible alcanzada. Las otras dos opciones son ambas falsas.
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1,1) hasta la casilla (n, m) y para ello se aplica el esquema programación dinámica para obtener un algoritmo lo más eficiente posible en cuanto a complejidad temporal y espacial. ¿Cuáles serían ambas complejidades? Temporal Θ(n x m) y espacial Θ(n x m) Temporal Θ(n x m) y espacial Θ(mín{n,m}) Temporal Θ(máx{n, m}) y espacial Θ(máx{n, m}).
(imagen) f(n) ∈ O(g(n)) y g(n) ∈ O(f(n)) f(n) ∈ O(g(n)) pero g(n) ∉ O(f(n)) g(n) ∈ O(f(n)) pero f(n) ∉ O(g(n)).
Se desea obtener todas las permutaciones de una lista compuesta por n elementos. ¿Qué esquema es el más adecuado? Vuelta atrás, es el esquema más eficiente para este problema. Divide y vencerás, puesto que la división en sublistas se podría hacer en tiempo constante. Ramificación y poda, puesto que con buenas funciones de cota es más eficiente que vuelta atrás.
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de divide y vencerás. ¿Cuál sería la recurrencia apropiada para el caso general? nc(n, m) = nc(n - 1, m) + nc(n, m - 1) + nc(n - 1, m - 1) nc(n, m) = nc(n - 1, m) * nc(n, m - 1) * nc(n - 1, m - 1) Ninguna de las otras dos recurrencias se corresponde con un esquema de divide y vencerás.
Un tubo de n centímetros de largo se puede cortar en segmentos de 1 centímetro, 2 centímetros, etc... Existe una lista de los precios a los que se venden los segmentos de cada longitud. Una de las maneras de cortar el tubo es la que más ingresos nos producirá. Se quiere resolver el problema mediante vuelta atrás. ¿Cual sería la forma más adecuada de representar las posibles soluciones? Una tabla que indique, para cada posición donde se va a cortar, cada uno de los posibles valores acumulados. Un vector de booleanos. Un par de enteros que indiquen los cortes realizados y el valor acumulada.
De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. Θ(n) ⊂ Θ(n^2) n + n log n ∈ Ω(n) O(2^(log n)) ⊂ O(n^2).
En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución hasta el momento... Las otras dos opciones son ambas verdaderas… Pueden eliminar vectores que representan posibles soluciones factibles. Garantizan que no se va a explorar todo el espacio de soluciones posibles.
En el problema del viajante de comercio (travelling salesman problem) queremos listar todas las soluciones factibles. Lo más importante es conseguir una cota pesimista adecuada. Las diferencias entre ramificación y poda y vuelta atrás son irrelevantes en este caso. La más adecuado sería usar una técnica de ramificación y poda ya que es muy importante el orden en el que se exploran las soluciones parciales. El orden en el que se exploran las soluciones parciales no es relevante; por ello, la técnica ramificación y poda no aporta nada con respecto a vuelta atrás.
Dado un problema de maximización resuelto mediante un esquema de ramificación y poda, ¿qué ocurre si la cota optimista resulta ser un valor excesivamente elevado? Que se podría explorar menos nodos de los necesarios. Que se podría podar el nodo que conduce a la solución óptima. Que se podría explorar más nodos de los necesarios.
Un algoritmo recursivo basado en el esquema divide y vencerás... Las otras dos opciones son ambas verdaderas. ... alcanza su máxima eficiencia cuando el problema de tamaño n se divide en a problemas de tamaño n/a. ... nunca tendrá un coste temporal asintótico (o complejidad temporal) exponencial.
Dado el problema de las torres de Hanoi resuelto mediante divide y vencerás, ¿cuál de las siguientes relaciones de recurrencia expresa mejor su complejidad temporal para el caso general, siendo n el número de discos? T(n) = 2T(n - 1) + 1 T(n) = 2T(n - 1) + n T(n) = T(n - 1) + n.
Una de las prácticas de laboratorio consistió en el cálculo empírico de la complejidad temporal promedio del algoritmo de ordenación de vectores Quicksort tomando como centinela el elemento del vector que ocupa la posición central. ¿Cuál es el orden de complejidad que se obtuvo? n log^2 n n^2 n log n.
Se desea ordenar una lista enlazada de n elementos haciendo usco del algoritmo Mergesort. En este caso, al tratarse de una lista, la complejidad temporal asintótica de realizar la división en subproblemas resulta ser lineal con el tamaño de esa lista. ¿Cuál sería entonces el coste temporal de realizar dicha ordenación? Θ(n log n) Θ(n^2) Ninguna de las otras dos opciones es cierta.
(imagen) La complejidad temporal exacta es Θ(n log n) La complejidad temporal en el mejor de los casos es Ω(1) La complejidad temporal en el mejor de los casos es Ω(n).
Dado el problema del laberinto con tres movimientos, ¿cuál de las estrategias siguientes proveería de una cota optimista para ramificación y poda? Suponer que ya no se van a realizar más movimientos. Las otras dos estrategias son ambas válidas Suponer que en adelante todas las casillas del laberinto son accesibles.
¿Qué ocurre si la cota pesimista de un nodo se corresponde con una solución que no es factible? Que el algoritmo sería más lento pues se explorarían más nodos de los necesarios. Nada especial, las cotas pesimistas no tienen por qué corresponderse con soluciones factibles. Que el algoritmo sería incorrecto pues podría descartarse un nodo que conduce a la solución óptima.
Denunciar test Consentimiento Condiciones de uso