ADA JUNIO 2024

¿Qué expresión refleja mejor la complejidad asintótica respecto a n del siguiente fragmento de código?. Σa=1 -> log n : 2^a. Σa=1 ->n-1 : Σb=0->a-1: 1. Σa=1->n-1:n/2.

¿Se puede reducir el coste temporal de un algoritmo recursivo almacenando los resultados devueltos por las llamadas recursivas?. No, ello no reduce el coste temporal ya quelas llamadas recursivas se deben realizar de cualquier manera. 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.

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

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

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 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. Que la solución no sea la óptima.

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

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.

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. Es posible que no encontremos el óptimo. 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.

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 se extraen los nodos de la cola de prioridad?. No podemos afirmar nada, pues no hemos definido ningún criterio para la ordenación de la cola. 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.

Un problema tiene subestructura óptima cuando . su solución se puede construir eficientemente a partir de soluciones de subproblemas suyos. 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.

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. Podría perderse la solución óptima pero la que obtendríamos no se alejará mucho de ella. El programa terminaría mas rápido. Seguiría funcionando bien pero sería más lento.

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) = 1) es más eficiente?. La estrategia divide y vencerás. Para este problema, las dos estrategias citadas serían similares en cuanto a eficiencia. Programación dinámica.

¿De qué clase de complejidad es la solución de la siguiente relación de recurrencia?. Depende del valor de b. f(n) e ⊖(log n). f(n) e ⊖(n).

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 solo nos vamos a mover en tres direcciones (como en el caso restringido). Suponer que ya no se van a realizar más movimientos. Las otras dos estrategias son ambas válidas.

Dada la siguiente 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. 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. La complejidad temporal en el peor de los casos viene dada por la expresión Σk=1 ->n: (n-1). La complejidad temporal en el mejor de los casos ocurre cuando el vector está vacío.

La solución voraz al problema de la mochila con objetos no fraccionables. Siempre encuentra la solución óptima al problema. 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.

El uso de funciones de cota en ramificación y poda ... transforma en polinómicas complejidades que antes eran exponenciales. 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.

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. ..puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas. Las otras dos opciones son ambas ciertas.

¿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 ⊖(n^2 ) y espacial ⊖(n). Temporal y espacial ⊖(n). Temporal y espacial ⊖(n^2).

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?. Iguales. La del primer supuesto mayor que la del segundo. La del segundo supuesto mayor que la del primero.

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

Si f e Q(gl) y f e Q(g2) entonces siempre se cumplirá: de las siguientes conclusiones, 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 € Ω(min(g1, g2)). f e Ω(g1*g2). f e Ω(g1+g2).

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

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 así: 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 movimientos 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 1. 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 que 0.0.

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 menor que su cota optimista. ¿Qué quiere decir esto?. Que el nodo debe expandirse. Que el nodo no debe expandirse. Que hay un error en alguna de las dos cotas.

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

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 obtener cotas pesimistas. Para evitar la formación de ciclos. Para ambas cosas.

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 sería a expensas de usar más memoria. Sí, pero la complejidad temporal seguiría siendo la misma. No.

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

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. El logaritmo del tamaño del vector. Constante con el tamaño del vector.

En un algoritmo de ramificación y poda, el orden escogido para priorizar los nodos en la lista de nodos vivos . ... nunca afecta al tiempo necesario para encontrar la solución óptima. 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.

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

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)?. Solo una. 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.

Cuál es la relación de recurrencia asociada a la complejidad temporal de la siguiente función?. T(n) = 1 +2 * T(n - 1); T(0) = 1. T(n) = 2 * T(n - 1); T(0) = 1. T(n) = 1 + T(n - 1); T(0) = 1.

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 de programa. ¿Podemos comparar ambas funciones para decidir qué algoritmo es mejor?. No, porque al contar operaciones elementales, podríamos obtener una complejidad asintótica mayor que si contamos pasos de programa. 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.

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

¿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). Ω(n) y O(n^2 ). Ω(n) y O(2^n). ⊖(2^n).

Si un problema de optimización lo es para una función que toma valores continuos . .. Divide y vencerás puede resultar más eficiente que la programación dinámica iterativa en cuanto al uso de memoria. 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.

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 - 1. p, n - i. p, i.