Cuestiones
ayuda
option
Mi Daypo

TEST BORRADO, QUIZÁS LE INTERESEDivide y Vencerás y Programación Dinámica

COMENTARIOS ESTADÍSTICAS RÉCORDS
REALIZAR TEST
Título del test:
Divide y Vencerás y Programación Dinámica

Descripción:
Algoritmia

Autor:
AVATAR

Fecha de Creación:
27/11/2018

Categoría:
Universidad

Número preguntas: 26
Comparte el test:
Facebook
Twitter
Whatsapp
Comparte el test:
Facebook
Twitter
Whatsapp
Últimos Comentarios
No hay ningún comentario sobre este test.
Temario:
¿Qué esquema algorítmico utiliza el algoritmo de ordenación Quicksort? Divide y Vencerás Programación Dinámica Backtracking.
Ante un problema que presenta una solución recursiva siempre podemos aplicar: Divide y vencerás Programación Dinámica Cualquiera de las dos anteriores.
En cual de los siguientes casos no se puede aplicar el esquema Divide y Vencerás: Cuando los subproblemas son de tamaños muy diferentes Cuando el problema no cumple el principio de optimalidad Se puede aplicar en ambos casos.
Dado el algoritmo de búsqueda binaria, supongamos que, en vez de dividir la lista de elementos en dos mitades del mismo tamaño, la dividamos en dos partes de tamaños 1/3 y 2/3. El coste de este algoritmo: Es el mismo que el original Es mayor que el del original Es menor que el del original.
Si n es el número de elementos del vector, el coste del algoritmo Mergesort es: O( n^2 ) y Ω( n log(n) ) Θ( n log(n) ) Θ( n^2 ).
Un problema se puede resolver por Divide y Vencerás siempre que: Cumpla el principio de optimalidad Cumpla el teorema de reducción Ninguna de las anteriores.
La serie de números de Fibonacci se define de la siguiente forma: (imagen) Para implementar esta función podemos emplear... Divide y vencerás Programación dinámica Cualquiera de las dos anteriores.
La serie de números de Fibonacci se define de la siguiente forma: (imagen) ¿Qué implementación de entre las siguientes supone el menor coste? Divide y vencerás Programación dinámica Ambas tienen el mismo coste asintótico.
El problema de la mochila, ¿Puede solucionarse de forma óptima empleando la estrategia de divide y vencerás? Sólo para el caso de la mochila con fraccionamiento Sólo para el caso de la mochila sin fraccionamiento Sí, se puede aplicar para ambos casos.
Para que un problema de optimización se pueda resolver mediante programación dinámica es necesario que: Cumpla el principio de optimalidad Cumpla el teorema de reducción Cumpla las dos anteriores.
Dada una solución recursiva a un problema, ¿Cómo podemos evitar la resolución de los mismos subproblemas muchas veces? Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas pequeños Resolver los subproblemas de menor a mayor y guardar su resultado en una tabla, inicializándola con los problemas pequeños Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas más grandes.
Si aplicamos programación dinámica a un problema que también tiene solución por divide y vencerás podemos asegurar que... El coste temporal se reduce y el espacial aumenta con respecto a la solución por DyV El coste temporal aumenta y el espacial se reduce con respecto a la solución por DyV Ninguna de las anteriores.
¿Cuándo utilizaremos Programación Dinámica en lugar de Divide y Vencerás? Cuando se incrementa la eficacia Cuando se incrementa la eficiencia Cuando se reduce el coste espacial.
En programación dinámica, dónde almacenaremos los valores de los problemas resueltos? En un vector unidimensional En un vector bidimensional Depende del problema.
Supongamos el problema de la mochila resuelto mediante Programación Dinámica y particularizado para n elementos y un peso máximo trasportable de P. ¿Es necesario calcular valores para toda la matriz auxiliar para obtener el resultado? Si No Depende de los valores de n y P.
Un problema de optimización cuya solución se puede expresar mediante una secuencia de decisiones cumple el principio de optimalidad si, dada una secuencia óptima: Existe una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado Existe al menos una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado Cualquier subsecuencia de esa solución corresponde a la solución óptima de su subproblema asociado.
La programación dinámica, para resolver un problema, aplica la estrategia... Se resuelven los problemas más pequeños y, combinando las soluciones, se obtienen las soluciones de problemas sucesivamente más grandes hasta llegar al problema original Se descompone el problema a resolver en subproblemas más pequeños, que se resuelven independientemente para finalmente combinar las soluciones de los subproblemas para obtener la solución del problema original Ninguna de las anteriores.
¿Qué esquema de programación es el adecuado para resolver el problema k-ésimo mínimo en un vector? Programación Dinámica Divide y Vencerás Ninguno de los dos.
Si n es el número de elementos de un vector. La solución de menor coste al problema de encontrar su k-ésimo mínimo tiene la siguiente complejidad: Ω(n) y O( n log(n) ) Ω(n) y O( n^2 ) Ninguna de las dos.
Si n es el número de elementos de un vector. Podemos encontrar una solución al problema de encontrar su k-ésimo que esté acotada superiormente por: O( n^3 ) O(n) Ninguna de las anteriores.
Dada la solución recursiva al problema de encontrar el k-ésimo mínimo de un vector. Cada llamada recursiva, ¿cuántas nuevas llamadas recursivas genera? una o ninguna dos o ningua una o dos.
La solución al problema de encontrar el k-ésimo mínimo de un vector pone en práctica la siguiente estrategia: Ordenar totalmente el vector Ordena parcialmente el vector No ordena ningún elemento del vector.
¿Qué esquema de programación es el adecuado para resolver el problema de la búsqueda binaria? Programación Dinámica Divide y Vencerás Ninguno de los dos.
Si n es el número de elementos de un vector. La solución de menor coste al problema de la búsqueda binaria tiene la siguiente complejidad: Ω( log(n) ) y O( n log(n) ) Θ( n log(n) ) Ω(1) y O( log(n) ).
¿Con qué esquema de programación obtenemos algoritmos que calculan la distancia de edición entre dos cadenas? Programación Dinámica Divide y Vencerás Ambos.
Disponemos de dos cadenas de longitudes m y n. Si resolvemos el problema de la distancia de edición mediante programación dinámica, ¿De qué tamaño debemos definir la matriz que necesitaremos? (m-1) x (n-1) m x n (m+1) x (n+1).
Denunciar test Consentimiento Condiciones de uso