A-c4-2024

1. Un problema de decisión en el que no hay función objetivo... (marca la opción correcta). ... solo puede ser resuelto de manera eficiente mediante un algoritmo voraz. ... no puede ser resuelto mediante la técnica de ramificación y poda. ... puede que tenga solución eficiente mediante programación dinámica.

2. De las siguientes tres afirmaciones, una es cierta y dos falsas, o bien una es falsa y dos son ciertas. Marca la que en ese sentido es diferente a las otras dos. El problema de la mochila discreta no se puede resolver mediante la técnica de divide y vencerás. El problema de la mochila continua no se puede resolver mediante la técnica de divide y vencerás pues se podría producir un número infinito de llamadas recursivas. El problema de la mochila continua no se puede resolver mediante la técnica de ramificación y poda pues se podría producir un número infinito de ramas.

De las siguientes tres afirmaciones, una es cierta y dos falsas, o bien una es falsa y dos son ciertas. Marca la que en ese sentido es diferente a las otras dos. Ramificación y poda sirve para resolver problemas que vuelta atrás no puede. Ramificación y poda siempre es más eficiente que vuelta atrás. Ramificación y poda resuelve el mismo tipo de problemas que vuelta atrás.

En el esquema de ramificaci´ on y poda, ¿qu´e estructura es la m´as adecuada si queremos realizar una exploraci´ on por niveles?. Pila. Cola sin prioridades. Cola de prioridad.

Indica cu´al de las siguientes afirmaciones sobre el problema del fontanero diligente es cierta: El esquema voraz podr´ıa no encontrar ninguna soluci´ on. Se puede demostrar que un esquema voraz encuentra siempre la soluci´ on ´ optima. Se puede demostrar que un un esquema voraz siempre encuentra alguna soluci´ on, aunque no sea ´ optima.

Indica cuál de las siguientes afirmaciones es cierta: Si un esquema de vuelta atrás encuentra la solución óptima a un problema, un esquema voraz también la encuentra siempre. Si un esquema de vuelta atrás encuentra la solución óptima a un problema, un esquema voraz también podría encontrarla. Si un esquema de vuelta atrás encuentra la solución óptima a un problema, un esquema voraz no se puede plantear.

Dada la versión restringida del problema mcp, ya tenemos cumplimentado el almacén de resultados parciales. ¿cuál es la complejidad temporal del mejor algoritmo que puede escribirse para obtener un camino óptimo?. Cuadrática, pues hay que volver a recorrer toda la tabla. Lineal, pues hay que visitar cada una de las casillas que han servido para obtenerla dificultad del camino óptimo. Constante, pues la tabla ya está construida.

Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera?. a. b. c.

Cuando un algoritmo recursivo que sigue el esquema divide y vencerás incurre en complejidades temporales prohibitivas porque se resuelven repetidamente los mismos subproblemas... . . . debemos convertirlo obligatoriamente a iterativo para evitarlo. . . . podemos guardar soluciones parciales en un almacén para evitar esa repetición, pero resolveremos inevitablemente más problemas que si lo convertimos en iterativo. . . . podemos guardar soluciones parciales en un almacén para evitar esa repetición y puede ser que resolvamos menos problemas que si lo convertimos en iterativo.

¿En qué caso la complejidad temporal del algoritmo de ordenación quicksort es igual a la complejidad temporal del algoritmo mergesort?. En el caso peor de ambos. En el caso mejor de ambos. Tanto en el caso peor como en el caso mejor de ambos.

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. a. b. c.

De las siguientes afirmaciones, 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. A Las cotas pesimistas no son compatibles con el esquema de vuelta atrás. B En el esquema de ramificación y poda, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles. C El esquema de vuelta atrás no es compatible con el uso conjunto de cotas pesimistas y optimistas.

Se dispone de un vector v que almacena números enteros en orden estrictamente creciente, y se desea averiguar si existe algún elemento que cumpla v[i] = i. De entre las estrategias que se citan, ¿cuál sería la eficiente para resolver el problema?. Algoritmo voraz. Divide y vencerás. Programación dinámica.

Tratándose de un problema de optimización, en la lista de nodos vivos de ramificación y poda... ... sólo se introducen nodos prometedores, es decir, nodos que pueden mejorar la mejor solución que se tiene en ese momento. ... puede haber nodos que no son prometedores. Las otras dos opciones son ambas ciertas.

Se pretende resolver la versión general del problema mcp y para ello se dispone de tres posibles cotas optimistas. Teóricamente, ¿cuál es la mejor si lo que se pretende es reducir la cantidad de nodos a explorar?. La que obtenga valores más pequeños (caminos de menor dificultad). La que obtenga valores más elevados (caminos de mayor dificultad. La que más se aproxime a la solución óptima del nodo en cuestión.

De las siguientes tres afirmaciones, una es cierta y dos falsas, o bien una es falsa y dos son ciertas. Marca la que en ese sentido es diferente a las otras dos. a Para que un problema tenga solución mediante programación dinámica es condición necesaria que pueda resolverse mediante divide y vencerás. b Todo problema que tiene solución mediante divide y vencerás también la tendrá mediante programación dinámica. c Todo problema que tiene solución mediante ramificación y poda ttambién la tendrá mediante programación dinámica.

17 :D. a. b. c.

Se pretende implementar mediante programación dinámica recursiva la función: double f( double x, double y ) { if( x <= y ) return 1; return g(x,y) + f(x-1,y); } Donde double g(double,double)es una función definida en otro sitio. ¿Cuál es la mejor estructura para el almacén?. double A[][]. double A[]. ninguna de las otras dos opciones es cierta.

Dado el siguiente programa recursivo: si quisieéamos mejorarlo haciendo uso de la técnica de programación dinámica, ¿cuales serían las complejidades temporal y espacial más ajustadas del algoritmo resultante?. Respectivamente, O(n) y O(1). Ambas complejidades serían O(1). Ambas complejidades serían O(n).

Con respecto a la complejidad temporal de la siguiente función, ¿cuál de las siguientes afirmaciones es cierta?. La complejidad temporal en el mejor de los casos es constante. El coste temporal exacto de la función es Θ(n). Las otras dos afirmaciones son ambas falsas.

Dada la versión general del problema mcp, ¿qué obtenemos si calculamos la media aritmética de la dificultad de las casillas que quedan por explorar a partir de un nodo cualquiera del árbol de búsqueda?. Ninguna de las otras dos opciones es cierta. Una cota optimista del nodo. Una cota pesimista del nodo.

Si en el algoritmo Mergesort, en vez de dividir el vector a ordenar en dos grupos para luego ordenarlos y mezclarlos, lo hiciésemos dividiendo el vector en tres grupos, ¿cómo quedaría el caso general de la ecuación de recurrencia asociada a la complejidad temporal del algoritmo resultante?. f(n) = n + 3f(n/3). f(n) = n/3 + 3f(n/3). f(n) = 3n + f(n/3).

23. a. b. c.

De entre los siguientes, ¿qué esquema es el más eficiente para solucionar la versión restringida del problema mcp obteniendo incluso un camino cuya dificultad coincide con la óptima?. Método voraz. Programación dinámica. Ramificación y poda.

Tenemos un vector desordenado y queremos obtener los tres elementos más pequeños. ¿Cuál sería la complejidad temporal más ajustada para hacerlo? (sin pérdida de generalidad puedes suponer que en el vector todos los elemento son distintos). Lineal con la longitud del vector. El logaritmo de la longitud del vector. Cuadrática con la longitud del vector.

26. Con respecto a n, ¿Cuál es la complejidad temporal del siguiente fragmento de código? int a =0; for( int i = 0; i <n; i += 2) for( int j = 0; j <10; j += 2) a += A[i][j]; }. Θ(n^2). Θ(n). Ninguna de las otras dos opciones es cierta.

Si se aplica el esquema programación dinámica para resolver la versión restringida del problema mcp ¿cuál es la complejidad temporal y espacial del mejor algoritmo que se puede obtener?. Temporal Θ(máx{n,m}) y espacial Θ(máx{n,m}). Temporal Θ(n * m) y espacial Θ(máx{n,m}). Temporal Θ(máx{n,m}) y espacial Θ(mín{n,m}.

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. a. b. c.

Indica cuál de las siguientes afirmaciones sobre el problema de la mochila continua es cierta: El esquema voraz podría no encontrar ninguna solución. Un esquema voraz siempre encuentra alguna solución, aunque no sea óptima. Se puede demostrar que un esquema voraz encuentra siempre la solución óptima.

Se pretende implementar mediante programación dinámica recursiva la función int f( int x, int y ) { if( x == 0 ) return 1; return g(x,y) + f(x-1,y-1); } Donde int g(int,int) es una función definida en otro sitio. Asumiendo que en la llamada inicial a f(x,y) siempre se cumplirá x==y, ¿cuál es la mejor estructura para el almacén?. int A. int A[]. ninguna de las otras dos opciones es cierta.

Si la solución óptima de un subproblema NO puede construirse de manera eficiente a partir de las soluciones óptimas de sus subproblemas, ¿cuál de los siguientes esquemas cabe esperar que se comporte mejor para obtener la solución del problema original?. Programación dinámica. Ramificación y poda. Divide y vencerás.

¿Cuál es la relación de recurrencia que representa la complejidad en el peor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase). a. b. c.

Se desea obtener la suma de los elementos de un vector de enteros usando un esquema de divide y vencerás. De las siguiente aproximaciones hay una que es válida y dos que no lo son, o viceversa. indicad la que (en este sentido) es distinta de las otras dos. Hacer un bucle que recorra el vector y vaya sumando sus elementos. Dividir el vector en dos vectores de aproximadamente igual tamaño, llamar recursivamente a la función para que sume cada uno de esos vectores y sumar los resultados devueltos. Separar los elementos pares de los impares en dos vectores, llamar recursivamente a la función para que sume cada uno de esos vectores y sumar los resultados devueltos.

Dada la versión general del problema mcp queremos listar todos los caminos posibles (sean o no los óptimos). Lo más adecuado sería usar una técnica de ramificación y poda ya que es muy importante el orden en el que se exploran las soluciones parciales. El orden en el que se exploran las soluciones parciales no es relevante; por ello, la técnica ramificación y poda no aporta nada con respecto a vuelta atrás. Con una buena cota pesimista inicial, el esquema de ramificación y poda es más eficiente que el de vuelta atrás.

Supongamos el problema de la mochila discreta modificado de manera que cada objeto puede seleccionarse, no seleccionarse o seleccionarse solo la mitad obteniendo en este caso la mitad de su valor. ¿Qué algoritmo resulta ser más eficiente para encontrar la solución óptima?. Un algoritmo de ramificación y poda. Un algoritmo de vuelta atrás. Un algoritmo voraz.

¿Cuál es la complejidad temporal de la aproximación voraz a la solución de la versión restringida del problema mcp?. O(n*m). O(n+m). O(3^(n+m) ).

Con respecto al parámetro n,¿Cuál es la complejidad temporal de la siguiente función?. Θ(n). Θ(n log n). Θ( log^2 n).

Se pretende resolver la versión general del problema mcp y para ello se dispone de tres posibles cotas pesimistas. ¿Cuál deberíamos utilizar para conseguir un programa lo más rápido posible?. Depende , para contestar a esta cuestión es necesario disponer de más información. La que obtenga valores más elevados (caminos de mayor dificultad). La que más se aproxime a la solución óptima del nodo en cuestión.

a. b. c.

Qué ocurre con la complejidad temporal de un algoritmo de programación dinámica cuando se mejora la complejidad espacial?. Que normalmente aumenta. Que normalmente también disminuye. Que normalmente no cambia.