Mod1Final

El esquema voraz... Puede que no encuentre una solución pero si lo hace se garantiza que es la óptima. Las otras dos opciones son ambas falsas. Garantiza encontrar una solución a cualquier problema, aunque puede que no sea óptima.

Un algoritmo recursivo basado en el esquema divide y vencerás ... ... alcanza su máxima eficiencia cuando el problema de tamaño n se divide en a problemas de tamaño n/a. ... nunca tendrá un coste temporal asintótico exponencial. Las dos anteriores son verdaderas.

¿Cuál es el coste temporal de crear un montículo de máximos a partir de un vector ordenado de mayor a menor?. Θ(n). Θ(n·log(n)). Θ(1).

En un problema de minimización resuelto mediante ramificación y poda, una cota pesimista es... ... una cota superior para el valor óptimo, pero que nunca coincide con este. ... una cota inferior para el valor óptimo que a veces coincide con este. Ninguna de las otras dos opciones es cierta.

Indica cuál de los siguientes conjuntos es el conjunto O(f): (a). (b). (c).

Uno de estos tres algoritmos de ordenación no opera directamente sobre el vector, y necesita almacenamiento adicional para los elementos del mismo. ¿Cuál es?. Mergesort. Heapsort. Quicksort.

Encargamos a un becario que elabore un algoritmo para sumar todos los números de un vector. Al cabo de un rato nos viene con un algoritmo cuya complejidad temporal es O(log(n)). ¿Qué hacemos?. Damos las gracias al becario, ese es el algoritmo obvio. Despedimos al becario, eso es imposible. Subimos el sueldo al becario, ha encontrado un algoritmo innovador.

Se pretende calcular el valor 2^n, n∈N, haciendo una transcripción literal de la expresión de la imagen. ¿Cuál sería la complejidad temporal asintótica, en función de n, del algoritmo resultante?. O(2^n). O(n²). O(n).

En cuanto a la complejidad temporal de la siguiente función, ¿qué podemos decir acerca del mejor de los casos?. Que el mejor de los casos ocurre cuando el vector tiene 2 elementos o menos y la complejidad es Ω(1). Que uno de los mejores casos ocurre cuando v[j] = v[1] ∀j ∈ N y la complejidad es Ω(n). Las otras dos opciones son ambas falsas.

¿Cuál es el caso peor del algoritmo de ordenación Quicksort que toma el primer elemento como pivote?. Cuando el elemento pivote queda siempre en medio. Cuando debemos hundir el pivote hasta el fondo del montículo. Cuando el elemento pivote queda siempre en uno de los dos extremos.

Cuál es la complejidad temporal en función del tamaño del problema (n) de multiplicar dos matrices cuadradas?. O(n²). O(n^(3/2)). O(n³).

En un algoritmo de optimización resuelto mediante ramificación y poda ¿Podrı́a encontrarse la solución óptima sin haber alcanzado nunca un nodo hoja?. Sı́, pero esto solo podrı́a ocurrir si se hace uso de cotas pesimistas. Sı́, esto puede ocurrir incluso si no se hace uso de cotas pesimistas. No, los nodos hojas son los nodos completados y por lo tanto hay que visitar al menos uno de ellos para almacenarlo como la mejor solución hasta el momento.

¿Puede utilizarse relaciones de recurrencia para analizar la complejidad de un algoritmo de vuelta atrás?. No, ya que siempre saldrı́a una complejidad exponencial. No, las relaciones de recurrencia no se pueden aplicar en este caso. Sí.

Se pretende mejorar mediante programación dinámica iterativa la siguiente función (v1 y v2 son vectores definidos como variables globales). ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(m). O(n). O(m·n).

De las siguientes situaciones, o bien dos son posibles y una no lo es, o bien al contrario, solo una es posible y las otras dos no lo son. Marca la que, en este sentido, es diferente a las demás. f(n) ∈ O(n) y f(n) ∈ Ω(1). f(n) ∈ O(n) y f(n) ∈ Ω(n²). f(n) ∈ O(n) y f(n) ∈ O(n²).

Existen dos algoritmos que para ordenar un vector de n elementos, buscan el máximo de esos n elementos, lo intercambian con el n-ésimo elemento para ponerlo al final, y luego ordenan, usando el mismo algoritmo, el vector de las primeras n - 1 componentes. ¿Cuál de las afirmaciones siguientes es cierta?. Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por selección; el primero tiene un coste temporal O(n·log(n)) y el segundo, O(n²). Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por burbuja o bubblesort; el primero tiene un coste temporal O(n·log(n)) y el segundo, O(n²). Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por selección; el primero tiene un coste temporal O(n) y el segundo, O(n²).

La complejidad temporal del algoritmo Mergesort cuando se aplica a un vector de tamaño n es. . . (selecciona la más ajustada). . . . Ω(n·log(n)) y O(n²). . . . Θ(n·log(n)). . . . Ω(n) y O(n²).

Si se cumple el límite de la imagen, se puede afirmar que: f(n) ∈ Θ(n^k). f(n) = an^k. f(n) ∈ O(n).

¿Podemos saber cuál serı́a el elemento en posición k cuando ordenáramos un vector de n elementos sin tener que ordenarlo?. Sı́, y el algoritmo es Ω(n) y O(n²), aunque la frecuencia de los casos peores disminuye muy rápidamente con n. No. Debemos ordenarlo. Sı́, y el algoritmo es Ω(n·log(n)) y O(n²), aunque la frecuencia de los casos peores disminuye muy rápidamente con n.

Se dispone de un conjunto de n valores numéricos dispuestos en forma de árbol binario y se desea obtener el valor de la suma de todos ellos. ¿Cuál es la complejidad temporal del mejor algoritmo que se puede escribir?. O(log(n)). O(n·log(n)). O(n).

De acuerdo con la siguiente imagen: Una implementación ingenua de la función T(n), la cual llamarı́a a T(n-1), T(n-2) y T(n-3) tendrı́a una complejidad prohibitiva por la repetición de cálculos que se producirı́a. Es posible una implementación de programación dinámica iterativa con complejidad Θ(n). El problema no tiene una solución de programación dinámica iterativa pero se puede re- solver añadiendo memoización al cálculo recursivo ingenuo en el que el cálculo de T(n) comporta realizar las llamadas a T(n-1), T(n-2) y T(n-3).

En cuanto a la complejidad temporal de la siguiente función, ¿cuál de las siguientes formulaciones expresa mejor su complejidad en el peor de los casos?. (a). (b). (c).

Queremos formar una suma M con el número mı́nimo posible de monedas tomadas (con repetición) de un conjunto de m monedas C = {c1, c2, c3, ..., cm}. Una solución recursiva posible es la de la imagen. ¿Serı́a posible convertir esta solución recursiva en un algoritmo de programación dinámica iterativa con complejidad temporal O(M|C|)?. No, no hay manera de evitar la repetición de cálculos y por tanto la complejidad temporal es prohibitiva. Sı́, ya que es posible calcular nopt(x) para cualquier x > 0 usando nopt (y) calculados para y < x. No, pero sı́ que se puede añadir memoización al cálculo para evitar la repetición de cálculos.

Una de las tres afirmaciones siguientes sobre los algoritmos que obtienen el árbol de recubrimiento mı́nimo de un grafo ponderado no dirigido es cierta. ¿Cuál es?. El algoritmo de Kruskal va ampliando un único árbol de recubrimiento mı́nimo. El algoritmo de Prim va ampliando un único árbol de recubrimiento mı́nimo. El algoritmo de Prim se puede acelerar usando una estructura de datos de conjuntos disjuntos con las operaciones union y find.

En la estrategia de ramificación y poda se suele usar una cola de prioridad para decidir en qué orden se expanden los nodos. Imaginemos un problema de optimización. ¿Puede ser que el valor por el cual se ordenan los nodos sea una cota pesimista del nodo?. No, porque para podar necesitamos una cota optimista. No, porque una cota pesimista es tı́picamente el valor que se encuentra en una de las hojas que cuelga del nodo. Sí.

¿Se puede resolver mediante ramificación y poda un problema de selección discreta en el que cada una de las n decisiones se toman de un conjunto finito diferente?. Sí, siempre. No. Las decisiones deben ser todas de la misma naturaleza. Sı́, pero sólo si las decisiones son todas binarias.

Se pretende resolver el problema del viajante de comercio (travelling salesman problem) mediante el esquema de vuelta atrás, ¿cuál de los siguientes valores se espera que se comporte mejor para decidir si un nodo es prometedor?. El coste del mı́nimo árbol de recubrimiento de las ciudades restantes. La suma de los pesos de las k aristas restantes más cortas, donde k es el número de ciudades que quedan por visitar. El valor que se obtiene de multiplicar k por el peso de la arista más corta de entre las restantes, donde k es el número de ciudades que quedan por visitar.

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

Tengo que sumar una larga lista de n cantidades diferentes y se me ha ocurrido que una manera de ganar tiempo es la siguiente estrategia recursiva: parto la lista en dos sublistas iguales, calculo su suma por separado usando la misma técnica y luego sumo las dos cantidades. Cuando al partir una lista me quedo con una cantidad sólo, la suma es esa cantidad, y si me quedan cero cantidades, la suma es cero. ¿Gano tiempo, es decir, hago menos sumas?. No, en este caso el coste temporal es Θ(n·log(n)). Sı́, ya que en este caso el coste temporal se reduce a Θ(log(n)). No, ya que la complejidad temporal del método propuesto es la misma que la de sumar una a una las cantidades.

Con respecto al parámetro n, ¿Cuál serı́a la complejidad temporal de la siguiente función si se aplicara memoización?. lineal. constante. logarítmica.

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. Θ(log(n²)) = Θ(log(n³)). O(n) ⊂ O(1). Ω(n) ⊂ Ω(1).

¿Cuál de las siguientes formulaciones expresa mejor la complejidad temporal, en función del parámetro n, de la siguiente función? (asumimos que n es potencia exacta de 2). (a). (b). (c).

¿Puede ocurrir que la solución recursiva de estilo “divide y vencerás” pero con memoización de un problema resuelva menos subproblemas que la mejor solución iterativa posible de programación dinámica?. No, nunca. Sı́, porque no existe garantı́a de que la mejor solución iterativa posible no resuelva problemas repetidos, mientras que la técnica de memoización lo garantiza directamente mediante el uso de un almacén. Sı́, porque la mejor solución iterativa posible de programación dinámica puede resolver subproblemas que no sean necesarios al resolver subproblemas posteriores.

De las siguientes expresiones, 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. (a). (b). (c).

En un algoritmo de búsqueda exhaustiva, ¿Qué ocurre si la cota pesimista de un nodo se corresponde con una solución que no es factible?. Que podrı́a descartarse un nodo que conduce a la solución óptima. Nada especial, las cotas pesimistas no tienen por qué corresponderse con soluciones factibles. Que el algoritmo serı́a más lento pues se explorarı́an más nodos de los necesarios.

Tenemos un conjunto de n enteros positivos y queremos encontrar el subconjunto de tamaño m de suma mı́nima. Lo más adecuado serı́a usar una técnica de ramificación y poda, aunque en el peor caso el coste temporal asintótico (o complejidad temporal) serı́a exponencial. Para encontrar la solución habrı́a que probar con todas las combinaciones posibles de m enteros, con lo que la técnica de ramificación y poda no aporta nada con respecto a vuelta atrás. Una técnica voraz darı́a una solución óptima.

Sea el vector v[8] = {8, 6, 4, 5, 4, 3, 2, 2}. Indica cuál de las siguientes opciones es cierta. (se asume la notación del lenguaje C/C++ en la que el primer elemento del vector está en la posición 0, es decir, en v[0]). El vector v no es un montı́culo máximo porque el elemento v[3]=5 debe ser “flotado” (desplazado hacia la izquierda). El vector v es un montı́culo máximo. El vector v no es un montı́culo máximo porque el elemento v[2]=4 debe ser “hundido” (desplazado hacia la derecha)..

Sea un problema de optimización por selección discreta, con restricciones, en el que se deben tomar n decisiones booleanas para optimizar un indicador, y se abordará mediante un método de búsqueda y enumeración (vuelta atrás, ramificación y poda). ¿Cuál de las siguientes afirmaciones es correcta?. La complejidad temporal será como mucho O(n·log(n)) porque en general basta con ordenar adecuadamente las decisiones para convertir cualquier problema de este tipo en un problema de complejidad temporal lineal. La complejidad temporal en el peor caso será O(n²) ya que se toman n decisiones binarias. Puede haber problemas para los que la complejidad será exponencial o peor; ninguna estrategia de poda puede garantizar que esto no va a ocurrir.

Tenemos un “superprocesador” que tiene una instrucción que permite la ordenación de 100 elementos en un tiempo constante. Para este superprecesador, adaptamos el algoritmo Mergesort de forma que cada vez que queremos ordenar menos de 100 elementos, en lugar de hacer las llamadas recursivas, llama a esta instrucción. ¿cuál serı́a la complejidad de este algoritmo?. O(n·log(n)). O(n). O(1).

¿Cuál de estos problemas no tiene una solución eficiente utilizando programación dinámica?. La mochila discreta cuyos pesos son números naturales. El problema de la asignación de tareas. El problema del cambio.