exámen ada

En un problema de minimización mediante ramificación y poda: La cota pesimista parcial de un nodo tiene que se siempre mayor o igual que la cota pesimista del nodo inicial. La cota pesimista parcial de un nodo tiene que ser siempre menor o igual que la mejor solución en curso. Ninguna de las otras opciones es correcta.

Cuál es el propósito principal de un Heap en el algoritmo de ordenación HeapSort. Permitir la extracción repetida del elemento máximo o mínimo de manera eficiente. Lograr una ordenación parcial del vector, es decir, que algunos elementos queden en la posición correcta pero otros no. Facilitar la inserción eficiente de elementos en el nuevo vector ordenado.

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 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. 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.

Dado el siguiente programa recursivo: si quisiéramos reescribirlo para usar programación dinámica ¿cuál es la complejidad espacial más ajustada del algoritmo?. O(1). O(n2). O(n).

Asumiendo un modelo de computación en el que los números enteros pueden ser arbitrariamente grandes cuál es la complejidad temporal asintótica de la siguiente función (en función del tamaño del problema)?. Ninguna de las otras opciones es correcta. O(n). O(logn).

La búsqueda binaria puede considerarse una instancia del esquema: Divide y vencerás. Programación dinámica. Algoritmo voraz.

Decid cuál de estas tres afirmaciones es cierta: El valor óptimo de la mochila discreta es una cota superior del valor óptimo de la mochila continua correspondiente. El valor óptimo de la mochila continua es una cota superior del valor óptimo de la mochila discreta correspondiente. las otras dos afirmaciones son falsas.

Sobre el problema del Viajante de comercio resuelto mediante vuelta atrás, dos afirmaciones son verdaderas y una falsa, o viceversa. Señala la que difiere de las otras dos. Aún con una implementación sin cotas, es un problema con complejidad temporal abordable. El cálculo incremental del recorrido y el uso de cotas (pesimistas y optimistas) reducen notablemente la complejidad temporal en el peor caso. Las otras dos afirmaciones son falsas.

Se pretende obtener la complejidad temporal en el caso más desfavorable de la siguiente función. O(n log n). las otras dos opciones son ciertas. O(n log n).

Sobre el esquema de programación dinámica, dos afirmaciones son verdaderas y una falsao viceversa. Señala la que difiere de las otras dos. Se apoya en el esquema de divide y vencerás, siendo una mejora de éste en términos de eficiencia. Es recomendable, aunque no imprescindible, que el problema cumpla con la condición de estructura óptima. Solo se refiere a la conversión de un algoritmo recursivo en iterativo para mejorar su eficiencia.

Estamos resolviendo el problema del laberinto (versión general) mediante ramificación y poda empleando una estrategia dirigida de priorización de nodos basada en una cola de prioridad. Recuerda que cada iteración del bucle principal consiste en extraer el nodo de máxima prioridad de la cola, expandirlo, y, para cada nodo expandido: comprobar si es factible, actualizar la solución en curso con la cota pesimista parcial, y añadirlo a la cola si es prometedor. La mejor complejidad asintótica que se puede conseguir para una iteración del bucle principal es: O(1). O(log n), siendo en el número de nodos en la cola. O(n), siendo n el número de nodos en la cola.

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

Cual es la complejidad temporal de la aproximación voraz a la solución de la versión restringida del problema del laberinto. O(n + m). las otras dos opciones son ambas ciertas. O(max(n,m)).

Dada la versión restringida del problema del laberinto m x n, estamos interesados, no solo en obtener la longitud del camino de salida más corto; también nos interesa la longitud del camino más corto entre el origen y cualquier casilla accesible del laberinto ¿con que complejidad temporal, en funcion de n y m, podria obtenerse?. O(m * n). Ninguna de las dos opciones es correcta. O(3^(m + n).

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

En un algoritmo de ramificación y poda, conforme se va completando un nodo, ¿que ocurre con sus cotas?. su cota pesimista debería aproximarse a la mejor solución que puede obtenerse a partir de ese nodo. su cota optimista deberia aproximarse a la mejor solución que puede obtenerse a partir de ese nodo. las otras dos afirmaciones son ciertas.

b. b. a.

Respecto a los algoritmos voraces ¿cual de las siguientes afirmaciones es correcta?. Siempre encuentran una solución, aunque no siempre sea óptima. Siempre hallan la mejor solución , aunque requieren mucho tiempo al explorar todas las posibilidades. Las otras dos afirmaciones son falsas.

En el algoritmo de Kruskal ¿que se selecciona en cada paso?. el vértice con menor grado en el grafo. la arista de menor peso que conecta un vértice visitado con otro sin visitar. la arista de menor peso que no forma ciclos.

Respecto a la estrategia de ramificación y poda... Siempre produce algoritmos más eficientes que la vuelta atrás. La principal diferencia con la de vuelta atrás es el uso de estrategias Least Cost. Las otras dos afirmaciones son ciertas.

Dada la versión restringida del problema del laberinto resuelto mediante programación dinámica iterativa comenzando en la entrada al laberinto ¿qué representa el contenido de cada casilla (i, j) del almacén?. la longitud del camino más corto desde esa casilla hasta el destino. la longitud del camino más corto que llega a esa casilla desde el origen. la longitud del camino más corto desde esa casilla hasta el destino pero solo si la casilla forma parte del camino óptimo.

En la resolución del problema de la función compuesta mínima mediante vuelta atrás, ¿que ocurriria si no se limitara la profuncidad del arbol de llamadas recursivas con valor máximo M?. El programa acabaría encontrando la solución óptima, pero a costa de una complejidad temporal prohibitiva. se podría conseguir que el programa siempre encontrara solución poniendo un 1 en el vector solución antes que un 0. salvo en casos muy raros, el programa nunca acabaría.

disponemos de dos funciones de coste f(n) y g(n) tal que f E O(g). ¿puede existir un valor x para el que f(x) > g(x)?. si, pero tambien existirá un valor n0 tal que ... si, y además es posible que el valor n0 tal que ... no exista. no, no puede existir ese valor.

Indica cual de estas posibles cotas pesimistas para el problema de laberinto (version general) seria la más ajustada. la longitud del camino actual mas la de su continuación hasta el final del mapa mediante un algoritmo voraz que solo considera movimientos hacia E, SE o S. la longitud del camino actual. la longitud del camino actual mas la de su continuación hasta el final del mapa mediante un algoritmo de programación dinamica que solo considera movimientos hacia E, SE o S.

si el coste temporal de un algoritmo es T(n), cual de las siguientes situaciones es imposible. a. b. c.

Dada la version general del problema del laberinto m x n, la distancia de manhattan entre las casillas (i, j) y (m, n) viene dada por la suma del número movimientos del tipo horizontal que quedan hasta llegar al extremos derecho del laberinto(n - j) y los del tipo vertical que quedan hasta llegar al extremo derecho del laberinto (m - i). ¿para que puede resultar util esta distancia?. para obtener cotas optimistas. para obtener cotas pesimistas. ninguna de las otras dos opciones es válida.

con respecto a la versión general (sin restricciones adicionales) del problema de la mochila sin fraccionamiento, de las siguientes afirmaciones dos son verdaderas y una es falsa, o viceversa. señala la que difiere de las otras dos. .. cumple la propiedad de subestructura optima y por lo tanto se puede plantear una solución de divide y vencerás. ... no se conoce ninguna reducción en subproblemas que cumpla el teorema de reducción. ... tiene una solución eficiente utilizando programación dinámica.

asumiendo un modelo de computación en el que el número de bits utilizados para representar enteros está acotado ¿cual es la complejidad temporal asintotica de la siguiente función (en funcion del tamaño del problema?. en este caso no tiene sentido hablar de complejidad temporal asintotica. O(n). O(n log n).

indica cual de estos criterios para ordenar la lista de nodos vivos permite resolver más rápido el problema de la función compuesta mínima. busqueda en anchura. busqueda en profundidad. ambos criterios son válidos y no afectan al tiempo de ejecución.

di cual de estos resultados de coste temporal asintotico es falsa. la ordenación de un vector usando el algoritmo Quicksort requiere en el peor caso un tiempo en omega(n2). la ordenación de un vector usando el algoritmo mergesort requiere en el peor caso un tiempo en omega(n2). la busqueda binaria en un vector ordenado requiere en el peor caso un teimpo en O(log n).

dada la siguiente función. O(log n). O(n2). O(n).

cual de las siguientes formulaciones expresa mejor el coste temporal asintotico de la siguiente funcion. a. b. c.

cual es el cose temporal asintotico de la siguiente función. O(n). O(n log n). O(log2 n).

En la resolución del problema de corte de tubos mediante programación dinámica: la programación dinámica recursiva (memoización) siempre resuelve menos subproblemas que la programación dinámica iterativa. la programación dinámica recursiva (memoización), dependiendo de la instancia del problema, puede resolver menos subproblemas que la programación dinámica iterativa. la programación dinámica recursiva (memoización) y la programación dinámica iterativa siempre resuelven los mismos subproblemas.

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

en cuanto al problema del cambio que consiste en formar una suma M con el mínimo número de monedas posibles, extraidas (con repetición) de un conjunto C. es posible diseñar una solución basada en el esquema divide y vencerás que siempre encuentra el valor óptimo. es posible diseñar una solución voraz que siempre encuentra el valor óptimo. las otras dos opciones son correctas.

en la resolución del problema del laberinto (versión general), el uso de una cota pesimista parcial sirve para: evitar ciclos. descartar nodos cuando se llega a una posición del mapa mediante un camino más largo que el mejor camino para llegar a esa posición. mejorar la solución en curso antes de llegar a una hoja.

la solución voraz del problema de la mochila continua, es decir, con objetos fraccionables, tiene una complejidad temporal asintotica de: O(log n). O(n). O(n log n).

respecto a los algoritmos de vuelta atrás ¿cual de las siguientes afirmaciones es correcta?. siempre encuentran una solución, aunque no siempre sea óptima. siempre hallan la mejor colución, aunque requieren mucho tiempo al explorar todas las posibilidades. las otras dos afirmaciones son falsas.

si un algoritmo de ramificación y poda utiliza una cola de prioridad con un criterio inadecuado ¿que ocurrirá muy probablemente?. aumentará considerablemente el número de instancias que están en el caso peor. seguirá siendo más eficiente que la vuelta atrás gracias aluso de la cola de prioridad. las otras dos opciones son correctas.