option
Cuestiones
ayuda
daypo
CREAR TEST
buscar.php

TEST BORRADO, QUIZÁS LE INTERESE: 4

COMENTARIOS ESTADÍSTICAS RÉCORDS
REALIZAR TEST
Título del Test:
4

Descripción:
el cuarto

Autor:
autónomo digo anónimo
OTROS TESTS DEL AUTOR

Fecha de Creación: 11/06/2024

Categoría: Fans

Número Preguntas: 44
COMPARTE EL TEST
COMENTARNuevo Comentario
No hay ningún comentario sobre este test.
Temario:
Decid cual de estas tres es la cota optimista mas ajustada al valor optimo de la mochila discreta: el valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor especifico de los objetos el valor de una mochila que contiene todos los objetos aunque se pase del peso maximo el valor de la mochila continua correspondiente.
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 0(2^log n) C O(n^2) promedio(n) C promedio(n^2) n + n log n pertenece mejor(n).
Dado el problema del laberinto con tres movimientos, ¿cual de las estrategias siguientes proveeria de una cota optimista para ramificacion y poda? suponer que en adelante todas las casillas del laberinto son accesibles suponer que ya no se van a realizar mas movimientos las otras dos estrategias son ambas valida.
En el problema del viajante de comercio (travelling salesman problem) queremos listar todas las soluciones factibles el orden en el que se exploran las soluciones parciales noes relevante; por ello, la tecnica ramificacion y poda no aporta nada fcon 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 lomas adecuado seria usar una tecnica de ramificacion y poda ya que es muy importante el orden en el que se exploran las soluciones parciales.
Se desea obtener todas las permutaciones de una lista compuesta por n elementos. ¿Que esquema es el mas adecuado? ramificacion y poda, puesto que con buenas funciones de cota es mas eficiente que vuelta atras vuelta atras, es el esquema mas eficiente para este problema divide y venceras, puesto que la division en sublistas se podria hacer en tiempo constante.
¿Cual es la complejidad temporal, en el peor de los casos, del mejor algoritmo que se puede escribir para resolver el problema de la mochila discreta? Exponencial con el numero de objetos a tratar. Polinomica con el numero de objetos a tratar, siempre que se utilice programacion dinamica. Ninguna de las otras dos son ciertas.
Un algoritmo que calcula una funcion recursivamente tiene coste prohibitivo y se decide mejorarlo transformandolo en un algoritmo de programacion dinamica iterativa, pero se le añade memoizacion. ¿podria ser que el algoritmo iterativop evalue la funcion mas veces que el recursivo con memoizacion? No, ambos evaluan la funcion el mismo numero de veces. No, el recursivo evalua la funcion muchas mas veces. Podria er, por ejemplo, como ocurre en el caso de la mochila discreta con pesos enteros.
Asumiendo que n es par, las siguientes recurrencias matematicas, obtienen el valor de la potencia enésima (x^n), cual de las siguientes afirmaciones es cierta La primera recurrencia resultara ser la mas eficiente siempre que se utilice la programacion dinamica recursiva para su implementacion. Ambas recurrencias son equivalentes en cuanto a complejidad temporal La segunda recurrencia resulta ser la mas eficiente siempre que se utilice divide y venceras. .
Con respecto al tamaño del problema ¿Cual es el orden de complejidad temporal asintotica de la siguiente funcion?void traspuesta(mat & A) constante lineal cuadratico.
Si f no pertenece O(g1) y f pertenecea O(g2) entonces NO siempre se cumplira f pertenece omega(min(g1,g2)) f pertenece O(max(g1,g2)) f pertenece omega(g1+g2).
Que tiene que valer k en la relacion de recurrencia T(n)= 1 n<1 ////// n^k + 2T(n/2) n>1 para que T(n)=n log(n)? 0 1 log(n).
Cual de las siguientes relaciones de recurrencia es la del algoritmo mergesort T(n) = n + 2T (n/2) para n>1 T(n) = n + T (n/2) para n>1 T(n) = n + T (n-1) para n>1.
Los algoritmos de ordenacion quicksort y mergesort tienen el mismo coste temporal asintotico en el caso mejor tienen el mismo coste temporal asintotico en el caso peor tienen el mismo coste temporal en los dos casos.
Que tiene que valer b en la relacion de recurrencia T(n) = 1 n<1 /// 1+bT(n-1) n>1para que T(n)=2^n 1 2 0.
Queremos resolver por ramificacion y poda el problema de la mochila discreta.Si resolvemos el mismo problema de la forma voraz pero sin ordenar previamente los objetospor valor/peso, obtendremos Una cota pesimista Una cota optimista Nada que podamos utilizar.
Queremos resolver por vuelta atras el problema de las n reinas. El usar una buena cota optimistapermitiria: No es aplicable ese tipo de podas a este problema. Muy probablemente, hacer que el programa vaya mas lento. Muy probablemente, resolver el problema de forma mas rapida.
Sea V el conjunto de todos los valores faciales que presentan las monedas de un pais, una cantidad M¿Cual de las siguientes afirmaciones es falsa? El algoritmo que calcularia n(M) asi seria un algoritmo voraz y tendria un coste razonable. El algoritmo recursivo que calcularia n(M) asi tendria un coste prohibitivo El algoritmo recursivo que calcularia n(M) se podria convertir en un algoritmo con coste razonable usando memoizacion.
El arbol de expansion de minimo coste de un grafo ...puede utilizarse como cota optimista para resolver el problema del viajante de comercio ...puede utilizarse como cota pesimista para resolver el problema del viajante de comercio Ninguna de las otras dosopciones es verdadera.
Si lim n-->infinito (g(n)/f(n)) resulta ser una constante positiva no nula, cual de las siguientesexpresiones no puede darse f(n) perteneciente O(g(n)) g(n) no pertenece a O(f(n)) f(n) perteneciente a Omega(g(n)) y g(n).
Tenemos un vector ordenado de tamaño n o y un vector desordenado de tamaño n dqueremos obtener un vector ordenado con todos los elementos ¿Que sera mas rapido? Ordenar el desordenado y luego mezclar las listas. Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado. Depende de si n o > n d o no.
Tenemos una lista ordenada de tamaño n o y una lista desordenada de tamaño n d, queremos obtener una lista ordenada con todos los elementos, ¿Cual seria la complejidad de insertaruno a uno todos los elementos de la lista desordenada en la ordenada? O(n d log n o) O(n o x n d + n 2/d) O(n d x n o).
Tenemos una lista recursiva con la siguiente cabecera:double f( const double &)Con solo esta informacion, cual podria serla definicion adecuada para el almacen? Ninguna de las dos otras opciones son verdaderas vector <double> A int A[].
Queremos resolver por ramificacion y poda el problema de la mochila discreta.Si resolvemos el mismo problema de la forma voraz PERMITIENDO COGER OBJETOS FRACCIONADOS pero sin ordenar previamente los objetospor valor/peso, obtendremos Nada que podamos utilizar Una cota pesimista Una cota optimista.
Cual es el coste espacial asintotico del siguiente algoritmo: int f( int n) int a = 1 , r= 0; for( int i =0 , i<n , i++) r= a + r; a= 2*r; O(1) O(log(n)) O(n).
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. El algoritmo de Prim es voraz y el de Kruskal no. 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.
La siguiente relacion de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una funcion polinomica Cual es la definicion correcta de Omega(f) O(g) = f: N-> g(n)<cf(n) O(g) = f: N-> f(n)<cg(n) O(g) = f: N-> g(n)<cf(n).
¿Que aporta la tecnica de ramificacion y poda frente a vuelta atras? Eficiencia, los algoritmos de ramificacion y poda son mas eficaces que los de vuelta atras. La posibilidad de analizar distintas estrategias para seleccionar el siguiente nodo a expandir. YO DIRIA QUE ES ESTA La posibilidad de combinar el uso de cotas pesimistas y optimistas para cualquier nodo ya sea completado o sin completar.En vuelta atras esto no se puede hacer. ESTA TAMBIEN PUEDE SER. .
Sea n el numero de elementos que contienen los vectoresw y v ,¿cual es la complejidad temporal asintotica en funcion de n asumiendo que la llamadainicial i toma valor n? float f (vector <float> &w, vector <unsigned> &v) omega(n) y O(n²) promedio(2^n) omega(n) y O(2^n).
En el siguiente problema de cortar un tubo de longitud n en segmentos de longitud entera entre 1 y n ¿Que deberia ir en lugar de XXXXXX? void fill(price m[]) +cutrod(XXXXXX) n,m[n]-1,p n-i, m,p n-m[n],m,p.
Tenemos un vector ordenado y queremos comprobar si contiene un elemento dado ¿ Cual sera la complejidad temporal mas ajustada para hacerlo ? El tamaño del vector Constante con el tamaño del vector El logaritmo del tamaño del vector.
Dadas las siguientes funciones: //Precondicion: 0<= i < v.size(); i < j <= v.size() Se quiere reducir la complejidad temproal usano programacion dinamica iterativa, cual seria la complejidad espacial cubica cuadratica exponencial.
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.
Tratandose de un esquema general para resolver problemas de maximizacion ¿ que falta en el hueco? Solution BB ( Problem p) if(????????????) n.optimistic_b() <= pb n.optimistic_b() >= pb n.pesimistic_b() <= pb.
La programacion dinamica... Las otras dos opciones son ciertas normalmente se usa para resolver problemas de optimizacion con dominios discretizables puesto que las tablas se han de indexar con este tipo de valores. en algunos casos se puede utilizar para resolver problemas de optimizacion con dominios continuos pero probablemente pierda su eficacia ya que puede disminuir drasticamente el numero de subproblemas repetidos.
¿Cual es la mejor complejidad espacial que se puede conseguir O(y) O(y2) O(1).
Se pretende implementar mediante programacion dinamica iterativa la funcion recursiva: float f(unsigned x, int y){ if( y < 0 ) return 0; float A = 0.0; if ( v1[y] <= x ) A = v2[y] + f( x-v1[y], y-1 ); float B = f( x, y-1 ); return min(A,2+B); Un informatico quiere subir a una montana y para ello decide que tras cada paso, el siguiente debe tomarlo en la direccion de maxima pendiente hacia arriba. Ademas, entendera que ha alcanzado la cima cuando llegue a un punto en el que no haya ninguna direccion que sea cuesta arriba. ¿que tipo de algoritmo esta usando nuestro informatico? un algoritmo de programacion dinamica. un algoritmo voraz un algoritmo divide y venceras.
En la solucion al problema de la mochila continua ¿por que es conveniente la ordenacion previa de los objetos? Para reducir la complejidad temporal en la toma de cada decision: de O(n) a O(1), donde n es el numero de objetos a considerar. Para reducir la complejidad temporal en la toma de cada decision: de O(n2) a O(nlogn), donde n es el numero de objetos a considerar. Porque si no se hace no es posible garantizar que la toma de decisiones siga un criterio voraz.
¿ Como se veria afectada la solucion voraz al problema de la asignacion de tareas en el casode que se incorporaran restricciones que contemplen que ciertas tareas no pueden ser adjudicadas a ciertos trabajadores ? Ya no se garantizaria la solucion optima pero si una factible. La solucion factible ya no estaria garantizada, es decir, pudiera ser que el algoritmo no llegue a solucion alguna Habria que replantearse el criterio de seleccion para comenzar por aquellos trabajadores con mas restricciones en cuanto a las tareas que no pueden realizar para asegurar, al menos, una solucion factible.
Un tubo de n centimetros 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 longitud. Una de las maneras de cortar el tubo es la que mas ingresos nos producira. Di cual de estas tres afirmaciones es falsaSeleccione una: Hacer una evaluacion exhaustiva de ''fuerza bruta'' de todas las posibles maneras de cortar el tubo consume un tiempo Θ(n!). Es posible evitar hacer la evaluacion exhaustiva ``de fuerza bruta'' guardando, para cada posible longitud j<n el precio mas elevado posible que se puede obtener dividiendo el tubo correspondiente. Hacer una evaluacion exhaustiva ``de fuerza bruta'' de todas las posibles maneras de cortar el tubo consume untiempo Θ(2n).
Se pretende implementar mediante programacion dinamica iterativa la funcion recursiva: unsigned f( unsigned y, unsigned x) // suponemos y >= x if (x==0 || y==x) return 1; return f(y-1, x-1) + f(y-1, x); ¿Cual es la mejor complejidad espacial que se puede conseguir? Seleccione una: O(y2) O(y) O(1).
¿Cual de estas estrategias voraces obtiene siempre un mejor valor para la mochila discreta?Seleccione una: Meter primero los elementos de mayor valor. Meter primero los elementos de mayor valor especifico o valor por unidad de peso. Ninguna de las otras dos opciones es cierta. .
En el metodo voraz Seleccione una: siempre se encuentra solucion pero puede que no sea la optima. es habitual preparar los datos para disminuir el coste temporal de la funcion que determina cual es la siguiente decision a tomar. el dominio de las decisiones solo pueden ser conjuntos discretos o discretizables.
¿Que mecanismo se usa para acelerar el algoritmo de Prim? Seleccione una: El TAD "Union-find" Mantener una lista de los arcos ordenados segun su peso. Mantener para cada vertice su "padre" mas cercano.
En la solucion al problema de la mochila continua ¿por que es conveniente la ordenacion previa de los objetos?Seleccione una: Para reducir la complejidad temporal en la toma de cada decision: de O(n) a O(1), donde n es el numero de objetos a considerar. Para reducir la complejidad temporal en la toma de cada decision: de O(n2) a O(nlogn), donde n es el numero de objetos a considerar. Porque si no se hace no es posible garantizar que la toma de decisiones siga un criterio voraz.
Denunciar Test
▲