¿Qué mecanismo se usa para acelerar el algoritmo de Prim? El TAD "Union-find" Mantener una lista de los arcos ordenados según su peso. Mantener para cada vértice su "padre" más cercano. Se pretende implementar mediante programación dinámica iterativa la función recursiva:
unsigned f ( unsigned x, unsigned v ( ) ) {
if (x==0)
return 0;
unsigned m = 0;
for ( unsigned k = 1 ; k < x; k++ )
m =max( m, v [k] + f( x-k, v ) ) ;
return m;
}
¿Cuál es la mejor complejidad espacial que se puede conseguir? O(1) O(x) O(x^2). El valor que se obtiene con el método voraz para el problema de la mochila discreta es... una cota superior para el valor óptimo. una cota inferior para el valor óptimo que a veces puede ser igual a este. una cota inferior para el valor óptimo, pero que nunca coincide con este. Si f1(n) ∈ O( ( g1 n)) y f2(n) ∈ O( ( g2 n)) entonces...
f1(n) + ( f2 n) ∈ O( ( g1 n) + ( g2 n)) Las otras dos opciones son ambas ciertas f1(n) + ( f2 n) ∈ O(max( ( g1 n), ( g2 n))). Con respecto a la complejidad espacial de los algoritmos de ordenación Quicksort, Heapsort y Mergesort y sin considerar el espacio
que pueda ocupar las posibles pilas de recursión: Las complejidad espacial de todos ellos es lineal con el tamaño del vector a ordenar Mergesort tiene complejidad espacial lineal con el tamaño del vector a ordenar, la de los otros dos es constante. Mergesort y Heapsort tienen complejidad espacial lineal con el tamaño del vector a ordenar, la de Quicksort es constante. La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde es una función polinómica:
T(n) = { 1 si n ≤ 1
2T( n/2) + g(n) en otro caso
Di cuál de las siguientes afirmaciones es cierta: Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante
inserción binaria. Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica. ¿En qué caso la complejidad temporal del algoritmo de ordenación Quicksort es igual a la complejidad temporal del algoritmo Mergesort? Tanto en el caso peor como en el caso mejor de ambos En el caso peor de ambos. En el caso mejor de ambos. Para que la complejidad de un algoritmo presente caso mejor y peor distintos ... es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño es condición necesaria que existan instancias distintas del problema con el mismo tamaño. es condición suficiente que existan instancias distintas del problema con el mismo tamaño. Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces f ∈ Θ(g1 + g2) f ∉ Θ(max(g1, g2 )) f ∈ Θ(g1 * g2 ). Si f ∉ O(g1 ) y f ∈ O(g2 ) entonces NO siempre se cumplirá: f ∈ O(max(g1, g2)) f ∈ Ω(g1 + g2) f ∈ Ω(min(g1, g2)). Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál es más eficiente en cuanto a coste temporal?
unsigned long pot2_1(unsigned n){
if (n==0) return 1;
if (n%2==0) return pot2_1( n/2 ) * pot2_1( n/2 );
else return 2 * pot2_1( n/2 ) * pot2_1( n/2 );
}
unsigned long pot2_2(unsigned n){
if (n==0) return 1;
unsigned long aux= pot2_2( n/2 );
if (n%2==0) return aux * aux;
else return 2 * aux * aux;
} La primera, pot2_1(n), es más eficiente que la otra. La segunda, pot2_2(n), es más eficiente que la otra. Las dos funciones son equivalentes en cuanto a coste temporal. Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?
void f( unsigned n ){
if( n < 1 ) return;
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ )
for( int k = 0; k < n; k++ )
cout << "*";
for( int i = 0; i < 8; i++ )
f( n / 2 );
} Θ(n^3 log n) Θ(n^2 log n) Θ(n^3). La solución óptima al problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado ... debe construirlo arista a arista: vértice a vértice no puede ser. debe construirlo vértice a vértice: arista a arista no puede ser puede construirlo tanto vértice a vértice como arista a arista. En el método voraz ... siempre se encuentra solución pero puede que no sea la óptima. es habitual preparar los datos para disminuir el coste temporal de la función que determina cuál es la siguiente decisión a tomar. el dominio de las decisiones sólo pueden ser conjuntos discretos o discretizables. Se pretende aplicar la técnica memoización a la siguiente función recursiva:
int f ( int x , int y ) {
if ( x > y ) return 1 ;
return x *(y -1) + f (x,y- 2 ) ;
}
En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante? O(y - x), tanto temporal como espacial. Temporal O(x * y) y espacial O(x) Ninguna de las otras dos opciones es correcta. La solución de programación dinámica iterativa del problema de la mochila discreta .. calcula menos veces el valor de a mochila que la correspondiente solución de programación dinámica recursiva. tiene la restricción de que los valores de los objetos tienen que ser números discretos o discretizables tiene la restricción de que los pesos de los objetos tienen que ser valores discretos o discretizables. ¿Cuál de los siguientes pares de problemas son equivalentes en cuanto al tipo de solución (óptima, factible, etc.) aportada por el método voraz? La mochila continua y la asignación de tareas. El fontanero diligente y el problema del cambio. La mochila discreta y la asignación de tareas. De los problemas siguientes, indicad cuál no se puede tratar eficientemente como los otros dos: El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y de sus valores. El problema del cambio, o sea, el de encontrar la manera de entregar una cantidad de dinero usando el mínimo de monedas posibles. El problema de cortar un tubo de forma que se obtenga el máximo beneficio posible. Se pretende implementar mediante programación dinámica iterativa la función recursiva:
unsigned f ( unsigned x , unsigned v[] ) {
if ( x==0)
return 0;
unsigned m = 0;
for ( unsigned y = 1 ; y < x; y ++ )
m = max ( m, v[y] + f ( x - y , v ) ) ;
return m;
}
¿Cuál es la mejor complejidad temporal que se puede conseguir? O(x) O(x*y) O(x^2). ¿Cuál de estas estrategias voraces obtiene siempre un mejor valor para la mochila discreta? Ninguna de las otras dos opciones es cierta. Meter primero los elementos de mayor valor específico o valor por unidad de peso. Meter primero los elementos de mayor valor. Cuando la descomposición recursiva de un problema da lugar a subproblemas de tamaño similar, ¿qué esquema promete ser más apropiado? El método voraz. Programación dinámica. Divide y vencerás, siempre que se garantice que los subproblemas no son del mismo tamaño. En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función?
int f( int n ) {
int k=0;
for (int i n; i > 0; i/=3)
for (int j =i ; j > 0; j -=3)
k++;
return k ;
} 0(n) 0(n log(n)) 0(n^2). Si el coste temporal de un algoritmo es T(n), ¿cuál 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). 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) Θ(log n). Por qué muchos algoritmos voraces presentan complejidades temporales en O( n log n )? Porque el proceso de selección de los elementos que se incorporarán a la solución es siempre O(n log n). Porque primero ordenan de alguna manera los elementos y porque una vez ordenados la complejidad temporal del proceso de selección de los elementos que se incorporarán a la solución está en O( n log n ). Porque primero ordenan de alguna manera los elementos y porque una vez ordenados la complejidad temporal del proceso de selección de los elementos que se incorporarán a la solución es estrictamente inferior a O(n log n). En un problema de optimización, si el dominio de las decisiones es un conjunto infinito podremos aplicar el esquema vuelta atrás siempre que se trate de un conjunto infinito numerable. una estrategia voraz puede ser la única alternativa. es probable que a través de programación dinámica se obtenga un algoritmo eficaz que lo solucione. 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. Θ(log2 (n)) = Θ(log3 (n)) Θ(log2(n)) = Θ(log3 (n)) log(n^3) ∉ Θ(log3(n)). ¿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. ¿Cuál es la complejidad temporal de la siguiente función recursiva?
unsigned desperdicio (unsigned n) {
if (n<=1)
return 0;
unsigned sum = desperdicio (n/ 2) + desperdicio (n/ 2) ;
for (unsigned i =1 ; i <n- 1 ; i++)
for (unsigned j =1 ; j<=i ; j ++)
for (unsigned k=1 ; k<=j ; k++)
sum+=i*j*k;
return sum;
} Θ(n^3 log n) Θ(n^3) Θ(2^n). La solución de programación dinámica iterativa del problema de la mochila discreta ... tiene un coste temporal asintótico exponencial. calcula menos veces el valor de la mochila que la correspondiente solución de programación dinámica recursiva. tiene la restricción de que los pesos tienen que ser enteros positivos. Decid cuál de estas tres es la cota pesimista más ajustada al valor óptimo de la mochila discreta: El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos. El valor de la mochila continua correspondiente. El valor de una mochila que contiene todos los objetos restantes aunque se pase del peso máximo permitido. Tenemos una función recursiva con la siguiente cabecera:
double f( const double & )
Con sólo esta información, ¿cuál podría ser una definición adecuada para el almacén? vector<int> A; Ninguna de las otras dos opciones son válidas. vector<double> A;. Dada la versión restringida del problema del laberinto, si solo se desea conocer la longituddel camino de salida más corto, ¿cuál es la mejor complejidad temporal y espacial que sepuede conseguir si se aplica programación dinámica? Temporal Θ(nm) y espacial Θ(mín{n,m}) Ninguna de las otras dos opciones es cierta. Temporal Θ(nm) y espacial Θ(nm). El uso de funciones de cota en ramificacion y poda... puede reducir el numero de instancias del problema que pertenecen al caso peor transforma en polinomicas complejidades que antes eran exponenciales garantiza queel algoritmo va a ser mas eficiente ante cualquierinstancia del problema. Si el coste temporal de un algoritmo es T(n) , ¿cual de las siguientes situaciones es imposible? T(n) pertenece Ω(n) y T(n) pertenece Θ(n^2) T(n) pertenece O(n) y T(n) pertenece Θ(n) T(n) pertenece Θ(n) y T(n) pertenece Ω(n^2). De las siguientes afirmaciones marca la que es verdadera. Las cotas pesimistas no son compatibles con un esquema de vuelta atras. El esquema de vuelta atras no es compatible con el uso conjuntode cotas pesimistas y optimistas. En un esquema de vuelta atras, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles. 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) O(n^2) ⊂ O(2^log2 n) n + n log2 n ∈ Ω(n + n log2 n). La ventaja de RyP frente a Backtracking es que la primera genera las soluciones posibles al problema mediante.. Las otras dos son verdaderas un recorrido guiado por la cola de prioridad de donde se extraen primero los nodos que representan subárboles más prometedores del espacio de soluciones Un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones. 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 solo 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. La complejidad en el mejor de los casos de un algoritmo de ramificación y poda... ... es siempre exponencial con el número de decisiones a tomar. ... suele ser polinómica con el número de alternativas por cada decisión. ... puede ser polinómica con el número de decisiones a tomar. Un algoritmo recursivo basado en el esquema divide y venceras... ... nunca tendra un coste temporal asintotico (o complejidad temporal) exponencial Las otras dos opciones son ambas verdaderas. ... alcanza su maxima eficiencia cuando el problema de tamaño se divide en a problemas de tamano n/a. ¿Cual de estos problemas tiene una solucion eficiente utilizando programacion dinamica? El problema del cambio. La mochila discreta sin restricciones adicionales. El problema de la asignacion de tareas. Una de estas afirmaciones es falsa. ¿Cuál es? Seleccione una: El algoritmo de Prim se puede acelerar notablemente si se guarda, para cada vértice no visitado, los datos de la arista de mínimo peso que lo une a un vértice visitado. El algoritmo de Kruskal se puede acelerar notablemente si los vértices se organizan en una estructura union-find. El algoritmo de Prim va construyendo un bosque de árboles que va uniendo hasta que acaba con un árbol de recubrimiento de coste mínimo. Dados dos nodos cualesquiera del árbol de búsqueda de ramificación y poda, en general, ¿sepuede saber con certeza cuál está más cerca de la solución óptima del problema a resolver? Sí, pero solo si ambos nodos son hoja. Sí, el que tiene mejor cota pesimista. Sí, el que tiene mejor cota optimista. Decid cual de estas tres estrategias proveería la cota pesimista mas ajustada al valor optimo de la mochila discreta: 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 máximo permitido. Asumir que ya no se van a coger mas objetos. Cuando se resuelve usando backtracking un problema de n decisiones en el que siempre hay como minimo 2 opciones para cada decision, ¿cual de las siguientes complejidades es la mejor que nos podemos encontrar? O(n^2) O(n!) O(2^n). 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. Con respecto a la tecnica poda con memoria, solo una de las siguientes afirmaciones es cierta. ¿Cual es? En una solucion de vuelta atras para la version general del problema del laberinto, sirve también para descartar ciclos. No se puede aplicar para resolver la version restringida del problema del laberinto No resulta eficaz para resolver la version general del problema del laberinto mediante ramificación y poda. En el esquema de vuelta atras, los mecanismos de poda basados en la mejor solucion hasta el momento... Las otras dos opciones son ambas verdaderas. ... garantizan que no se va a explorar todo el espacio de soluciones posibles. ... pueden eliminar vectores que representan posibles soluciones factibles. El valor que se obtiene con el método voraz para el problema de la mochila discreta es... ... una cota inferior para el valor óptimo que a veces puede ser igual a este. ... una cota superior para el valor óptimo. ... una cota inferior para el valor óptimo, pero nunca coincide con este. ¿Cual de estos problemas tiene una solucion eficiente utilizando programación dinamica? el problema del cambio el problema de la asignacion de tareas la mochila discreta sin restricciones adicionales. Tratandose de un esquema general para resolver problemas de minimizacion ¿ que falta en el hueco?Solution BB ( Problem p)if(????????????) n.optimistic_b() < = pb n.optimistic_b() >= pb n.pesimistic_b() < = pb. 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 esquema resulta ser mas eficiente en cuanto al coste temporal? divide y venceras programacion dinamica en este caso tanto programacion dinamica como divide y venceras, resultan ser equivalentes en cuanto a la complejidad temporal. La complejidad en el mejor de los casos de un algoritmo de ramificacion y poda suele ser polinomica con el numero de alternativas por cada decision puede ser polinomica con el numero de decisiones a tomar es siempre exponencial con el numero de decisiones a tomar. Decid cual de estas tres es la cota pesimista mas ajustada al valor optimo de la mochila discreta el valor de la mochila continua correspondiente el valor de una mochila que contiene todos los objetos aunque se pase del peso maximo permitido el valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor especifico de los objetos. Marca la FALSA La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo de O(log n) La ordenación de un vector usando Mergesort requiere en el caso peor un tiempo de O(n^2) La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo O(n^2). El arbol de expansion de minimo coste de un grafo Ninguna de las otras dos opciones es verdadera ...puede utilizarse como cota pesimista para resolver el problema del viajante de comercio ...puede utilizarse como cota optimista para resolver el problema del viajante de comercio. 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 como cota optimista para un nodo? La suma de los pesos de las aristas que completan la solucion paso a paso visitando el vertice mas cercano al ultimo visitado. 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 k aristas restantes mas cortas, donde k es el numero de ciudades que quedan por visitar. Un tubo de n cm de largo se puede cortar en segmentos de 1 centimetro , 2 centimetros etc. existe una lista de los precios a los que se venden los segmentos de cada longituduna de las maneras de cortar el tubo es que mas ingresos nos producira . se quiere resolver el problema mediante vuelta atras¿cual seria la forma mas adecuada de representar las posibles soluciones? un par de enteros que indiquen los cortes realizados y el valor acumulado una tabla que indique para cada posicion donde se va a cortar cada uno de los posibles valores acumulados un vector de booleanos. Dado el problema del laberinto con tres movimientos, se pretende conocer la longitud del camino de salida mas corto. Para ello se aplica el esquema voraz con un criterio de seleccion que consiste en elegir primero el movimiento Este siempre que la casilla sea accesible. Si no lo es se descarta ese movimiento y se prueba con Sureste y por ultimo, si este tampoco es posible, se escoge el movimiento Sur. ¿Que se puede decir del algoritmo obtenido? que es un algoritmo voraz pero sin garantia de solucionar el problema que en realidad no es un algoritmo voraz pues las decisiones que se toman no deberian reconsiderarse que en realidad no es un algoritmo voraz pues el criterio de seleccion no lo es. Que diferencia (entre otras) hay entre el algoritmo de Prim y el de Kruskal? El subgrafo que paso a paso va generando el algoritmo de prim siempre contiene una única componente conexa. Aun siendo el grafo de partida totalmente conexo, el algoritmo de Kruskal garantiza la solución optima mientras que el de prim solo garantiza un suboptimo. El algoritmo de Prim es voraz y el de Kruskal no. 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) O(1) O(n·log(n)). Con respecto a la técnica poda con memoria, solo una de las siguientes afirmaciones es cierta.¿Cuál es? En una solución de vuelta atrás para la versión general del problema del laberinto,sirve también para descartar ciclos. No resulta eficaz para resolver la versión general del problema del laberinto me-diante ramificación y poda. No se puede aplicar para resolver la versión restringida del problema del laberinto. La mejor solucion que se conoce para el problema de la mochila continua sigue el esquema... ... voraz ... ramificacion y poda ... divide y venceras. Cuando se resuelve, usando Backtracking, un problema de n decisiones, en el que siempre hay como mínimo dos opciones por decisión, cual de estas complejidades en el caso peor es la mejor que nos podemos encontrar O(2^n) O(n^2) O(n!). Que algoritmo es mas rápido, quicksort o mergesort? son los dos igual de rápidos: O(nlog(n)) el mergesort es siempre más rápido como su nombre indica, el quicksort. Estamos resolviendo la version restringida del problema del laberinto. Ya hemos obtenido el almacen de resultados parciales. ¿Con que complejidad temporal podemos obtener un camino de salida de longitud mínima si es que existe? Ω(mín(n, m)) y O(mn) Θ(m +n) Θ(mn). Una de las respuestas siguientes es falsa. ¿Cuál es? El problema del viajante de comercio ...Seleccione una: ... se puede resolver exactamente usando un algoritmo voraz derivado del de Kruskal. ... se puede resolver exactamente usando un algoritmo de búsqueda y enumeración como es el de vuelta atrás o el de ramificación y poda. ... se puede resolver exactamente usando un algoritmo de programación dinámica. ¿En ramificacion y poda, tiene sentido utilizar la cota optimista de los nodos como criterio para ordenar la lista de nodos vivos? Si, aunque no es una garantia de que sea una buena estrategia de busqueda si, en el caso de quese ordene la lista de nodos vivos, siempre debe hacerse segun el criterio de la cota optimista no, la cota optimista solo se utiliza para determinar si una n-tupla es prometedora. Sea f(n) = 2f(n - 1) + 1 f(n) C O(2^n) f(n) C O(n^2) f(n) C O(n). Indica cual de las siguientes expresiones es falsa promedio(n) C O(n^2) promedio(n) C O(n) promedio(n/2) = promedio(n). ¿Cual de estas estrategias para calcular el n-esimo elemento de la serie de Fibonacci
(f(n) = f(n-1)+f(n-2), f(1) = f(2) = 1)
es más eficiente? La estrategia voraz Para este problema, las dos estrategias citadas serian similares en cuanto a eficiencia Programacion dinamica. Estamos resolviendo la versión restringida del problema del laberinto. Ya hemos obtenido el almacén de resultados parciales. ¿Con qué complejidad temporal podemos obtener un camino de salida de longitud mínima si es que existe? Θ(mn) Ω(mín(n, m)) y O(mn) Θ(m+n). 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) = T(n-1) + n T(n) = 2T(n-1) + 1 T(n) = 2T(n-1) + n. ¿Que nos proporciona la media 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 nada de interés el coste temporal asintotico en el caso medio.
