Algoritmia-c2-2025

Dada la siguiente función: De las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien al contrario, una es cierta y dos son falsas. Marca la que en este sentido es diferente a las otras dos. La complejidad temporal en el peor de los casos viene dada por la expresión [sumatorio de n, desde k=1, de (n-k). El peor de los casos ocurre cuando el primer elemento del vector es estrictamente mayor que los restantes sin importar el orden de los demás. La complejidad temporal en el mejor de los casos ocurre cuando el vector está vacío.

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 doscantidades. 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 Θ(nlogn). Sí, ya que en este caso el coste temporal se reduce a Θ(logn). No, ya que la complejidad temporal del método propuesto es la misma que la de sumar una a una las cantidades.

Dada la versión restringida del problema del laberinto, disponemos de una matriz mxn (ya cumplimentada) donde cada casilla (i,j) contiene la longitud del mejor camino desde esa casilla hasta el destino. ¿Cuál es la complejidad temporal del mejor algoritmo que puede escribirse para obtener un camino óptimo que llega a la salida desde el origen?. Ninguna de las otras dos opciones es cierta. Θ(mín{n,m}). Θ(máx{n,m}).

De las siguientes situaciones, o bien dos son posibles y una no lo es, o bien al contrario, solo una es posible y las otras dos no lo son. Marca la que, en este sentido, es diferente a las demás. a. b. c.

Qué ocurre con la complejidad temporal de un algoritmo de programación dinámica cuando se mejora la complejidad espacial?. Que normalmente aumenta. Que normalmente también disminuye. Que normalmente no cambia.

Se pretende implementar mediante programación dinámica recursiva la función: Donde double g(int,int) es una función definida en otro sitio. ¿cuál es la mejor estructura para el almacén?. int A[][]. int A[]. Ninguna de otras anteriores es cierta.

Uno de estos tres algoritmos NO tiene una complejidad espacial constante con el tamaño del problema que resuelve (sin considerar la pila de recursión). ¿Cuál es?. Mergesort. Heapsort. Quicksort.

¿Cuál es la relación de recurrencia que representa la complejidad promedio del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase). a. b. c.

Di cual de estas afirmaciones es cierta. a. b. c.

El elemento n-ésimo de la serie tribonacci, T(n), se define como sigue: T(n)=T(n-3)+T(n-2)+T(n-1) para n>=3; T(0)=1, T(1)=1 y T(2)=1.¿Cuál de estas afirmaciones es falsa?. Una implementación ingenua de la función T(n), la cual llamaría a T(n-1), T(n-2) y T(n-3) tendría una complejidad temporal prohibitiva por la repetición de cálculos que se produciría. Es posible una implementación de programación dinámica iterativa con complejidad temporal Θ(n). El problema no tiene una solución de programación dinámica iterativa pero se puede resolver añadiendo memoización al cálculo recursivo ingenuo en el que el cálculo de T(n) comporta realizar las llamadas a T(n-1), T(n-2) y T(n-3).

De las siguientes afirmaciones, 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. Si alguna de las cotas pesimistas de un nodo coincide con alguna de sus cotas optimistas entonces ese nodo no debe ser explorado. Si alguna de las cotas pesimistas de un nodo no mejora la mejor solución que se tiene hasta el momento entonces ese nodo no debe ser explorado. Si alguna de las cotas pesimistas de un nodo no mejora cualquiera de sus cotas optimistas entonces ese nodo no debe ser explorado.

¿Garantiza el uso de una estrategia de divide y vencerás la existencia de una solución de complejidad temporal polinómica a cualquier problema?. No. Sí, en cualquier caso. Sí, pero siempre que la complejidad temporal conjunta de las operaciones de descomposición del problema y la combinación de las soluciones sea polinómica.

¿Cuál es el propósito principal de un Heap en el algoritmo de ordenación HeapSort?. Permitir la extracción repetida del elemento máximo o mínimo de manera eficiente. Conseguir una ordenación parcial en el vector. Insertar elementos en el nuevo vector ordenado de manera eficiente.

¿Se puede resolver mediante ramificación y poda un problema de selección discreta en el que cada una de las n decisiones se toman de un conjunto finito diferente?. Sí, siempre. No. Las decisiones deben ser todas de la misma naturaleza. Sí, pero sólo si las decisiones son todas binarias.

Tratándose de un problema de optimización, en la lista de nodos vivos de ramificación y poda... ...sólo se introducen los nodos que con certeza van a mejorar la mejor solución que se tiene en ese momento. ... puede haber nodos que no son prometedores. Las otras dos opciones son ambas ciertas.

Con respecto a n, ¿Cuál es la complejidad temporal del siguiente fragmento de código?. Θ(n^2). Θ(n). Ninguna de las otras dos opciones es cierta.

Estamos resolviendo el problema del laberinto mediante un algoritmo de búsqueda y enumeración. Supongamos que el mejor camino de salida encontrado hasta el momento es de longitud 100. Más adelante, tenemos que decidir acerca de un nodo n del que hemos obtenido una cota optimista que ha resultado ser 80 y una pesimista con valor 90. ¿Cuál de las siguientes afirmaciones es siempre cierta?. Algo está mal pues la cota pesimista recién calculada no puede ser inferior a 100. Algo está mal pues la cota optimista recién calculada no puede ser inferior a 100. El nodo n podría formar parte de la solución y además, tenemos la certeza de que su cota pesimista es la mejor encontrada hasta el momento.

Con respecto a la versión general del problema de la mochila sin fraccionamiento... (marcar la opción falsa). ... cumple la propiedad de subestructura óptima y por lo tanto se puede plantear una solución de divide y vencerás. ... no se conoce ninguna reducción en subproblemas que cumpla el teorema de reducción. ... tiene una solución eficiente utilizando programación dinámica.

Dada la versión restringida del problema del laberinto, estamos interesados en obtener, para cada casilla accesible, el camino más corto entre el origen (0,0) y esa casilla. ¿Qué esquema de entre los siguientes es el más apropiado en este caso?. Memoización. Ambas técnicas resultan equivalentes. Programación dinámica iterativa.

La complejidad temporal del algoritmo Mergesort cuando se aplica a un vector de tamaño n es...(selecciona la más ajustada). . . . Ω(nlogn) y O(n^2). . . . Θ(nlogn). . . . Ω(n) y O(n^2).

Dada la versión general del problema del laberinto mxn, la distancia de Manhattan entre las casillas (i, j) y (m,n) viene dada por la suma del número movimientos del tipo horizontal que quedan hasta llegar al extremo derecho del laberinto (n-j) y los del tipo vertical que quedan hasta llegar al extremo inferior del laberinto (m-i). ¿Para qué puede resultar útil esta distancia? (dmanhattan(i,j) = n-j + m-i). Para obtener cotas optimistas. Para obtener cotas pesimistas. Ninguna de las otras dos opciones es válida.

¿Cuál es la complejidad temporal de la aproximación voraz a la solución de la versión restringida del problema del laberinto?. O(n+m). Las otras dos opciones son ambas ciertas. O(máx{n,m}).

En un algoritmo de vuelta atrás, ¿se podrían priorizar las expansiones de los nodos con mejor cota optimista de manera que el algoritmo siga siendo de vuelta atrás?. No, ya no sería de vuelta atrás. Sí, pero a costa de aumentar considerablemente su complejidad temporal. Sí, basta con cambiar la estrategia del búsqueda.

¿Qué se deduce... a. b. c.

Dada la versión restringida del problema del laberinto, disponemos de una matriz mxn (ya cumplimentada) donde cada casilla (i,j) contiene la longitud del mejor camino desde esa casilla hasta el destino. ¿para qué resulta útil esta matriz si se pretende resolver el problema mediante ramificación y poda? (cuidado: se trata de la versión restringida del problema). Las otras dos opciones son ambas ciertas. Para obtener cotas optimistas. Para obtener cotas pesimistas.

Estamos resolviendo el problema del laberinto mediante un algoritmo de búsqueda y enumeración. Supongamos que nos encontramos en un nodo interno n situado en un nivel x del árbol de estados posibles. ¿Qué podemos decir acerca del valor de x?. Es una cota optimista de n. Es una cota pesimista de n. Por sí solo, n no es cota, ni optimista ni pesimista.

Le he pedido a una IA (inteligencia artificial) que me resuelva la versión general del problema del laberinto y me ha propuesto un algoritmo similar al del listado, pero resulta poco eficaz. (La matriz visited está correctamente inicializada al valor false.) De las siguientes opciones, o bien dos son ciertas y una es falsa, o bien al contrario, solo una es cierta y las otras dos no lo son. Marca la que, en este sentido, es diferente a las demás. No detecta todos los subproblemas repetidos que pueden aparecer. La poda basada en la mejor solución hasta el momento se puede mejorar fácilmente. No hace uso de ninguna cota optimista.

¿Cuál de las siguientes formulaciones expresa mejor la complejidad temporal, en función del parámetro n, de la siguiente función? (asumimos que n es potencia exacta de 2). a. b. c.

Si se aplica programación dinámica para resolver la versión restringida del problema del laberinto ¿cuál es la complejidad temporal y espacial del mejor algoritmo recursivo que se puede obtener? (sin considerar el espacio ocupado por la pila de recursión). Temporal Θ(2^(min{n,m})) y espacial Θ(1). Ω(nxm), temporal y espacial. Temporal Θ(nxm) y espacial Θ(min{n,m}).

Cuál es la complejidad temporal en función del tamaño del problema (n) del mejor algoritmo que se puede escribir para sumar todos los elementos de una matriz?. O(n^2). O(logn). O(n).

Tenemos un conjunto de n enteros positivos y queremos encontrar el subconjunto de tamaño m de suma mínima. Lo más adecuado sería usar una técnica de ramificación y poda, aunque en el peor caso el coste temporal asintótico (o complejidad temporal) sería exponencial. Para encontrar la solución habría que probar con todas las combinaciones posibles de m enteros, con lo que la técnica de ramificación y poda no aporta nada con respecto a vuelta atrás. Una técnica voraz daría una solución óptima.

Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función?. Θ(n^2). Ninguna de las otras dos opciones es cierta. Θ(n^2 logn).

Se pretende resolver la versión general del problema del laberinto y para ello disponemos de varias cotas pesimistas. ¿Cuál deberíamos usar si lo que se pretende es reducir la cantidad de nodos a expandir?. La que obtenga valores más pequeños. La que obtenga valores más elevados. Es indiferente pues el uso de cotas pesimistas no reduce la cantidad de nodos que se expanden.

Con respecto a un Heap de máximos, de las siguientes afirmaciones, 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. Todos los nodos internos son menores que sus hijos. El elemento máximo siempre se encuentra en una hoja. El elemento máximo siempre se encuentra en la raíz.

¿Cuál es el caso peor del algoritmo de ordenación Quicksort que toma el primer elemento como pivote?. Cuando el elemento pivote queda siempre en medio. Cuando debemos hundir el pivote hasta el fondo del montículo. Cuando el elemento pivote queda siempre en uno de los dos extremos.

En el algoritmo de Kruskal, ¿qué se selecciona en cada paso?. El vértice con menor grado en el grafo. La arista de menor peso que conecta un v´ertice visitado con otro sin visitar. La arista de menor peso, sin más.

En programación dinámica, ¿qué significa “subestructura óptima“?. Que la solución óptima a un problema puede construirse a partir de las soluciones óptimas de sus subproblemas. Que el tamaño del problema se ha repartido de forma equitativa entre los subproblemas. Que todos los subproblemas son independientes entre s´.

Se pretende resolver la versión general del problema del laberinto y para ello disponemos de varias cotas optimistas. ¿Cuál deberíamos usar si lo que se pretende es reducir la cantidad de nodos a expandir?. La que obtenga valores más pequeños. La que obtenga valores más elevados. La que más se aproxime a la mejor solución que se puede obtener con el nodo interno al que se le calcula la cota optimista.

Delassiguientes 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. a. b. c.

En ramificación y poda, el uso de cotas optimistas ... ... pueden eliminar soluciones factibles. ... garantizan que no se va a explorar todo el espacio de soluciones posibles. Las otras dos opciones son ambas ciertas.