Un examen

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 "p" que da el precio para cada longitud, pero falta un trozo. ¿Qué debería ir en lugar de XXXXXXX?. p, n-i. p, i. p, n-1.

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. ...garantiza que el algoritmo va a ser más eficiente ante cualquier instancia del problema. ...transforma en polinómicas complejidades que antes eran exponenciales.

Dada la función: De las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien al contrario, una es cierta y dos son falsas. Marca la que en este sentido es diferente a las otras dos. La complejidad temporal en el peor de los casos viene dada por la expresión Σ(n-i). La complejidad temporal en el mejor de los casos ocurre cuando el vector está vacío. El peor de los casos ocurre cuando el primer elemento del vector es estrictamente mayor que los restantes sin importar el orden de los demás.

Si f ∈ Ω(g1) y f ∈ Ω(g2) De las siguiente cuestiones, o bien dos son ciertas y una es falsa, o bien al contrario, una es cierta y dos son falsas. Marca la que en este sentido es diferente a las otras dos. f ∈ Ω(g1 * g2). f ∈ Ω(g1 + g2). f ∈ Ω(min(g1,g2)).

En la resolución mediante ramificación y poda del problema del camino de coste mínimo, obtenemos para un nodo determinado, una cota pesimista parcial estrictamente menos que su cota optimista. ¿Qué quiere decir eso?. Que el nodo no debe expandirse. Que hay un error en alguna de las dos cotas. Que el nodo debe expandirse.

En clase vimos una demostración que justificaba que el esquema voraz es adecuado para resolver el problema de la mochila continua (con fraccionamiento). Entre otros posibles motivos ¿Por qué esa misma demostración no sirve para el problema de la mochila discreta seleccionando objetos de la misma manera?. Las otras dos opciones son ambas ciertas. Porque no hay garantía de que la solución esté formada por una secuencia compuesta únicamente de unos y, a continuación, otra secuencia compuesta únicamente de ceros. Porque no hay garantía de que la mochila se llene.

¿Qué estructura de datos se suele utilizar para almacenar el árbol de búsqueda completo en un algoritmo de ramificación y poda?. Ninguna, no se almacena. Un árbol cuya aridad depende del problema. Una cola de prioridad.

¿Cuál es la mejor complejidad temporal y espacial, en función de "n", que se puede obtener en la solución de programación dinámica para el problema (visto en clase) 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?. Temporal y espacial θ(n). Temporal y espacial θ(n^2). Temporal θ(n^2) y espacial θ(n).

Si comparamos la cota pesimista y la optimista de un mismo nodo. ¿Qué podríamos saber?. El intervalo en el que se encuentra la mejor solución que se puede obtener con ese nodo. Si el nodo es prometedor. Si el nodo debe ser descartado.

¿De qué clase de complejidad es la solución de la siguiente relación de recurrencia?. A. B. C.

Disponemos de dos algoritmos que queremos comparar. Hemos calculado la función de complejidad del algoritmo A contando operaciones elementales, y del algoritmo B contando pasos del programa. ¿Podemos comparar ambas funciones para decidir qué algoritmo es mejor?. Sí, pero sólo podremos comparar sus clases de notación asintótica. Sí, ambos métodos son totalmente equivalentes. El mejor algoritmo será aquel con la menor función. No, porque al contar operaciones elementales, podríamos obtener una complejidad asintótica mayor que si contamos pasos del programa.

¿Qué expresión refleja mejor la complejidad asintótica respecto a "n" del siguiente fragmento de código?. A. B. C.

Tenemos un vector ordenado y queremos comprobar si contiene un elemento dado. ¿Cuál sería la complejidad temporal mas ajustada para hacerlo?. El logaritmo del tamaño del vector. Constante con el tamaño del vector. El tamaño del vector.

¿Cuál es la relación de recurrencia asociada a la complejidad temporal de la siguiente función?. A. B. C.

¿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. El número de llamadas recursivas que se hacen. La combinación de las soluciones a los subproblemas.

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. puede influir en el número de nodos que se descartan sin llegar a expandirlos. nunca afecta al tiempo necesario para encontrar la solución óptima.

Queremos resolver la versión general del problema del camino de coste mínimo mediante ramificación y poda. Para obtener la cota optimista de un nodo cualquiera procedemos asi: calculamos el número de casillas que quedan, por la diagonal derecha-abajo, hasta llegar a una pared del mapa. A ese valor le sumamos el número de casillas que podrían quedar desde esa pared hasta la salida utilizando únicamente movimiento del tipo abajo o derecha, según corresponda (distancia de Chebishev). ¿Qué podemos decir acerca de la cota optimista que se obtendría?. Que solo será una cota optimista válida si se asegura que todas las casillas tengan un coste mínimo de 0. Que solo será una cota optimista válida si las casillas contienen valores reales mayores a 0.0. Que solo será una cota optimista válida si se asegura que todas las casillas tengan un coste mínimo de 1.

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 sólo si se usan cotas optimistas para podar el árbol de búsqueda.

¿Cuál es la complejidad temporal asintótica de la función f? (en la primera llamada, el parámetro i toma valor n-1; el tamaño de los vectores "w" y "v" es "n". A. B. C.

¿Garantiza la estrategia de divide y vencerás una solución de complejidad temporal polinómica a cualquier problema?. Sí, en cualquier caso. 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. No, la complejidad temporal puede ser incluso peor que cualquier función polinómica.

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(n log n). O(log n).

La solución voraz al problema de la mochila con objetos no fraccionables: No siempre encuentra la solución óptima al problema, pero sí una muy buena aproximación, a partir de la cual se puede obtener el óptimo en tiempo constante. No siempre encuentra la solución óptima al problema, pero puede emplearse como cota pesimista en algoritmos de búsqueda y enumeración. Siempre encuentra la solución óptima al problema.

En un problema de minimización mediante Vuelta Atrás, empleamos una cota optimista que es mucho mayor que la mejor solución que podría alcanzarse desde un nodo determinado. Como consecuencia: El programa será más lento que con otra cota optimista. Dicha decisión tendrá un impacto mínimo en el tiempo de ejecución del programa, puesto que es más importante elegir una buena cota pesimista inicial. Es posible que no encontramos el óptimo.

Dada la solución por programación dinámica recursiva de la versión restringida del problema del camino de coste mínimo, en general, ¿cuántas veces se llega al caso base de la recursión (la casilla inicial)?. Un valor que es O(2^n), donde n es el tamaño del mapa. Un valor que es O(n), donde n es el tamaño del mapa. Solo una.

Queremos resolver la versión general del problema del camino de coste mínimo por ramificación y poda. Para ello se usa una estrategia que consiste en priorizar las expansiones de los nodos que contienen un camino explorado de menor coste. ¿Qué podemos decir del algoritmo resultante?. Que el recorrido en el árbol de búsqueda será equivalente a un recorrido por niveles, por lo que no es necesario utilizar una cola de prioridad. Las otras dos opciones son ambas ciertas. Que la primera hoja a la que se llegue es la solución del problema y por lo tanto ya no será necesario explorar más nodos de la lista de nodos vivos, aunque no esté vacía.

Un problema tiene subestructura óptima cuando. es posible escribir una solución voraz para el problema. es posible dividir su tamaño de forma equitativa para construir cada uno de los subproblemas. su solución se puede construir eficientemente a partir de soluciones de subproblemas suyos.

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 eficiente que divide y vencerás en cuanto al uso de memoria. El uso de memoria de la programación dinámica iterativa y de divide y vencerás es el mismo independientemente de si el dominio es discreto o continuo. Divide y vencerás puede resultar más eficiente que la programación dinámica iterativa en cuanto al uso de memoria.

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 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.

En la solución de ramificación y poda del problema del camino de coste mínimo, ¿para qué puede resultar útil la técnica de poda con memoria?. Para evitar la formación de ciclos. Para ambas cosas. Para obtener cotas pesimistas.

Resolviendo el problema de la composición de funciones mediante ramificación y poda, declaramos el nodo y la cola de prioridad como sigue: using Node = tuple<short, int>; priority_queue<Node >pq; Cada nodo contiene, en este orden, el número de veces que se ha aplicado una función y el resultado obtenido. ¿Qué se puede afirmar sobre el orden en el que extraen los nodos de la cola de prioridad?. Que se extraerán en un orden que permite encontrar pronto la solución óptima. Que se extraerán en un orden que dificulta encontrar pronto la solución óptima. No podemos afirmar nada, pues no hemos definido ningún criterio para la ordenación de la cola.

Dada la versión general del problema del camino de coste mínimo, ¿cuál de las estrategias siguientes proveería de una cota optimista para ramificación y poda?. Suponer que ya no se van a realizar más movimientos. Las otras dos estrategias son ambas válidas. Suponer que solo nos vamos a mover en tres direcciones (como en el caso restringido).

¿A qué esquema de entre los estudiados pertenece la siguiente función?. Ramificación y poda. Vuelta atrás. Programación dinámica.

Queremos utilizar el algoritmo heapsort para ordenar un vector de manera descendente (de mayor a menor). ¿Cómo serían las complejidades temporales asintóticas de construir el heap en estos dos supuestos: (1) el vector que recibe está ordenado ascendente; (2) el vector que recibe está ordenado descendente?. La del primer supuesto mayor que la del segundo. La del segundo supuesto mayor que la del primero. Iguales.

En un algoritmo de ramificación y poda se puede usar una cota optimista para estimar el coste restante desde el nodo actual hasta el objetivo. ¿Qué propiedad debe cumplir esta cota para asegurar que siempre se encontrará la solución óptima?. Debe disminuir a medida que se acerca al objetivo. Las dos anteriores son ciertas. Nunca sobreestimar el coste real. No se sabe la respuesta.

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. puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas. Las otras dos opciones son ambas ciertas. es irrelevante si no se utilizan mecanismos de poda basados en la mejor solución hasta el momento.

Queremos resolver el problema general del camino de coste mínimo. Supón que estamos usando una función f como cota optimista y funciona correctamente. ¿Qué pasaría si, en el fuente, multiplicamos esta función por 1,1. Marca la FALSA. El programa terminaría mas rápido. Seguiría funcionando bien pero sería mas lento. Podría perderse la solución óptima pero la que obtendríamos no se alejaría mucho de ella.

¿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. Sí, si se repiten llamadas a la función con los mismos argumentos. No, ellos no reduce el coste temporal ya que las llamadas recursivas se deben realizar de cualquier manera.

¿Cuál de estas estrategias para calcular el n-ésimo elemento de la serie de Fibonacci(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. Programación dinámica. La estrategia divide y vencerás.

Usando la técnica de programación dinámica con ahorro de memoria ¿podría acelerarse el programa usando tres vectores en vez de dos?. Sí, pero la complejidad temporal seguiría siendo la mismo. No. Sí, pero sería a expensas de usar más memoria.

¿Cuál de los siguiente algoritmos de ordenación funciona más rápido para ordenar vectores muy grandes que ya están casi ordenados?. Heapsort. Ambos por igual. Quicksort empleando el primer elemento como pivote.