Preguntas repetidas 23/24

¿Puede ocurrir que la solución recursiva de estilo “divide y vencerás” pero con memoización de un problema resuelva menos subproblemas que la mejor solución iterativa posible de programación dinámica?. ● A) No, nunca. ● B) Sí, porque no existe garantía de que la mejor solución iterativa posible no resuelva problemas repetidos, mientras que la técnica de memoización lo garantiza directamente mediante el uso de un almacén. ● C) Sí, porque la mejor solución iterativa posible de programación dinámica puede resolver subproblemas que no sean necesarios al resolver subproblemas posteriores.

En la estrategia de ramificación y poda se suele usar una cola de prioridad para decidir en qué orden se expanden los nodos. Imaginemos un problema de optimización. ¿Puede ser que el valor por el cual se ordenan los nodos sea una cota pesimista del nodo?. ● A) No, porque para podar necesitamos una cota optimista. ● B) No, porque una cota pesimista es típicamente el valor que se encuentra en una de las hojas que cuelga del nodo. ● C) Sí.

a. b. c.

Existen dos algoritmos que para ordenar un vector de n elementos, buscan el máximo de esos n elementos, lo intercambian con el n-ésimo elemento para ponerlo al final, y luego ordenan, usando el mismo algoritmo, el vector de las primeras n - 1 componentes. ¿Cuál de las afirmaciones siguientes es cierta?. ● A) Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por selección; el primero tiene un coste temporal O(n logn) y el segundo, O(n2). ● B) Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por burbuja o bubblesort; el primero tiene un coste temporal O(n logn) y el segundo, O(n2). ● C) Uno de los algoritmos es heapsort y el otro es una de las posibles maneras de realizar la ordenación por selección; el primero tiene un coste temporal O(n) y el segundo, O(n2).

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 técnica y luego sumo las dos cantidades. Cuando al partir una lista me quedo con una cantidad sólo, la suma es esa cantidad, y si me quedan cero cantidades, la suma es cero. ¿Gano tiempo, es decir, hago menos sumas?. ● A) No, en este caso el coste temporal es Θ(n logn). ● B) Sí, ya que en este caso el coste temporal se reduce a Θ(log n). ● C) No, ya que la complejidad temporal del método propuesto es la misma que la de sumar una a una las cantidades.

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

Uno de estos tres algoritmos de ordenación no opera directamente sobre el vector, y necesita almacenamiento adicional para los elementos del mismo. ¿Cuál es?. ● A) Mergesort. ● B) Heapsort. ● C) Quicksort.

Tiene un coste temporal prohibitivo, ya que puede calcular nopt(x) para el mismo valor de x más de una vez. Dependiendo de cuáles sean los valores faciales y la suma, puede ser que el algoritmo recursivo no encuentre solución. Encuentra siempre la solución óptima.

Dada la versión restringida del problema MCP , estamos interesados en obtener, para cada casilla del mapa, el camino más corto entre esa casilla y el destino (n - 1,m - 1). ¿Qué esquema de entre los siguientes es el más apropiado en este caso?. ● A) Memoización. ● B) Ramificación y poda. ● C) Vuelta atrás.