mod 1 C2 2026

Se pretende resolver la versión general del problema del laberinto mediante un algoritmo de vuelta atrás. ¿Qué ocurre si la solución subóptima inicial coincide con la cota optimista del nodo inicial?. Que la cota optimista está mal estimada. Que el algoritmo no debería explorar ningún nodo más. Que el algoritmo sería incorrecto ya que el subóptimo de partida es en realidad una cota pesimista para el nodo inicial.

Di cuál de estas tres afirmaciones sobre las soluciones basadas en algoritmos de búsqueda y enumeración (vuelta atrás, ramificación y poda) para el problema de la mochila sin división de los objetos es cierta. Requieren que los pesos sean discretos o discretizables. Requieren que los valores sean discretos o discretizables. No requieren que los pesos sean discretos o discretizables.

El algoritmo de ordenación Quicksort divide el problema en dos subproblemas. Con respecto al tamaño del problema (n), ¿Cuál es la complejidad temporal asintótica de realizar esa división?. Θ(n). Depende de la versión de Quicksort. Θ(1).

Con respecto al Teorema de reducción: Las otras dos opciones son ambas falsas. Que se cumpla es condición necesaria para poder aplicar programación dinámica. Que se cumpla es condición necesaria para poder aplicar divide y vencerás.

En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución 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.

En cuanto a la complejidad temporal de la siguiente función, marca la opción apropiada. (En la llamada inicial, pri =0 y ult =n-1, donde n es la longitud de la cadena cad). En el peor de los casos es O(n/2). Las otras dos opciones son ambas ciertas. El mejor de los casos ocurre cuando la cadena está vacía o contiene un solo carácter.

¿Cuál es la relación de recurrencia asociada a la complejidad temporal de la siguiente función?. T(n) = { 1 n=0 { n + T(n-1) n>=1. T(n) = { 1 n=0 { 1 + T(n-1) n>=1. T(n) = { 1 n=0 { 1 + 2T(n-1) n>=1.

¿Cuál de estos problemas no tiene una solución eficiente utilizando programación dinámica?. La mochila discreta cuyos pesos son números reales. El problema del cambio. La mochila discreta cuyos pesos son números naturales.

Sea la siguiente relación de recurrencia, Si T(n) ∈ Θ(n2), ¿en cuál de estos tres casos nos encontraríamos?. g(n) = n². g(n) =n. Ninguna de las otras dos opciones es correcta.

Indica cuál es la complejidad temporal en función de n, donde A es un vector de enteros y k es una constante que no depende de n, del fragmento siguiente: Θ(n). Θ(n²). Θ(k).

Se pretende resolver la versión general del problema del laberinto mediante un algoritmo de búsqueda y enumeración. Para reducir los nodos visitados, utilizamos un almacén de resultados parciales obtenido mediante la técnica de programación dinámica iterativa aplicándola a la versión restringida del mismo problema. El almacén se rellena hacia adelante comenzando en la casilla de entrada al laberinto. ¿De qué poda se trata?. De una poda basada en la cota pesimista. Ninguna de las otras dos opciones es cierta. De una poda basada en la cota optimista.

Si el coste temporal de un algoritmo es T(n), o bien dos de las siguientes situaciones son posibles y solo una es imposible, o bien al contrario, dos son imposibles y solo una es posible. Marca la que, en este sentido, es diferente a las otras dos. Τ(n) ∈ Θ(n) y T(n) ∈ Ω(n²). Τ(n) ∈ O(n) y T(n) ∈ Θ(n). Τ(n) ∈ O(n) y T(n) ∈ Θ(n²).

Disponemos de n claves que llegan una a una y debemos construir un montículo de máximos. ¿Cuál de las siguientes estrategias no garantiza obtenerlo?. Insertar las clave en un vector y después hundir sucesivamente cada elemento desde la última posición hasta la primera. Insertar las clave en un vector y después flotar sucesivamente cada elemento desde la última posición hasta la primera. Partir de un montículo vacío e insertar cada clave que va llegando usando push.

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. Θ(2^n). Θ(n). Θ(n^2).

De las siguientes expresiones, o bien dos son verdaderas y una es falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos. O(n²) ⊂ O(n³). Ω(n³) ⊂ Ω(n²). Θ(n²) ⊂ Θ(n³).

¿Qué hace la siguiente función?. Nada, deja el vector como estaba. Ordena el vector А. Invierte el vector A (el último elemento quedará el primero).

Un problema presenta una subestructura óptima. ¿Por qué no es suficiente para que tenga solución eficiente mediante la técnica programación dinámica?. Porque la subestructura óptima no garantiza la existencia de solapamientos en los subproblemas. Porque la subestructura óptima no garantiza resolver el inconveniente derivado del solapamiento de los subproblemas. Porque además el problema ha de tener solución naive con la que se pueda aplicar la técnicа.

Se pretende resolver la versión general del problema del laberinto mediante un algoritmo de ramificación y poda. Para determinar si un nodo es prometedor se estima la longitud restante haciendo uso de un algoritmo voraz que completa el camino hasta la salida. ¿Qué podemos decir del algoritmo resultante?. Que presumiblemente explorará menos nodos de los necesarios. Que si comienza con una solución subóptima encontrará antes la óptima. Que presumiblemente explorará más nodos de los necesarios.

En cuanto a la posibilidad de aplicar la técnica de programación dinámica iterativa para resolver un problema: No necesariamente ha de conocerse de antemano todos los posibles subproblemas pero sí debe saberse, dados dos de ellos cualesquiera, cuál es más pequeño. Se debe conocer de antemano todos los posibles subproblemas pero no necesariamente se debe disponer de una ordenación entre todos ellos según tamaño. Se debe conocer de antemano todos los posibles subproblemas y además, se debe disponer de una ordenación entre todos ellos según tamaño.

Se pretende mejorar mediante programación dinámica iterativa la siguiente función (v1 y v2 son vectores definidos como variables globales), ¿Cuál es la mejor complejidad espacial que se puede conseguir?. O(y). O(x·y). O(x).

¿Cuál de las siguientes estrategias de búsqueda es más apropiada en un esquema de vuelta atrás?. Ninguna de las otras dos estrategias es compatible con el esquema de vuelta atrás. Explorar primero los nodos con mejor cota optimista. Explorar primero los nodos con mejor valor hasta el momento en la función que se pretende optimizar.

En un algoritmo de optimización resuelto mediante ramificación y poda ¿Podría encontrarse la solución óptima sin haber alcanzado nunca un nodo hoja?. Sí, esto puede ocurrir incluso si no se hace uso de cotas pesimistas. No, los nodos hojas son los nodos completados y por lo tanto hay que visitar al menos uno de ellos para almacenarlo como la mejor solución hasta el momento. Sí, pero esto solo podría ocurrir si se hace uso de cotas pesimistas.

En la versión general del problema del laberinto, si estamos procesando la casilla (i, j) y la casilla de salida del laberinto es la (m, n), ¿cuál de las siguientes opciones será una buena cota pesimista al camino que queda por recorrer?. |m-i|+|m-j|. Ninguna de las otras dos opciones es cierta. máx(|m-i|, |n-j|).

En un algoritmo de búsqueda exhaustiva, ¿Qué ocurre si la cota pesimista de un nodo se corresponde con una solución que no es factible?. Nada especial, las cotas pesimistas no tienen por qué corresponderse con soluciones factibles. Que el algoritmo sería más lento pues se explorarían más nodos de los necesarios. Que el algoritmo sería incorrecto pues podría descartarse un nodo que conduce a la solución óptima.

Las siguientes afirmaciones se refierena un nodo cualquiera del árbol de búsqueda de ramificación y poda en un problema de minimización. De ellas, o bien dos son ciertas y una es falsa, o bien una es cierta y dos son falsas. Marca la que es diferente a las otras dos. El nodo es prometedor si su cota pesimista es menor que la mejor cota pesimista encontrada hasta antes de llegar a este nodo. El nodo no es prometedor si su cota optimista es mayor que la mejor cota pesimista encontrada hasta antes de llegar a este nodo. El nodo no es prometedor si su cota pesimista es menor que su cota optimista.

Se pretende resolver la versión general del problema del laberinto mediante ramificación y poda y para ello se usa una estrategia que consiste en priorizar las expansiones de los nodos que contienen un camino explorado más corto. ¿Qué podemos decir del algoritmo resultante?. Que el recorrido en el árbol de búsqueda será equivalente a un recorrido por niveles, por lo que no es necesario utilizar una cola de prioridad. Las otras dos opciones son ambas ciertas. Que la primera hoja a la que se llegue es la solución del problema y por lo tanto, ya no será necesario explorar más nodos de la lista de nodos vivos, aunque no esté vacía.

Indica cuál de las siguientes afirmaciones es cierta: Si un esquema de ramificación y poda encuentra la solución óptima a un problema, un esquema de vuelta atrás podría no encontrarla. Si un esquema de ramificación y poda encuentra la solución óptima a un problema, un esquema de vuelta atrás siempre es más ineficiente. Si un esquema de ramificación y poda encuentra la solución óptima a un problema, un esquema de vuelta atrás también la encuentra siempre.

Una de estas tres afirmaciones es falsa. ¿Cuál?. El esquema de ramificación y poda no garantiza que la complejidad temporal de resolución de un problema de selección discreta no sea exponencial. Los algoritmos voraces no sirven para resolver problemas de selección discreta. Un algoritmo voraz puede no encontrar la solución óptima de un problema de selección discreta.

Se pretende resolver el problema del viajante de comercio (travelling salesman problem) mediante el esquema de vuelta atrás, ¿cuál de los siguientes valores se espera que se comporte mejor para decidir de si un nodo es prometedor?. La suma de los pesos de las k aristas restantes más cortas, donde k es el número de ciudades que quedan por visitar. El valor que se obtiene de multiplicar k por el peso de la arista más corta de entre las restantes, donde k es el número de ciudades que quedan por visitar. la suma de los pesos de las aristas que completan la solución paso a paso visitando el vértice más cercano al último visitado.

¿Cuál es la definición correcta de O(g)?. O(g) ={f : IN -> IR+|∀c ∈ IR+, ∀n_0 ∈ IN, ∀n >= n_0, f(n) <= cg(n)}. O(g) ={f : IN -> IR+|∃c ∈ IR+, ∃n_0 ∈ IN, ∀n >= n_0, f(n) <= cg(n)}. O(g) ={f : IN -> IR+|∃c ∈ IR+, ∃n_0 ∈ IN, ∀n >= n_0, g(n) <= cf(n)}.

Con respecto a la Propiedad de subestructura óptima: Que se cumpla es condición necesaria para poder aplicar divide y vencerás. Que se cumpla es condición necesaria para poder aplicar programación dinámica. Las otras dos opciones son ambas verdaderas.

Sea un problema que cumple la propiedad de subestructura óptima pero no presenta solapamiento de subproblemas. ¿Qué técnica de diseño algorítmico suele ser la mejor opción?. Divide y vencerás. Programación dinámica. Algoritmos voraces.

Se dispone de un conjunto de n valores numéricos dispuestos en un vector sin orden preestablecido. Se desea escribir una función que reciba ese vector y un valor k (n/2 <= k <= n) y que devuelva los k valores más pequeños dispuestos en otro vector de manera ordenada. ¿Cuál es la complejidad temporal del mejor algoritmo que se puede escribir?. O(n·log(n)). O(k·log(n)). O(k·n).

Dado un vector de n números enteros, ¿con qué complejidad temporal se puede determinar si sus elementos están dispuestos formando un montículo de mínimos?. O(n). Ninguna de las otras dos opciones es correcta. O(log(n)).

Dada la versión reducida del problema del laberinto, se pretende conocer únicamente la longitud del camino de salida más corto. ¿Cuál es la mejor complejidad espacial y temporal que se puede conseguir?. Ө(máx(n, m)), tanto espacial como temporal. Ө(n·m), tanto espacial como temporal. Espacial Ө(mín(n, m)) y temporal Ө(n·m).

Queremos conocer el camino de mínima longitud en el problema restringido del laberinto usando un algoritmo de programación dinámica con la técnica de complejidad espacial mejorada (con dos vectores). ¿Cómo se puede obtener?. Recorriendo el primer vector, empezando por la casilla de salida y buscando los resultados de los subproblemas accesibles a partir de ella. Recorriendo el primer vector, empezando por la casilla de entrada y buscando los resultados de los subproblemas accesibles a partir de ella. Ninguna de las otras dos opciones es válida.

¿Cuál es la complejidad temporal (en función de n) del fragmento siguiente de C++?. Ө(log n). Ө(n). Ө(n·log(n)).

Consideremos el problema de la mochila sin fraccionamiento con capacidad máxima W = 10 y los siguientes objetos con sus pesos p_i y sus valores v_i. Supongamos un nodo interno del árbol de búsqueda que considera tomar el primer objeto y tiene que decidir por los restantes. Siguiendo el criterio del valor específico, ¿cuál de los siguientes pares (cota pesimista, cota optimista) es el que corresponde a ese nodo?. (35, 39). (30, 35). (30,39).

¿Cuál de las siguientes situaciones da lugar al peor caso del algoritmo Quicksort?. Cuando la profundidad de la recursión es Ө(n). Cuando el coste de particionar es lineal. Cuando la profundidad de la recursión es Ө(log(n)).

Si f ∈ Ө(g1) y f ∈ Ө(g2) entonces. f ∈ Ө(g1·g2). f ∈ Ө(g1 + g2). f ∉ Ө(máx(g1, g2).