Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando un algoritmo voraz se pretende conocer la dificultad del camino más favorable y para ello se va seleccionando una casilla escogida al azar de entre las tres posibles, hasta llegar al destino.¿Qué podemos decir de este algoritmo? Que aún siendo voraz existen otros criterios de selección con mejores resultados a priori Que es voraz puesto que las decisiones no se replantean. Que no es voraz.
Sea el problema "Camino de coste mínimo" con ocho movimientos: todas las casillas colindantes. Utilizando la técnica ramificación y poda se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. A
igualdad de coste temporal, ¿qué se prefiere una buena cota pesimista o una buena cota optimista? La optimista, una buena cota optimista siempre será más rentable que una buena
cota pesimista. La pesimista, una buena cota pesimista siempre será más rentable que una buena
cota optimista. No hay distinción, la más rentable siempre será la que mejor se aproxime a la
solución del nodo.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando la técnica memoización se pretende conocer la dificultad del camino más favorable. ¿Cuál es la mejor complejidad espacial y temporal que se puede
conseguir? Espacial Θ(n) y temporal Θ(n⋅m) Espacial Θ(n)y temporal Θ(2^max(n,m)) Θ(n⋅m), tanto espacial como temporal.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Se pretende listar todos los caminos posibles entre dos casillas cualesquiera ¿Qué técnica algorítmica deberíamos utilizar? Ramificación y poda. Programación dinámica. Backtracking.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. En cuanto a la complejidad espacial y temporal, ¿Cuál de los siguientes esquemas algorítmicos resulta más eficiente para resolverlo? Programación dinámica. Divide y vencerás Ramificación y poda.
Sea el problema "Camino de coste mínimo" con ocho movimientos: todas las casillas colindantes. Utilizando la técnica ramificación y poda se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. Para tratar de acelerar la búsqueda calculamos, para cada uno de los nodos visitados, una cota que consiste en suponer que la dificultad del camino restante es la suma de las dificultades de todas las casillas del mapa ¿De qué tipo de cota se trata? Optimista No es cota, ni pesimista ni optimista. Pesimista.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando la técnica ramificación y poda se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. Para tratar de acelerar
la búsqueda calculamos una cota para cada uno de los nodos visitados que consiste en resolver el mismo problema pero aplicando la técnica programación dinámica con la condición de que el camino debe pasar por la casilla asociada al nodo que acabamos de visitar. ¿Qué podemos decir de esa cota? Que es una cota pesimista y optimista al mismo tiempo. Que es una cota pesimista pero no optimista. Que en realidad no se trata de una cota, ni pesimista ni optimista.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur pero modificado de manera que el punto de partida es una casilla cualquiera (i,j) del mapa con nombre M (1 ≤ i ≤ n y 1 ≤ j ≤ m) y el destino en la casilla (n,m). Utilizando la técnica divide y vencerás se pretende conocer la dificultad del camino más favorable. ¿Cuál sería la recurrencia matemática más apropiada? b c d.
En un mapa similar al del problema "Camino de coste mínimo" con tres
movimientos: Este, Sureste y Sur se pretende conocer el número de caminos distintos que hay desde la casilla (1,1) hasta una casilla cualquiera (i,j) que pertenece al mapa. El mapa tiene n filas y m columnas ¿Cuál sería la recurrencia matemática más apropiada para abordarlo mediante Divide y vencerás? a b d.
Sea el problema "Camino de coste mínimo" con ocho movimientos: todas las casillas colindantes. Utilizando la técnica ramificación y poda se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. Para tratar de acelerar la búsqueda calculamos, para cada uno de los nodos visitados, una cota pesimista y otra optimista. ¿Cómo debería comportarse el algoritmo en el caso en el que el valor de ambas coincidan? Aún así es necesario expandir ese nodo. Ese nodo no debería expandirse. El algoritmo debería terminar pues ya ha encontrado la solución.
Sea el problema "Camino de coste mínimo" con 8 movimientos: las ocho casilla colindantes. Utilizando la técnica backtracking se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. Para el nodo inicial calculamos una cota pesimista y otra optimista ¿Cómo debería comportarse el algoritmo en el caso de que el valor de ambas coincidan? No debería continuar. Eso no es posible: alguna de las cotas estaría mal calculada. Debería continuar tratando de mejorar el valor obtenido.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Utilizando la técnica programación dinámica iterativa se pretende conocer la dificultad del camino más favorable. ¿Cuál es la mejor complejidad espacial y temporal que se puede conseguir? Espacial Θ(min(n,m)) y temporal Θ(n⋅m). Θ(n+m), tanto espacial como temporal. Espacial Θ(n) y temporal Θ(n⋅m).
.
Sea el problema "Camino de coste mínimo" con ocho movimientos (todas las casillas colindantes) pero modificado de manera que ahora se pretende encontrar el camino de máxima dificultad desde el origen hasta la casilla destino. ¿Qué cambios habría que hacer con respecto al problema sin modificar resuelto mediante ramificación y poda? Se podría intercambiar la cota pesimista por la optimista y viceversa. Se podría reutilizar la cota pesimista, pero adaptándola al nuevo problema. La cota optimista se podría reutilizar sin hacerle ningún cambio, pero utilizándola
como cota pesimista.
Sea el problema "Camino de coste mínimo" con ocho movimientos: todas las casillas colindantes. Utilizando la técnica ramificación y poda se pretende obtener la dificultad del camino más favorable desde el origen hasta la casilla destino. Para tratar de acelerar la búsqueda utilizamos un algoritmo de programación dinámica aplicado al mismo problema pero restringiendo los movimientos a tres: Este, Sureste y Sur. Con este algoritmo calculamos dos valores: 1: La dificultad del mejor camino desde una casilla cualquiera (i,j) hasta el destino; 2: La dificultad del mejor camino desde el origen hasta esa casilla (i,j). ¿con respecto al nodo que representa esa casilla, qué se puede decir de estos dos valores? Con el primero se puede componer una cota pesimista; con el segundo no se puede componer una cota optimista El primero es una cota pesimista; el segundo es una cota optimista. Con el segundo se puede componer una cota pesimista; con el primero no se puede componer una cota optimista.
Sea el problema "Camino de coste mínimo" con tres movimientos: Este, Sureste y Sur. Se pretende encontrar el camino más favorable con la menor complejidad temporal posible. ¿Cuál sería la más ajustada para realizar todo el proceso? O(n⋅m+m) O(n⋅m+n) O(n⋅m+n+m.
Una de las siguientes afirmaciones es falsa. Cuál? Si f ∈ O(g) y g ∈ O(f), entonces O(f) = O(g) Si f ∈ O(g) y g ∈ O(h), entonces f ∈ O(h) Si f ∈ O(g) y g ∈ O(f), entonces f = g.
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(2^log2(n)) ⊆ O(n^2) ⊂ O(n! (4^log2(n)) ⊆ O(n^2) ⊂ O(2^n) O(n^2) ⊂ O(2^log2(n)) ⊂ O(2^n)
.
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. Θ(log^2(n)) = Θ(log^3(n) Θlog(n3) ∉ Θ(log3(n)) Θ(log2(n)) = Θ(log3(n)).
Una de estas tres situaciones no es posible. ¿Cuál es? f(n) ∈ O(n) y f(n) ∈ Ω(1) f(n) ∈ O(n) y f(n) ∈ O(n2) f(n) ∈ Ω(n2) y f(n) ∈ O(n).
Con respecto a n, ¿Cuál es la complejidad temporal del siguiente fragmento de código? Θ(n^2) Θ(logn) Θ(n).
¿Cuál es la complejidad temporal de la siguiente función recursiva?(desperdicio) Θ(n^(2)logn) Θ(n^2) Θ(2^n).
¿Cuál es la complejidad temporal de la siguiente función recursiva?(desperdicio) Θ(n^(3)logn) Θ(n^3) Θ(3^n).
En función del parámetro n, ¿cuál es la complejidad temporal de la siguiente función? Θ(n^2) Θ(n) Θ(nlog(n)).
¿Cuál de las siguientes expresiones se corresponde mejor con el cálculo de la complejidad temporal asintótica en el caso peor del algoritmo que construye un Heap mínimo a partir de un vector (array) de números? a b Ninguna de las otras.
En cuanto a la complejidad temporal asintótica de estas dos funciones, ¿cuál de las siguientes afirmaciones es correcta? La segunda es más eficiente que la primera. Ambas son equivalentes en cuanto a eficiencia La primera es más eficiente que la segunda.
.
Sea T(n)=n+T(n−1) para n>1 y T(1)=1. Una de las afirmaciones siguientes es cierta.
Cuál? T(n)∈O(nlogn) T(n)∈O(n) T(n)∈O(n^3).
Sea la recurrencia:
dónde g(n) es una función polinómica. De las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien dos son falsas y una es cierta. Marca la opción que en este sentido es diferente a las demás.
27.5. La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica: Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal en el
caso mejor del algoritmo de ordenación Quicksort. Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal en el
caso peor del algoritmo de ordenación Quicksort. Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal en el
caso mejor del algoritmo de ordenación Mergesort Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal en el
caso mejor del algoritmo de ordenación Mergesort.
Sea la recurrencia:
dónde g(n) es una función polinómica. De las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien dos son falsas y una es cierta. Marca la opción que en este sentido es diferente a las demás. Si g(n)∈O(n) la relación de recurrencia representa la complejidad temporal del
algoritmo de ordenación Mergesort Si g(n)∈O(1)la relación de recurrencia representa el número de llamadas recursivas
que hace el algoritmo de ordenación Mergesort Si g(n)∈O(n^2) la relación de recurrencia representa la complejidad temporal del
algoritmo de búsqueda por inserción.
Sea la recurrencia:
donde g(n) es una función polinómica. De las siguientes afirmaciones, o bien dos son ciertas y una es falsa, o bien dos son falsas y una es cierta. Marca la opción que en este sentido es diferente a las demás Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del
algoritmo que inserta un elemento en un montículo Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal en el
peor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un
vector (estudiado en clase) Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del
algoritmo de ordenación por inserción binaria.
Sea la recurrencia:
Indica cuál de las siguientes afirmaciones es cierta: T(n) ∈ O(2^n ) T(n) ∈ O(sqrt(2)^n) Las otras dos opciones son ambas ciertas.
En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función? Θ(n) Θ(n2) Θ(nlog(n)).
¿Cuál es la complejidad temporal de la siguiente función? Θ(n^2) Ω(n) y O(n^2) Ω(1) y O(n^2).
Si limn→∞(f(n)/n2)=0 limn→∞(f(n)/n2)=0, ¿Cuál de estas tres afirmaciones es la única que podría ser cierta? f(n) ∈ Θ(n2) f(n) ∈ Θ(n3) f(n) ∈ Θ(n).
Sea:
Suponiendo n→∞, ¿cuál de las siguientes afirmaciones es cierta? g(n) ∈ Ω(n log n) g(n) ∈ Θ(n \log n) g(n) ∈ O(n).
En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función? Θ(n log(n)) Θ(n2) Θ(n).
Si limn→∞(f(n)/n2) = k y k ≠ 0¿cuál de estas tres afirmaciones es falsa? f(n) ∈ Θ(n^2) f(n) ∈ O(n) f(n) ∈ Θ(n^3).
En función del tamaño del problema al que denotamos ¿Cuál es la complejidad asintótica de la siguiente función? n Ω(1) O(n/2) Ω(1) y O(n2) Θ(n).
El coste temporal de un algoritmo se ajusta a la siguiente ecuación de recurrencia:
¿qué coste temporal asintótico (o complejidad temporal) tendrá el algoritmo? O(2n) O(n!) O(n2).
En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función?
Θ(n) Θ(n^2) Θ(nlog(n)).
En función del parámetro n ¿cuál es la complejidad temporal de la siguiente función? Θ(n) Θ(n^2) Θ(nlog(n)).
Considerad la función siguiente:
Si la talla del problema viene dada por n=f−i+1, ¿cuál es el coste temporal asintótico en el supuesto de que n sea una potencia de 2 ? O(n^2) O(n) O(nlogn).
Si lim n→∞(g(n)/f(n)) resulta ser una constante positiva no nula, cuál de las siguientes expresiones NO puede darse? f(n) ∈ Θ(g(n)) f(n) ∈ Ω(g(n)) y g(n) ∈ Ω(f(n)) g(n) ∉ Θ(f(n)).
Con respecto al tamaño del problema, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n) Ninguna de las otras dos opciones es correcta. Θ(1).
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ O(2^n) f(n) ∈ Θ(2^n) f(n) ∈ Ω(2^n).
Si limn→∞(g(n)/f(n)) resulta ser cero, cuál de las siguientes expresiones puede darse? f(n) ∈ Θ(g(n)) f(n) ∈ Ω(g(n)) y g(n) ∈ Ω(f(n)) Ninguna de las otras dos opciones son ciertas.
Sea el vector v[8] = {8,6,4,5,4,5,2,2}. Indica cuál de las siguientes opciones es cierta. (se asume la notación del lenguaje C/C++ en la que el primer elemento del vector está en la posición 0, es decir, en v[0]). El vector v no es un montículo máximo porque el elemento v[2]=4 debe ser
``hundido'' (desplazado hacia la derecha). El vector v no es un montículo máximo porque el elemento v[3]=5 debe ser ``flotado''
(desplazado hacia la izquierda). El vector v es un montículo máximo.
Tenemos una función recursiva con la siguiente cabecera: double f( const double & ) Con sólo esta información, ¿cuál podría ser una definición adecuada para el almacén? Ninguna de las otras dos opciones son válidas. vector<int> A; vector<double> A;.
En un problema de optimización, si el dominio de las decisiones es un conjunto infinito es probable que a través de programación dinámica se obtenga un algoritmo eficaz que lo solucione. una estrategia voraz puede ser la única alternativa. podremos aplicar el esquema vuelta atrás siempre que se trate de un conjunto infinito numerable.
Sólo una de las tres afirmaciones siguientes es cierta. Cuál? Mientras que el algoritmo de Prim va construyendo un único árbol de recubrimiento seleccionando aristas una a una, el algoritmo de Kruskal va construyendo un bosque que va uniendo añadiendo vértices hasta obtener un único árbol de recubrimiento Los algoritmos de Prim y de Kruskal mantienen en todo momento un único árbol de recubrimiento, que crece añadiendo aristas o vértices. Mientras que el algoritmo de Prim va construyendo un único árbol de recubrimiento seleccionando vértices uno a uno, el algoritmo de Kruskal va construyendo un bosque que va uniendo añadiendo aristas, hasta obtener un único árbol de recubrimiento.
Decid cuál de estas tres es la cota pesimista más ajustada al valor óptimo de la mochila discreta: El valor de una mochila que contiene todos los objetos restantes aunque se pase del peso máximo permitido El valor de la mochila continua correspondiente. El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos.
En un algoritmo de ramificación y poda, si la lista de nodos vivos no está clasificada de forma apropiada …
51.5 En un algoritmo de ramificación y poda, si la lista de nodos vivos no está ordenada de forma apropiada... ... podría ocurrir que se pode el nodo que conduce a la solución óptima ... podría ocurrir que se descarten nodos factibles. ... podría ocurrir que se descarten nodos factibles.
Se pretende resolver el problema del viajante de comercio (travelling salesman problem) mediante Ramificación y poda. ¿Cuál de las siguientes acciones resulta ser mejor cota optimista para aplicarla a los nodos intermedios? Obtener el árbol de recubrimiento de mínimo coste a los vértices aún no visitados Asumir que ya no quedan más vértices por visitar y cerrar el camino desde el último vértice visitado. Completar el recorrido pendiente mediante un algoritmo voraz.
¿Qué ocurre si la cota pesimista de un nodo se corresponde con una solución que no es factible? Que el algoritmo sería incorrecto pues podría descartarse un nodo que conduce a la solución óptima Que el algoritmo sería más lento pues se explorarían más nodos de los necesarios Nada especial, las cotas pesimistas no tienen por qué corresponderse con soluciones factibles.
La solución de programación dinámica iterativa del problema de la mochila discreta ... tiene la restricción de que los pesos tienen que ser enteros positivos ... tiene un coste temporal asintótico exponencial. ... tiene un coste temporal asintótico exponencial.
¿Qué tienen en común el algoritmo que obtiene el k-ésimo elemento más pequeño de un vector (estudiado en clase) y el algoritmo de ordenación Quicksort? La división del problema en subproblemas El número de llamadas recursivas que se hacen. La combinación de las soluciones a los subproblemas.
La versión de Quicksort que utiliza como pivote la mediana del vector… ... no presenta caso mejor y peor para instancias del mismo tamaño ... es la versión con mejor complejidad en el mejor de los casos ... es más eficiente si el vector ya está ordenado.
La versión de Quicksort que utiliza como pivote el primer elemento del vector ...
57.5. La versión de Quicksort que utiliza como pivote el elemento del vector que ocupa la primer posición... ... no presenta caso mejor y peor para instancias del mismo tamaño ... se comporta peor cuando el vector ya está ordenado ... se comporta mejor cuando el vector ya está ordenado.
Se quiere desarrollar un programa que compruebe si es posible que un caballo de ajedrez, mediante una secuencia de sus movimientos permitidos, recorra todas las casillas de un tablero N×N a partir de una determinada casilla dada como entrada y sin repetir ninguna casilla. De entre las estrategias que se citan, ¿cuál sería la eficiente para resolver el problema?
Programación dinámica Vuelta atrás.
Algoritmo voraz.
¿Para cuál de estos problemas de optimización existe una solución voraz?
59.5 ¿Para cuál de estos problemas de optimización se conoce al menos una solución voraz óptima?
59.5.2 ¿Para cuál de estos problemas de optimización se conoce una solución óptima voraz? El problema de la mochila discreta El problema de la asignación de coste mínimo de n tareas a n trabajadores cuando el coste de asignar la tarea i al trabajador j, cij está tabulado en una matriz. El árbol de recubrimiento mínimo para un grafo no dirigido con pesos.
Una agencia transportista tiene que transportar un gran número de cajas de diversos tamaños de una ciudad a otra en un camión. Se pretende minimizar el número de viajes. La forma de cargar el camión es escoger cada vez la caja que más llena el espacio que queda disponible. ¿Qué tipo de estrategia se está utilizando? Una estrategia voraz que no garantiza la solución óptima Una estrategia voraz que garantiza la solución óptima. Una estrategia divide y vencerás.
Con respecto a la complejidad espacial de los algoritmos de ordenación Quicksort, Heapsort y Mergesort: Mergesort y Heapsort tienen complejidad espacial lineal con el tamaño del vector a ordenar, la de Quicksort es constante. Las complejidad espacial de todos ellos es lineal con el tamaño del vector a ordenar. Mergesort tiene complejidad espacial lineal con el tamaño del vector a ordenar, la de los otros dos es constante.
Para uno de estos tres problemas no se conoce una solución trivial y eficiente que siga el esquema voraz. Si g(n)∈O(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort. Si g(n)∈O(1) la relación de recurrencia representa el número de llamadas recursivas que hace el algoritmo de ordenación Mergesort. Si g(n)∈O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda por inserción.
Por qué muchos algoritmos voraces presentan complejidades temporales en O(nlogn)? Porque primero ordenan de alguna manera los elementos y porque una vez ordenados la complejidad temporal del proceso de selección de los elementos que se incorporarán a la solución está en O(nlogn). Porque primero ordenan de alguna manera los elementos y porque una vez ordenados la complejidad temporal del proceso de selección de los elementos que se incorporarán a la solución es estrictamente inferior a O(nlogn). Porque el proceso de selección de los elementos que se incorporarán a la solución es siempre O(nlogn). .
Dado un vector de tamaño n de 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) O(logn) O(1).
Un problema de tamaño n puede transformarse en tiempo O(n^2) en otro de tamaño n-1. Por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante. ¿cuál de estas clases de coste temporal asintótico es la más ajustada? O(2^n) O(n^2) O(n^3).
Uno de estos tres problemas no tiene una solución trivial y eficiente que siga el esquema voraz El problema de la mochila discreta sin limitación en la carga máxima de la mochila. El problema de la mochila continua. El problema del cambio sin restricciones en cuanto al número de monedas disponibles de cada clase.
El valor que se obtiene con el método voraz para el problema de la mochila discreta es... ... una cota superior para el valor óptimo.
... una cota inferior para el valor óptimo, pero que nunca coincide con este.
... una cota inferior para el valor óptimo que a veces puede ser igual a este.
Qué diferencia (entre otras) hay entre el algoritmo de Prim y el de Kruskal? El algoritmo de Prim es voraz y el de Kruskal no.
El subgrafo que paso a paso va generando el algoritmo de Prim siempre contiene una única componente conexa mientras que el de Kruskal no tiene por qué Aún siendo el grafo de partida totalmente conexo, el algoritmo de Kruskal garantiza la solución óptima mientras que el de Prim sólo garantiza un subóptimo.
Se dispone de n números enteros almacenados en una estructura de datos que no es un vector (una lista, un conjunto, ...). Se pretende rellenar un vector con esos números de manera que conformen un montículo de mínimos. ¿Cuál sería la complejidad temporal más ajustada de realizar el proceso? O(n logn) O(n) O(n^2 logn).
¿Cuál de estas afirmaciones es falsa? Todos los problemas de optimización tienen una solución voraz que es óptima sea cual sea la instancia a resolver. Hay problemas de optimización en los cuales el método voraz sólo obtiene la solución óptima para algunas instancias y un subóptimo para muchas otras instancias. Hay problemas de optimización para los cuales se puede obtener siempre la solución óptima utilizando una estrategia voraz.
¿Qué esquema algorítmico utiliza el algoritmo de ordenación Quicksort? Divide y Vencerás Programación Dinámica. Backtracking.
Ante un problema que presenta una solución recursiva siempre podemos aplicar: Divide y vencerás. Programación Dinámica Cualquiera de las dos anteriores.
En cuál de los siguientes casos no se puede aplicar el esquema Divide y Vencerás: Cuando los subproblemas son de tamaños muy diferentes. Cuando el problema no cumple el principio de optimalidad. Se puede aplicar en ambos casos.
Dado el algoritmo de búsqueda binaria, supongamos que, en vez de dividir la lista de elementos en dos mitades del mismo tamaño, la dividamos en dos partes de tamaños 1/3 y 2/3. El coste de este algoritmo: Es el mismo que el original. Es mayor que el del original. Es menor que el del original.
Si n es el número de elementos del vector, el coste del algoritmo Mergesort es: O( n^2 ) y Ω( n log(n) ). Θ( n log(n) ). Θ( n^2 ).
Un problema se puede resolver por Divide y Vencerás siempre que: Cumpla el principio de optimalidad Cumpla el teorema de reducción. Ninguna de las anteriores.
La serie de números de Fibonacci se define de la siguiente forma:
Para implementar esta función podemos emplear... Divide y vencerás. Programación dinámica. Cualquiera de las dos anteriores.
La serie de números de Fibonacci se define de la siguiente forma:
¿Qué implementación de entre las siguientes supone el menor coste? Divide y vencerás. Programación dinámica. Ambas tienen el mismo coste asintótico.
El problema de la mochila, ¿Puede solucionarse de forma óptima empleando la estrategia de divide y vencerás? Sólo para el caso de la mochila con fraccionamiento. Sólo para el caso de la mochila sin fraccionamiento Sí, se puede aplicar para ambos casos.
Para que un problema de optimización se pueda resolver mediante programación dinámica es necesario que: Cumpla el principio de optimalidad. Cumpla el teorema de reducción. Cumpla las dos anteriores.
Dada una solución recursiva a un problema, ¿Cómo podemos evitar la resolución de los mismos subproblemas muchas veces? Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas pequeños Resolver los subproblemas de menor a mayor y guardar su resultado en una tabla, inicializándola con los problemas pequeños Resolver los subproblemas de mayor a menor y guardar su resultado en una tabla, inicializándola con los problemas más grandes.
Si aplicamos programación dinámica a un problema que también tiene solución por divide y vencerás podemos asegurar que… El coste temporal se reduce y el espacial aumenta con respecto a la solución por DyV El coste temporal aumenta y el espacial se reduce con respecto a la solución por DyV Ninguna de las anteriores.
Cuándo utilizaremos Programación Dinámica en lugar de Divide y Vencerás? Cuando se incrementa la eficacia. Cuando se incrementa la eficiencia. Cuando se reduce el coste espacial.
En programación dinámica, dónde almacenaremos los valores de los problemas resueltos? En un vector unidimensional. En un vector bidimensional Depende del problema.
Supongamos el problema de la mochila resuelto mediante Programación Dinámica y particularizado para n elementos y un peso máximo trasportable de P. ¿Es necesario calcular valores para toda la matriz auxiliar para obtener el resultado? Si No Depende de los valores de n y P.
Un problema de optimización cuya solución se puede expresar mediante una secuencia de decisiones cumple el principio de optimalidad si, dada una secuencia óptima: Existe una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado Existe al menos una subsecuencia de esa solución que corresponde a la solución óptima de su subproblema asociado Cualquier subsecuencia de esa solución corresponde a la solución óptima de su subproblema asociado.
La programación dinámica, para resolver un problema, aplica la estrategia… Se resuelven los problemas más pequeños y, combinando las soluciones, se obtienen las soluciones de problemas sucesivamente más grandes hasta llegar al problema original Se descompone el problema a resolver en subproblemas más pequeños, que se resuelven independientemente para finalmente combinar las soluciones de los subproblemas para obtener la solución del problema original. Ninguna de las anteriores.
¿Qué esquema de programación es el adecuado para resolver el problema k-ésimo mínimo en un vector? Programación Dinámica. Divide y Vencerás Ninguno de los dos.
Si n es el número de elementos de un vector. La solución de menor coste al problema de encontrar su k-ésimo mínimo tiene la siguiente complejidad: Ω(n) y O( n log(n) ) Ω(n) y O( n^2 ). Ninguna de las dos.
Si n es el número de elementos de un vector. Podemos encontrar una solución al problema de encontrar su k-ésimo que esté acotada superiormente por: O( n^3 ). O(n). Ninguna de las anteriores.
Dada la solución recursiva al problema de encontrar el k-ésimo mínimo de un vector. Cada llamada recursiva, ¿cuántas nuevas llamadas recursivas genera? una o ninguna. dos o ninguna. una o dos.
.
La solución al problema de encontrar el k-ésimo mínimo de un vector pone en
práctica la siguiente estrategia: Ordenar totalmente el vector Ordena parcialmente el vector No ordena ningún elemento del vector.
¿Qué esquema de programación es el adecuado para resolver el problema de la búsqueda binaria? Programación Dinámica Divide y Vencerás Ninguno de los dos.
Si n es el número de elementos de un vector. La solución de menor coste al problema de la búsqueda binaria tiene la siguiente complejidad Ω( log(n) ) y O( n log(n) ). Θ( n log(n) ) Ω(1) y O( log(n) ).
¿Con qué esquema de programación obtenemos algoritmos que calculan la distancia de edición entre dos cadenas? Programación Dinámica. Divide y Vencerás. Ambos.
Disponemos de dos cadenas de longitudes m y n. Si resolvemos el problema de la distancia de edición mediante programación dinámica, ¿De qué tamaño debemos definir la matriz que necesitaremos? (m-1) x (n-1). m x n. (m+1) x (n+1).
¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz óptima?
97.5 ¿Cuál de estos tres problemas de optimización no tiene, o no se le conoce, una solución voraz (greedy) que es óptima? El árbol de cobertura de coste mínimo de un grafo conexo El problema de la mochila discreta o sin fraccionamiento El problema de la mochila continua o con fraccionamiento.
Los algoritmos de programación dinámica hacen uso... ... de que la solución óptima se puede construir añadiendo a la solución el elemento óptimo de los elementos restantes, uno a uno ... de que se puede ahorrar cálculos guardando resultados anteriores en un almacén ... de una estrategia trivial consistente en examinar todas las soluciones posibles.
De los problemas siguientes, indicad cuál 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 mínimo de monedas posibles. El problema de la mochila sin fraccionamiento y sin restricciones en cuanto al dominio de los pesos de los objetos y de sus valores El problema de cortar un tubo de forma que se obtenga el máximo beneficio posible.
Supongamos que un informático quiere subir a una montaña y como no es una persona normal decide que tras cada paso, el siguiente debe tomarlo en la dirección de máxima pendiente hacia arriba. Además, entenderá que ha alcanzado la cima cuando llegue a un punto en el que no haya ninguna dirección que sea cuesta arriba.
¿Qué tipo de algoritmo está usando nuestro informático? Un algoritmo voraz Un algoritmo divide y vencerás.
Un algoritmo de programación dinámica.
.
La mejora que en general aporta la programación dinámica frente a la solución ingenua se consigue gracias al hecho de que... ... en la solución ingenua se resuelve pocas veces un número relativamente grande de subproblemas distintos. ... en la solución ingenua se resuelve muchas veces un número relativamente pequeño de subproblemas distintos. El número de veces que se resuelven los subproblemas no tiene nada que ver con la eficiencia de los problemas resueltos mediante programación dinámica.
En la solución al problema de la mochila continua ¿por qué es conveniente la
ordenación previa de los objetos? Para reducir la complejidad temporal en la toma de cada decisión: de O(n) a O(1),
donde n es el número de objetos a considerar. Porque si no se hace no es posible garantizar que la toma de decisiones siga un
criterio voraz Para reducir la complejidad temporal en la toma de cada decisión: de O( n^2) a O (n
log(n) ), donde n es el número de objetos a considerar.
Dada la suma de la recurrencia:
¿cuál de las siguientes afirmaciones es cierta? T(n) ∈ Θ(n^2) T(n) ∈ Θ(n!). T(n) ∈ Θ(2^n).
Cuando la descomposición recursiva de un problema da lugar a subproblemas de tamaño similar, ¿qué esquema promete ser más apropiado? El método voraz. Divide y vencerás, siempre que se garantice que los subproblemas no son del mismo tamaño Programación dinámica.
En el método voraz... ... siempre se encuentra solución pero puede que no sea óptima ... es habitual preparar los datos para disminuir el coste temporal de la función que determina cuál es la siguiente decisión a tomar ... el dominio de las decisiones sólo pueden ser conjuntos discretos o discretizables.
¿Cómo se vería afectada la solución voraz al problema de la asignación de tareas en el caso de que se incorporaran restricciones que contemplen que ciertas tareas no pueden ser adjudicadas a ciertos trabajadores?
106.5. ¿Cómo se vería afectada la solución voraz al problema de la asignación de tareas en el caso de que incorporaran restricciones que contemplen que ciertas tareas no pueden ser adjudicadas a ciertos trabajadores? Ya no se garantizaría la solución óptima pero sí una factible Habría que replantearse el criterio de selección para comenzar por aquellos trabajadores con más restricciones en cuanto a las tareas que no pueden realizar para asegurar, al menos, una solución factible La solución factible ya no estaría garantizada, es decir, pudiera ser que el algoritmo no llegue a solución alguna.
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
¿Cuál es la mejor estructura para el almacén? int A. int A[]. int A [] [].
Se pretende implementar mediante programación dinámica iterativa la función recursiva: int A[]. int A. int A[] [].
¿Cuál de estas estrategias para calcular el n-ésimo elemento de la serie de Fibonacci (f(n) = f(n-1) + f(n-2) , f(1) = f(2) = 1) es más eficiente? La estrategia voraz Programación Dinámica. Las dos estrategias citadas serían similares en cuanto a eficiencia.
Supongamos que una solución recursiva a un problema de optimización muestra estas dos características: por un lado, se basa en obtener soluciones óptimas a problemas parciales más pequeños, y por otro, estos subproblemas se resuelven más de una vez durante un proceso recursivo. Este problema es candidato a tener una solución alternativa basada en...
110.5 La solución recursiva ingenua a un determinado problema de optimización muestra estas dos características: por un lado, se basa en obtener soluciones optimas a problemas parciales más pequeños, y por otro, estos subproblemas se resuelven más de una vez durante el proceso recursivo. Este problema es candidato a tener una solución alternativa basada en… Un algoritmo voraz. Un algoritmo de programación dinámica. Un algoritmo de estilo Divide y Vencerás.
El problema de encontrar un árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado...
111.5 El problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado… Sólo se puede resolver con una estrategia voraz si existe una arista para cualquier
par de vértices del grafo no se puede resolver en general con una estrategia voraz se puede resolver siempre con una estrategia voraz.
Si ante un problema de decisión existe un criterio de selección voraz entonces... al menos una solución factible está garantizada la solución óptima está garantizada. ninguna de las otras dos opciones es cierta.
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
¿Cuál es la mejor complejidad espacial que se puede conseguir? O(x). O(y). O(xy).
¿Cuál de estas tres estrategias voraces obtiene un mejor valor para la mochila discreta? Meter primero los elementos de menor peso Meter primero los elementos de mayor valor específico o valor por unidad de peso Meter primero los elementos de mayor valor.
La eficiencia de los algoritmos voraces se basa en el hecho de que... antes de tomar una decisión se comprueba si satisface las restricciones del problema. con antelación, las posibles decisiones se ordenan de mejor a peor las decisiones tomadas nunca se reconsideran.
Un tubo de n centímetros de largo se puede cortar en segmentos de 1 centímetro, 2 centímetros, etc... Existe una lista de los precios a los que se venden los segmentos de cada longitud. Una de las maneras de cortar el tubo es la que más ingresos nos producirá. Di cuál de estas tres afirmaciones es FALSA. Hace una evaluación exhaustiva "de fuerza bruta" de todas las posibles maneras de cortar el tubo consume un tiempo Θ(2^n). Es posible evitar hacer la evaluación exhaustiva "de fuerza bruta" guardando, para cada posible longitud j < n el precio más elevado posible que se puede obtener dividiendo el tubo correspondiente. Hacer una evaluación exhaustiva "de fuerza bruta" de todas las posibles maneras de cortar el tubo consume un tiempo Θ(n!).
Se pretende implementar mediante programación dinámica iterativa la función recursiva: ¿Cuál es la mejor complejidad espacial que se puede conseguir? O(x^2) O(1) O(x).
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
¿Cuál es la mejor complejidad espacial que se puede conseguir? O(y^2) O(1) O(y) O(x^2).
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
¿Cuál es la mejor complejidad temporal que se puede conseguir? O(y) O(x*y) O(x).
Se pretende implementar mediante programación dinámica iterativa la función recursiva:
¿Cuál es la mejor complejidad espacial que se puede conseguir? O(x^2). O(x) O(1).
La programación dinámica... En algunos casos se puede utilizar para resolver problemas de optimización con dominios continuos pero probablemente pierda su eficacia ya que puede disminuir drásticamente el número de subproblemas repetidos Las otras dos opciones son ciertas. Normalmente se usa para resolver problemas de optimización con dominios discretizables puesto que las tablas se han de indexar con este tipo de valores.
Dado un problema de optimización, el método voraz... siempre obtiene una solución factible siempre obtiene la solución óptima. garantiza la solución óptima sólo para determinados problemas.
Un algoritmo recursivo basado en el esquema divide y vencerás... Las demás opciones son verdaderas. ... será más eficiente cuanto más equitativa sea la división en subproblemas. ... nunca tendrá una complejidad exponencial.
Sea f(n) la solución de la relación de recurrencia f(n) = f(n/2) + 1; f(1) = 1. Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( n ). f(n) ∈ Θ( n log(n) ). f(n) ∈ Θ( log(n) ).
Sea f(n) la solución de la relación de recurrencia f(n) = 2*f(n/2) + n; f(1) = 1.
Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( n^2 ) f(n) ∈ Θ( n log(n) ) f(n) ∈ Θ( n ).
Sea f(n) la solución de la relación de recurrencia…
f(n) = 2f(n-1) + 1; f(1) = 1
Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ( 2^n ). f(n) ∈ Θ( n^2 ). f(n) ∈ Θ( n ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera. Marca la que (en este sentido) es distinta a las otras dos. O( n^2 ) ⊂ O( 2^(log2(n)) ) ⊂ O( 2^n ). O( n^2 ) ⊂ O( 2^(log2(n)) ) ⊆ O( 2^n ). O( 2^(log2(n)) ) ⊂ O( n^2 ) ⊂ O( 2^n ).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera. Marca la que (en este sentido) es distinta a las otras dos. Θ(log^2(n)) = Θ(log(n^2)). Θ(log^2(n)) = Θ(log(n)) Θ(log(n)) = Θ(log(n^2)).
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera. Marca la que (en este sentido) es distinta a las otras dos. Ω( n^3) ⊂ Ω( n^2 ) Θ( n^2 ) ⊂ Θ( n^3 ). O( n^2 ) ⊂ O( n^3 ). Ω( n^2) ⊂ Ω( n^3 ).
Para la complejidad de un algoritmo presente caso mejor y peor distintos... ... es condición necesaria que existan instancias distintas del problema con el mismo tamaño ... es condición suficiente que existan instancias distintas del problema con el mismo tamaño ... es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño. .
Se dispone de un vector de tamaño n cuyos elementos están de antemano organizados formando un montículo (heap).¿Cuál sería la complejidad temporal de reorganizar el vector para que quede ordenado? O( n ). O( log(n) ). O(n log(n) ).
Indica cuál es la complejidad, en función de n, del fragmento siguiente: O( n log(n) ). O( n ) O( n^2 ).
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ Θ( n ). f(n) ∈ Θ( n^2 log(n) ) f(n) ∈ Θ( n^2 ).
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ Θ( n^3 ) f(n) ∈ Θ( n ) f(n) ∈ Θ( n log(n)).
Dado el siguiente fragmento de código...
for(i=0; i < n; i++) for(int j = 1; j < i; j+=2) s+=i*j;
Indica cuál de las siguientes expresiones es la que mejor refleja su complejidad temporal. ∑ log(j) Ninguna de las otras dos opciones son correctas ∑ log(i).
Un vector de enteros de tamaño n tiene sus elementos estructurados en forma de montículo (heap). ¿Cuál es la complejidad temporal en el mejor de los casos de borrar el primer elemento del vector y reorganizarlo posteriormente para que siga manteniendo la estructura de montículo? Ninguna de las otras dos opciones es correcta Constante con el tamaño del vector O(n).
Un problema de tamaño n puede transformarse en tiempo O(n) en siete de tamaño n/7; por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante. ¿Cuál de estas clases de coste temporal asintótico es la más ajustada? O( n log(n) ). O( n^2 ) O( n ).
Un problema de tamaño n puede transformarse en tiempo O(n^3) en ocho de tamaño n/2; por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante. ¿Cuál de estas clases de coste temporal asintótico es la más ajustada? O( n^2 log(n) ). O( n^3 ) O( n^3 log(n) ).
Indica cuál es la complejidad en función de n del fragmento siguiente: O( n^2 ) O( n ) O( n log(n) ).
Un programa con dos bucles anidados uno dentro del otro. El primero hace n iteraciones aproximadamente y el segundo la mitad, tarda un tiempo… O( n^2 ). O( n log(n) ). O( n√n).
Di cuál de estos resultados de coste temporal asintótico es falsa: La ordenación de un vector usando el algoritmo Mergesort requiere en el peor caso un tiempo en Ω( n^2 ). La ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en Ω( n^2 ). La búsqueda binaria en un vector ordenado requiere en el peor caso un tiempo en O( log(n) ).
¿Cuál de los siguientes pares de problemas son equivalentes en cuanto al tipo de solución (óptima, factible, etc.) aportada por el método voraz? El fontanero diligente y la mochila continua El fontanero diligente y el problema del cambio El fontanero diligente y la asignación de tareas.
La solución óptima al problema de encontrar el árbol de recubrimiento de coste mínimo para un grafo no dirigido, conexo y ponderado… Puede construirlo tanto vértice a vértice como arista a arista Debe construirlo vértice a vértice: arista a arista no puede ser Debe construirlo arista a arista: vértice a vértice no puede ser.
¿Qué mecanismo se usa para acelerar el algoritmo de Prim? El TAD "Union-find" Mantener una lista de los arcos ordenador según su peso. Mantener para cada vértice su "padre" más cercano.
Se pretende aplicar la técnica memoización a la siguiente función recursiva: En el caso más desfavorable, ¿qué complejidades temporal y espacial cabe esperar de la función resultante? O(y - x), tanto temporal como espacial Temporal O(x*y) y espacial O(x) Ninguna de las otras dos opciones es correcta.
Cuando se calculan los coeficientes binomiales usando la recursión, que problema se da y cómo se puede resolver? La recursión puede ser infinita y por tanto es necesario organizarla según el esquema iterativo de programación dinámica. Se repiten muchos cálculos y ello se puede evitar usando programación dinámica. Se repiten muchos cálculos y ello se puede evitar haciendo uso de una estrategia voraz.
¿Por qué se utiliza el TAD "Union-find" en el algoritmo de Kruskal? Para comprobar si un arco forma ciclos. Para comprobar si un vértice ya ha sido visitado Para comprobar si dos vértices son equivalentes.
¿Cuál de estas estrategias voraces obtiene siempre un mejor valor para la mochila discreta? meter primero los elementos de mayor valor específico o valor por unidad de peso. meter primero los elementos de mayor valor. ninguna de las otras dos opciones es cierta.
Se pretende implementar mediante programación dinámica iterativa la función
recursiva:
¿Cuál es la mejor complejidad temporal que se puede conseguir? O(y). O(x) O(x*y).
Se pretende implementar mediante programación dinámica iterativa la función
recursiva:
¿Cuál es la mejor complejidad temporal que se puede conseguir? O(x^2) O(x) O(x*y).
El método voraz se emplea en la resolución de problemas de selección y optimización en los que se pretende encontrar: Una solución que satisfaga unas restricciones y optimice una cierta función objetivo Todas las soluciones que satisfagan unas restricciones La dos respuestas anteriores son correcta.
Voraz siempre da solución óptima: Al problema de la mochila sin fraccionamiento. Al problema de la mochila con fraccionamiento. A los dos.
En el método Voraz, aunque las decisiones son irreversibles, podemos asegurar que: Siempre obtendremos la solución óptima. Siempre obtendremos una solución factible Sólo obtendremos la solución óptima para algunos problemas.
Dado un problema de optimización y un algoritmo Voraz que lo soluciona,
¿Cuándo podemos estar seguros de que la solución obtenida será óptima? Cuando demostremos formalmente que el criterio conduce a una solución óptima
para cualquier instancia del problema Voraz siempre encuentra solución óptima En ambos casos. Las dos son correctas.
Si aplicamos un algoritmo voraz que no nos garantiza la solución óptima sobre un problema entonces... Obtendremos una solución factible. Puede que no encuentre ninguna solución aunque ésta exista. Si el problema tiene solución óptima, el esquema voraz nos garantiza que la encuentra.
El problema de la mochila, ¿encuentra su solución óptima empleando la estrategia voraz?: Sólo para el caso de la mochila con fraccionamiento. Sólo para el caso de la mochila sin fraccionamiento. En cualquiera de los casos anteriores.
Dado un grafo G que representa las poblaciones de la provincia de Alicante de más de 20.000 habitantes junto con todas las carreteras de conexión entre ellas. Queremos obtener el recorrido que nos permita pasar por todas estas ciudades una única vez y volver al punto de origen recorriendo el mínimo número de kilómetros. Si aplicamos una estrategia voraz sobre este grafo obtendremos… Una solución factible. La solución óptima Puede que no encuentre ninguna solución aunque ésta exista.
Al aplicar backtracking obtenemos la solución óptima a un problema: Siempre En algunos casos. Sólo cuando el problema cumple el principio de Optimalidad.
Si aplicamos un esquema backtracking que no nos garantiza la solución óptima sobre un problema entonces Obtendremos una solución factible Puede que no encuentre ninguna solución aunque ésta exista Ninguna de las anteriores.
Backtracking es aplicable a problemas de selección y optimización en los que:
160.5 La estrategia de vuelta atrás es aplicable a problemas de selección y optimización en los que El espacio de soluciones es un conjunto infinito.
El espacio de soluciones es un conjunto finito. En cualquiera de los casos. El espacio de soluciones puede ser tanto finito como infinito pero en este último caso
debe ser al menos numerable.
En un problema resuelto por backtracking, el conjunto de valores que pueden tomar las componentes de la tupla solución, ha de ser: Infinito. finito. continuo.
Al aplicar vuelta atrás a la solución de problemas, obtenemos algoritmos con costes computacionales: Polinómicos. Exponenciales Los dos son correctos. Depende del problema.
Vuelta atrás se emplea en la resolución de problemas de optimización en los que se pretende encontrar: Una solución que satisfaga unas restricciones y optimice una cierta función objetivo. Todas las soluciones que satisfagan unas restricciones Las dos respuestas anteriores son correctas.
Backtracking procede a obtener la solución a un problema de optimización empleando la siguiente estrategia Genera todas las combinaciones de la solución y selecciona la que optimiza la
función objetivo Genera todas las soluciones factibles y selecciona la que optimiza la función
objetivo. Genera una solución factible empleando un criterio óptimo.
Backtracking es una técnicas de resolución general de problemas basada en: La búsqueda sistemática de soluciones. La construcción directa de la solución Ninguna de las anteriores.
Backtracking genera las soluciones posibles al problema: Mediante el recorrido en profundidad del árbol que representa el espacio de soluciones. Mediante el recorrido en anchura del árbol que representa el espacio de soluciones Ninguna de las anteriores.
El problema de la mochila, ¿puede solucionarse empleando vuelta atrás?: Sólo para el caso de la mochila con fraccionamiento Sólo para el caso de la mochila sin fraccionamiento Se puede aplicar para ambos casos.
El problema del viajante de comercio puede resolverse correctamente empleando estos esquemas de programación: Solo backtracking Empleando cualquiera de estos: Voraz y backtracking Sólo programación dinámica.
El tiempo de ejecución de un algoritmo de ramificación y poda depende de: La instancia del problema La función de selección de nodos para su expansión. De ambos.
Dado un problema resuelto mediante backtracking y mediante ramificación y poda, el coste computacional de la solución por ramificación y poda, en comparación con la de backtracking es: Igual. Mayor Menor.
¿Cuál de estas afirmaciones es falsa? Backtracking inspecciona todo el espacio de soluciones de un problema mientras que Ramificación y poda no. La complejidad en el peor caso de las soluciones Backtracking y ramificación y poda a un mismo problema es la misma Para un mismo problema, ramificación y poda explora siempre un número de nodos menor o igual que backtracking.
El problema de la asignación de turnos tiene solución óptima voraz aplicando la siguiente estrategia: Seleccionamos los alumnos en orden descendente de preferencia respetando las restricciones de cabida de cada turno Seleccionamos los alumnos en orden ascendente de preferencia respetando las restricciones de cabida de cada turno. El problema no tiene solución óptima voraz.
El problema de la asignación de turnos tiene solución óptima empleando: Backtracking. Voraz. Ambos.
El problema de la asignación de turnos tiene solución… Óptima mediante backtracking Aproximada (sub-óptima) mediante voraz Ambas.
Dada la solución recursiva mediante vuelta atrás al problema de la asignación de turnos ¿cuántas nuevas llamadas recursivas genera cada llamada recursiva? una o dos una o ninguna ninguna de las anteriores.
El problema de la asignación de turnos resuelto mediante backtracking tiene una
complejidad: Exponencial. Polinómica. Ninguna de la dos.
Cuando se resuelve un algoritmo de vuelta atrás un problema de n decisiones, en el que siempre hay como mínimo dos opciones para cada decisión, ¿cuál de las siguientes complejidades en el caso peor es la mejor que nos podemos encontrar? O(2^n) O(n!). O(n^2).
Al resolver el problema del viajante de comercio mediante vuelta atrás y asumiendo un grafo de n vértices totalmente conexo, ¿cuál de estas es una buena cota pesimista al iniciar la búsqueda? Se multiplica n por la distancia de la arista más corta que nos queda por considerar Se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las n aristas más cortas Se resuelve el problema usando un algoritmo voraz que añade cada vez al camino el vértice más cercano al último añadido.
Se desea obtener todas las permutaciones de una lista compuesta por n elementos, ¿Qué esquema es el más adecuado? Ramificación y poda, puesto que con buenas funciones de cota es más eficiente para este problema que vuelta atrás. Divide y vencerás, puesto que la división en sublistas se podría hacer en tiempo constante Vuelta atrás, para este problema no hay un esquema más eficiente.
La complejidad en el mejor de los casos de un algoritmo de ramificación y poda... es siempre exponencial con el número de decisiones a tomar. suele ser polinómica con el número de alternativas por cada decisión puede ser polinómica con el número de decisiones a tomar.
La complejidad en el peor de los casos de un algoritmo de ramificación y poda… Puede ser exponencial con el número de alternativas por cada decisión Puede ser polinómica con el número de decisiones a tomar Es exponencial con el número de decisiones a tomar.
La estrategia de ramificación y poda genera las soluciones posibles al problema mediante… un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones. un recorrido en profundidad del árbol que representa el espacio de soluciones. un recorrido en anchura que representa el espacio de soluciones.
¿Para qué sirven las cotas pesimistas en ramificación y poda? Para tener la certeza de que la cota optimista está bien calculada Para descartar nodos basándose en la preferencia por algún otro nodo ya completado Para descartar nodos basándose en el beneficio esperado.
En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es mayor que el valor de una cota optimista? (entendiendo que ambas cotas se aplican sobre el mismo nodo) En general sí, si se trata de un problema de maximización, aunque en ocasiones ambos valores pueden coincidir. En general sí, si se trata de un problema de minimización, aunque en ocasiones ambos valores pueden coincidir. No, nunca es así.
En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es
menor que el valor de una cota optimista? En general sí, si se trata de un problema de minimización, aunque en ocasiones ambos valores pueden coincidir. En general sí, si se trata de un problema de maximización, aunque en ocasiones ambos valores pueden coincidir Sí, siempre es así.
En los algoritmos de ramificación y poda… El uso de cotas pesimistas sólo resulta eficaz cuando se dispone de una posible solución de partida. Una cota optimista es necesariamente un valor insuperable, de no ser así se podría podar el nodo que conduce a la solución óptima Una cota optimista es necesariamente un valor alcanzable, de no ser así no está garantizado que se encuentre la solución óptima Una cota pesimista es el valor que a lo sumo alcanza cualquier nodo factible que no es el óptimo.
La ventaja de la estrategia ramificación y poda frente a vuelta atrás es que la primera genera las soluciones posibles al problema mediante... un recorrido guiado por una cola de prioridad de donde se extraen primero los nodos que representan los subárboles más prometedores del espacio de soluciones las otras dos opciones son verdaderas. un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones.
¿Cuál es la diferencia principal entre una solución de vuelta atrás y una solución de ramificación y poda para el problema de la mochila? El orden de exploración de las soluciones. El coste asintótico en el caso peor El hecho que la solución de ramificación y poda puede empezar con una solución subóptima voraz y la de vuelta atrás no.
Tratándose de un problema de optimización, en la lista de nodos vivos de ramificación y poda... sólo se introducen nodos prometedores, es decir, nodos que pueden mejorar la mejor solución que se tiene en ese momento. puede haber nodos que no son prometedores. las otras dos opciones son ciertas.
Cuando resolvemos un problema mediante un esquema de ramificación y poda... los valores entre los cuales se elige en cada una de las decisiones tienen que formar un conjunto finito las decisiones sólo pueden ser binarias los valores entre los cuales se elige en cada una de las decisiones pueden formar un conjunto infinito.
La estrategia de ramificación y poda necesita cotas pesimistas... para decidir el orden de visita de los nodos del árbol de soluciones. sólo si se usa para resolver problemas de optimización. para determinar si una solución es factible.
El uso de funciones de cota en ramificación y poda... transforma en polinómicas complejidades que antes eran exponenciales. puede reducir el número de instancias del problema que pertenecen al caso peor. garantiza que el algoritmo va a ser más eficiente ante cualquier instancia del problema.
En la estrategia de ramificación y poda… cada nodo tiene su propia cota pesimista y también su propia cota optimista. cada nodo tiene su propia cota pesimista, la cota optimista sin embargo, es común para todos los nodos cada nodo tiene su propia cota optimista, la cota pesimista sin embargo, es común para todos los nodos.
Si para resolver un mismo problema usamos un algoritmo de vuelta atrás y lo modificamos mínimamente para convertirlo en un algoritmo de ramificación y poda, ¿qué cambiamos realmente? La comprobación de las soluciones factibles: en ramificación y poda no es necesario puesto que sólo genera nodos factibles. Cambiamos la función que damos a la cota pesimista Aprovechamos mejor las cotas optimistas.
Si para resolver un mismo problema usamos un algoritmo de ramificación y poda y lo modificamos mínimamente para convertirlo en un algoritmo de vuelta atrás, ¿qué cambiamos realmente? cambiamos la función que damos a la cota pesimista. provocamos que las cotas optimistas pierdan eficacia sería necesario comprobar si las soluciones son factibles o no puesto que ramificación y poda solo genera nodos factibles.
En el esquema de vuelta atrás, los mecanismos de poda basados en la mejor solución hasta el momento… Las dos anteriores son verdaderas. garantizan que no se va a explorar nunca todo el espacio de soluciones posibles. pueden eliminar soluciones parciales que son factibles.
En ausencia de cotas optimista y pesimistas, la estrategia de vuelta atrás... no se puede usar para resolver problemas de optimización debe recorrer siempre todo el árbol no recorre todo el árbol si hay manera de descartar subárboles que representan conjuntos de soluciones no factibles.
Decid cuál de estas tres es la cota optimista que poda más eficientemente cuando se usa la estrategia de vuelta atrás para resolver el problema de la mochila: El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico del objeto. El valor de una mochila El valor óptimo de la mochila continua correspondiente.
Decid cuál de estas tres no sirve como cota optimista para obtener el valor óptimo de la mochila discreta: El valor de una mochila que contiene todos los objetos aunque se pase del peso máximo permitido El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos. El valor de la mochila continua correspondiente.
Es un problema de optimización, si el dominio de las decisiones es un conjunto infinito. Podemos aplicar el esquema vuelta atrás siempre que se trate de un conjunto infinito numerable. Es probable que a través de programación dinámica se obtenga un algoritmo eficaz que lo soluciones. Una estrategia voraz puede ser la única alternativa.
Dado un problema de optimización cualquiera, ¿la estrategia de vuelta atrás garantiza la solución óptima? Es condición necesaria que el dominio de las decisiones sea discreto o discretizable y que el número de decisiones a tomar esté acotado Sí, puesto que ese método analiza todas las posibilidades Sí, siempre que el dominio de las decisiones sea discreto o discretizable y además se empleen mecanismos de poda basados en la mejor solución hasta el momento.
Se desea encontrar el camino más 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. Para limitar la búsqueda en un algoritmo de vuelta atrás, se utiliza la solución de un algoritmo voraz basado en moverse en cada paso a la ciudad, de entre las posibles según el mapa de carreteras, que esté más cercana al destino en línea recta. ¿Qué tipo de cota sería? Sería una cota pesimista siempre que se tenga la certeza de que esa aproximación encuentra la solución factible. Ninguna de las otras dos opciones. Sería una cota optimista siempre que se tenga la certeza de que esa aproximación encuentra una solución factible.
Se desea encontrar el camino más 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 también se conocen las coordenadas geográficas de cada ciudad se quiere usar la distancia geográfica (en línea recta) entre cada par de ciudades para como cota para limitar la búsqueda en un algoritmo de vuelta atrás. ¿Qué tipo de cota sería? No se trataría de ninguna poda puesta que es posible que esa heurística no encuentre una solución factible. Una cota pesimista Una cota óptimista.
Se desea encontrar el camino más 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. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia geográfica (en línea recta) entre cada par de ciudades. Se pretende acelerar la búsqueda de un algoritmo de ramificación y poda priorizando los nodos vivos (ciudades) que estén a menor distancia geográfica de la ciudad objetivo.
El nuevo algoritmo solo será más rápido para algunas instancias del problema Esta estrategia no asegura que se obtenga el camino más corto El nuevo algoritmo siempre sea más rápido.
Se desea encontrar el camino más 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. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia geográfica (en línea recta) entre cada par de ciudades. Para limitar la búsqueda en un algoritmo de vuelta atrás, se utiliza la solución de un algoritmo voraz basado en moverse en cada paso a la ciudad, de entre las posibles según el mapa de carreteras, que esté más cercana al destino según su distancia geográfica. Este algoritmo voraz, ¿serviría como cota pesimista? No, ya que no asegura que se encuentre una solución factible. Sí, puesto que la distancia geográfica asegura que otra solución mejor no es posible. No, ya que en algunos casos puede dar distancias menores que la óptima.
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. También se conocen las coordenadas geográficas de cada ciudad y por tanto la distancia geométrica (en línea recta) entre cada par de ciudades. Se pretende acelerar la búsqueda de un algoritmo de ramificación y poda priorizando los nodos vivos (ciudades) que estén a menor distancia geográfica de la ciudad objetivo. El nuevo algoritmo no garantiza que vaya a ser más rápido para todas las instancias del problema posibles. El nuevo algoritmo siempre sera más rápido. Esta estrategia no asegura que se obtenga el camino mas corto.
La solución recursiva ingenua (pero correcta) a un problema de optimización llama más de una vez a la función con los mismos parámetros. 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 parámetros de cada llamada cuando ésta 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 básico.
Si un problema de optimización lo es para una función que toma valores continuos ... La programción dinámica iterativa siempre es mucho más eficiente que la programación dinámica iterativa en cuanto al uso de memoria La programación dinámica recursiva puede resultar mucho más eficiente que la
programación dinámica iterativa en cuanto al uso de memoria El uso de memoria de la programación dinámica iterativa y de la programación dinámica recursiva es el mismo independientemente de si el dominio es discreto o continuo.
Al resolver el problema del viajante de comercio mediante vuelta atrás, ¿cuál de estas cotas optimistas se espera que pode mejor el árbol de búsqueda? Se multiplica k por la distancia de la arista más corta que nos queda por considerar, donde k es el número de saltos que nos quedan por dar. Se resuelve el resto del problema usando un algoritmo voraz que añade cada vez al camino el vértice más cercano al último añadido Se ordenan las aristas restantes de menor a mayor distancia y se calcula la suma de las k aristas más cortas, donde k es el número de saltos que nos quedan por dar.
La complejidad temporal en el mejor de los casos… es el tiempo que tarda el algoritmo en resolver el problema de tamaño o talla más pequeña que se le puede presentar las otras dos opciones son ciertas es una función del tamaño o talla del problema que tiene que estar definida para todos los posibles valores de ésta.
La mejor solución que se conoce para el problema de la mochila continua sigue el esquema ...divide y vencerás ...ramificación y poda ...voraz.
La complejidad en el mejor de los casos de un algoritmo de ramificación y poda.. es siempre exponencial con el número de decisiones a tomar puede ser polinómica con el número de decisiones a tomar suele ser polinómica con el número de alternativas por cada decisión.
Cuando se usa un algoritmo voraz para abordar la resolución de un problema de optimización por selección discreta (es decir, un problema para el cual la solución consiste en encontrar un subconjunto del conjunto de elementos que optimiza una determinada función), ¿cuál de estas tres cosas es imposible que ocurra? Que el algoritmo no encuentre ninguna solución. Que se reconsidere la decisión ya tomada anteriormente respecto a la selección de un elemento anterior respecto a la selección de un elemento a la vista de la decisión que se debe tomar en el instante actual. Que la solución no sea la óptima.
Sea la siguiente relación de recurrencia.
Si T(n) ∈ O(n²), ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n g(n) = n² g(n) = 1 g(n) = nlogn.
Uno de estos tres problemas no tiene una solución eficiente que siga el esquema de programación dinámica El Problema de la mochila discreta El Problema de las torres de Hanoi.
El problema de cortar un tubo de longitud n en segmentos de longitud entera entre 1 y n de manera que se maximice el precio de acuerdo con una tabla que da el precio para cada longitud el valor que se obtiene con el método voraz para el problema de la mochila discreta es… ... una cota inferior para el valor óptimo, pero que nunca coincide con este ... una cota superior para el valor óptimo ... una cota inferior Para el valor óptimo que a veces puede ser igual a este.
El siguiente programa resuelve el problema de cortar un tubo de longitud n en segmentos de longitud entera entre 1 y n de manera que se maximice el precio de acuerdo con una tabla que da el precio para cada longitud, pero falta un trozo. ¿Qué debería ir en lugar de XXXXXXX? p,r-1,n p,r,n-r[n]. p,r,n-i.
Sea A una matriz cuadrada n x n. Se trata de buscar una permutación de las columnas tal que la suma de los elementos de la diagonal de la matriz resultante sea mínima. Indicad cuál de las siguientes afirmaciones es falsa La complejidad temporal de la mejor solución posible al problema es O(n!). Si se construye una solución al problema basada en el esquema de ramificación y poda, una buena elección de cotas optimistas y pesimistas podría evitar la exploración de todas las permutaciones posibles. La complejidad temporal de la mejor solución posible al problema es O(n²).
Cuál de los siguientes algoritmos proveería una cota pesimista para el problema de encontrar el camino más corto entre dos ciudades (se supone que el grafo es conexo) Calcular la distancia geométrica (en línea recta) entre la ciudad origen y destino Para todas las ciudades que son alcanzables en un paso desde la ciudad inicial, sumar la distancia a dicha ciudad y la distancia geometrica hasta la ciudad destino Calcular la distancia recorrida moviéndose al azar por el grafo hasta llegar(por azar) a la ciudad destino.
Dadas las siguientes funciones: Se quiere reducir la complejidad temporal de la función g usando programación dinámica iterativa. ¿cuál sería la complejidad espacial? cúbica cuadrática. exponencial.
En una cuadrícula se quiere dibujar el contorno de un cuadrado de n casillas de lado. ¿cual será la complejidad temporal del mejor algoritmo que pueda existir? O(n²) O(n) O(sqrt(n)).
Cuando se resuelve el problema de la mochila discreta usando la estrategia de vuelta atrás, ¿puede ocurrir que se tarde menos en encontrar la solución óptima si se prueba primero a meter cada objeto antes de no meterlo? Sí, tanto si se usan cotas optimistas para podar el árbol de búsqueda como si no. No, ya que en cualquier caso se deben explorar todas las soluciones factibles Sí, pero sólo si se usan cotas optimistas para podar el árbol de búsqueda.
Garantiza el uso de una estrategia “divide y vencerás" la existencia de una solución de complejidad temporal polinómica a cualquier problema? Sí, en cualquier caso. No, la complejidad temporal puede ser incluso peor que cualquier función polinómica 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ómíca.
En el esquema de vuelta atrás el orden en el que se van asignando los distintos valores a las componentes del vector que contendrá la solución... es irrelevante si no se utilizan mecanismos de poda basados en la mejor solución hasta el momento puede ser relevante si se utilizan mecanismos de poda basados en estimaciones optimistas. Las otras dos opciones son ciertas.
Se quieren ordenar d números distintos comprendidos entre 1 y n. Para ello se usa un array de n booleanos que se inicializan primero a false. A continuación se recorren los d números cambiando los valores del elemento del vector de booleanos correspondiente a su número a true. Por último se recorre el vector de booleanos escribiendo los índices de los elementos del vector de booleanos que son true. ¿Es este algoritmo más rápido (asintóticamente) que el mergesort? Sí, ya que el mergesort es O(nlogn] y este es O(n) Sólo si dlogd > kn (donde k es una constante que depende de la implementación) No, ya que este algoritmo ha de recorrer varias veces el vector de booleanos.
¿Cuál de estos problemas tiene una solución eficiente utilizando programación dinámica? El problema de la asignación de tareas. El problema del cambio La mochila discreta sin restricciones adicionales.
Di cuál de estos tres algoritmos no es un algoritmo de "divide y vencerás". Quicksort. Mergesort El algoritmo de Prim.
Si f(n) E O(n³), ¿puede pasar que f(n) E O(n²)? No, porque n³ no E O(n²) Sólo para valores bajos de n. Es perfectamente posible, ya que O(n²) C O(n³).
¿Cuál de las siguientes jerarquías de complejidades es la correcta? O(1)⊂O(lg n)⊂O(lg lg n) ⊂ … ... ⊂ (n!)⊂O(2^n) ⊂O(n^n) ... ⊂ (2^n)⊂O(n!) ⊂O(n^n).
¿Cuál es el objetivo de la etapa de análisis en el Diseño y Análisis de un Algoritmo? Determinar el lenguaje y herramientas disponibles para su desarrollo Estimar los recursos que consumirá el algoritmo una vez implementado. Estimar la potencia y características del equipo informático necesarios para el correcto funcionamiento del algoritmo.
¿Cuál de los siguientes algoritmos de ordenación tiene menor complejidad? Burbuja Inserción directa Mergesort.
¿El tiempo de ejecución de un algoritmo depende de la talla del problema? Sí, siempre. No, nunca No necesariamente.
Ordena de menor a mayor las siguientes complejidades: 3,1,2 y 4 1,3,2 y 4 1,3,4 y 2.
El estudio de la complejidad resulta realmente interesante para tamaños grandes de problema por varios motivos: Las diferencias reales en tiempo de compilación de algoritmos con diferente coste para tamaños pequeños del problema no suelen ser muy significativas. Las diferencias reales en tiempo de ejecución de algoritmos con diferente coste para tamaños grandes del problema no suelen ser muy significativas. Ninguna de las anteriores.
¿Por que se emplean funciones de coste para expresar el coste de una algoritmo? Para poder expresar el coste de los algoritmos con mayor exactitud Para que la expresión del coste del algoritmo sea válida para cualquier entrada al mismo. Para poder expresar el coste de un algoritmo mediante una expresión matemática.
El caso base de una ecuación de recurrencia asociada a la complejidad temporal de un algoritmo expresa: El coste de dicho algoritmo en el mejor de los casos El coste de dicho algoritmo en el peor de los casos. Ninguna de las anteriores.
La complejidad de la función TB es: Θ ( n ). Θ (n · lg n). Θ (n^2 · lg n).
Dado el polinomio f(n)= A(m) n^m + A(m-1) n^(m-1) + … + A0, con A(m) ∈ R+ entonces f pertenece al orden: O(n^m). Ω(n^m). La dos respuestas anteriores son correctas.
Si f1(n) ∈ Ο(g1(n)) y f2(n) ∈ Ο(g2(n)) entonces: f1(n)·f2(n) ∈ Ο(maximo(g1(n),g2(n))) f1(n)·f2(n) ∈ Ο (g1(n)· g2(n)) Ambas son correctas.
Si f1(n) ∈ Ο(g1(n)) y f2(n) ∈ Ο(g2(n)) entonces: f1(n)+f2(n) ∈ Ο(max(g1(n),g2(n))) f1(n)+f2(n) ∈ Ο (g1(n)+g2(n)) Ambas son correctas.
Un algoritmo cuya talla es n y que tarda 40^n segundos en resolver cualquier instancia tiene una complejidad temporal: Θ ( n^n ). Θ ( 4^n ). Ninguna de las anteriores.
Si dos algoritmos tienen la misma complejidad asintótica: No necesitan exactamente el mismo tiempo para su ejecución Necesitan exactamente el mismo tiempo para su ejecución Ninguna de las anteriores.
Los algoritmos directos de ordenación, respecto de los indirectos: Presentan una mayor complejidad temporal y sus tiempos de ejecución absolutos son mayores Presentan una menor complejidad temporal y sus tiempos de ejecución absolutos son menores Presentan una mayor complejidad temporal si bien sus tiempos de ejecución absolutos son menores.
La talla o tamaño de un problema depende de: Conjunto de valores asociados a la entrada y salida del problema. Conjunto de valores asociados a la salida del problema Conjunto de valores asociados a la entrada del problema.
En un algoritmo recursivo, la forma de dividir el problema en subproblemas: Influye en la complejidad espacial del mismo Influye en su complejidad temporal No influye en ninguna de sus complejidades.
f(n) = 5n+3m·n +11 entonces f(n) pertenece a: O (n·m). O (n^m) Las dos son correctas.
El sumatorio, desde i=1 hasta n, de i^k pertenece a: Ο(n^(k+1)) Ο(n^k). Ninguna de las anteriores.
La complejidad de la función A2 es: O( √n · a ) O( √n / a ) O( n / √a ).
Cual de las siguientes definiciones es cierta: Las cotas de complejidad se emplean cuando para una misma talla se obtienen diferentes complejidades dependiendo de la entrada al problema Las cotas de complejidad se emplean cuando para diferentes tallas se obtienen diferentes complejidades dependiendo de la entrada al problema. Ninguna de las anteriores.
Cuando para distintas instancias de problema con el mismo tamaño no obtenemos el mismo resultado: No es posible calcular la complejidad a priori y debemos ejecutar el programa varias veces con la misma talla y obtener el tiempo medio para hallar la complejidad media No se puede aplicar la técnica de paso de programa, ya que esta técnica es para calcular la complejidad a priori. Calculamos el máximo y mínimo coste que nos puede dar el algoritmo.
f(n) = 5n+5 ¿ f(n) pertenece a O(n)? Sí. El valor de c es 5 y el valor mínimo de n0 es de 3
Sí. El valor de c es 9 y el valor mínimo de n0 es de 1 Sí. El valor de c es 6 y el valor mínimo de n0 es de 5.
f(n) = 10n+7 ¿ f(n) pertenece a O(n2)? Sí. Para c = 1 y a partir de un valor de n0 =10 Sí. Para cualquier valor de c positivo siempre existe un n0 a partir del que se cumple No.
Si f(n) ∈ Ω (g(n)) entonces: ∃ c, n0∈ R+: f(n) ≥ c· g(n) ∀ n ≥ n0 ∃ c, n0∈ R+: f(n) ≥ c· g(n) ∀ n ∃ c, n0∈ R+: f(n) ≤ c· g(n) ∀ n ≥ n0.
El coste asociado a la siguiente ecuación de recurrencia es: Θ(n lg(n^2) ). Θ(n^2 lg(n) ). Θ(n lg(n) ).
En los algoritmos de ramificación y poda, ¿el valor de una cota pesimista es siempre menor o igual que el valor de una cota optimista? (se entiende que ambas cotas se aplican sobre el mismo nodo) Solo si se trata de un problema de maximización No, depende del problema Sólo si se trata de un problema de minimización.
La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica: Si g(n) ∈ O(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica Si g(n) ∈ O(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación por inserción binaria Si g(n) ∈ O(n) la relación de recurrencia representa la complejidad temporal en el mejor caso del algoritmo de búsqueda del k-ésimo elemento más pequeño de un vector (estudiado en clase).
¿Cuál es el coste temporal asintótico de la siguiente función? O(n log(n)) O(n) O(n^2).
¿Qué aporta la técnica Ramificación y poda frente a Vuelta atrás? Eficiencia, los algoritmos de ramificación y poda son más eficientes que los de vuelta atrás… La posibilidad de analizar distintas estrategias para seleccionar el siguiente nodo a expandir. La posibilidad de combinar el uso de cotas pesimistas y optimistas para cualquier nodo ya sea completado o sin completar. En Vuelta atrás esto no se puede hacer.
Si limn→∞(f(n)/g(n)) = 0 entonces… … g(n) ∈ O(f(n)) … f(n) ∈ O(g(n)) … f(n) ∈ Θ(g(n)).
El algoritmo de ordenación Quicksort divide el problema en dos subproblemas.
¿Cuál es la complejidad temporal asintótica de realizar esa división? O(n). O(log n). O(n log n). Ω(n) y O(n^2).
El algoritmo Quicksort divide el problema en dos subproblemas. ¿Cuál es la complejidad temporal asintótica de realizar esa división? ninguna de las otras dos opciones es correcta Θ(logn). Θ(n logn).
Sea n el número de elementos que contienen los vectores w y v en la siguiente función f. ¿Cuál es su complejidad temporal asintótíca en función de n asumiendo que en la llamada inicial el parámetro i toma valor n? Ω(n) y O(n^2). Θ(2^n). Ω(n) y O(2^n).
El siguiente programa resuelve el problema de cortar un tubo de longitud n en segmentos de longitud entera entre 1 y n de manera que se maximice el precio de acuerdo con una tabla que da el precio para cada longitud, pero falta un trozo. ¿Qué debería ir en lugar de XXXXXXX? n,m[n]-1,p n-i,m,p n-m[n],m,p.
Sea la siguiente relación de recurrencia: g(n) = 1. g(n) = n g(n) = n^2.
¿Se puede reducir el coste temporal de un algoritmo recursivo almacenando los resultados devueltos por las llamadas recursivas? No, sólo se puede reducir el coste convirtiendo el algoritmo recursivo en iterativo.
Si, si se repiten llamadas a la función con los mismos argumento No, ello no reduce el coste temporal ya que las llamadas recursivas se deben realizar de cualquier manera.
Si f(n) ∈ O(n^2), ¿podemos decir siempre que f(n) ∈ O(n^3)? Sí, ya que n^2 ∈ Ω(n^3). Sí, ya que n^2 ∈ O(n^3) No, ya que n^2 ∉ O(n^3).
Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función? Θ(n^4). Θ(n^3 log(n)) Θ(n^3).
En un algoritmo de ramificación 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 …nunca afecta al tiempo necesario para encontrar la solución óptima ...puede influir en el número de nodos que se descartan sin llegar a expandirlos.
Se pretende resolver un problema de maximización utilizando ramificación y poda y para ello se dispone de tres posibles cotas optimistas. ¿Cuál deberíamos utilizar para tratar de reducir la cantidad de nodos a explorar? La que obtenga valores más elevados La que obtenga valores más pequeños La que más se acerque a una heurística voraz que obtenga una solución aproximada del problema.
Tratándose de un esquema general para resolver problemas de minimización, ¿qué falta en el hueco? n.optimistic_b() <= pb. n.optimistic_b() >= pb. n.pesimistic_b() <= pb.
Sea:
Di cuál de las siguientes afirmaciones es falsa: g(n) = Ω(n^k). g(n) = Θ(n^k). Las otras dos afirmaciones ambas son falsas.
Dadas las siguientes funciones: (Precondición: ) Se quiere reducir la complejidad temporal de la función g usando programación dinámica iterativa. ¿cuál sería la complejidad espacial? cúbica cuadrática exponencial.
Llamando n al tamaño del problema, ¿Cuál es la complejidad temporal de la siguiente función? O(n^n) O(n) O(n!).
Sea A una matriz cuadrada n x n. Se trata de buscar una permutación de las columnas tal que la suma de los elementos de la diagonal de la matriz resultante sea mínima. Indicad cuál de las siguientes afirmaciones es falsa. La complejidad temporal de la mejor solución posible al problema está en Ω(n^2) La complejidad temporal de la mejor solución posible al problema es O(n log n). Si se construye una solución al problema basada en el esquema de ramificación y poda, una buena elección de cotas optimistas y pesimistas podría evitar la exploración de todas las permutaciones posibles.
Tenemos un vector ordenado y queremos comprobar si contiene un elemento dado. ¿Cuál sería la complejidad temporal más ajustada para hacerlo? El tamaño del vector Constante con el tamaño del vector El logaritmo del tamaño del vector.
Los algoritmos de vuelta atrás que hacen uso de cotas optimistas generan las soluciones posibles al problema mediante... .. un recorrido guiado por estimaciones de las mejores ramas del árbol que representa el espacio de soluciones. ... un recorrido guiado por una cola de prioridad de donde se extraen primero los nodos que representan los subárboles más prometedores del espacio de soluciones. ... un recorrido en profundidad del árbol que representa el espacio de soluciones.
Dado el problema del laberinto con tres movimientos, ¿se puede aplicar un esquema de programación dinámica para obtener un camino de salida? No, con este esquema se puede conocer el número total de caminos distintos que conducen a la salida pero no se puede saber la composición de ninguno de ellos. Si, en caso de existir con este esquema siempre se puede encontrar un camino de salida No, para garantizar que se encuentra un camino de salida hay que aplicar métodos de búsqueda exhaustiva como vuelta atrás o ramificación y poda.
En ausencia de cotas optimistas y pesimistas, la estrategia de vuelta atrás… ... debe recorrer siempre todo el árbol ... no se puede usar para resolver problemas de optimización ... no recorre todo el árbol si hay manera de descartar subárboles que representan conjuntos de soluciones no factibles.
Decid cuál de estas tres es la cota optimista más ajustada al valor óptimo de la mochila discreta: El valor de una mochila que contiene todas los objetos aunque se pase del peso máximo permitido. El valor de la mochila continua correspondiente. El valor de la mochila discreta que se obtiene usando un algoritmo voraz basado en el valor específico de los objetos.
El coste temporal asintótico de insertar un elemento en un vector ordenado de forma que continue ordenado es: Ω(n^2) O(n) O(log n).
¿En ramificación y poda, tiene sentido utilizar la cota optimista de los nodos como criterio para ordenar la lista de nodos vivos? Sí, en el caso de que se ordene la lista de nodos vivos, siempre debe hacerse según el criterio de la cota optimista No, la cota optimista sólo se utiliza para determinar si una n-tupla es prometedora Sí, aunque no es una garantía de que sea una buena estrategia de búsqueda.
¿Qué estrategia de búsqueda es a priori más apropiada en un esquema de vuelta atrás? Explorar primera los nodos que están más completados En el esquema de vuelta atrás no se pueden definir estrategias de búsqueda Explorar primero los nodos con mejor cota optimista.
Sea la siguiente relación de recurrencia: Si T(n), ¿en cuál de estos tres casos nos podemos encontrar? Las otras dos opciones son ambas ciertas g(n) = log n g(n) = √n.
Si f ∈ Ω(g1) y f ∈ Ω(g2) entonces: f ∈ Ω(g1+g2) f ∉ Ω(mín(g1,g2)) f ∈ Ω(g1*g2).
Dada la siguiente función: Int exa
¿Cuál es su complejidad temporal asintótica? O(n^2) O(n). O(log n).
El esquema de vuelta atrás… Se puede aplicar a cualquier tipo de problema aunque el coste temporal es elevado Las otras dos opciones son ambas verdaderas. Garantiza que encuentra la solución Óptima a cualquier problema de selección discreta.
En el esquema de ramificación y poda, ¿qué estructura es la más adecuada si queremos realizar una exploración por niveles? Cola de prioridad Pila Cola.
¿Qué nos proporciona la media entre el coste temporal asintótico (o complejidad temporal) en el peor caso y el coste temporal asintótico en el mejor caso? Nada de interés. El coste temporal promedio El coste temporal asintótico en el caso medio.
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de programación dinámica. En cuanto a la complejidad temporal, ¿cuál es la mejora de la versión recursiva con memoización frente a la recursiva ingenua que se obtiene a partir del esquema divide y vencerás? La mejora no está garantizada puesto que la versión recursiva con memoización podría ser peor que la obtenida a partir del esquema divide y vencerás. De una complejidad exponencial que se obtendría con la ingenua se reduciría a polinómica con la de memoización. De una complejidad cuadrática que se obtendría con la ingenua se reduciría a lineal con la de memoización.
Dado el problema del laberinto con tres movimientos, se pretende conocer la longitud del camino de salida más corto. Para ella se aplica el esquema voraz con un criterio de selección que consiste en elegir primero el movimiento "Este" siempre que la casilla sea accesible. Si no lo es se descarta ese movimiento y se prueba con "Sureste" y por último, si este tampoco es posible, se escoge el movimiento "Sur". ¿Qué se puede decir del algoritmo obtenido? Que es un algoritmo voraz pero sin garantía de solucionar el problema… Que en realidad no es un algoritmo voraz pues el criterio de selección no lo es. Que en realidad no es un algoritmo voraz pues las decisiones que se toman no deberían reconsiderarse.
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1,1) hasta la casilla (n, m) y para ello se aplica el esquema programación dinámica para obtener un algoritmo lo más eficiente posible en cuanto a complejidad temporal y espacial. ¿Cuáles serían ambas complejidades? Temporal Θ(n x m) y espacial Θ(n x m) Temporal Θ(n x m) y espacial Θ(mín{n,m}) Temporal Θ(máx{n, m}) y espacial Θ(máx{n, m}).
Dado el problema del laberinto con tres movimientos, se desea saber el número de caminos distintos desde la casilla inicial (1, 1) hasta la casilla (n, m) y para ello se aplica un esquema de divide y vencerás. ¿Cuál sería la recurrencia apropiada para el caso general? nc(n, m) = nc(n - 1, m) + nc(n, m - 1) + nc(n - 1, m - 1) nc(n, m) = nc(n - 1, m) * nc(n, m - 1) * nc(n - 1, m - 1) Ninguna de las otras dos recurrencias se corresponde con un esquema de divide y vencerás.
¿Qué complejidad se obtiene a partir de la relación de recurrencia T(n) = 8T(n/2) + n^3 con T(1) = O(1)? O(n^3 log n) O(n^3) O(n log n).
Dada la siguiente función: Int exa La complejidad temporal exacta es Θ(n^2). La complejidad temporal en el mejor de los casos es Ω(n) La complejidad temporal en el mejor de los casos es Ω(1).
El esquema voraz… Las otras dos opciones son ambas falsas. Garantiza encontrar una solución a cualquier problema, aunque puede que no sea
óptima Puede que no encuentre una solución pero si lo hace se garantiza que es óptima.
Cuando la descomposición de un problema de lugar a subproblemas de tamaño similar al original, muchos de los cuales se repiten, ¿qué esquema es a priori más apropiado? Ramificación y poda Divide y vencerás. Programación dinámica.
Dada la siguiente función (donde max(a,b) ∈ Θ(1)) Float exa La complejidad temporal en el peor de los casos es O(n^2). La complejidad temporal en el peor de los casos es O(2^n). La complejidad temporal en el mejor de los casos es Ω(n^2).
¿Cuál sería la complejidad temporal de la siguiente función tras aplicar programación dinámica? Θ(n) Θ(n^2). Θ(n x m).
Si el coste temporal de un algoritmo es T(n), ¿cuál de las siguientes situaciones es imposible? T(n) ∈ Θ(n) y T(n) ∈ Ω(n^2). T(n) ∈ O(n) y T(n) ∈ Θ(n) T(n) ∈ Ω(n) y T(n) ∈ Θ(n^2).
Se desea resolver el problema de la potencia enésima (x^n), asumiendo que n es par y que se utilizará la siguiente recurrencia: pot.(x, n) = pot.(x, n/2) * pot.(x, n/2); ¿Qué esquema resulta ser más eficiente en cuanto al coste temporal? En este caso tanto programación dinámica como divide y vencerás resultan ser equivalentes en cuanto a la complejidad temporal Programación dinámica Divide y vencerás.
De las siguientes afirmaciones marca la que es verdadera. El esquema de vuelta atrás no es compatible con el uso conjunto de cotas pesimistas y optimistas. Las cotas pesimistas no son compatibles con un esquema de vuelta atrás En un esquema de vuelta atrás, las cotas pesimistas no tienen sentido si lo que se pretende es obtener todas las soluciones factibles.
Dado un problema de minimización resuelto mediante un esquema de ramificación y poda, ¿qué propiedad cumple una cota optimista? Asegura un ahorro en la comprobación de todas las soluciones factibles. Siempre es mayor o igual que la mejor solución pasible alcanzada. Las otras dos opciones son ambas falsas.
¿Qué se deduce de f(n) y g(n) si se cumple limn→∞(f(n)/g(n)) = k, con k ≠ 0? f(n) ∈ O(g(n)) y g(n) ∈ O(f(n)). f(n) ∈ O(g(n)) pero g(n) ∉ O(f(n)) g(n) ∈ O(f(n)) pero f(n) ∉ O(g(n)).
Un tubo de n centímetros de largo se puede cortar en segmentos de 1 centímetro, 2 centímetros, etc... Existe una lista de los precios a los que se venden los segmentos de cada longitud. Una de las maneras de cortar el tubo es la que más ingresos nos producirá. Se quiere resolver el problema mediante vuelta atrás. ¿Cual sería la forma más adecuada de representar las posibles soluciones? Una tabla que indique, para cada posición donde se va a cortar, cada uno de los posibles valores acumulados. Un vector de booleanos. Un par de enteros que indiquen los cortes realizados y el valor acumulada.
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. Θ(n) ⊂ Θ(n^2) n + n log n ∈ Ω(n) O(2^(log n)) ⊂ O(n^2).
En el problema del viajante de comercio (travelling salesman problem) queremos listar todas las soluciones factibles. Lo más importante es conseguir una cota pesimista adecuada Las diferencias entre ramificación y poda y vuelta atrás son irrelevantes en este caso. La más adecuado sería usar una técnica de ramificación 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 técnica ramificación y poda no aporta nada con respecto a vuelta atrás.
Dado un problema de maximización resuelto mediante un esquema de ramificación y poda, ¿qué ocurre si la cota optimista resulta ser un valor excesivamente elevado? Que se podría explorar menos nodos de los necesarios Que se podría podar el nodo que conduce a la solución óptima. Que se podría explorar más nodos de los necesarios.
Un algoritmo recursivo basado en el esquema divide y vencerás… Las otras dos opciones son ambas verdaderas ... alcanza su máxima eficiencia cuando el problema de tamaño n se divide en a problemas de tamaño n/a. ... nunca tendrá un coste temporal asintótico (o complejidad temporal) exponencial.
Dado el problema de las torres de Hanoi resuelto mediante divide y vencerás, ¿cuál de las siguientes relaciones de recurrencia expresa mejor su complejidad temporal para el caso general, siendo n el número de discos? T(n) = 2T(n - 1) + 1. T(n) = 2T(n - 1) + n T(n) = T(n - 1) + n.
Una de las prácticas de laboratorio consistió en el cálculo empírico de la complejidad temporal promedio del algoritmo de ordenación de vectores Quicksort tomando como centinela el elemento del vector que ocupa la posición central. ¿Cuál es el orden de complejidad que se obtuvo? n log^2 n n^2 n log n.
Se desea ordenar una lista enlazada de n elementos haciendo uso del algoritmo Mergesort. En este caso, al tratarse de una lista, la complejidad temporal asintótica de realizar la división en subproblemas resulta ser lineal con el tamaño de esa lista. ¿Cuál sería entonces el coste temporal de realizar dicha ordenación? Θ(n log n). Θ(n^2). Ninguna de las otras dos opciones es cierta.
Dada la siguiente función: marca la respuesta correcta: Int exa La complejidad temporal exacta es Θ(n log n).
La complejidad temporal en el mejor de los casos es Ω(1) La complejidad temporal en el mejor de los casos es Ω(n).
Dado el problema del laberinto con tres movimientos, ¿cuál de las estrategias siguientes proveería de una cota optimista para ramificación y poda? Suponer que ya no se van a realizar más movimientos Las otras dos estrategias son ambas válidas. Suponer que en adelante todas las casillas del laberinto son accesibles.
Los algoritmos de ordenación Quicksort y Mergesort tienen en común… ... que ordenan el vector sin usar espacio adicional ... que se ejecutan en tiempo O(n) ... que aplican la estrategia de divide y vencerás.
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.
La complejidad temporal (o coste temporal asintótico) en el mejor de los casos... es una función de la talla, o tamaño del problema, que tiene que estar definida para todos los posibles valores de ésta es el tiempo que tarda el algoritmo en resolver la talla más 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 total no supere un gramo. Como la balanza que tenemos solo tiene una precisión de 0.1 gramos, no se considerarán pesos que no sean múltiplos de esta cantidad. Queremos hacer un programa que genere todas las combinaciones posibles. No hay ningún problema en usar una técnica de vuelta atrás No se puede usar vuelta atrás porque las decisiones no son valores discretos No se puede usar vuelta atrás porque el número de combinaciones es infinito.
Dado un problema de optimización, ¿cuándo se puede aplicar el método de vuelta atrás? Es condición necesaria (aunque no suficiente) que el dominio de las decisiones sea discreto o discretizable Es condición necesaria y suficiente que el dominio de las decisiones sea discreto o discretizable No sólo es condición necesaria que el dominio de las decisiones sea discreto o discretizable; además, debe cumplirse que se puedan emplear mecanismos de poda basados en la mejor solución hasta el momento.
¿Cuál de estas tres expresiones es cierta? O( 2^(log n) ) ⊂ O(n^2) ⊂ O(2^n). O(n^2) ⊂ O( 2^(log n) ) ⊆ O(2^n). O(n^2) ⊂ O( 2^(log n) ) ⊂ O(2^n).
Indicad cuál de estas tres expresiones es falsa: Θ(n/2) = Θ(n) Θ(n) ⊂ O(n) Θ(n) ⊂ Θ(n^2).
Indicad cuál es el coste temporal asintótico (o complejidad temporal), en función de n, del programa siguiente: Es O(n^2) pero no Ω(n^2) Es Θ(n^2). Es Θ(n).
¿Pertenece 3n^2 + 3 a O(n^3)? Sí No Sólo para c = 1 y n0 = 5.
Las relaciones de recurrencia... aparecen sólo cuando la solución sea del tipo divide y vencerás. expresan recursivamente el coste temporal de un algoritmo sirven para reducir el coste temporal de una solución cuando es prohibitivo.
El coste temporal de un algoritmo se ajusta a la siguiente ecuación de recurrencia: ¿qué coste temporal asintótico (o complejidad temporal) tendrá el algoritmo? O(n log n) O(n^2) O(2^n).
¿Cuál es el coste espacial asintótico del siguiente algoritmo? O(1) O(log n) O(n).
¿Qué algoritmo es asintóticamente más rápido, Quicksort o Mergesort? Como su nombre indica, el Quicksort. Son los dos igual de rápidos, ya que el coste temporal asintótico de ambos es O(nlog n). El Mergesort es siempre más rápido o igual (salvo una constante) que el Quicksort.
El coste temporal del algoritmo de ordenación por inserción es… O(n^2) O(n). O(n log n).
El problema de la función compuesta mínima consiste en encontrar, a partir de un conjunto de funciones dadas, la secuencia mínima de composiciones de éstas que permita transformar un número n en otro m. Se quiere resolver mediante ramificación y poda. ¿Cuál sería la forma más adecuada de representar las posibles soluciones? Mediante un vector de booleanos. Mediante un vector de reales. Este problema no se puede resolver usando ramificación y poda si no se fija una cota superior al número total de aplicaciones de funciones.
¿Cuál de estas expresiones es falsa? 2n^2 + 3n + 1 ∈ O(n^3) n + n log n ∈ Ω(n) n + n log n ∈ Θ(n).
Uno de estos tres problemas no tiene una solución trivial y eficiente que siga el esquema voraz. El problema del cambio. El problema de la mochila discreta sin limitación en la carga máxima de la mochila El problema de la mochila continua.
Estudiad la relación de recurrencia: (donde p y q son enteros mayores que 1). Di cuál de los siguientes esquemas algorítmicos produce de manera natural relaciones de recurrencia así. Divide y vencerás Ramificación y poda Programación dinámica.
La versión Quicksort que utiliza como pivote el elemento del vector que ocupa la posición central... se comporta mejor cuando el vector está ordenado no presenta caso mejor y peor para instancias del mismo tamaño se comporta peor cuando el vector ya está ordenado.
La complejidad temporal de la solución de vuelta atrás al problema de la mochila discreta es... cuadrática en el caso peor exponencial en cualquier caso. exponencial en el caso peor.
Ante un problema de optimización resuelto mediante backtracking, ¿Puede ocurrir que el uso de las cotas pesimistas y optimistas sea inútil, incluso perjudicial? Según el tipo de cota, las pesimistas puede que no descarten ningún nodo pero el uso de cotas optimistas garantiza la reducción del espacio de búsqueda. No, las cotas tanto optimistas como pesimistas garantizan la reducción del espacio de soluciones y por tanto la eficiencia del algoritmo Sí, puesto que es posible que a pesar de utilizar dichas cotas no se descarte ningún nodo.
¿Qué se entiende por "tamaño del problema"? El valor máximo que puede tomar una instancia cualquiera de ese problema El número de parámetros que componen el problema. La cantidad de espacio en memoria que se necesita para codificar una instancia de ese problema.
Si limn→∞(f(n)/n^2) = k, y k ≠ 0, ¿cuál de estas tres afirmaciones es falsa? f(n) ∈ O(n^3) f(n) ∈ Θ(n^3) f(n) ∈ Θ(n^2).
La función gamma de un número semientero positivo (un número es semientero si al restarle 0.5 es entero) se define como: ¿Se puede calcular usando programación dinámica iterativa? No, ya que el índice del almacén sería un número real y no entero No, ya que no podríamos almacenar los resultados intermedios en el almacén Sí, pero la complejidad temporal no mejora.
¿Cuál de estas afirmaciones es falsa? La solución de programación dinámica iterativa al problema de la mochila discreta realiza cálculos innecesarios Los algoritmos iterativos de programación dinámica utilizan memoización para evitar resolver de nuevo los mismos subproblemas que se vuelven a presentar. La memoización evita que un algoritmo recursivo ingenuo resuelva repetidamente el mismo problema.
¿Cuál de estas afirmaciones es falsa? Hay problemas de optimización en los cuales el método voraz sólo obtiene la solución óptima para algunas instancias y un subóptimo para muchas otras instancias Todos los problemas de optimización tienen una solución voraz que es óptima sea cual sea la instancia a resolver Hay problemas de optimización para los cuales se puede obtener siempre la solución óptima utilizando una estrategia voraz.
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 Θ(f) = O(f) ∩ Ω(f) Ω(f) = Θ(f) ∩ O(f) O(f) =Ω(f) ∩ Θ(f).
Dada la relación de recurrencia: (donde p y a son enteros mayores que 1 y g(n) = n^k), ¿qué tiene que ocurrir para que se cumpla T(n)? p > a^k. p = a^k. p < a^k.
¿Cuál es la complejidad temporal en el mejor de los casos de la siguiente función? Ω(n). Ω(1). Esta función no tiene caso mejor.
En el problema del coloreado de grafos (mínimo número de colores necesarios para colorear todos los vértices de un grafo de manera que no queden dos adyacentes con el mismo color) resuelto mediante ramificación y poda, una cota optimista es el resultado de asumir que... se van a utilizar tantos colores distintos a los ya utilizados como vértices quedan por colorear. no se van a utilizar colores distintos a los ya utilizados. solo va a ser necesario un color más.
Se quiere reducir la complejidad temporal de la siguiente función haciendo uso de programación dinámica. ¿Cuál sería la complejidad temporal resultante? Cuadrática Se puede reducir hasta linea La función no cumple con los requisitos necesarios para poder aplicar programación dinámica.
Dada la relación de recurrencia: (donde p y a son enteros mayores que 1 y g(n) = n^k), ¿qué tiene que ocurrir para que se cumpla T(n) (n^k loga(n))? p > a^k p < a^k. p = a^k.
Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces: f ∈ Θ(g1*g2) f ∉ Θ(máx(g1,g2)) f ∈ Θ(g1 + g2).
Si limn→∞(f(n)/n^2) = k, y k ≠ 0, ¿cuál de estas tres afirmaciones es cierta? f(n) ∈ Ω(n^3) f(n) ∈ Θ(n^2). f(n) ∈ Θ(n^3).
Cogemos el algoritmo de Mergesort y en lugar de dividirlo el vector en dos partes, lo dividimos en tres. Posteriormente combinamos las soluciones parciales. ¿Cuál sería la complejidad temporal asintótica de la combinación de las soluciones parciales? Θ(n) Θ(log n) Ninguna de las otras dos opciones es cierta.
Si f ∈ Θ(g1) y f ∈ Θ(g2) entonces: f^2 ∈ Θ(g1*g2). Las otras dos opciones son ambas ciertas f ∈ Θ(max(g1,g2)).
¿Cuál de estas afirmaciones es cierta? La ventaja de la solución de programación dinámica iterativa al problema de la mochila discreta es que nunca se realizan cálculos innecesarios La memoización evita que un algoritmo recursivo ingenuo resuelva repetidamente el mismo problema Los algoritmos iterativos de programación dinámica utilizan memoización para evitar resolver de nuevo los mismos subproblemas que se vuelven a presentar.
Indica cuál es la complejidad en el peor caso de la función replace: O(n log n) O(n^2) O(n).
Sea f(n) la solución de la relación de recurrencia f(n) = 2f(n/2) + 1; f(1) = 1. Indicad cuál de estas tres expresiones es cierta: f(n) ∈ Θ(n) f(n) ∈ Θ(n^2) f(n) ∈ Θ(n log n).
Considerad estos dos fragmentos:
s = 0 ; for (i = 0;i<n;i++) s+=i;
y
s=0 ; for (i=0;i<n;i++) if (a[i] ¡= 0) s+=i;
y un array a[i] de números enteros. Indicad cuál de estas tres afirmaciones es cierta El coste temporal asintótico del primer programa en el caso peor es mas alto que en el segundo El coste temporal asintótico, tanto en el caso mejor como en el caso peor, de los dos programas es el miso El coste temporal asintótico del segundo programa en el caso peor es más alto que en el primero.
Indica cuál es la complejidad en función de n, donde k es una constante (no depende de n), del fragmento siguiente: O(n) O(n logn) O(n^2).
La versión de Quicksort que utiliza como pivote la mediana del vector… se comporta mejor cuando el vector ya está ordenado se comporta peor cuando el vector ya está ordenad el hecho de que el vector estuviera ordenado o no, no influye en la complejidad temporal de este algoritmo.
Dada la siguiente relación de recurrencia, ¿Qué cota es verdadera? f(n) ∈ Θ(n) f(n) ∈ Θ(n^3) f(n) ∈ Θ(√n log n).
Un problema de tamaño n puede transformarse en tiempo O(n^2) en nueve de tamaño n/3, por otro lado, la solución al problema cuando la talla es 1 requiere un tiempo constante. ¿Cuál de estas clases de coste temporal asintótico es la más ajustada? O(n logn) O(n^2 logn) O(n^2).
Indica cuál es la complejidad de la función siguiente: O(n^2) O(n). O(n logn).
Para que la complejidad de un algoritmo presente caso mejor y peor distintos… es condición necesaria y suficiente que existan instancias distintas del problema con el mismo tamaño es condición necesaria que existan instancias distintas del problema con el mismo tamaño es condición suficiente que existan instancias distintas del problema con el mismo tamaño.
La complejidad temporal en el mejor de los casos de un algoritmo recursivo… coincide con el valor del caso base de la ecuación de recurrencia que expresa la complejidad temporal del algoritmo las demás opciones son falsas siempre coincidirá con la complejidad temporal de las instancias que están en el caso base del algoritmo recursivo.
Considerad la función siguiente: (int M) Si la talla del problema viene dada por n = f – i + 1, ¿cuál es el coste temporal asintótico en el supuesto de que n sea una potencia de 2? O(n). O(n^2). O(n logn).
El coste temporal asintótico del fragmento
s=0; for(i=0; i < n; i++) for(j = i ; j<n; j++) s+=i*j;
Y del fragmento
s=0; for(i=0; i < n; i++) for(j = 0 ; j<n; j++) s+=i*i*j;
Son … …iguales … el del segundo, menor que el del primero. … el del primero, menor que el del segundo.
El problema de cortar un tubo de longitud n en segmentos de longitud entera, de manera que el precio total de sus partes sea máximo de acuerdo con una lista de precios por longitudes … no se puede resolver usando un algoritmo de vuelta atrás se pude resolver mediante un algoritmo de vuelta atrás pero existe una solución asintóticamente mucho mas eficiente se debe resolver mediante un algoritmo de vuelta atrás, dado que otros algoritmos no consideran todas las posibles maneras de cortar el tubo.
Di cual de estas tres soluciones a problemas de optimización no comporta, en el peor caso, tener que considerar O(n!) posibilidades la solución de vuelta atrás al problema del viajante de comercio (travelling salesman problem), o sea, el de encontrar un ciclo hamiltoniano de coste mínimo en un grafo conexo de n vértices donde cada arista tiene un coste asignado a solución de ramificación y poda al problema de asignación de n tareas a n trabajadores de forma de que cada trabajador hace exactamente una tarea y cada tarea es asignada a un trabajador exactamente, de forma que la suma de los costes de las tareas es mínimo la solución al problema de buscar un árbol que cubre todos los vértices de un grafo de n vértices de forma que el coste mínimo (mínimum spanning tree).
Dada la suma de recurrencia
¿cuál de las siguientes afirmaciones es cierta? T(n) ∈ Θ(n^2) T(n) ∈ Θ(n!) T(n) ∈ Θ(2^n).
¿Qué algoritmo es asintóticamente más rápido, el Quicksort central o el mergesort? como su nombre indica, el Quicksort central. son los dos igual de rápidos, ya que el coste temporal asintótico de ambos es O(n logn). el mergesort es siempre más rápido o igual (salvo una constante) que el Quicksort central.
¿Cuál de estas tres expresiones es falsa? 2n^2 + 3n + 1 ∈ O(n^3) n + n logn ∈ Ω(n) n + n logn ∈ Θ(n).
El coste temporal del algoritmo de ordenación por selección es... O(n^2) O(n) O(n log n).
De los problemas siguientes, indicad cuál no se puede tratar eficientemente como los otros dos: el problema de cortar un tubo de forma que se obtenga el máximo beneficio posible el problema del cambio, o sea, el de encontrar la manera de entregar una cantidad de dinero usando las mínimas monedas el problema del viajante de comercio.
Con respecto al parámetro n:
¿Cuál es la complejidad temporal de la siguiente función? Θ(n^3) Θ(n^2) Θ(n^2 logn) .
En un esquema de RyP, ¿podrían coincidir los valores obtenidos por las cotas pesimistas y optimistas de un nodo cualquiera? sí, en tal caso el valor obtenido por las cotas coincidiría también con el mejor valor que puede obtenerse de ese nodo no, en tal caso una de las cotas (o ambas) estaría mal calculada si, pero habría que seguir completando el nodo para saber cuál es la mejor solución que puede obtenerse de el.
Se desea resolver el problema de la potencia enésima (x^n), asumiendo que n es par y que se utilizará la siguiente recurrencia: pot(x,n) = pot(x,n/2) * pot(x,n/2); ¿Qué estrategia resulta ser más eficiente en cuanto al coste temporal? divide y vencerás en este caso tanto programación dinámica como divide y vencerás resultan ser equivalentes en cuanto a la complejidad temporal un algoritmo recursivo con memoización.
¿Qué tienen en común los algoritmos de ordenación Quicksort y Mergesort? la complejidad temporal de la división en subproblemas el número de llamadas recursivas que hacen en el mejor de los casos la complejidad temporal de la combinación de las soluciones parciales.
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 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.
¿Qué complejidad se obtiene a partir de la relación de recurrencia T(n) = 9T(n/3) + n^3 con T(1) = O(1)? O(n^3). O(n logn). O(n^3 logn).
¿Cuál de las siguientes estrategias de búsqueda es más apropiada en un 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 ninguna de las otras dos estrategias es compatible con el esquema de vuelta atrás.
Queremos resolver mediante vuelta atrás el problema de las 8 reinas (colocar 8 reinas en un tablero de ajedrez de manera que no se maten mutuamente). Una buena cota optimista permitiría: No es aplicable este tipo de podas a este problema Muy probablemente, explorar menos nodos Muy probablemente, resolver el problema de forma más rápida.
Sea la siguiente relación de recurrencia
Si T(n) ∈ Θ(n^2), ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n^2 g(n) = n^3 g(n) = n.
Se pretende aplicar la técnica memoización a la siguiente función recursiva: ¿Qué complejidad temporal y espacial cabe esperar de la función resultante? O(m - n), tanto espacial como temporal ninguna de las otras dos opciones es correcta O(n - m), tanto espacial como temporal.
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una es verdadera. Marca la que (en este sentido) es distinta a las otras dos n + n log2n ∈ Ω(n + nlog2n) O(n^2) ⊂ O(2^log2n). Ω(n^2) ⊂ Ω(n).
Dado un problema de minimización resuelto mediante un esquema de ramificación y poda, ¿qué ocurre si la cota optimista resulta ser un valor excesivamente pequeño? que se podría podar el nodo que conduce a la solución óptima que se podría explorar más nodos de los necesarios que se podría explorar menos nodos de los necesarios.
Es 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? 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. si, pero esto solo podría ocurrir si se hace uso de cotas pesimistas. si, esto puede ocurrir incluso si no se hace uso de cotas pesimistas.
Si lim f(n)/g(n) = infinito entonces… …f(n) ∈ O(g(n)) …f(n) ∈ Θ(g(n)) …f(n) ∈ Ω(g(n)).
Si f ∉ Θ(g1) y f ∈ Θ(g2) entonces siempre se cumplirá: f ∈ Ω(min(g1,g2)) f ∉ O(max(g1,g2)) f ∈ Ω(g1 + g2).
Decid cual de estas tres estrategias proveería la cota pesimista más ajustada al valor optimo de la mochila discreta: asumir que ya no se van a coger más objetos. completar las decisiones restantes basándose en la mejor solución voraz que pueda encontrarse para los restantes objetos y espacio disponible de la mochila el valor de una mochila que contiene todos los objetos aunque se pase del peso máximo permitido.
La siguiente relación de recurrencia expresa la complejidad de un algoritmo recursivo, donde g(n) es una función polinómica:
Di cuál de las siguientes afirmaciones es cierta: Si g(n) ∈ Θ(1) la relación de recurrencia representa la complejidad temporal del algoritmo de búsqueda dicotómica Si g(n) ∈ Θ(n^2) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación mediante inserción binaria Si g(n) ∈ Θ(n) la relación de recurrencia representa la complejidad temporal del algoritmo de ordenación Mergesort.
Sea la siguiente relación de recurrencia:
Si T(n) ∈ Θ (n^2), ¿en cuál de estos tres casos nos podemos encontrar? g(n) = n. g(n) = 1 g(n) = n^2.
Con respecto al parámetro n,
¿Cuál sería la complejidad temporal de la siguiente función si se aplicara memoización? lineal. constante logarítmica.
Con respecto al tamaño del problema,
¿Cuál es el orden de complejidad espacial asintótica de la siguiente función? (asumimos que A es una matriz cuadrada) constante lineal cuadrático.
Con respecto al parámetro n,
¿Cuál es la complejidad temporal de la siguiente función? Θ(n^3 logn) Θ(n^2 logn) Θ(n^3).
Tenemos una lista ordenada y queremos que quede ordenada en sentido contrario. ¿Cuál sería la complejidad más ajustada para hacerlo? la longitud de la lista. el logaritmo de la longitud de la lista la longitud de la lista multiplicada por su logaritmo.
Un tubo de n centímetros de largo se puede cortar en segmentos de 1 centímetro, 2 centímetros, etc. Existe una lista de los precios a los que se venden los segmentos de cada longitud. Una de las maneras de cortar el tubo es la que más ingresos nos producirá. Se quiere resolver el problema de manera recursiva. ¿qué recurrencia matemática podría utilizarse? r(n)= max(p(i)+ r(n-1)); r(0)=0 r(n)= max r(n-1) + p(i)); r(0)=0 Este problema no se puede resolver de manera recursiva.
Dado el siguiente programa recursivo: O(1). O(n^2) O(n).
Queremos resolver por vuelta atrás el problema de las n reinas. El usar una buena cota optimista permitiría: no es aplicable ese tipo de podas a este problema muy probablemente, hacer que el programa vaya más lento muy probablemente, resolver el problema de forma más rápida.
Si f ∉ O(g1) y f ∈ O(g2) entonces siempre se cumplirá: lim = infinito. lim = 0. las otras dos opciones son ambas ciertas.
Sea:
Indica cuál de las siguientes afirmaciones es cierta: T(n) ∈ O((√2)^n). T(n) ∈ O(2^n) las otras dos opciones son ambas ciertas.
Cuál es la complejidad temporal en el peor de los casos de construir un montículo (heap) a partir de un vector de tamaño n. O(n). O(logn) O(n logn).
Si lim (g(n)/f(n)) resulta ser cero, cuál de las siguientes expresiones puede darse f(n) ∈ Θ(g(n)) ninguna de las otras dos opciones son ciertas f(n) ∈ Ω(g(n)) y g(n) ∈ Ω(f(n)).
¿Cuál es la relación de recurrencia asociada a la complejidad temporal de la siguiente función? a b c.
Un vector de enteros de tamaño n tiene sus elementos estructurados en forma de montículo (heap). Cuál es la complejidad temporal en el peor de los casos de borrar el primer elemento del vector y reconstruirlo posteriormente para que siga manteniendo la estructura de montículo. O(n). O(logn). O(n logn).
Se pretende ordenar un vector cuyos n elementos están organizados formando un montículo (Heap). Sin tener en cuenta el tiempo empleando para este preproceso, ¿Con qué coste temporal asintótico se podría realizar la ordenación? O(n). ninguna de las otras dos opciones es la correcta O(n logn).
¿Cuál es la complejidad espacial del siguiente algoritmo? O(1) O(logn) O(n).
Con respecto al parámetro n,
¿Cuál es la complejidad temporal de la siguiente función? Θ(n^2). Θ(2^n). Θ(n).
El siguiente programa trata de resolver un problema p aplicando la técnica de memoización. ¿Se está aplicando bien la técnica? si no, puesto que se realizan llamadas recursivas no, puesto que es probable que se hagan cálculos innecesarios.
Sea V el conjunto de todos los valores faciales que presentan las monedas de un país (por ejemplo, en la zona Euro, {1, 2, 5, 10, 20, 50, 100, 200}). Una cantidad M se puede entregar con varias combinaciones de monedas, pero hay una que usa el mínimo número de monedas n(M), el cual se puede calcular recursivamente como
Indicad cuál de las siguientes afirmaciones es falsa: el algoritmo que calcularía n(M) así sería un algoritmo voraz y tendría un coste razonable el algoritmo recursivo que calcularía n(M) así tendría en general un coste prohibitivo porque calcularía n(x) muchas veces para la misma x. el algoritmo recursivo que calcularía n(M) se podría convertir en un algoritmo con un coste razonable usando memoización.
Sea T(n) = n + T(n − 1) para n > 1 y T(1)=1. Una de las afirmaciones siguientes es cierta T(n) ∈ O(n^3). T(n) ∈ O(n) T(n) ∈ O(nlogn).
Con respecto al parámetro n, ¿Cuál es la complejidad temporal de la siguiente función? Θ(2^n). Θ(n^2). Θ(n).
Sea el vector v[8]={8,6,5,4,4,3,2,2}. Indica cuál de las siguientes opciones es cierta. (se asume la notación del lenguaje C/C++ en la que el primer elemento del vector está en la posición 0, es decir, en v[0]). El vector v no es un montículo máximo porque el elemento v[3]=5 debe ser ``flotado''
(desplazado hacia la izquierda) El vector v no es un montículo máximo porque el elemento v[2]=4 debe ser ``hundido'' (desplazado hacia la derecha) El vector v es un montículo máximo.
¿Cuál es la complejidad temporal de la siguiente función recursiva? Θ(3^n). Θ(n^2 logn). Θ(n^2).
Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál
es más eficiente en cuanto a coste temporal? Las dos funciones son equivalentes en cuanto a coste temporal La primera, pot2_1(n), es más eficiente que la otra La segunda, pot2_2(n), es más eficiente que la otra.
Tenemos un vector desordenado y queremos obtener los tres elementos más pequeños. ¿Cuál sería la complejidad temporal más ajustada para hacerlo? (Sin pérdida de la generalidad puedes suponer que en el vector todos los elementos son distintos) El logaritmo de la longitud del vector. Cuadrática con la longitud del vector Lineal con la longitud del vector.
¿Cuál de las siguientes relaciones de recurrencia expresa mejor la complejidad espacial del algoritmo Mergesort? T(n) = n + T(n/2) para n > 1 y T(n)=1 para n<=1 T(n) = n + T(n-1) para n > 1 y T(n)=1 para n<=1 T(n) = n + 2T(n/2) para n > 1 y T(n)=1 para n<=1.
Tenemos un vector ordenado de tamaño no y un vector desordenado de tamaño nd y queremos obtener un vector ordenado con todos los elementos. ¿Qué será más rápido? Insertar los elementos del vector desordenado (uno a uno) en el vector ordenado Ordenar el desordenado y luego mezclar listas Depende de si no > nd o no.
Pertenece 3n^2 a O(n^3)? Ninguna de las otras dos opciones son verdaderas. Sí, pero sólo si se toma c > 3 No.
Si f(n) ∈ Θ(n^2), ¿podemos decir siempre que f(n) ∈ O(n^3)? Sí, ya que n^2 ∈ O(n^3) Sí, ya que n^2 ∈ Ω(n^3) No, ya que n^2 ∉ O(n^3).
Las siguientes funciones calculan el valor de la potencia n-ésima de dos. ¿Cuál es más eficiente en cuanto a coste temporal? Las dos funciones son equivalentes en cuanto a coste temporal. La primera, pot2_1(n), es más eficiente que la otra. La segunda, pot2_2(n), es más eficiente que la otra.
De las siguientes expresiones, o bien dos son verdaderas y una falsa, o bien dos son falsas y una verdadera. Marca la que (en este sentido) es distinta a las otras dos. log(n^3) ∉ Θ(log3(n)) Θ(log2(n)) = Θ(log3(n)) Θ(log^2(n)) = Θ(log^3(n)).
¿En qué caso la complejidad temporal del algoritmo de ordenación Mergesort es igual a la complejidad temporal de Quicksort tomando como pivote un elemento al azar del vector? Tanto en el caso peor como en el caso mejor de ambos En el caso peor de ambos En el caso mejor de ambos.
La relación de recurrencia T(n) = 1 + T(n-1) si n > 1; T(1) = 1… Ninguna de las otras dos opciones es cierta. Expresa la complejidad temporal asintótica en el peor de los casos del algoritmo de búsqueda binaria. Expresa el número de llamadas recursivas que hace el algoritmo Quicksort en el peor de los casos.
|
