WorksheetsDivisión y conquista
Total questions: 10
Worksheet time: 6mins
¿Cuál de estas operaciones no suele ser parte de la resolución principal de un problema por D&Q?
Dividisión del problema en subproblemas
Ordenamiento de sub problemas
Resolución de subproblemas
Combinación de resultados de subproblemas
Cual de las siguientes propiedades es indispensable en un problema para lograr un algoritmo por División y conquista óptimo?
Elección greedy
Subestructura óptima
Relación de recurrencia
Todas las anteriores
Ninguna de las anteriores
El teorema maestro ...
Resuelve cualquier relación de recurrencia de los algoritmos de división y conquista
Requiere para su aplicación la existencia de un caso base con f(n) polinomial
Si puede aplicarse nos dará una cota inferior para un n lo suficientemente grande del algoritmo analizado
Requiere para su aplicación que la relación de recurrencia tenga 1 o más subproblemas y que divida la cantidad de elementos por subproblemas en 1 o más subconjuntos de igual cantidad de elementos
Aún cumpliendo las condiciones de los valores a, b y teniendo un f(n) definido podría no ser aplicable
Indique cuál de las siguientes afirmaciones sobre el teorema maestro no es correcta
Incluye 3 casos de aplicación
La aplicación del caso correcto depende de si predomina el trabajo dentro de cada subproblema f(n) o la cantidad de subproblemas totales en la recurrencia.
Se puede aplicar únicamente si f(n)=n^c con c entero positivo
No se puede aplicar si la recurrencia es del tipo T(m - b) + f(n)
¿ Cómo se arma T(m) para este caso ? : Un algoritmo de búsqueda divide un arreglo en 3 partes, quedándome con 1 parte en O(1). Dada T(m) = a. T(m/b) + F(m), y según el Teorema del Maestro
T(m) = 3 * T(m) + O(3)
T(m) ϵ 3 * T(m/3) + O(3)
T(m) ϵ T(m/3) + O(1)
T(m) ϵ 3 * T(m/3) + O(1)
¿En qué caso se categoriza la función F(m) del algoritmo?: Un algoritmo de búsqueda divide un arreglo en 3 partes, quedándome con 1 parte en O(1). Dada T(m) = a. T(m/b) + F(m)
F(m) ϵ O(m^(log b (a - ϵ)), ϵ > 0
F(m) ϵ Θ(m^(log b (a)))
F(m) = 𝝮(m^c), c > log b (a), a F(m/b) <= kF(m), k < 1
Un algoritmo de búsqueda divide un arreglo en 3 partes, quedándome con 1 parte en O(1). Dada T(m) = a. T(m/b) + F(m), y según el Teorema del Maestro, ¿ Cuál es el resultado final ?
T(m) ϵ log 3 (m)
T(m) ϵ m * log(m)
T(m) ϵ m^3
El problema de "contar inversiones" tiene la misma relación de recurrencia y complejidad que
Búsqueda binaria
Puntos mas cercanos en el plano
Karatsuba
Merge Sort
El problema "punto extremo en un polígono convexo" tiene la misma relación de recurrencia que el problema
Búsqueda binaria
Merge Sort
Multiplicación rápida de Strassen
Ninguno de los anteriores
Analice la siguiente estrategia para resolver el árbol recubridor mínimo: Dado el grafo G dividir recursivamente en dos mitades A y B. Seleccionar el eje de menor valor que cruce A y B. El resultado es el MST del grafo
Es óptima para todo G por utilizar la propiedad de corte
Es óptima para todo G por utilizar la propiedad del ciclo
No es óptima para todo G. En el MST pueden existir varios ejes que crucen A y B
No es óptima porque división y conquista no se puede aplicar por ausencia de subestructura óptima
