El problema del alfarero (solución discreta con tiempos continuos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈N y el tiempo necesario para su fabricación ti∈R, i∈[0..n−1]. El tiempo disponible para la fabricación de objetos está limitado por T∈R
Se pretende resolver mediante ramificación y poda y para ello se hace uso de una cota que consiste en coger, de entre las clases aún no consideradas, un número al azar de objetos a fabricar siempre que se cumpla las restricciones del problema ¿Que podemos decir de esta cota?
Que es una cota optimista Que no es cota, ni optimista ni pesimista Que es una cota pesimista.
El funcionamiento del algoritmo de ordenación Heapsort es similar al algoritmo de ordenación por selección, ya que localiza el valor más grande y lo sitúa en la posición final del vector; a continuación, localiza el siguiente valor más grande y lo sitúa en la posición anterior a la última, etc.
¿Cuál de las afirmaciones siguientes es cierta?
Seleccione una: Por ello, los dos algoritmos tienen la misma complejidad en el caso peor, O(n2), aunque la complejidad en el caso mejor de Heapsort es O(nlogn). El algoritmo Heapsort tiene una complejidad O(n) en el caso peor, mejor que la complejidad O(n2) del algoritmo de selección, porque Heapsort utiliza una algoritmo mucho más eficiente para localizar los valores del vector que valen más. El algoritmo Heapsort tiene una complejidad O(nlogn) en el caso peor, mejor que la complejidad O(n2) del algoritmo de selección, porque Heapsort utiliza una algoritmo mucho más eficiente para localizar los valores del vector que valen más.
El problema del alfarero (solución discreta con tiempos continuos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈N y el tiempo necesario para su fabricación ti∈R, i∈[0..n−1]. ¿Cuántos objetos de cada clase hay que fabricar para maximizar la ganancia teniendo en cuenta que el tiempo total está limitado por T∈R?
¿Cuál de los siguientes esquemas algorítmicos resultaría más eficiente para resolverlo?
Seleccione una: Vuelta atrás. Un algoritmo voraz. Programación dinámica.
Una empresa tiene M referencias en su stock. Cada referencia j∈[1,M] tiene un peso pj y un valor vj y dispone de nj unidades en su stock. Dispone de un solo camión en el que puede cargar como máximo un peso P. Indicad cuál de las tres funciones siguientes representa una posible solución voraz aproximada al problema de cargar el camión de manera que se transporte un valor máximo. int f(
const vector<int> &p,
const vector<int> &v,
const vector<int> &n,
int P,
int k
) {
if( k == 0 || P == 0 )
return 0;
int gain = 0
for( int num_objs = 0; num_objs <= n[k-1]; num_objs++ )
gain = max( gain, f(p, v, n, P - num_objs * p[k-1], k-1));
return gain;
} int f(
const vector<int> &p,
const vector<int> &v,
const vector<int> &n,
int P,
int k
) {
if( k == 0 || P == 0 )
return 0;
int num_objs = min( P/p[k-1], n[k-1]);
return num_objs * v[k-1] + f( p, v, n, P - num_objs * p[k-1], k-1);
} int f(
const vector<int> &p,
const vector<int> &v,
const vector<int> &n,
int P,
int k
) {
if( k == 0 || P == 0 )
return 0;
int gain = 0
for( int num_objs = 0; num_objs <= 1; num_objs++ )
gain = max( gain, f(p, v, n, P - num_objs * p[k-1], k-1));
return gain;
}.
¿Qué hace la siguiente función?
void f( vector<int> &A ) {
priority_queue<int> pq;
for( auto a: A )
pq.push(a);
A.clear();
while( !pq.empty() ) {
A.push_back(pq.top());
pq.pop();
}
} Invierte el vector A (el último elemento quedará el primero) Ordena el vector A Nada, deja el vector como estaba.
Indica cuál es la complejidad, en función de n, del fragmento siguiente:
for( int i = 0; i < n; i++ ) {
A[i] = 0;
for( int j = 0; j < 20; j++ )
A[i] += B[j];
} Θ(n2) Θ(n) Θ(nlogn) .
Una de las afirmaciones siguientes es cierta y las otras dos falsas. Indicad cuál es la falsa. La complejidad temporal de Quicksort es O(n2) y Ω(nlogn) O(nn)∈O(n!) O(3n)∈O(2n).
Las soluciones factibles a un problema de optimización deben cumplir dos restricciones y queremos resolver el problema mediante vuelta atrás o ramificación y poda. ¿Cuál de las siguientes afirmaciones es cierta?
Seleccione una: La cota optimista usada para podar se puede basar en relajar una cualquiera de las dos restricciones. La cota optimista usada para podar nunca se puede basar en la relajación de ninguna de las restricciones que deben cumplir las soluciones factibles. La cota optimista usada para podar se debe basar en relajar ambas restricciones simultáneamente.
Sea el vector v={1,3,2,7,4,6,8} cuyos elementos están dispuestos formando un montículo de mínimos. Posteriormente añadimos en la última posición del vector un elemento nuevo con valor 5. ¿Qué operación hay que hacer para que el vector siga representando un montículo de mínimos?
Seleccione una: Intercambiar el 8 con el 5. Intercambiar el 7 con el 5. No hay que hacer nada pues el vector v={1,3,2,7,4,6,8,5} también es un montículo de mínimos.
Cuál de la siguientes es la complejidad temporal más ajustada para un algoritmo que calcula la potencia n-ésima de una matriz cuadrada, expresada en función de n? O(logn) O(nlogn) O(n).
En el método voraz ... ... para garantizar la solución óptima, las decisiones solo pueden pertenecer a dominios discretos o discretizables. ... 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. ... para garantizar la solución óptima, las decisiones solo pueden pertenecer a dominios continuos.
El problema del alfarero (solución continua con tiempos continuos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈N y el tiempo necesario para su fabricación ti∈R, i∈[0..n−1]. ¿Cuántos objetos de cada clase hay que fabricar para maximizar la ganancia teniendo en cuenta que el tiempo total está limitado por T∈R?
Si el alfarero pudiera vender objetos sin terminar a un precio proporcional al estado de terminación. ¿Cuál de las siguientes estrategias sería más apropiada para resolverla?
Seleccione una: Programación dinámica. Vuelta atrás. Un algoritmo voraz.
Queremos aplicar la técnica de memoización a la siguiente función recursiva:
double f( double x ) {
if( x <= 2 )
return x;
return f(sqrt(x-1)) + f(sqrt(x-2));
}
¿Cual sería un buen candidato para el almacén? [la función sqrt() calcula la raiz cuadrada] No se puede aplicar la técnica de memoización vector<double> M(xMax+1); (donde xMax es el valor de x en la primera llamada) vector<double, double> M(xMax+1,xMax+1); (donde xMax es el valor de x en la primera llamada).
¿Cuál de las siguientes formulaciones expresa mejor el número de llamadas recursivas que hace Quicksort en el mejor de los casos? a b d.
El problema del alfarero (solución discreta con valores y tiempos discretos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈N y el tiempo necesario para su fabricación ti∈N, i∈[0..n−1]. ¿Cual es el valor máximo de los objetos que puede fabricar teniendo en cuenta que el tiempo total está limitado por T∈N?
Para ello se escribe la siguiente función siguiendo la técnica de divide y vencerás:
int potter( const vector<int> &v, const vector<int> &m, const vector<int> &t, int T, int k ) {
if( k == 0 )
return 0;
int max_earnings = -1;
for( int c = 0; c <= m[k-1]; c++ ) {
int earnings = 0;
if( T >= c * t[k-1] )
// ==> Falta una línea <==
max_earnings = max( max_earnings, earnings);
}
return max_earnings;
} earnings = c * v[k-1] + potter( v, m, t, k-1, T - c * t[k-1] ); earnings = potter( v, m, t, k-1, T - c * t[k-1] ); earnings = potter( v, m, t, k-1, T );.
El problema del alfarero (solución discreta con tiempos discretos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈N y el tiempo necesario para su fabricación ti∈N, i∈[0..n−1]. El tiempo total disponible viene dado por T∈N
Se pretende listar todas las posibilidades de fabricación de objetos. ¿Qué estrategia es la más adecuada? Un algoritmo voraz. Ramificación y poda. Vuelta atrás.
El problema del alfarero (solución discreta con valores y tiempos continuos): Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N; El valor de cada pieza terminada, vi∈R y el tiempo necesario para su fabricación ti∈R, i∈[0..n−1]. ¿Cuántos objetos de cada clase hay que fabricar para maximizar la ganancia teniendo en cuenta que el tiempo total está limitado por T∈R?
Se pretende resolverlo mediante ramificación y poda. Las siguientes funciones tratan de estimar una ganancia aproximada para la parte del nodo aún sin completar. ¿cuál es la mejor para usarla como parte de la cota optimista?
double optimistic( const vector<int> &m, const vector<double> &v, const vector<double> &t, double T, size_t from) {
double gain = 0.0;
for( size_t i = from; i < m.size() && T > 0; i++ ){
double num_objs = min( T/t[i], double(m[i]));
gain += num_objs * v[i];
T -= num_objs * t[i];
}
return gain;
} double optimistic( const vector<int> &m, const vector<double> &v, const vector<double> &t, double T, size_t from) {
double gain =0.0;
for( size_t i = from; i < m.size() && T > 0; i++ ){
for( int j = 1; j <= m[i]; j++) {
if( t[i] < T ) {
gain += v[i];
T -= t[i];
}
}
}
return gain;
} double optimistic( const vector<int> &m, const vector<double> &v, const vector<double> &t, double T, size_t from) {
double gain = 0.0;
for( size_t i = from; i < m.size() && T > 0; i++ ){
for( int j = 1; j <= m[i]; j++) {
gain += v[i];
T -= t[i];
}
}
return gain;
}.
La serie denominada tribonacci se define de la siguiente manera: T(0)=T(1)=1, T(2)=2, i T(n)=T(n−3)+T(n−2)+T(n−1) para n>3. Solo una de las afirmaciones siguientes es cierta. ¿Cuál es?
Seleccione una: Un algoritmo de programación dinámica iterativa para calcular T(n) tendría un coste espacial Θ(n) y este coste no se podría reducir a Θ(1). Un algoritmo de programación dinámica iterativa permite calcular el valor de T(n) en tiempo Θ(n). Un algoritmo recursivo con memoización para calcular T(n) para a un n grande tendría una complejidad prohibitiva.
¿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)
int f(int n){
int k=0;
for (int i = 2; i <= n; i*=2)
for (int j=i; j > 0; j-=2)
k++;
return k;
} b c d.
Una de estas afirmaciones es falsa. ¿Cuál es?
Seleccione una: 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. 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.
Se dispone de n clases de objetos. De cada una de ellas se conoce el número máximo de piezas que se puede fabricar, mi∈N y el tiempo necesario para su fabricación ti∈R, i∈[0..n−1]. Queremos listar todas las posibilidades de fabricación de objetos teniendo en cuenta que el tiempo total está limitado por T∈R
Para ello hemos hecho el siguiente programa donde faltan unas líneas:
void combinations( const vector<int> &m, const vector<double> &t, double T, size_t k, vector<int> &x) {
if( k == m.size() ) {
print_comb(x);
return;
}
// ==> Aquí falta código <==
}
void combinations( const vector<int> &m, const vector<double> &t, double T ) {
vector<int> x(m.size());
combinations(m, t, T, 0, x);
}
¿Cuales son las líneas que faltan? [suponed que print_comb() imprime correctamente la combinación que hay codificada en x] for( int j = 0; j < m[k]; j++ ) {
x[j] = k;
if( T >= j * t[k] )
combinations( m, t, T - j * t[k], k+1, x );
} for( int j = 0; j <= m[k]; j++ ) {
x[k] = j;
if( T >= j * t[k] )
combinations( m, t, T - j * t[k], k+1, x );
} for( int j = 0; j < m[k]; j++ ) {
x[k] = j;
if( T >= j * t[k] )
combinations( m, t, T - j * t[k], k+1, x );
}.
Dada la siguiente función recursiva:
unsigned f( unsigned a, unsigned b ) {
if( a < 3 )
return a + 2*b;
return f(a-1, (7*b)%10);
}
donde suponemos que siempre se va a invocar la función con b < 10.
Queremos acelerarla aplicando la técnica de programación dinámica iterativa. ¿Cómo quedaría? unsigned f( unsigned a, unsigned b ) {
vector< vector<unsigned>> M(a+1,vector<unsigned>(10));
for( unsigned j = 0; j < 10; j++ )
for( unsigned i = 0; i <= a; i++ )
if( i < 3 )
M[i][j] = i + 2*j;
else
M[i][j] = M[i-1][(7*j)%10];
return M[a][b];
} unsigned f( unsigned a, unsigned b ) {
vector< vector<unsigned>> M(a+1,vector<unsigned>(10));
for( unsigned i = 0; i <= a; i++ )
for( unsigned j = 0; j < 10; j++ )
if( i < 3 )
M[i][j] = i + 2*j;
else
M[i][j] = M[i-1][(7*j)%10];
return M[a][b];
}
unsigned f( unsigned a, unsigned b ) {
vector< vector<unsigned>> M(a,vector<unsigned>(10));
for( unsigned j = 0; j < 10; j++ )
for( unsigned i = 0; i <= a; i++ )
if( i < 3 )
M[i][j] = i + 2*j;
else
M[i][j] = M[i-1][(7*j)%10];
return M[a][b];
}.
El problema del cambio: Se dispone de un conjunto finito de números naturales y se pretende obtener el subconjunto de menor tamaño cuyos elementos suman una cierta cantidad C. ¿Qué estrategia es la más apropiada para resolverlo? Ramificación y poda. Un algoritmo voraz. Programación dinámica.
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.
La función test() procesa una lista de n elementos y devuelve un real. La definición de la función es recursiva. Primero descompone la lista en dos sublistas de la misma longitud usando un segmento de código que tiene una complejidad lineal con la longitud de la lista, envía cada una de dos sublistas a test() para que la procese, hace una serie de operaciones, con el resultado y el valor de retorno, de coste temporal constante. ¿Cuál es el coste temporal asintótico de la función test() en función de n?
Seleccione una: Θ(logn) Θ(nlogn) Θ(n) .
¿Qué complejidad tiene la siguiente función?
void f( vector<int> &A ) {
priority_queue<int> pq( begin(A), end(A));
A.clear();
while( !pq.empty() ) {
A.push_back(pq.top());
pq.pop();
}
}
Suponed que la cola de prioridad está implementada como un heap y que n = A.size().
priority_queue<int> pq( begin(A), end(A)) construye un heap a partir de los datos que hay en el vector A. Θ(n2) Θ(n) Θ(nlogn) .
Indica cuál es la complejidad, en función de n (n≥0), del fragmento siguiente:
int f( int n) {
if( n == 0)
return n;
return f(n/2)*f(n/2);
}
Θ(logn) Θ(nlogn) Θ(n).
La función test() procesa una lista de n elementos y devuelve un real. La definición de la función es recursiva. Primero descompone la lista en dos sublistas de la misma longitud usando un segmento de código que tiene una complejidad lineal con la longitud de la lista, y después envía una de las dos sublistas a test() para que la procese, hace una serie de operaciones, con el resultado y el retorno, de coste temporal constante. ¿Cuál es el coste temporal asintótico de la función test() en función de n? Θ(logn) Θ(nlogn) Θ(n).
Si limn→∞(g(n)/f(n)) = 0, ¿Cuál de las siguientes expresiones NO puede darse? g(n)∈Ω(f(n)) f(n)∉Θ(g(n)) g(n)∉Θ(f(n)).
Dada la siguiente función construida mediante la técnica memoización:
int f( vector<unsigned> &x, unsigned i ) {
if( x[i] != SENTINEL )
return x[i];
if( i < 5 )
return i;
return x[i] = f(x, i-1) + f(x, i-3);
}
int f( unsigned i ){
vector<unsigned> x(i, SENTINEL);
return f( x, i);
}
¿Cual es la declaración para SENTINEL mas adecuada? const unsigned SENTINEL = numeric_limits<unsigned>::max(); const unsigned SENTINEL = 0; const unsigned SENTINEL = -1;.
|
