ADA FINAL

Dado un problema de optimización cualquiera, ¿la estrategia de vuelta atrás garantiza la solución óptima?. Sí, puesto que ese método analiza todas las posibilidades. Sí, siempre que el dominio de las decisiones sea discreto o discretizable y además se empleen macanismos de poda basados en la mejor solución hasta el momento. Es condición necesaria que el dominio de las decisiones sea discreto o discretizable y que el número de decisiones a tomar esté acotado.

En los algoritmos de ramificación y poda... Una cota optimista es necesariamente un valor alcanzable, de no ser así no está garantizando 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.

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 afirmaciones es falsa. 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 eficacia del algoritmo definiendo da 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 convirtiendo el algoritmo recursivo directamente en iterativo sin cambiar su funcionamiento básico.

Si un problema de optimización lo es para una función que toma valores continuos... La programación dinámica recursiva siempre es mucho más eficiente que la programación dinámica iterativa en cuanto al uso de memoria. 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. 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 continuo.

El uso de funciones de cota en ramificación y poda... ... transforma en polinómicas complejidades que antes eran exponenciales. ... garantiza que el algoritmo va a ser más eficiente ante cualquier instancia del problema. ... puede reducir el número de instancias del problema que pertenecen al caso peor.

Al resolver el problema del viajante de comercio mediante vuelta atrás, ¿cuál de estas cotas optimistas se espera que pode mejor el árbol de búsqueda?. Se multiplica k por la distancia de la arista más corta que nos queda por considerar, donde k es el número de saltos que nos quedan por dar. Se resuelve el resto del problema usando un algoritmo voraz que añade cada vez al camino el vértica más cercano al último añadido. Se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las k aristas más cortas, donde k es el número de saltos que nos quedan por dar.

¿Para cuál de estos problemas de optimización existe una solución voraz?. El problema de la mochila discreta. 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. El árbol de recubrimiento mínimo para un grafo no dirigido con pesos.

Se desea encontrar el camino más 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 (-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. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia en línea recta entre cada par de ciudades. Se pretende acelerar la búsqueda de un algoritmo de ramificación y poda priorizando los nodos vivos (ciudades) que estén a menor distancia geográfica de la ciudad objetivo. El nuevo algoritmo no garantiza que vaya a ser más rápido para todas las instancias del problema posibles. El nuevo algoritmo siempre será más rápido. Esta estrategia no segura que se obtenga el camino más corto.

La complejidad temporal en el menor de los casos... ... es el tiempo que tarda el algoritmo en resolver el problema de tamaño o talla más pequeña que se le puede presentar. Las dos opciones son ciertas. ... es una función del tamaño o talla del problema que tiene que estar definida para todos los posibles valores de está.

La mejor solución que se conoce para el problema de la mochila continua sigue el esquema de... ... divide y vencerás. ... ramificación y poda. ... voraz.

La complejidad en el mejor de los casos de un algoritmo de ramificación y poda... ... es siempre exponencial con el número de decisiones a tomar. ... puede ser polinómica con el número de decisiones a tomar. ... suele ser polinómica con el número de alternativas por cada decisió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 el algoritmo no encuentre ninguna solución. Que se reconsidere la decisión ya tomada anteriormente respecto a la selección de un elemento a la vista de la de la decisión que se debe tomar en el instante actual. Que la solución no sea óptima.

Cuando la descomposición recursiva de un problema da luegar a subproblemas de tamaño similar, ¿qué esquema promete ser más apropiado?. Programación dinámica. Divide y vencerás, siempre que se garantice que los subproblemas no son del mismo tamaño. El método voraz.

Sea la siguiente relación de recurrencia: Si T(n) € O(n^2), ¿en cuál de estos tres casos nos podemos encontrar?. g(n) = n. g(n) = n^2. g(n) = 1.

Un algoritmo recursivo basado en el esquema divide y vencerás... ... nunca tendrá una complejidad exponencial. ... será más eficiente cuanto más equitativa sea la división en subproblemas. ... Las dos anteriores son ciertas.

En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución hasta el momento... ... garantizan que no se va a explorar nunca todo el espacio de soluciones posibles. Las otras dos opciones son correctas. ... pueden eliminar soluciones parciales que son factibles.

Uno de estos tres problemas no tiene solución eficiente que siga el esquema de progrmación dinámica: El problema de la mochila discreta. El problema de las torres de Hanoi. 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.

El valor que se obtiene con el método voraz para el problema de la mochila discreta es... ... una cota inferior para el valor óptimo, pero nunca coincide con este. ... una cota superior para el valor óptimo. ... una cota inferior para el valor óptimo que a veces puede ser igual a este.

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 continua correspondiente. El valor de una mochila que contiene todos los objetos aunque se pase del peso máximo permitido. El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos.

Un problema de tamaño n puede transformarse en tiempo O(n^2) en otro de tamaño n - 1. Por otro lado, la solución al problema cuando la talla es 1 requiere tiempo constante. ¿cuál de estas clases de coste temporal asintótico es la más ajustada?. O(2^n). O(n^3). O(n^2).

Una de estas tres situaciones no es posible: f(n) € O(n) y f(n) € Ω(1). f(n) € Ω(n^2) y f(n) € O(n). f(n) € O(n) y f(n) € O(n^2).

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 principal se mínima. Indica cuál de las siguientes afirmaciones es falsa: La complejidad temporal de la mejor solución posible al problema es O(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. La complejidad temporal de la mejor solución posible al problema es O(n^2).

¿Cuál de los siguientes algoritmos proveería una cota pesimista para el problema de encontrar el camino más corto entre dos ciudades (se supone que el grafo es conexo)?. Calcular la distancia geométrica (en línea recta) entre la ciudad origen y destino. Para todas las ciudades que son alcanzables en un paso desde la ciudad inicial, sumar la distancia a dicha ciudad y la distancia geométrica hasta la ciudad destino. Calcular la distancia recorrida moviéndose al azar por el grafo hasta llegar (por azar) a la ciudad destino.

Si para resolver un mismo problema usamos un algoritmo de vuelta atrás y lo modificamos mínimamente para convertirlo en un algoritmo de ramificación y poda, ¿qué cambiamos realmente?. Cambiamos la función que damos a la cota pesimista. El algoritmo puede aprovechar mejor las cotas optimistas. La comprobación de las soluciones factibles: en ramificación y poda no es necesario puesto que sólo genere nodos factibles.

En una cuadrícula se quiere dibujar el contorno de un cuadrado de n casillas de lado. ¿cuál será la complejidad temporal del mejor algoritmo que pueda existir?. O(n^2). O(n). O(√n).

En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es mayor que el valor de una cota optimista? (se entiende que ambas cotas se aplican sobre el mismo nodo). No, nunca es así. En general sí, si se trata de un problema de minimización, aunque en ocasiones ambos valores pueden coincidir. En general sí, si se trata de un problema de maximización, aunque en ocasiones ambos valores pueden coincidir.

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. No, ya que en cualquier caso se deben explorar todas las soluciones factibles. Sí, pero solo si se usan cotas optimistas para podar el árbol de búsqueda.

Garantiza el uso de una estrategia "divide y vencerás" la existencia de una solución de complejidad temporal polinómica a cualquier problema?. Sí, en cualquier caso. No. Sí, pero siempre que la complejidad temporal conjunta de las operaciones de descomposición de problema y la combinación de las soluciones sea polinómica.

En el esquema de vuelta atrás el orden en el que se van asignando los distintos valores a la 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. ... puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas. Las otras dos opciones son correctas.

La versión de Quicksort que utiliza como pivote el elemento del vector que ocupa la primera posición... ... no presenta caso mejor y caso 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.

¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz que es óptima?. El problema de la mochila discreta. El problema de la mochila continua o con fraccionamiento. El árbol de cobertura de coste mínimo de un grafo conexo.

En un problema de optimización, si el dominio de las decisiones es un conjunto finito,. una estrategia voraz puede ser la única alternativa. es probable que a través de programación dinámica se obtengaun algoritmo eficaz que lo solucione. podremos aplicar el esquema de vuelta atrás siempre que se trate de un conjunto infinito numerable.

Dado un problema de optimización, el método vorzaz... ... siempre obtiene la solución óptima. ... garantiza la solución óptima sólo para determinados problemas. ... siempre obtiene una solución factible.

La mejora que en general aporta programación dinámica frente a la solución ingenua se consigue gracias al hecho de que... ... en la solución ingenua se resuelve pocas veces un número relativamente grande de subproblemas distintos. El número de veces que se resuelven los subproblemas no tiene nada que ver con la eficiencia de los problemas resueltos mediante programación dinámica. ...... en la solución ingenua se resuelve muchas veces un número relativamente pequeño de subproblemas distintos.

¿Cuál de estos problemas tiene una solución eficiente utilizando programación dinámica?. El problema de la asginación de tareas. El problemas del cambio. La mochila discreta sin restricciones adiccionales.

Di cuál de estos tres algoritmos no es un algoritmo de "divide y vencerás": Quicksort. Mergesort. El algoritmo de Prim.

Si f(n) € O(n^3), ¿puede pasar que f(n) € O(n^2)?. No, porque n^3 ∉ O(n^2). Sólo para valores bajos de n. Es perfectamente posible, ya que O(n^2) ⊂ O(n^3).