TEST BORRADO, QUIZÁS LE INTERESE: 3
COMENTARIOS |
ESTADÍSTICAS |
RÉCORDS
|
|---|
REALIZAR TEST
|
Título del Test:
3 Descripción: el tercero Autor: autónomo digo anónimo OTROS TESTS DEL AUTOR Fecha de Creación: 11/06/2024 Categoría: Fans Número Preguntas: 52 |
COMPARTE EL TEST
Comentar
No hay ningún comentario sobre este test.
Temario:
|
dado un problema de optimizacion cualquiera¿ la estrategia de backtracking garantiza la solucion optima? si, puesto que ese metodo analiza todas las posibilidades si , siempre que el dominio de las decisiones sea discreto o discretizable y ademas se empleen mecanismos de poda basados en la mejor solucion hasta el momento es condicion necesaria que el dominio de las decisiones sea discreto o discretizable y queel numero de decisiones a tomar este acotado. en los algoritmos de ramificacion y poda.. una cota optimista es necesariamente un valor alcanzable, de no ser asi no esta garantizado que se encuentre la solucion optima una cota optimista es necesariamente un valor insuperable , de no ser asi se podria podar el nodo que conduce a la solucion optima una cota pesimista es el valor que a lo sumo alcanza cualquier nodo factible que no es el optimo. el uso de funciones de cota en ramificacion y poda transforma en polinomicas complejidades que antes eran exponenciales garantiza que el algoritmo va a ser mas eficiente ante cualquier instancia del problema puede reducir el numero de instancias del problema que pertenecen al caso peor. la solucion recursiva ingenua(pero correcta) a un problema de optimizacion llama mas de una vez a la funcion con los mismos parametros . una de las siguientes afirmaciones es falsa se puede mejorar la eficiencia del algoritmo guardando en una tabla el valor devuelto para cada conjunto de parametros de cada llamada cuando esta se produce por primera vez se puedemejorar la eficiencia del algoritmo definiendo de antemano el orden en el que se deben calcular las soluciones a los subproblemas y llenando una tabla en ese orden se puede mejorar la eficiencia del algoritmo convirtiendo el algoritmo recursivo directamente en iterativo sin cambiar su funcionamiento basico. la mejor solucion que se conoce para el problema de la mochila continua sigue el esquema divide y venceras ramificacion y poda voraz. si un problema de optimizacion lo es para una funcion que toma valores continuos la programacion dinamica iterativa siempre es mucho mas eficiente que la programacion dinamica iterativa en cuanto al uso de memoria la programacion dinamica recursiva puede resultar mucho mas eficiente que la programacion dinamica iterativa en cuanto al uso de memoria el uso de memoria de la programacion dinamica iterativa y de la programacion dinamica recursiva es el mismo independientemente de si el dominio es discreto o continuo. al resolver el problema del viajante de comercio mediante backtracking , cual de estas cotas optimistas se espera que pode mejor el arbol de busqueda? se multiplica k por la distancia de la arista mas corta que nos queda por considerar donde k es el numero de saltos que nos quedan por dar se resuelve el resto del problema usando un algoritmo voraz que añade cada vez al camino el vertice mas cercano al ultimo añadido se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las k aristas mas cortas, donde k es el numero de saltos quenos quedan por dar. para cual de estos problemas de optimizacion existe una solucion voraz? el problema de la mochila discreta el problema de la asignacion de coste minimo de n tareas a n trabajadores cuando el coste de asignar la tarea i al trabajador j cij esta tabulado en una matriz el arbol de recubrimiento minimo para un grafo no dirigido con pesos. se desea encontrar el camino mas corto entre dos ciudades. para ello se dispone de una tabla con la distancia entres los pares de ciudades en los que hay carreteras o un valor centinela( por ejemplo, -1 ) si no hay,por lo que para ir de la ciudad inicial a la final esposible que haya que pasar por varias ciudades tambien se conocen las coordenadas geograficasde cada ciudad y por tanto la distancia geometrica en linea recta entre cada par de ciudades.se pretende acelerar la busqueda de un algoritmo de ramificacion uy poda priorizando los nodos vivos(ciudades( que esten a menor distancia geografica de la ciudad objetivo el nuevo algoritmo no garantiza que vaya a ser mas rapido para todas las instancias del problema posibles el nuevo algoritmo siempre sera mas rapido esta estrategia no asegura que se obtenga el camino mas corto. la complejidad temporal en el mejorde los casos es el tiempo que tarda el algoritmo en resolver el problema de tamaño o tallamas pequeña que se le puede presentar las otras dos opciones son ciertas es una funcion del tamaño o talla del problema que tiene que estar definida para todos los posibles valores de esta. la complejidad en el mejor de los casos de un algoritmo de ramificacion y poda es siempre exponencial con el numero de decisiones a tomar puede ser polinomica con el numero de decisiones a tomar suele ser polinomica con el numero de alternativas por cada decisión. un algoritmo recursivo basado en divide y venceras nunca tendra una complejidad exponencial sera mas eficiente cuanto mas equitativa sea la division en subproblemas las dos anteriores son correctas. cuando se usa un algoritmo voraz para abordar la resolucion de un problema de optimizacion por seleccion directa( es decir, un problema para el cual la solucion consiste en encontrar un subconjunto del conjunto de elementos que optimiza una determinadafuncion ) ¿Cual de estas tres cosas es imposible que ocurra? que el algoritmo no encuentre ninguna solucion quese reconsidere la decision ya tomada anteriormente respecto a la seleccion de un elemento a la vista de la decision que se debe tomar en el instante actual que la solucion no sea la optima. cuando la descomposicion recursiva de un problema da lugar a subproblemas de tamaño similar, que esquema promete ser mas apropiado? programacion dinamica divide y venceras , siempre que se garantice que los subproblemas no son del mismo tamaño voraz. sea la siguiente relacion de recurrenciat(n) + 1 si n<= 1 // + 2T(n/2) + g(n) en otro caso.. Si t(n) pertenece O(n^2) en cual de los casos nos podemos encontrar? g(n) = n g(n) = n^2 g(n)= 1. en el esquema de backtracking los mecanismos de poda basados en la mejor solucion hasta el momento garantizan que no se va a explotar nunca todo el espacio de soluciones las otras dos opciones son ciertas pueden eliminar soluciones parciales que son factibles. uno de estos tres problemas no tiene una solucion eficiente que siga el esquema de programación dinamica el problema de la mochila discreta el problema de las torres de hanoi el problema de cortar un tubo de longitud nen segmentos de longitud entera entre 1 y n de manera que se maximice el precio de acuerdo con una tabla que da el precio para cada longitud. el valor que se obtiene con el metodo voraz para el problema de la mochila discreta es una cota inferior para el valor optimo, pero que nunca coincide con teste una cota superior para el valor optimo una cota inferior para el valor optimo que aveces puede ser igual a este. decid cual de estas tres es la cota pesimista mas ajustada al valor optimo de la mochila discreta el valor de lamochila 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 algorimo voraz basado en el valor especifico de los objetos. un problema de tamaño n puede transformarse en tiempo O(n^2) en otro de tamaño n-1 , por otro lado, la solucion al problema cuando la talla es 1 requiere un tiempo constante, ¿cual de estas clases de coste temporal asintotico esla mas ajustada? O(2^n) O(n^3) O(n^2). Sea la siguiente relacion de recurrencia :::: T( n)= 1 si n<=1 ////// [2T (n/2)+ g(n) en otro caso.Si T(n) e O(n), ¿en cual de estos tres casos nos podemos encontrar? g(n)=n^2 las otras dos opcionesson ambas ciertas g(n) = log n. ¿Que se deduce de f(n) y g(n) se se cumple lim n... infinito [f(n)/g(n)] = K, con K distinto 0? g(n) pertenece 0[0(f(n)] pero f(n) "no incremento" 0[g(n)] f(n) pertenece 0[g(n)] y g(n) "incremento 0`f(n)] f(n) pertenece 0[g(n)] pero g(n) "no incremento" 0[f(n)]. ¿Cual seria la complejidad temporal de la siguiente funcion tras aplicar programacion dinamica? promedio(n x m) promedio(n) promedio (n^2). Dado un problema de maximizacion resuelto mediante un esquema de ramificacion y poda, ¿que ocurre si la cota optimista resulta ser un valor excesivamente elevado? que se podria explorar mas nodos de los necesarios que se podria explorar menos nodos de los necesarios que se podria podar el nodo que conduce a la solucion optima. 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? en este caso tanto programacion dinamica como divide y venceras, resultan ser equivalentes en cuanto a la complejidad temporal programacion dinamica divide y venceras. 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 . El coste temporal asintotico de insertar un elemento en un vector ordenado de forma que continue ordenado es... ... 0(log n) ... mejor(n^2) ... 0(n). 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 seria la recurrencia apropiada para el caso general? ninguna de las otras dos recurrenciasse corresponde con un esquema de divide y venceras nc(n,m) = nc(n -1,m) + nc(n,m -1) + nc(n -1,m -1) nc(n,m) = nc(n -1,m) * nc(n,m -1) * nc(n -1,m -1). Dado un problema de minimizacion resuelto mediante un esquema de ramificacion y poda, ¿que propiedad cumple una cota optimista? las otras dos opciones son ambas faltas asegura un ahorro en la comprobacion de todas las soluciones factibles siempre es mayor o igual que la mejor solucion posible alcanzada. En el esquema de ramificacion y poda, ¿que estructura es la mas adecuada si queremos realizar una exploracion por niveles? cola cola de prioridad pila. Dado el problema del laberinto con tres movimientos, ¿se puede aplicar un esquema de programacion dinamica para obtener un camino de salida? 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. si, en caso de existir con este esquema siempre se puede encontrar un camino de salida. ¿Que ocurre si la cota pesimista de un nodo se corresponde con una solucion que no es factible? que el algoritmo seria incorrecto pues podria descartarse un nodo que conduce a la solucion optima. que el algoritmo seria mas lento pues se explorarian mas nodos de los necesarios. nada especial, las cotas pesimistas no tienen por que corresponderse con soluciones factibles. Se desea ordenar una lista enlazada de n elementos haciendo uso del algoritmo Mergesort. En este caso, al tratarse de una lista, la complejidad temporal asintotica de realizar la division en subproblemasresulta ser lineal con el tamaño de esa lista. ¿Cual seria entonces el coste temporal de realizar dicha ordenacion? ninguna de las otras dos opciones es cierta promedio(n log n) promedio(n^2). Una de las practicas de laboratorio consistio enel calculo empirico de la complejidad temporal promedio del algoritmo de ordenacion de vectores Quicksort tomando como centinela el elemento del vector que ocupa la posicion central. ¿Cual es elorden de complejidad que se obtuvo? n log n n log^2 n n^2. Un tubo de n centimetros de largo se puede cortar en segmentos de 1 ctm., 2 ctm, 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. 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. Si f pertenece mejor(g1) y f pertenece mejor(g2) entonces f pertenece mejor(g1 * g2) f pertenece mejor(g1 + g2) f no pertenece mejor[min (g1, g2)] . El esquema de vuelta atras... 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 las otras dos opciones son ambas verdaderas. Que estrategia de busqueda es a priori mas apropiada en un esquema de vuelta atras? explorar primero los nodos con mejor cota optimista explorar primero los nodos que estan mas completados en elesquema de vuelta atras no se pueden definir estrategias de busqueda. Que complejidad se obtiene a partir de la relacion de recurrencia T(n) = 8T(n/2) + n^3 con T(1) = 0(1) ? 0(n log n) 0(n^3 log n) 0(n^3 ). Dada la siguiente funcion: 0(n log n) 0(n "al cuadrado") 0(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 asintotico en el caso medio nada de interes el coste temporal promedio. Si el coste temporal de un algoritmo es T(n), ¿cual de las siguientes situaciones es imposible? T(n) pertenece mejor(n) y T(n) pertenece promedio(n^2) T(n) pertenece promedio(n) y T(n) pertenece mejor(n^2) T(n) pertenece 0(n) y T(n) pertenece promedio(n). ¿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. 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 n se divide en "a" problemas de tamaño n/a. Dado el problema dellaberinto con tres movimientos, se desea saber el numero de caminos distintos desde la casilla incial (1,1) hasta la casilla (n,m) y para ello se aplica el esquema programacion dinamica para obtener un algoritmo lo mas eficiente posible en cuanto a complejidad temporal y espacial, ¿cuales serian ambas complejidades? temporal promedio[max(n,m)] y espacial promedio[max (n,m)] temporal promedio(n x m) y espacial promedio(n x m) temporal promedio(n x m) y espacial promedio[min (n,m)]. 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 en realidad no es un algoritmo voraz pues las decisiones que se toman no deberian reconsiderarse que es un algoritmo voraz pero sin garantia de solucionar el problema que en realidad no es un algoritmo voraz pues el criterio de seleccion no lo es. En ausencia de cotas optimistas y pesimistas, la estrategiade vuelta atras... ... no recorre todo el arbol si hay manera de descartar subarboles que representan conjuntos de soluciones no factibles ...debe recorrer siempre todo el arbol ...no se puede usar para resolver problemas de optimización. De las siguientes afirmaciones marca la que es verdadera 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 conjuto de cotas pesimistas y optimistas las cotas pesimistas no son compatibles con un esquem ade vuelta atras. El esquema voraz... puede que no encuentre una solucion pero si lo hace se garantiza que es optima las otras dos opciones son ambas falsas garantiza encontrar una solucion a cualquier problema, aunque puede que no sea optima. Cuando la descomposicion de un problema da lugar a subproblemas de tamaño similar al original, muchos de los cuales se repiten, ¿que esquema es a priori mas apropiado? programacion dinamica ramifiacion y poda divide y venceras. 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 obtendria con la ingenua se reduciria a lineal con la de memoizacion la mejora no esta garantizada puesto que la version recursiva con memoizacion podria ser peor que la obtenida a partir del esquema divide y venceras de una complejidad exponencial que se obtendria con la ingenua se reduciria a polinomica con la de memoizacion. 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. |
Denunciar Test