algir enero 2024

Dada la version restringida del problema MCP, queremos obtener todos los caminos que llegan a la salida del mapa y tambien sus dificultades asociadas. ¿Cual de las siguientes tecnicas resultarıa mas eficiente?. Tanto programacion dinamica como vuelta atras resultarıan equivalentes. Programacion dinamica. Vuelta atras.

Queremos resolver la siguiente instancia del problema de la mochila 0/1: v = (8, 6, 4); w =(2, 3, 4); W = 6 donde v; w y W son, respectivamente, el vector de valores de los objetos; el vector de sus pesos y la carga maxima de la mochila. Con respecto a posibles cotas pesimista y optimista del nodo inicial del arbol de busqueda de vuelta atras, ¿cual de los siguientes valores son correctos?. cota pesimista=14; cota optimista=15. cota pesimista=15; cota optimista=14. Ninguna de las otras dos opciones es correcta.

O(2^n). O(n^2). O(n).

En la estrategia de ramificacion y poda se suele usar una cola de prioridad para decidir en que orden se expanden los nodos. Imaginemos un problema de optimizacion. ¿Puede ser que el valor por el cual se priorizan los nodos a expandir sea una cota pesimista del nodo?. No, porque para podar necesitamos una cota optimista. No, porque una cota pesimista es tıpicamente el valor que se encuentra en una de las hojas que cuelga del nodo. Si.

Se pretende aplicar la tecnica memoizacion a la siguiente funcion recursiva: ¿Que complejidades temporal y espacial cabe esperar de la funcion resultante?. Temporal O(x*y) y espacial O(x). O(y-x), tanto temporal como espacial. Ninguna de las otras dos opciones es correcta.

Dada la version restringida del problema MCP, estamos interesados en obtener, para cada casilla del mapa, el camino mas corto entre el origen (0,0) y esa casilla. ¿Que esquema de entre los siguientes es el mas apropiado en este caso?. Memoizacion. Ambas tecnicas resultan equivalentes. Programacion dinamica iterativa.

a. b. c.

a. b. c.

Dados dos nodos cualesquiera del arbol de busqueda de ramificacion y poda, en general, ¿se puede saber con certeza cual esta mas cerca de la solucion optima del problema a resolver?. Sı, el que tiene mejor cota pesimista. Sı, pero solo si ambos nodos estan completados. Sı, el que tiene mejor cota optimista.

a. b. c.

¿Puede ocurrir que la solucion recursiva de estilo “divide y venceras” pero con memoizacion de un problema resuelva menos subproblemas que la mejor solucion iterativa posible de programacion dinamica?. No, nunca. Sı, porque no existe garantıa de que la mejor solucion iterativa posible no resuelva problemas repetidos, mientras que la tecnica de memoizacion lo garantiza directamente mediante el uso de un almacen. Sı, porque la mejor solucion iterativa posible de programacion dinamica puede resolver subproblemas que no sean necesarios al resolver subproblemas posteriores.

Con respecto al Principio de optimalidad: Las otras dos opciones son ambas verdaderas. Que se cumpla es condicion necesaria para poder aplicar divide y venceras. Que se cumpla es condicion necesaria para poder aplicar programacion dinamica.

¿Se puede resolver el problema de la mochila discreta con pesos discretos utilizando unicamente la tecnica de divide y vencer ´ as?. No, ya que no se cumple la Propiedad ”subestructura optima”. No, ya que no cumple el Teorema de reduccion. Si, pero a costa de una complejidad temporal prohibitiva.

Se dispone de un conjunto de n valores dispuestos en una matriz dˆd sin orden preestablecido. ¿Con que complejidad, con respecto a n, podemos determinar la posicion donde esta el mas pequeño?. O(n). O(n^2). O(sqrt(2)).

¿Que hace el algoritmo de Prim para que la toma de decisiones sea eficiente?. Almacena la mejor arista que conecta cada vertice no visitado con otro ya visitado. Utiliza el TAD union-busqueda para no tener que comprobar si una arista forma ciclos. Almacena las aristas por orden creciente de pesos, eliminando tras cada decision aquellas que conectan vertices ya visitados.

Tenemos un vector de tamaño n cuyos elementos estan dispuestos formando un heap de maximos. ¿Cual serıa la complejidad temporal de ordenarlo de manera descendente?. O(n). Niguna de las otras dos opociones es cierta. O(n log n).

a. b. c.

Tengo que sumar una larga lista de n cantidades diferentes y se me ha ocurrido que una manera de ganar tiempo es la siguiente estrategia recursiva: parto la lista en dos sublistas iguales, calculo su suma por separado usando la misma tecnica y luego sumo las dos cantidades. Cuando al partir una lista me quedo con una cantidad solo, la suma es esa cantidad, y si me quedan cero cantidades, la suma es cero. ¿Gano tiempo, es decir, hago menos sumas?. No, en este caso el coste temporal es Θ(n log n). No, en este caso el coste temporal es Θ(n log n). No, ya que la complejidad temporal del metodo propuesto es la misma que la de sumar una a una las cantidades.

a. b. c.

a. b. c.

Queremos resolver la version general del problema MCP mediante ramificacion y poda y para ello implementamos la lista de nodos vivos mediante una pila.¿que podemos decir del algoritmo resultante?. Que para mejorar a vuelta atras sera necesario hacer uso de las cotas pesimistas de los nodos intermedios. Que presumiblemente sera mas eficiente que vuelta atras, tanto en tiempo como en espacio requerido. Que presumiblemente sera menos eficiente que vuelta atras.

a. b. c.

a. b. c.

Queremos resolver la version general del problema MCP mediante ramificacion y poda.¿Podrıamos tener mas de una cota optimista por cada nodo del arbol de busqueda?. Si, no hay ningun problema en ello. No, la cota optimista debe ser unica. Sı, pero por cada cota optimista adicional debemos tener otra cota pesimista, para poder emparejarlas.

a. b. c.

En un vector cuyos elementos estaban ordenados, acabamos de anadir al final y sin respetar el orden inicial, unos cuantos elementos con valor indeterminado. Queremos restablecer la ordenacion haciendo uso del algoritmo Quicksort ¿Que elemento deberıamos utilizar como pivote?. El que ocupa la ultima posicion. El que ocupa la primera posicion. El que ocupa la posicion central.

Con respecto al Teorema de reduccion: Que se cumpla es condicion necesaria para poder aplicar divide y venceras. Las otras dos opciones son ambas falsas. Que se cumpla es condicion necesaria para poder aplicar programaci dinamica.

Dada la version general del problema MCP ¿Que ocurre si la cota optimista de un nodo resulta ser el valor que se obtiene de una solucion factible pero que no es la mejor en el subarbol generado por ese nodo?. Que el algoritmo serıa incorrecto pues podrıa descartarse el nodo que conduce a la solucion optima. Que el algoritmo serıa mas lento pues se explorarıan mas nodos de los necesarios. Nada especial, las cotas optimistas se corresponden con soluciones factibles que no tienen por que ser las mejores.

a. b. c.

Se pretende resolver la version general del problema MCP mediante ramificacion y poda. Utilizamos una cota optimista que consiste en estimar la dificultad del camino restante haciendo uso de del algoritmo voraz implementado en la practica 7. ¿Que podemos decir del programa resultante?. Que presumiblemente explorara mas nodos de los necesarios. Que presumiblemente explorara menos nodos de los necesarios. Que si comienza con una solucion suboptima encontrara antes la optima.

a. b. c.

Uno de estos tres algoritmos de ordenacion no opera directamente sobre el vector, y necesita almacenamiento adicional para los elementos del mismo. ¿Cual es?. Mergesort. Heapsort. Quicksort.

a. b. c.

¿Que diferencia un algoritmo de ramificacion y poda de otro de vuelta atras?. La manera de determinar si un nodo es prometedor. Las estrategias de busqueda, que en vuelta atras no pueden implementarse. La manera de tratar las cotas pesimistas.

Dada la version general del problema MCP, queremos obtener todos los caminos que llegan a la salida del mapa y tambien sus dificultades asociadas. En este caso, ¿serıa util utilizar la distancia de Chebyshev? (La distancia de Chebyshev entre dos puntos viene dada por ladiferencia maxima entre las coordenadas de cada dimension). NO. Sı, presumiblemente mejorara la estrategia de busqueda. Sı, presumiblemente mejorara la poda basada en la mejor solucion encontrada hasta el momento.

¿Que tecnica de entre las estudiadas se usa generalmente para implementar los algoritmos de busqueda informada?. Vuelta atras. Programacion dinamica. Ramificacion y poda.

a. b. c.

Estamos resolviendo el problema MCP mediante un algoritmo de busqueda y enumeracion. El mejor camino de llegada encontrado hasta el momento tiene una dificultad con valor 100.Mas adelante, tenemos que decidir acerca de un nodo n del que hemos obtenido una cota optimista que ha resultado ser 120. ¿Cual de las siguientes afirmaciones es siempre cierta?. Esa cota optimista esta mal calculada. El nodo n debe ser descartado. El nodo n debe ser expandido.

Dada la version restringida del problema MCP, estamos interesados en obtener, para cada casilla del mapa, el camino mas corto entre esa casilla y el destino (n - 1, m - 1). ¿Que esquema de entre los siguientes es el mas apropiado en este caso?. Memoizacion. Ramificacion y poda. Vuelta atras.

En un problema de optimizacion, si el dominio de las decisiones es un conjunto infinito,. podremos aplicar el esquema vuelta atras siempre que se trate de un conjunto infinito numerable. una estrategia voraz puede ser la unica alternativa. es probable que a traves de programacion dinamica se obtenga un algoritmo eficaz que lo solucione.