TEST BORRADO, QUIZÁS LE INTERESE: 1
COMENTARIOS |
ESTADÍSTICAS |
RÉCORDS
|
|---|
REALIZAR TEST
|
Título del Test:
1 Descripción: el primero 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:
|
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. A continuacion 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 O(n log n) y este es O(n) No, ya que este algoritmo ha de recorrer varias veces el vector de booleanos. Solo si d log d > k n (donde k es una constante que depende de la implementacion). Uno de estos tres problemas no tiene una solucion trivial y eficiente que siga el esquema voraz. El problema de la mochila continua. El problema del cambio. El problema de la mochila discreta sin limitacion en la carga maxima de la mochila. 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... ... puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas. Las dos anteriores son ciertas. ... es irrelevante si no se utilizan mecanismos de poda basados en la mejor soluci on hasta el momento. O(n log n) O(n2) O(n). Los algoritmos de vuelta atras que hacen uso de cotas optimistas generan las soluciones posibles al problema mediante . . . . . . un recorrido en profundidad del arbol que representa el espacio de soluciones. . . . un recorrido guiado por una cola de prioridad de donde se extraen primero los nodos que representan los subarboles mas prometedores del espacio de soluciones. . . . un recorrido guiado por estimaciones de las mejores ramas del arbol que representa el espacio de soluciones. Cual de estos problemas tiene una solucion eficiente utilizando programacion dinamica? La mochila discreta sin restricciones adicionales. El problema del cambio. El problema de la asignacion de tareas. En un algoritmo de ramificacion y poda, si la lista de nodos vivos no est a ordenada de forma apropiada . . . . . . podria ocurrir que se pode el nodo que conduce a la solucion optima. . . . podria ocurrir que se exploren nodos de forma innecesaria. . . . podria ocurrir que se descarten nodos factibles. 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. Como tambien se conocen las coordenadas geograficas de cada ciudad sequiere usar la distancia geografica (en linea recta) entre cada par de ciudades como cota para limitar la busqueda en un algoritmo de vuelta atras. ¿Que tipo de cota ser ia? Una cota optimista. Una cota pesimista. No se trataria de ninguna poda puesto que es posible que esa heuristica no encuentre una solucion factible. Cuando se usa un algoritmovoraz 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 subconjunto del conjunto de elementos que optimiza una determinada funcion), ¿cual de estas tres cosas es imposible que ocurra? Que el algoritmo no encuentre ninguna solucion. Que la solucion no sea la optima. Que se reconsidere la decision ya tomada anteriormente respecto a la selecci on de un elemento a la vista de la decisi on que se debe tomar en un instante. ¿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) esm as eficiente? Para este problema, las dos estrategias citadas serian similares en cuanto a eficiencia Programacion dinamica La estrategia voraz. La siguiente relacion de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una funci on polin omica: T(n) =1 si n <= 1 //// 2T(n/2 ) + g(n) en otro caso Di cu al de las siguientes afirmaciones es falsa: Si g(n) pertenece O(1) la relacion de recurrenciarepresenta la complejidad temporal del algoritmo de busqueda dicotomica. Si g(n) pertenece O(n^2) la relacion de recurrencia representa la complejidad temporal del algoritmo de busqueda por insercion. Si g(n) pertenece O(n) la relacion de recurrencia representa la complejidad temporal del algoritmo de ordenacion mergesort. Sea la siguiente relacion de recurrencia T(n) = 1 si n<=1///2T(n/2 ) + g(n) en otro casoSi T(n) pertenece O(n), ¿en cusal de estos tres casos nos podemos encontrar? g(n) = 1 g(n) = n2 g(n) = n. Si un problema de optimizacion lo es para una funcionque toma valores continuos ... La programacion dinamica iterativa siempre es mucho mas eficiente que la programacion dinamica recursiva en cuanto al uso de memoria. El uso dememoria de la programacion dinamica iterativa y de la programacion dinamica recursiva es el mismo independientemente de si el dominio es discreto o continuo. La programacion dinamica recursiva puede resultar mucho mas eficiente que la programacion dinamica iterativa en cuanto al uso de memoria. Estudiad la relacion de recurrencia:T(n) = 1 si n<=1//////p*T(n/q) + g(n) en otro caso(donde p y q son enteros mayores que 1). Di cual de los siguientes esquemas algoritmicos produce de manera natural relacionesde recurrencia asi. Programacion dinamica Divide y venceras Ramificacion y poda. 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 solo si se usan cotas optimistas para podar el arbol de busqueda. Garantiza el uso de una estrategia “divide y vencer as” la existencia de una solucion de complejidad temporal polinomica a cualquier problema? Si, en cualquier caso. Si, pero siempre que la complejidad temporal conjunta de las operaciones de descomposicion del problema y la combinacion de las soluciones sea polinomica. No. El algoritmo de ordenacion Quicksort divide el problema en dos subproblemas.¿Cual es la complejidad temporal asintotica de realizar esa division? O(n) O(n log n) mejor(n) y O(n2). ¿Se puede reducir el coste temporal de un algoritmo recursivo almacenando los resultados devueltos por las llamadas recursivas? No, solo se puede reducir el coste convirtiendo el algoritmo recursivo en iterativo Si, si se repiten llamadas a la funcion con los mismos argumentos No, ello no reduce el coste temporal ya que las llamadas recursivas se deben realizar de cualquier manera. ¿Para cual de estos problemas de optimizacion se conoce 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, c_ij esta tabulado en una matriz El arbol de recubrimiento minimo para un grafo no dirigido con pesos. Cual de los siguientes criterios proveeria una cota optimista 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. Utilizar la solucion (suboptima) que se obtiene al resolver el problema mediante un algoritmo voraz. 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 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 restantes aunque se pase del pesomaximo permitido. El valor de la mochila continua correspondiente. 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 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. ¿Que tienen en comun el algoritmo que obtiene el k-esimo elemento mas pequeño de un vector (estudiado en clase) y el algoritmo de ordenacion Quicksort? La division del problema en subproblemas. El numero de llamadas recursivas que se hacen La combinacion de las soluciones a los subproblemas. ¿Cual de los siguientes pares de problemas son equivalentes en cuanto al tipo de solucion (optima, factible, etc.) aportada por el metodo voraz? Seleccione una: El fontanero diligente y el problema del cambio. El fontanero diligente y la mochila continua. El fontanero diligente y la asignacion de tareas. En un algoritmo de ramificacion y poda, el orden escogido para priorizar los nodos en la lista de nodos vivos . . . . . . determina la complejidad temporal en el peor de los casos del algoritmo. . . . puede influir en el numero de nodos que se descartan sin llegar a expandirlos. . . . nunca. Si f(n) pertenece a O(n^2), ¿podemos decir siempre que f(n) pertenece a O(n^3)? Solo para valores bajos de n No, ya que n^2 no pertenece a O(n^3) Si ya que n2 pertenece a O(n^3). Sea g(n) = (sumatorio [desde i=0] hasta K) de a_i*n^i. Di cual de las siguientes afirmacioneses falsa: g(n) pertenece a mejor (n^K) Las otras dos afirmaciones son ambas falsas. g(n) pertenece a promedio(n^K). Sea A una matriz cuadrada n × n. Se trata de buscar una permutacion de las columnas tal que la suma de los elementos de la diagonalde la matriz resultante sea minima. Indicad cual de las siguientes afirmaciones es falsa. La complejidad temporal de la mejor solucion posible al problema esta en mejor(n^2). 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 O(n log n). La version de Quicksort que utiliza como pivote el elemento del vector que ocupa la posicion central . . . ... se comporta peor cuando el vector ya esta ordenado. ... se comporta mejor cuando el vector ya esta ordenado. ... no presenta caso mejor y peorpara instancias del mismo tamaño. Los algoritmos de ordenacion quicksort y mergesort tienen en comun: que ordenan el vector sin usar espacio adicional que ejecutan en tiempo O(n) que aplican la estrategia de Divide y venceras. ¿Cual es la diferencia principal entre una solucion de vuelta atras y una solucion de ramificaion y poda para el problema de la mochila? el coste asintotico en el caso peor el hecho de que la solucion de ramificacion y poda puede empezar con una solucion suboptima voraz y backtracking no el orden de exploracion de las soluciones. Tenemos un conjunto de n enteros positivos y queremos encontrar el subconjunto de tamaño m y de suma minima. lo mas adecuado seria usar una tecnica de ramificacion y poda , aunque en el peor caso el coste temporal asintotico ( o complejidad temporal) seria exponencial para encontrar la solucion habria que probar con todas las combinaciones posibles de m enteros, con lo que la tecnica de ramificacion y poda no aporta nada con respecto a vuelta atras. una tecnica voraz daria una solucion optima. Di cual de estos resultados de coste temporal asintotico es falsa la ordenacion de un vector usando el algoritmo quicksort requiere en el peor caso omega(n^2) = la ordenacion de un vector usando el algoritmo mergesort requiereen el peor caso un tiempo de omega(n^2) la busqueda binaria en un vector ordenado requiere en el peor caso un tiempo en 0(log n). En el problema del viajante de comercio queremos listar todas las soluciones factibles lo mas adecuado seria usar una tecnica de ramificacion y poda ya que es muy importante el orden en el que se exploran las soluciones parciales el orden en el que se exploran las soluciones parciales no es relevante, por ello la poda de ramificacion y poda no aporta nada con respecto ala vuelta atras lo mas importante es conseguir una cota pesimista muy adecuada . las diferencias entre ramificacion y poda y vuelta atras son irrelevantes en este caso. la complejidad temporal (o coste temporal asintotico) en el mejor de los casos es una funcion de la talla , o tamaño del problema, que tiene queestar definida para todos los posibles valores de esta es el tiempo que tarda el algoritmoen resolver la talla mas pequeña que se le puede presentar las dos anteriores son verdaderas. tenemos n substancias diferentes en polvo y queremos generar todas las distintas formas de mezclarlas de forma que el peso no supere un gramocomo la balanza que tenemos solo tiene precision de 0.1 gramos no se consideraran pesos que no sean multipolosdeesa cantidad. queremos hacer un programa que genere todas las combinaciones posibles no hay ningun problema en usar una tecnica de vuelta atras no se puede usar backtracking porque las decisiones no son valores abstractos no se puede usar backtracking porque el numero de combinaciones es infinito. un algoritmo recursivo basado en el esquema divide y venceras ... ...alcanza su maxima eficiencia cuando el problema de tamaño n se divide en a problemas de tamaño n/a ... nunca tendra un coste temporal asintotico (o complejidad temporal) asintotico ... las dos anteriores son verdaderas. dado un problema de optimizacion ¿cuando se puede aplicar el metodo de vuelta atras? es condicion necesaria(aunque no suficiente) que el dominio de las decisiones sea discreto o discretizable es condicion necesaria y suficiente que el dominio de las decisiones sea discreto o discretizable no solo es condicion necesaria que el dominio de las decisiones sea discreto o discretizable, ademas debe cumplirse que se puedan emplear mecanismos de poda basados en la mejor solucion hasta el momento. cual de estas tres expresiones es cierta? O(2^log(n)) C O(N^2) C O(2^n) O(n^2) C O(2^log(n)) C O(2^n) O(n^2) C O(2^log(n)) C O(2^n). sea f(n) la solucion de la relacion de recurrencia f(n) = 2f(n/2) +n; f(1) = 1 indicad cual de estas tres expresiones es cierta f(n) pertenece promedio(n^2) f(n) pertenece promedio(n log n) f(n) pertenece promedio(n). indicad cual de estas tres expresiones es falsa promedio(n/2) = promedio(n) promedio(n) C O(n) promedio(n) C promedio(n^2). indica cual es el coste temporal en funcion de n del problema siguiente s= 0; for(i = 0; i <n ; i++) for (j=i;j<n;j++) s+=n*ij; es O(n^2) pero no omega(n^2) es promedio(n^2) es promedio(n). un programa con dos bucles anidados uno dentro de otro , cada uno de los cuales hace aproximadamente n iteraciones , tarda un tiempo O(n^2) O(2^n) O(n). la eficiencia de los algoritmos voraces se basa en... ... el hecho de que , con antelacion las, posibles decisiones se ordenan de mejor a peor ... el hecho de que las decisiones tomadas no se reconsideran ... en el esquema voraz no se puede hablar de eficiencia puesto que a menudo no resuelve el problema. en el esquema de backtracking , los mecanismos de poda basados en la mejor solucion en curso pueden eliminar vectores que representan posibles soluciones factibles garantizan que no se va a explotar todo el espacio de soluciones posibles las dos anteriores son verdaderas. sea f(n_i la solucion de la relacion de recurrencia f(n) = 2f(n-1) + 1; f(1) = 1. Indicad cual de estas tres expresiones es cierta f(n) pertenece promedio(n^2) f(n) pertenece promedio(2^n) f(n) pertenece promedio(n). pertenece3n^2 + 3 a O(n^3) no solo para c=1 y n_0 = 5 si. las relaciones de recurrencia aparecen solo cuando la solucion es del tipo divide y venceras expresan recursivamente el coste temporal de un algoritmo sirven para reducir el coste temporal deuna solucion cuando es prohibitivo. el coste temporal de un algoritmo se ajusta a la siguiente ecuacion de recurrencia : t(n) 1 para n=0 , ,,,, , n + sumatorio de t(j) n > 1, que coste temporal asintotico o complejidad temporal tendra el algoritmo O(n log n) O(n^2) O(2^n). la version del quicksort que ocupa como pivote el elemnto que ocupa la posicion central 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. de los problemas siguientes , indicad cual no se puede tratar eficientemente como los otros dos el problema del corte de tubos, que se obtenga el maximo beneficio posible el problema del cambio , osea, el de entregar una cantidad de dinero usando las minimas monedas el problema del viajante de comercio. De los problemas siguientes, indicad cual no se puede tratar eficientemente como los otros dos: El problema del cambio, o sea, el de encontrar la manera de entregar una cantidad de dinero usando el minimo de monedas posibles. El problema de cortar un tubo de forma que se obtenga el maximo beneficio posible. El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y de sus valores. que algoritmo es asintoticamente mas rapido el quicksort o el mergesort? como su nombre indica, quicksort son los dos igual de rapidos , ya que el coste temporal asintotico de ambos es O (n log n) el mergesort es siempre el mas rapido o igual (salvo una constante) que el quicksort. el coste temporal del algoritmo de ordenacion por insercion es O(N^2) O(N) O(n log n). los algoritmos de programacion dinamica hacen uso de que la solucion optima se puede construir anadiendo el componente optimo de los restantes , uno a uno de que se puede ahorrar esfuerzo guardando los resultados de esfuerzos anteriores de una estrategia trivial consistente en examinar todas las soluciones posibles. cual de estos tres problemas de optimizacion no tiene unasolucion voraz que sea optima el problema de la mochila continua o con fraccionamiento el problema de la mochila discreta el arbol de cobertura de coste minimo de un grafo conexo. el problema de la funcion compuesta minima consiste en encontrar a partir de un cojunto de funcionesdadas , al secunecia minima de composiciones de estas que permita trasformarun numero n en otro m. se quiere resolver mediante ramificacion y poda. cual seria la forma mas adecuada de representar las posibles soluciones? mediante un vector de booleanos mediante un vector de reales este problema no se puede resolver usando ramificacion y poda si no se fija unacota superior al numero total de aplicaciones de funciones. cual de estas expresiones es falsa? 2n^2 + 3n + 1 pertenece O(n^3) n + nlogn pertenece omega(n) n + nlogn pertenece promedio(n). si el coste temporal de un algoritmo es T8n) , ¿cual de las siguientes situaciones esimposible? T(n) pertenece O(n) y T(n) pertenece promedio(n) T(n) pertenece omega(n) y T(n) pertenece promedio(n^2) T(n) pertenece promedio(n) y T(n) pertenece omega(n^2). el coste temporal asintotico de insertar un elemento en un vector ordenado de forma que continue ordenado es O(n) O(logn) O(n^2). ¿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 el coste temporal asintotico en el caso medio nada de interes. en ausencia de cotas optimistas y pesimistas, la estrategia de backtracking... no se puede usar para resolver problemas de optimizacion no recorre todo el arbol si hay manera de descartar subarboles que representen conjuntos de soluciones no factibles debe recorrer siempre todo el árbol. |
Denunciar Test