ADA - teoria

Dado el problema del laberinto con tres movimientos, se desea saber el n´umero de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n,m) y para ello se aplica el esquema de programaci´on din´amica para obtener un algoritmo lo m´as eficiente posible en cuanto a complejidad temporal y espacial. ¿Cu´ales ser´ıan ambas complejidades?. Temporal Θ(n · m) y espacial Θ(m´ın{n, m}). Temporal Θ(m´ax{n, m}) y espacial Θ(m´ax{n, m}). Temporal Θ(n · m) y espacial Θ(n · m).

Dado el problema del laberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de programacion dinamica. En cuanto a la complejidad temporal, ¿cual es la mejora de la version recursiva con memoizacion frente a la recursiva ingenua que se obtiene a partir del esquema divide y venceras?. De una complejidad cuadratica que se obtendrıa con la ingenua se reducir´ıa a lineal con la de memoizacion. De una complejidad exponencial que se obtendrıa con la ingenua se reducir´ıa a polinomica con la de memoizacion. La mejora no esta garantizada puesto que la version recursiva con memoizacion podrıa ser peor que la obtenida a partir del esquema divide y venceras.

Dado un problema de minimizacion resuelto mediante un esquema de ramificacion y poda, ¿que ocurre si la cota optimista resulta ser un valor excesivamente pequeno?. Que se podrıa podar el nodo que conduce a la solucion optima. Que se podria explorar mas nodos de los necesarios. Que se podrıa explorar menos nodos de los necesarios.

En ausencia de cotas optimistas y pesimistas, la estrategia de vuelta atras. . . . . . no se puede usar para resolver problemas de optimizacion. . . . no recorre todo el arbol si hay manera de descartar sub ´ arboles ´ que representan conjuntos de soluciones no factibles. . . . debe recorrer siempre todo el arbol.

Se desea obtener todas las permutaciones de una lista compuesta por n elementos. ¿Que esquema es el mas adecuado?. Divide y venceras, puesto que la divisi ´ on en sublistas se podrıa hacer en tiempo constante. Ramificacion y poda, puesto que con buenas funciones de cota es mas eficiente que vuelta atr ´ as. Vuelta atras, es el esquema mas eficiente para este problema.

Dado el problema del laberinto con tres movimientos, ¿cual de las estrategias siguientes proveerıa de una cota optimista para ramificacion y poda?. Suponer que en adelante todas las casillas del laberinto son accesibles. Las otras dos estrategias son ambas validas. Suponer que ya no se van a realizar mas movimientos.

En el problema del viajante de comercio (travelling salesman problem) queremos listar todas las soluciones factibles. Lo mas adecuado serıa usar una tecnica de ramificacion 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 tecnica ramificacion y poda no aporta nada con respecto a vuelta atras. Lo mas importante es conseguir una cota pesimista adecuada. Las diferencias entre ramificacion y poda y vuelta atras son irrelevantes en este caso.

Dada la siguiente funcion: int exa (string & cad, int pri, int ult){ if (pri>=ult) return 1; else if (cad[pri]==cad[ult]) return exa(cad, pri+1, ult-1); else return 0; }. O(n). O(log n). O(n^2).

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. Ω(n^2) ⊂ Ω(n^3). O(n^2) ⊂ O (n^3). Θ(n^2) ⊂ Θ(n^3).

Dado un problema de minimizacion resuelto mediante un esquema de ´ ramificacion y poda, ¿qu ´ e propiedad cumple una cota optimista?. Siempre es mayor o igual que la mejor solucion posible alcanzada. Las otras dos opciones son ambas falsas. Asegura un ahorro en la comprobacion de todas las soluciones ´ factibles.

Queremos resolver mediante vuelta atras el problema de las 8 reinas (colocar 8 reinas en un tablero de ajedrez de manera que no se maten mutuamente). Una buena cota optimista permitirıa: No es aplicable este tipo de podas a este problema. Muy probablemente, explorar menos nodos. Muy probablemente, resolver el problema de forma m´as r´apida.

De las siguientes afirmaciones marca la que es verdadera. Las cotas pesimistas no son compatibles con un esquema de vuelta atras. En un esquema de vuelta atras, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles. El esquema de vuelta atras no es compatible con el uso conjunto de cotas pesimistas y optimistas.

En el esquema de vuelta atras, los mecanismos de poda basados en la mejor solucion hasta el momento... ... garantizan que no se va a explorar todo el espacio de soluciones posibles. Las otras dos opciones son ambas verdaderas. ... pueden eliminar vectores que representan posibles soluciones factibles.

¿Que tienen en comun los algoritmos de ordenacion Quicksort y Mergesort. La complejidad temporal de la division en subproblemas. La complejidad temporal de la combinacion de las soluciones ´ parciales. El numero de llamadas recursivas que hacen en el mejor de los ´ casos.

¿Que nos proporciona la media aritmetica entre el coste temporal asintotico (o complejidad temporal) en el peor caso y el coste temporal asintotico en el mejor caso?. El coste temporal promedio. El coste temporal asintotico en el caso medio. En general, nada de interes.

16. Dada la siguiente funcion: int exa (vector <int>& v){ int j, i=1, n=v.size(); if (n>1) do{ int x = v[i]; for (j=i; j >0 and v[j-1] >x; j--) v[j]=v[j-1]; v[j]=x; i++; } while (i<n); return 0; }. La complejidad temporal en el mejor de los casos es Ω(n). La complejidad temporal en el mejor de los casos es Ω(1). La complejidad temporal exacta es Θ(n^2).

Dado el problema del laberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla inicial ´ (1,1) hasta la casilla (n, m) y para ello se aplica un esquema de divide y venceras.¿Cual serıa la recurrencia apropiada para el caso general?. nc(n, m) = nc(n − 1, m) ∗ nc(n, m − 1) ∗ nc(n − 1, m − 1). Ninguna de las otras dos recurrencias es valida. nc(n, m) = nc(n − 1, m) + nc(n, m − 1) + nc(n − 1, m − 1).

Dado el problema del laberinto con tres movimientos, ¿se puede aplicar un esquema de programacion dinamica para obtener un camino de salida?. Sı, con este esquema siempre se puede encontrar un camino de salida si existe. No, para garantizar que se encuentra un camino de salida hay que aplicar metodos de busqueda exhaustiva como vuelta atras o ramificacion y poda. No, con este esquema se puede conocer el numero total de caminos distintos que conducen a la salida pero no se puede saber la composicion de ninguno de ellos.

Dado el problema de las torres de Hanoi resuelto mediante divide y venceras, ¿cual de las siguientes relaciones recurrencia expresa mejor su complejidad temporal para el caso general, siendo n el numero de discos?. T(n) = 2T(n − 1) + n. T(n) = T(n − 1) + n. T(n) = 2T(n − 1) + 1.

En un algoritmo de optimizacion resuelto mediante ramificacion y poda ¿Podrıa encontrarse la solucion optima sin haber alcanzado nunca un nodo hoja?. 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 solucion hasta el momento. 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.

El algoritmo de ordenacion´ Quicksort divide el problema en dos subproblemas. ¿Cual es la complejidad temporal asintotica de realizar esa division?. Θ(log n). Θ(n). Θ(n log n).

En un problema de optimizacion, si el dominio de las decisiones es un conjunto infinito,. es probable que a traves de programacion dinamica se obtenga un algoritmo eficaz que lo solucione. podremos aplicar el esquema vuelta atras siempre que se trate de un conjunto infinito numerable. una estrategia voraz puede ser la unica alternativa.

Un algoritmo recursivo basado en el esquema divide y venceras... ... alcanza su maxima eficiencia cuando el problema de tamaño se divide en a problemas de tamano n/a. ... nunca tendra un coste temporal asintotico (o complejidad temporal) exponencial. Las otras dos opciones son ambas verdaderas.

Decid cual de estas tres estrategias proveerıa la cota pesimista mas ajustada al valor optimo de la mochila discreta: Asumir que ya no se van a coger mas objetos. Completar las decisiones restantes basandose en la mejor solucion voraz que pueda encontrarse para los restantes objetos y espacio disponible de la mochila. El valor de una mochila que contiene todos los objetos aunque se pase del peso maximo permitido.

¿Que complejidad se obtiene a partir de la relaci ´ on de recurrencia ´ T(n) = 9T(n/3) + n^3 con T(1) = O(1)?. O(n^3). O(n log n). O(n^3 log n).

Si el coste temporal de un algoritmo es T(n), ¿cual de las siguientes situaciones es imposible?. T(n) ∈ O(n) y T(n) ∈ Θ(n). T(n) ∈ Ω(n) y T(n) ∈ Θ(n^2). T(n) ∈ Θ(n) y T(n) ∈ Ω(n^2).

¿Cual de las siguientes estrategias de busqueda es mas apropiada en un esquema de vuelta atras?. Ninguna de las otras dos estrategias es compatible con el esquema de vuelta atras. Explorar primero los nodos con mejor cota optimista. Explorar primero los nodos con mejor valor hasta el momento en la funcion que se pretende optimizar.

¿Cual seria la complejidad temporal de la siguiente funcion tras aplicar programacion dinamica? double f(int n, int m) { if(n == 0) return 1; return m * f(n-1,m) * f(n-2,m); }. Θ(n^2). Θ(n · m). Θ(n).

Se desea resolver el problema de la potencia enesima (x^n), asumiendo que n es par y que se utilizara la siguiente recurrencia: pot(x,n) = pot(x,n/2) * pot(x,n/2); ¿Que estrategia resulta ser mas eficiente en cuanto al coste temporal?. Divide y venceras. En este caso tanto programacion dinamica como divide y venceras resultan ser equivalentes en cuanto a la complejidad temporal. Un algoritmo recursivo con memoizacion.

¿Cual de estos problemas tiene una soluci ´ on eficiente utilizando ´ programaci´on din´amica?. El problema de la asignacion de tareas. La mochila discreta con pesos y valores reales positivos. El problema del cambio.

Dada la siguiente funcion (donde ´ max(a,b)∈ Θ(1)): float exa(vector<float>&v,vector<int>&p,int P,int i) { float a, b; if (i>=0){ if (p[i] <= P) a= v[i]+exa(v,p,P-p[i],i-1); else a= 0; b= exa(v,p,P,i-1); return max(a,b); } return 0; }. La complejidad temporal en el peor de los casos es O(2^n). La complejidad temporal en el mejor de los casos es Ω(n^2). La complejidad temporal en el peor de los casos es O(n^2).

Sea la siguiente relacion de recurrencia ´ { 1 si n ≤ 1 T(n) = { { 8T(n/8) + g(n) en otro caso Si T(n) ∈ Θ(n^2), ¿en cual de estos tres casos nos podemos encontrar?. g(n) = n^2. g(n) = n^3. g(n) = n.

Si f /∈ O(g1) y f ∈ O(g2) entonces siempre se cumplira: f ∈ Ω(mın(g1, g2)). f /∈ O(max(g1, g2)). f ∈ Ω(g1 + g2).

Si lım n→∞ f(n) g(n) = ∞ entonces . . . ... f(n) ∈ O(g(n)). ... f(n) ∈ Ω(g(n)). ... f(n) ∈ Θ(g(n)).

El esquema de vuelta atras... Las otras dos opciones son ambas verdaderas. Garantiza que encuentra la solucion optima a cualquier problema de seleccion discreta. Se puede aplicar a cualquier tipo de problema aunque el coste temporal es elevado.

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. n + n log2 n ∈ Ω(n + n log2 n). O(n^2) ⊂ O(2^log2 n). Ω(n^2) ⊂ Ω(n).

Con respecto a la complejidad espacial de los algoritmos de ordenacion Quicksort, Heapsort y Mergesort ... Las complejidad espacial de todos ellos es lineal con el tamano del vector a ordenar. Mergesort y Heapsort tienen complejidad espacial lineal con el tamano del vector a ordenar, la de Quicksort es constante. Mergesort tiene complejidad espacial lineal con el tamano del vector a ordenar, la de los otros dos es constante.

Se desea ordenar una lista enlazada de n elementos adaptando el algoritmo Mergesort. En este caso, al tratarse de una lista, la complejidad temporal asintotica de realizar la division en subproblemas resulta ser lineal con el tamaño de esa lista. ¿Cual serıa entonces el coste temporal de realizar dicha ordenacion?. Θ(n^2). Ninguna de las otras dos opciones es cierta. Θ(n log n).

Se pretende resolver el problema del viajante de comercio (travelling salesman problem) mediante el esquema de vuelta atras, ¿cual de los siguientes valores se espera que se comporte mejor para decidir si un nodo es prometedor?. La suma de los pesos de las k aristas restantes mas cortas, donde k es el numero de ciudades que quedan por visitar. El valor que se obtiene de multiplicar k por el peso de la arista mas corta de entre las restantes, donde k es el numero de ciudades que quedan por visitar. La suma de los pesos de las aristas que completan la solucion paso a paso visitando el vertice mas cercano al ultimo visitado.

La siguiente relacion de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una funcion polinomica: 1 si n ≤ 1 T(n) = { 2T(n/2) + g(n) en otro caso Di cual de las siguientes afirmaciones es cierta: Si g(n) ∈ Θ(n) la relacion de recurrencia representa la complejidad temporal del algoritmo de ordenacion mergesort. Si g(n) ∈ Θ(1) la relacion de recurrencia representa la complejidad temporal del algoritmo de busqueda dicotomica. Si g(n) ∈ Θ(n^2) la relacion de recurrencia representa la complejidad temporal del algoritmo de ordenacion mediante insercion binaria.