En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es siempre menor o igual que el valor de una cota optimista? (se entiende que ambas cotas se aplican sobre el mismo nodo) Solo si se trata de un problema de maximización No, depende del problema Sólo si se trata de un problema de minimización.
¿Qué tienen en común el algoritmo que obtiene el k-ésimo elemento más pequeño de un vector (estudiado en clase) y el algoritmo de ordenación Quicksort? La división del problema en subproblemas La combinación de las soluciones a los subproblemas El número de llamadas recursivas que se hacen.
La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica:
(imagen)
Di cuál de las siguientes afirmaciones es falsa: Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación por inserción binaria. Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal en el mejor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase).
(imagen) a b c.
La solución recursiva ingenua (pero correcta) a un problema de optimización llama más de una vez a la función con los mismos parámetros.
Una de las siguientes tres afirmaciones es falsa. Se puede mejorar la eficiencia del algoritmo definiendo de antemano el orden en el que se deben calcular las soluciones a los subproblemas y llenando una tabla en ese orden. Se puede mejorar la eficiencia del algoritmo guardando en una tabla el valor devuelto para cada conjunto de parámetros de cada llamada cuando ésta se produce por primera vez. Se puede mejorar la eficiencia del algoritmo convirtiendo el algoritmo recursivo directamente en iterativo sin cambiar su funcionamiento básico.
¿Garantiza la estrategia "divide y vencerás" una solución de complejidad temporal polinómica a cualquier problema? Sí, en cualquier caso. No, la complejidad temporal puede ser incluso peor que cualquier función polinómica. Sí, pero siempre que la complejidad temporal conjunta de las operaciones de descomposición del problema y la combinación de las soluciones sea polinómica.
¿Cuál de estas estrategias para calcular el n-ésimo elemento de la serie de Fibonaccí(f(n) = f(n—1)+f(n—2), f(1) = f(2) = 1) es más eficiente? Para este problema, las dos estrategias citadas serían similares en cuanto a eficiencia La estrategia divide y vencerás Programación dinámica.
Con respecto al tamaño del problema, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n) Θ(1) Ninguna de las otras dos opciones es correcta.
¿Qué aporta la técnica Ramificación y poda frente a Vuelta atrás? Eficiencia, los algoritmos de ramificación y poda son más eficientes que los de vuelta atrás… La posibilidad de analizar distintas estrategias para seleccionar el siguiente nodo a expandir. La posibilidad de combinar el uso de cotas pesimistas y optimistas para cualquier nodo ya sea completado o sin completar. En Vuelta atrás esto no se puede hacer.
(imagen) ... g(n) ∈ O(f(n)) ... f(n) ∈ O(g(n)) ... f(n) ∈ Θ(g(n)).
Cuando se resuelve el problema de la mochila discreta usando la estrategia de vuelta atrás, ¿puede ocurrir que se tarde menos en encontrar la solución óptima si se prueba primero a meter cada objeto antes de no meterlo? Sí, tanto si se usan cotas optimistas para podar el árbol de búsqueda como si no. Sí, pero sólo si se usan cotas optimistas para podar el árbol de búsqueda. No, ya que en cualquier caso se deben explorar todas las soluciones factibles.
En un algoritmo de ramificación y poda, si la lista de nodos vivos no está ordenada de forma apropiada... ...podría ocurrir que se pode el nodo que conduce a la solución óptima. ...podría ocurrir que se exploren nodos de forma innecesaria. ...podría ocurrir que se descarten nodos factibles.
El algoritmo de ordenación Quicksort divide el problema en dos subproblemas. ¿Cuál es la complejidad temporal asintótica de realizar esa división? O(n) O(log n) O(n log n).
Cuando se usa un algoritmo voraz para abordar la resolución de un problema de optimización por selección discreta (es decir, un problema para el cual la solución consiste en encontrar un subconjunto del conjunto de elementos que optimiza una determinada función), ¿cuál de estas tres cosas es imposible que ocurra? Que la solución no sea la óptima. Que se reconsidere la decisión ya tomada anteriormente respecto a la selección de un elemento a la vista de la decisión que se debe tomar en un instante. Que el algoritmo no encuentre ninguna solución.
Sea n el número de elementos que contienen los vectores w y v en la siguiente función f. ¿Cuál es su complejidad temporal asintótíca en función de n asumiendo que en la llamada inicial el parámetro i toma valor n? Ω(n) y O(n^2) Θ(2^n) Ω(n) y O(2^n).
¿Para cuál de estos problemas de optimización existe una solución voraz? El problema de la mochila discreta. El árbol de recubrimiento mínimo para un grafo no dirigido con pesos El problema de la asignación de coste mínimo de n tareas a n trabajadores cuando el coste de asignar la tarea i al trabajador j, c(ij) está tabulado en una matriz.
Se desea encontrar el camino mas corto entre dos ciudades. Para ello se dispone de una tabla con la distancia entre los pares de ciudades en los que hay carreteras o un valor centinela (por ejemplo, -1) si no hay, por lo que para ir de la ciudad inicial a la final es posible que haya que pasar por
varias ciudades. Como también se conocen las coordenadas geográficas de cada ciudad se quiere usar la distancia geográfica (en línea recta) entre cada par de ciudades como cota para limitar la búsqueda en un algoritmo de vuelta atrás. ¿Qué tipo de cota sería? Una cota optimista. No se trataría de ninguna cota puesto que es posible que esa heurística no encuentre una solución factible. Una cota pesimista.
Decid cuál de estas tres es la cota pesimista más ajustada al valor óptimo de la mochila discreta: El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos. El valor de la mochila continua correspondiente. El valor de una mochila que contiene todos los objetos restantes aunque se pase del peso máximo permitido.
En los algoritmos de ramificación y poda... Una cota optimista es necesariamente un valor alcanzable, de no ser así no está garantizado que se encuentre la solución óptima. Una cota optimista es necesariamente un valor insuperable, de no ser así se podría podar el nodo que conduce a la solución óptima. Una cota pesimista es el valor que a lo sumo alcanza cualquier nodo factible que no es el óptimo.
El uso de funciones de cota en ramificación y poda... ...puede reducir el número de instancias del problema que pertenecen al caso peor. ...transforma en polinómicas complejidades que antes eran exponenciales. ...garantiza que el algoritmo va a ser más eficiente ante cualquier instancia del problema.
El siguiente programa resuelve el problema de cortar un tubo de longitud n en segmentos de longitud entera entre 1 y n de manera que se maximice el precio de acuerdo con una tabla que da el precio para cada longitud, pero falta un trozo. ¿Qué debería ir en lugar de XXXXXXX? a b c.
Sea la siguiente relación de recurrencia:
(imagen)
Si T(n) ∈ O(n), ¿en cuál de estos tres casos nos podemos encontrar? g(n) = 1 g(n) = n g(n) = n^2.
¿Se puede reducir el coste temporal de un algoritmo recursivo almacenando los resultados devueltos por las llamadas recursivas? No, sólo se puede reducir el coste convirtiendo el algoritmo recursivo en iterativo Si, si se repiten llamadas a la función con los mismos argumentos No, ello no reduce el coste temporal ya que las llamadas recursivas se deben realizar de cualquier manera.
(imagen) a b c.
(imagen) a b c.
Si un problema de optimización lo es para una función que toma valores continuos... La programación dinámica iterativa siempre es mucho más efíciente que la programación dinámica recursiva en cuanto al uso de memoria. El uso de memoria de la programación dinámica iterativa y de la programación dinámica recursiva es el mismo independientemente de si el dominio es discreto o contínuo. La programación dinámica recursiva puede resultar mucho más eficiente que la programación dinámica iterativa en cuanto al uso de memoria.
En un algoritmo de ramificación y poda, el orden escogido para priorizar los nodos en la lista de nodos vivos . . . ...determina la complejidad temporal en el peor de los casos del algoritmo. …nunca afecta al tiempo necesario para encontrar la solución óptima. ...puede influir en el número de nodos que se descartan sin llegar a expandirlos.
Se pretende resolver un problema de maximización utilizando ramificación y poda y para ello se dispone de tres posibles cotas optimistas.
¿Cuál deberíamos utilizar para tratar de reducir la cantidad de nodos a explorar? La que obtenga valores más elevados. La que obtenga valores más pequeños. La que más se acerque a una heurística voraz que obtenga una solución aproximada del problema.
(imagen) a b c.
(imagen) a b c.
(imagen) a b c.
(imagen) a b c.
En el esquema de vuelta atrás el orden en el que se van asignando los distintos valores a las componentes del vector que contendrá la solución... es irrelevante si no se utilizan mecanismos de poda basados en la mejor solución hasta el momento. las dos anteriores son ciertas. puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas.
¿Cuál es la diferencia principal entre una solución de vuelta atrás y una solución de ramificación y poda para el problema de la mochila? El coste asintótico en el caso peor. El hecho que la solución de ramificación y poda puede empezar con una solución subóptima voraz y la de vuelta atrás no. El orden de exploración de las soluciones.
La versión de Quicksort que utiliza como pivote el primer elemento del vector... ... no presenta caso mejor y peor para instancias del mismo tamaño. ... se comporta mejor cuando el vector ya está ordenado. ... se comporta peor cuando el vector ya está ordenado.
(imagen) a b c.
Sea A una matriz cuadrada n x n. Se trata de buscar una permutación de las columnas tal que la suma de los elementos de la diagonal de la matriz resultante sea mínima. Indicad cuál de las siguientes afirmaciones es falsa. La complejidad temporal de la mejor solución posible al problema está en Ω(n^2) La complejidad temporal de la mejor solución posible al problema es O(n log n) Si se construye una solución al problema basada en el esquema de ramificación y poda, una buena elección de cotas optimistas y pesimistas podría evitar la exploración de todas las permutaciones posibles.
Tenemos un vector ordenado y queremos comprobar si contiene un elemento dado. ¿Cuál sería la complejidad temporal mas ajustada para hacerlo? El tamaño del vector. Constante con el tamaño del vector. El logaritmo del tamaño del vector.
En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución hasta el momento... pueden eliminar soluciones parciales que son factibles. las dos anteriores son verdaderas. garantizan que no se va a explorar nunca todo el espacio de soluciones posibles.
Los algoritmos de vuelta atrás que hacen uso de cotas optimistas generan las soluciones posibles al problema mediante... ... un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones. ... un recorrido guiado por una cola de prioridad de donde se extraen primero los nodos que representan los subárboles más prometedores del espacio de soluciones. ... un recorrido en profundidad del árbol que representa el espacio de soluciones.
|
