TEST BORRADO, QUIZÁS LE INTERESE: 2
COMENTARIOS |
ESTADÍSTICAS |
RÉCORDS
|
|---|
REALIZAR TEST
|
Título del Test:
2 Descripción: el segundo Autor: autónomo digo anónimo OTROS TESTS DEL AUTOR Fecha de Creación: 11/06/2024 Categoría: Fans Número Preguntas: 62 |
COMPARTE EL TEST
Comentar
No hay ningún comentario sobre este test.
Temario:
|
el coste temporal asintotico del programas
s= 0; for(i = 0; i < n; i++) for(j = i; j<n;j++) s+= i*j;
y del programas
s= 0; for(i = 0; i < n; i++) for(j = 0; j<n;j++) s+= i*i*j el del primero, menor que el segundo el del segundo, menor que el primero iguales. 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 division en sublistas se podria hacer en tiempo constante 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. la solucion recursiva ingenua a un determinado problema de optimizacion muestra estas dos caracteristicas: por un lado, se basa en obtener soluciones optimas a problemas parciales mas pequeños y por otro, estos subproblemasse resuelven mas de una vez durante el proceso recursivo. Este problema es candidato a tener una solucion alternativa basada en... un algoritmo del estilo de divide y venceras un algoritmo de programacion dinamica un algoritmo voraz. decid cual de estas tres es la cota optimistamas ajustada al valor optimo de la mochila discreta el valor de la mochila continua correspondiente 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 permitido. a funcion Y de un numero semientero positivo( un numero es semientero si al restarle 0.5 es entero) se define como double gamma(double n) if(n == 0.5)return sqrt(PI); return n*gamma(n-1) se puede calcular usando programacion dinamica iterativa? si no, ya que el indice del almacen seria un numero real y no entero no, ya que no podriamos almacenar los resultados intermedios en el almacen. 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 vector de booleanos 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. cuando la descomposicion de un problema da lugar a subproblemas de tamaño similar al original, muchos delos cuales se repiten, que esquema es a priori mas apropiado? divide y venceras programacion dinamica ramificacion y poda. un problema de tamaño n puede transformarse entiempo O(n^2) en nueve de tamaño n/3 por otro lado la solucion al problema cuando la talla es 1 requiere un tiempo constante, ¿cual de estas clases de coste temporal asintotico es las mas ajustada? O(nlogn) O(n^2 logn) O(n^2). indica cual de las siguientes expresiones es falsa promedio(n/2) = promedio(n) promedio(n) C O(n) promedio(n) C O(n^2). sea la solucion a la relacion de recurrencia f(n) = 2f(n/2) + n /// f(1) = 1 f(n) pertenece promedio(n^2) f(n) pertenece promedio(n) f(n) pertenece promedio(n logn). para que la complejidad de un algoritmo presente caso mejor y peor distintos es condicion necesaria y suficiente que existan instancias distintasdel problemacon el mismo tamaño es condicion necesaria que existan instancias distintasdel problema con el mismo tamaño es condicion suficiente que existan instancias distintasdel problema con el mismo tamaño. un problema de tamaño n puede transformarse en O(n) en siete de tamaño n/7 , por otro lado la solucion al problema cuando la talla es 1 requiere tiempo constante ¿ que cota es mas ajustada? O(n^2) O(n) O(n logn). La complejidad temporal en el mejor de los casos de un algoritmo recursivo coincide con el valor del caso base de la ecuacion de recurrencia que expresa la complejidad del algoritmo las demas opciones son falsas siempre coincidira con la complejidad temporal de las instancias que estan en el caso base del algoritmo recursiva. 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(2^n) O(n!) O(n^2). al resolver el problema del viajante de comercio mediantebacktracking asumiendo un grafo den vertices totalmente conexo ¿cual de estas es una buena cotapesimista al iniciar la busqueda? se multiplica n por la distancia de la arista mas corta que nos queda por considerar se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las n aristas mas cortas se resuelve el problema usando un algoritmo voraz que añade cada vez al camino el vertice mas cercano al ultimo añadido. 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 para este problema que backtracking divide y venceras puesto que la division en sublistas se podria hacer en tiempo constante backtracking , para este problema no hay un esquema mas eficiente. 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 suele ser polinomica con el numero de alternativas por cada decision puede ser polinomica con el numero de decisiones a tomar. la complejidad en el peor de los casos de un algoritmo de ramificacion y poda puede ser exponencial con el numero de alternativas por cada decision puede ser polinomica con el numero de decisiones a tomar es exponencial con el numero de decisiones a tomar. La estrategia de ramificacion y poda genera las soluciones posibles al problema mediante un recorrido guiado por estimaciones de las mejores ramas del arbol que representa el espacio de soluciones un recorrido en profundidad del arbol que representa el espacio de soluciones un recorrido en anchura del arbol que representa el espacio de soluciones. para que sirven las cotas pesimistas en ramificacion y poda para tener la certeza de que la cota optimista esta bien calculada para descartar nodos basandose en la preferencia por algun otro nodo ya completado para descartar nodos basandose en el beneficio esperado. en los algoritmos de ramificacion y poda ¿ el valor de una cota pesimista es mayor que el valor de una cota optimista?(entendiendo que ambas cotas se aplican sobre el mismo nodo en general si , si se trata de un problema de maximizacion , aunque en ocasiones ambos valores pueden coincidir en general si, si se trata de un problema de minimizacion , aunque en ocasiones ambos valores pueden coincidir no , nunca es asi. en los algoritmos de ramificacion y poda , el valor de una cota pesimistaes menor que el valor de una cota optimista (entendiendo que ambas cotas se aplican sobre el mismo nodo) en general si , si se trata de un problema de minimizacion , aunque en ocasiones ambos valores pueden coincidir en general si , si se trata de un problema de maximizacion , aunque en ocasiones ambos valores pueden coincidir si, siempre es asi. en los algoritmos de ramificacion y poda el uso de cotas pesimistas solo resulta eficaz cuando se dispone de una posible solucionde partida 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 optimista es necesariamente un valor alcanzable , de no ser asi no esta garantizado que se encuentre la solucion optima. Di cual de estos tres algoritmos no es un algoritmo de divide y venceras Quicksort Mergesort Algoritmo de Prim. Sea A una matriz cuadrada n x n. Se trata de buscar una permutacion de las columnas tal que la suma de los elementos de la diagonal de la matriz resultante sea minima. Indicad cual de las siguientes afirmaciones es falsa la complejidad temporal de la mejor solucion posible al problema es 0(n!) si se construye una solucion al problema basada en el esquema de ramificacion y poda, una buena eleccion de cotas optimistas y pesimistas podria evitar la exploracion de todas las permutaciones posibles la complejidad temporal de la mejor solucion posible al problema es Omega(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) pertenece 0(n cuadrado), ¿en cual de estos tres casos nos podemos encontrar? g(n) = n g(n) = n cuadrado g(n) = 1 . ¿Cual de estos tres problemas de optimizacion no tiene, o no se le conoce, una solucion voraz (greedy) que es optima? el problema de la mochila discreta el problema de la mochila continuao con fraccionamiento el arbol de cobertura de coste minimo de un grafo conexo. Un algoritmo recursivo basado en el esquema divide y venceras... ... nunca tendra una complejidad exponencial ... sera mas eficiente cuanto mas equitativa sea la division en subproblemas las dos anteriores son ciertas. Un problema de tamaño n puede transformarse en tiempo 0(n cuadrado) 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 es la mas ajustada? 0(2^n) 0(n^3) 0(n^2). La complejidad temporal en el mejor de los casos... ... es el tiempo que tarda el algoritmo en resolver el problema de tamaño o talla mas 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. Al resolver el problema del viajante de comercio mediante vuelta atras, ¿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 que nos quedan por dar. 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 dela programacion dinamica recursiva es el mismo independientemente de si el dominio es discreto o continuo. La version de Quicksort que utiliza como pivote el elemento del vector que ocupa la primera posicion... ... no presenta caso mejor y peorpara instancias del mismo tamaño ... se comporta mejor cuando el vector ya esta ordenado ... se comporta peor cuando el vector ya esta ordenado. Si f(n) pertenece 0(n^3), ¿puede pasar que f(n) pertenece 0(n^2)? no, porque n al cubo “no incrementa” 0(n al cuadrado) solo para valores bajos de n es perfectamente posible, ya que 0(n cuadrado) C 0(n^2). 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 este ... una cota superior para el valor optimo ... una cota inferior para el valor optimo que a veces puede ser igual a este. 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 este ... una cota superior para el valor optimo ... una cota inferior para el valor optimo que a veces puede ser igual a este. Uno de estos tres problemas no tiene una solucion eficiente que siga el esquema de programacion dinamica el problema de la mochila discreta el problema de las torres de Hanoi el problema de cortar un tubo de longitud n en 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. La mejor solucion que se conoce para el problema de la mochila continua sigue el esquema... ... divide y venceras ... ramificacion y poda ... voraz . En los algoritmos de ramificacion y poda... una cota optimista es necesariamente un valor alcanzable, de no se 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 . 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 nunca todo el espacio de soluciones posibles las otras dos opciones son ciertas ... pueden eliminar soluciones parciales que son factibles. La solucion recursiva ingenua (pero correcta) a un problema de optimizacion llama mas de una vez a la funcion conlos mismos parametros. Una de las siguientes tres 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 puede mejorar 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. Cuando se resuelve el problema de la mochila discreta usando la estrategia de vuelta atras, ¿puede ocurrir que se tarde menos en encontrar la solucion optima si se prueba primero a meter cada objeto antes de no meterlo? si, tanto si se usan cotas optimistas para podar el arbol de busqueda como si no no, ya que en cualquier caso se deben explorar todas las soluciones factibles si, pero solosi se usan cotas optimistas para podar el arbol de busqued. Cual de los siguientes algoritmos proveeria una cota pesimista para el problema de encontrar el camino mas corto entre dos ciudades (se supone que el grafo es conexo) calcular la distancia geometrica (en linea recta) entre la ciudad origen y destino para todas las ciudades que son alcanzables en un paso desde la ciudad inicial, sumar la distancia a dicha ciudad y la distancia geometrica hasta la ciudad destino calcular la distancia recorrida moviendose al azar por el grafo hasta llegar (por azar) a la ciudad destino. 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 enel valor especifico de los objetos. 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 decision . Una de estas tres situaciones no es posible f(n) pertenece 0(n) y f(n) pertenece omega(1) f(n) pertenece mejorcaso(n cuadrado) y f(n) pertenece 0(n) f(n) pertenece 0(n) y f(n) pertenece 0(n cuadrado). En el esquema de vuelta atras el orden en el que se van asignando los distintos valores a las componentes del vector que contendra la solucion... ...es irrelevante si no se utilizan mecanismos de poda basados en la mejor solucion hasta el momento ...puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas las otras dos opciones son ciertas. En los algoritmos de ramificacion y poda, ¿el valor de una cota pesimista es mayor que el valor de una cota optimista? (se entiende que ambas cotas se aplican sobre el mismo nodo) no, nunca es asi en general si, si se trata de un problema de minimizacion, aunque en ocasiones ambos valores pueden coincidir en general, si, si se trata de un problema de maximizacion , aunqueen ocasiones ambos valores pueden coincidir. El uso de funciones de cota en ramificacion y poda... ... transforma en polinomicas complejidades que antes eran exponenciales ... garantiza queel algoritmo va a ser mas eficiente ante cualquierinstancia del problema ... puede reducir el numero de instancias del problema que pertenecen al caso peor. Se quieren ordenar d numeros distintos comprendidos entre 1 y n. Para ello se usa un array de n booleanos que se inicializan primero a false. Acontinuacion se recorren los d numeros cambiando los valores del elemento del vector de booleanos correspondiente a su numero a true. Por ultimo se recorre el vector de booleanos escribiendo los indices de los elementos del vector de booleanos que son true. ¿Es este algoritmo mas rapido (asintoticamente) que el mergesort? si, ya que el mergesort es 0(n log n) y este es 0(n) solo si d log d > k n (donde k es una constante que depende de la implementacion) no, ya que este algoritmo ha de recorrer varias veces el vector de booleanos. Si para resolver unmismo problema usamos un algoritmo de vuelta atras y lo modificamos minimamente para convertirlo en un algoritmo de ramificacion y poda, ¿que cambiamos realmente? cambiamos la funcion que damos ala cota pesimista el algoritmo puede aprovechar mejor las cotas optimistas la comprobacion de las soluciones factibles: en ramificacion y poda no es necesario puesto que solo genera nodos factibles. En una cuadricula se quiere dibujar el contorno deun cuadrado de n casillas de lado, ¿cual sera la complejidad temporal del mejor algoritmo que pueda existir? 0 (n cuadrado) 0 (n) 0 (raiz cuadrada n). 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 el metodo voraz. Se desea encontrar el camino mas corto entre dos ciudades. Para ello se dispone de una tabla con la distancia entre 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 es posible que haya que pasar por varias ciudades. Tambien se conocen las coordenadas geograficas de 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 y poda priorizando losnodos 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 mejora que en general aporta la programacion dinamica frente a la solucion ingenua se consigue gracias al hecho de que... ... en la solucion ingenua se resuelve pocas veces un numero relativamente grande de subproblemas distintos ... el numero de veces que se resuelven los subproblemas no tiene nada que ver con la eficiencia de los problemas resueltos meidante programacion dinamica ... en la solucion ingenua se resuelve muchas veces un numero relativamente pequeño de subproblemas distintos. ¿Cual de estos problemas tiene una solucion eficiente utilizando programacion dinamica? el problema de la asignacion de tareas el problema del cambio la mochila discreta sin restricciones adicionales . 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. Cuando se usa un algoritmo voraz para abordar la resolucion de un problema de optimizacion por seleccion discreta (es decir, un problema para el cual la solucion consiste en encontrar un subconjuto del conjuto de elementos que optimiza una determinada funcion), ¿cual de estas tres cosas es imposible que ocurra? que el algoritmo no encuentre ninguna solucion que se reconsidere la decision ya tomada anteriormente respecto a la seleccion de unelemento a la vista de la decision que se debe tomar en el instante actua que la solucion no sea la optima. Dado un problema de optimizacion, el metodo voraz.... ...siempre obtiene la solucion optima ... garantiza la solucion optima solo para determinados problemas ... siempre obtiene una solucion factible. Dado un problema de optimizacion cualquiera, ¿la estrategia de vuelta atras garantiza la solucion optima? si, puesto que este metodo analiza todas las posibilidades si, siempre que eldominio 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 que el numero de decisiones a tomar este acotado. ¿Garantiza el uso de una estrategia “divide y venceras” la existencia de una solucion de complejidadtemporal polinomica a cualquierproblema? si, en cualquier caso no si, pero siempre que la complejidad temporal conjunta de las operaciones de descomposicion del problema y la combinacion de las soluciones sea polinomica. En un problema de optimizacion, si el dominio de las decisiones es un conjunto infinito una estrategia voraz puede ser la unica alternativa 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. |
Denunciar Test