05 Abr
Divide y Vencerás (DV) y Programación Dinámica (PD)
¿Qué esquema algorítmico utiliza el algoritmo de ordenación Quicksort?
Divide y Vencerás.
Ante un problema que presenta una solución recursiva, ¿siempre podemos aplicar Divide y Vencerás?
Divide y Vencerás.
¿En cuál de los siguientes casos no se puede aplicar el esquema Divide y Vencerás?
(Contexto necesario) Se puede aplicar en ambos casos.
Si n es el número de elementos del vector, ¿cuál es el coste del algoritmo Mergesort?
O(n log n).
¿Un problema se puede resolver por Divide y Vencerás siempre que…?
(Contexto necesario) Ninguna de las anteriores.
¿Qué esquema se usa para implementar la serie de números de Fibonacci?
Divide y Vencerás (recursivo simple) y Programación Dinámica (optimizado).
¿Qué implementación de Fibonacci supone el menor coste?
Programación Dinámica.
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 sin fraccionamiento. (Nota: Generalmente se resuelve con PD o Backtracking para óptimo en 0/1).
¿Para que un problema de optimización se pueda resolver mediante Programación Dinámica (PD) es necesario que…?
Cumpla el principio de optimalidad.
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 menor a mayor, guardando sus resultados en una tabla (tabulación) o mediante memoización.
Supongamos el problema de la mochila resuelto mediante Programación Dinámica y particularizado para n elementos y un peso máximo transportable de P. ¿Es necesario calcular valores para toda la matriz auxiliar para obtener el resultado?
No.
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…
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.
¿Qué esquema de programación es el adecuado para resolver el problema del k-ésimo mínimo en un vector?
Divide y Vencerás (ej. algoritmo Quickselect).
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:
Tiempo promedio Θ(n), peor caso O(n²).
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.
La solución al problema de encontrar el k-ésimo mínimo de un vector pone en práctica la siguiente estrategia:
Ordenar parcialmente el vector.
¿Qué esquema de programación es el adecuado para resolver el problema de la búsqueda binaria?
Divide y Vencerás.
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:
Mejor caso Ω(1), peor caso 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.
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).
Algoritmos Voraces (AV), Backtracking (BKTRCK) y Ramificación y Poda (RyP)
El método voraz se emplea en la resolución de problemas de selección y optimización en los que se pretende encontrar:
Una solución que satisfaga unas restricciones y optimice una cierta función objetivo.
¿Para qué problema conocido el método Voraz siempre da la solución óptima?
Para el problema de la mochila con fraccionamiento.
En el método Voraz, aunque las decisiones son irreversibles, podemos asegurar que:
Sólo obtendremos la solución óptima para algunos problemas.
Dado un grafo G que representa las poblaciones de la provincia de Alicante de más de 20.000 habitantes… (Pregunta incompleta) ¿qué tipo de solución busca inicialmente un algoritmo?
Una solución factible.
Al aplicar Backtracking, ¿obtenemos la solución óptima a un problema?
Siempre (si se exploran todas las soluciones factibles en un problema de optimización).
Backtracking procede a obtener la solución a un problema de optimización empleando la siguiente estrategia:
Genera todas las soluciones factibles y selecciona la que optimiza la función objetivo.
Backtracking es una técnica de resolución general de problemas basada en:
La búsqueda sistemática de soluciones.
El problema de la mochila, ¿puede solucionarse empleando Vuelta Atrás (Backtracking)?
Sí, para el caso sin fraccionamiento (Mochila 0/1).
El problema del viajante de comercio (TSP) puede resolverse correctamente empleando estos esquemas de programación:
Backtracking y Ramificación y Poda.
El tiempo de ejecución de un algoritmo de Ramificación y Poda depende de:
La instancia del problema y la función de selección de nodos para su expansión.
El problema de la asignación de turnos, ¿tiene solución óptima voraz aplicando alguna estrategia conocida?
No tiene solución óptima voraz general.
El problema de la asignación de turnos, ¿tiene solución óptima empleando qué técnica?
Backtracking (o Ramificación y Poda, Programación Entera).
Deja un comentario