Dado un problema de minimización resuelto mediante un esquema de
ramificación y poda,¿qué propiedad cumple una cota optimista? Siempre es mayor o igual que la mejor solución posible alcanzada. Las otras dos opciones son falsas Asegura un ahorra en la comprobación de todas las soluciones factibles. Queremos resolver mediante vuelta atrás el problema de las 8 reinas (colocar 8 reinas en un tablero de ajedrez de manera que no se maten mutuamente). Una buena cota optimista permitiría: No es aplicable este tipo de podas a este problema Muy probablemente, explorar menos nodos. Muy probablemente, resolver el problema de forma más rápida. De las siguientes afirmaciones marca la que es verdadera 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. El esquema de vuelta atrás no es compatible con el uso conjunto de cotas pesimistas y optimistas.
. ¿Cuál de estos problemas tiene una solución eficiente utilizando programación dinámica? El problema de la asignación de tareas.
La mochila discreta con pesos y valores reales positivos. El problema del cambio. Dada la siguiente función ( donde max(a, b) ∈ Θ(1) ): La complejidad temporal en el peor de los casos es O(2ⁿ) La complejidad temporal en el mejor de los casos es Ω(n²) La complejidad temporal en el peor de los casos es O(n²). Si T(n) ∈ Θ(n²), ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n² g(n) = n³ g(n)=n. Si f (not ∈) O(g1) y f ∈ O(g2) entonces siempre se cumplirá: f ∈ Ω(mín(g1, g2)) f (not ∈) O(máx(g1, g2)) f ∈ Ω(g1 + g2). Si lím(n→∞) f(n) / g(n) = ∞ entonces ... ...f(n) ∈ O(g(n)) ...f(n) ∈ Ω(g(n)) ...f(n) ∈ Θ(g(n)). 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 log₂n ∈ Ω(n + n log₂n) O(n²) ⊂ O(2ˡᵒᵍ² ⁿ) Ω(n² ) ⊂ Ω(n). Con respecto a la complejidad espacial de los algoritmos de ordenación Quicksort, Heapsort y Mergesort . . . Las complejidad espacial de todos ellos es lineal con el tamaño del vector a ordenar. Mergesort y Heapsort tienen complejidad espacial lineal con el tamaño del vector a ordenar, la de Quicksort es constante. Mergesort tiene complejidad espacial lineal con el tamaño del vector a ordenar, la de los otros dos es constante.
