Algoritmia

En un algoritmo de búsqueda y enumeración, ¿qué podemos decir acerca de la heurística que se utiliza para determinar si un nodo debe expandirse o no?. Que puede equivocarse, por eso se le llama heurística. Que también puede usarse como estrategia de búsqueda. Las otras dos opciones son ambas ciertas.

¿Cuál es el coste de monticulizar (heapify) un vector de tamaño N?. O(NlogN) y Ω(N). Θ(N). O(N) y Ω(1).

Con los valores numéricos almacenados en un fichero, queremos construir un heap(montículo). ¿cuál es la forma más eficiente de proceder?. Almacenar esos valores en un vector y después, reorganizar sus elementos para que estén dispuestos en forma de heap. Almacenar esos valores directamente en un heap que inicialmente está vacío y va creciendo por cada uno de los valores insertados. Ambas formas de proceder son equivalentes en cuanto a eficiencia.

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

¿Cuál es la complejidad temporal en función de n, del siguiente fragmento: for(int i = 0; i < n; i++){ A[i] = 0; for(int j = 0; j < 20; j++) A[i] += B[j]; }. Θ(nlogn). Θ(n^2). Θ(n).

Sea el vector v = {1, 3, 2, 7, 4, 6, 8} cuyos elementos están dispuestos formando un montículo de mínimos. Posteriormente añadimos en la última posición del vector un elemento nuevo con valor 5. ¿Qué operación hay que hacer para que el vector siga representando un montículo de mínimos?. Intercambiar el 7 con el 5. Intercambiar el 8 con el 5. No hay que hacer nada pues el vector v = {1, 3, 2, 7, 4, 6, 8} también es un montículo de mínimos.

¿Cuál es la complejidad, en función de n, del siguiente fragmento: (suponed que A está definido como vector<int>A(n) y sort() es la función de ordenación de la librería estándar de C++, que tiene la mejor complejidad, temporal y espacial, posible para un algoritmo de ordenación de propósito general.) std::sort(begin(A), end(A)); int acc = 0; for(auto i : A) acc += i;. Θ(nlogn). Θ(n^2). Θ(n).

Para resolver la versión general del problema de la mochila con n objetos y carga máxima W, hemos escrito un algoritmo de divide y vencerás que, sucesivamente, divide el problema en dos subproblemas; cada uno de ellos toma la mitad de los objetos y la mitad de la carga máxima de la mochila. El caso base ocurre cuando solo hay un objeto que se añade a la solución si cabe en la fracción de carga máxima que corresponde a ese subproblema, y si no cabe se descarta. Asumiendo que n y W son potencias exactas de 2, ¿qué podemos decir de esta solución?. Que con los resultados de los subproblemas no siempre se puede componer la solución del problema original. Que no cumple el teorema de reducción. Que, aunque con los resultados de los subproblemas se puede componer la solución del problema original, esta formulación no mejora la solución estudiada en clase.

Queremos aplicar la técnica de memoización a la siguiente función recursiva: double f(double x) { if(x <= 2) return x; return f(sqrt(x-1)) + f(sqrt(x-2)); } ¿Cuál sería un buen candidato para el almacén? (La función sqrt() obtiene la raíz cuadrada; xMax es el valor de x en la primera llamada.). vector< vector<double> > M(xMax+1,vector<double>(xMax+1)). vector<double> M(xMax+1). Ninguna de las otras dos opciones es válida.

¿Cuál es la característica principal de un algoritmo voraz aplicado al problema del senderista?. Explora exhaustivamente todas las posibles soluciones del mapa de coordenadas. Toma decisiones locales óptimas en cada paso sin considerar el panorama general. Utiliza una estrategia basada en estimaciones heurísticas para encontrar la solucón óptima.

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 como cota optimista para un nodo?. 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.

¿Cómo se utiliza la cola de prioridad en el algoritmo de ramificación y poda para resolver el problema del senderista?. Se agregan los nodos a la cola de prioridad en orden aleatorio para explorar todas las posibilidades. Los nodos se agregan a la cola de prioridad según una estimación heurística para priorizar los caminos más prometedores. Los nodos se extraen de la cola de prioridad según se vayan obteniendo.

Un fontanero tiene una jornada de Q cuartos de hora (es así como se organiza la agenda) y tiene C clientes. El trabajo del cliente i tarda qi cuartos de hora y el fontanero le cobra un precio pi. Es posible que no pueda atender todos los clientes en la jornada, que nunca puede alargar. Este problema tiene una solución bien conocida que permite elegir qué clientes visitar para que la suma cobrada al final de la jornada sea la máxima. ¿Qué podemos decir de esta solución?. Que se ha de implementar forzosamente con un algoritmo de búsqueda y enumeración como el de vuelta atrás. Que la organización de la agenda en cuartos de hora permite obtener una solución de complejidad temporal Θ(QC) y complejidad espacial Θ(Q). Que no se puede implementar con una solución de “divide y vencerás” con memoización.

Con respecto a los algoritmos estudiados durante el curso que encuentran el árbol de recubrimiento de mínimo coste, de las afirmaciones siguientes, 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 diferente de las otras dos. El algoritmo de Kruskal va construyendo un bosque de árboles que va uniendo hasta que acaba con un árbol de recubrimiento de coste mínimo. El algoritmo de Prim se puede acelerar notablemente si los vértices se organizan en una estructura union-find. La complejidad temporal del algoritmo de Prim es cúbica con respecto al número de vértices del grafo.

Se dispone de un conjunto de n valores numéricos dispuestos en forma de montículo y se desea obtener el valor de la suma de todos los que al menos tienen un hijo (es decir, no son nodos hoja). ¿Cuál es la complejidad temporal del mejor algoritmo que se puede escribir?. O(n). O(logn). O(nlogn).

¿Qué inconveniente presenta la siguiente función? void maze(const Maze &maze, vector<vector<bool>> &visited, Point ¤tPoint, size_t currentLength, size_t ¤tBestLength) { if (currentPoint == maze.exit()) { currentBestLength = min(currentBestLength, currentLength); return; } for (auto step : allSteps) { Point next = currentPoint.next(step); if (maze.is_valid(next) && !visited[next.x()][next.y()] && currentLength < currentBestLength) { visited[next.x()][next.y()] = true; maze(maze, visited, next, currentLength + 1, bestLength); visited[next.x()][next.y()] = false; } } return; }. Que no detecta todos los subproblemas repetidos que pueden aparecer. Que la poda basada en la mejor solución hasta el momento se puede mejorar fácilmente. Las otras dos opciones son ambas ciertas.

Una empresa de transportes dispone de M vehículos para repartir N paquetes, todos al mismo destino. Cada paquete i tiene un peso Pi y se tiene que entregar antes de que transcurra un tiempo TPi . Por otro lado, cada vehículo j puede transportar una carga máxima Cj , tarda un tiempo TVj para llegar al destino y consume una cantidad Lj de litros de combustible, independientemente de la carga que transporta. Imaginad un algoritmo de vuelta atrás que obtenga la manera en que se tienen que transportar los objetos (en qué vehículo j tiene que ir cada objeto i) para que el consumo sea el mínimo. ¿Cuál sería una buena cota optimista?. La solución voraz del problema de cargar cada paquete en el camión de menor consumo donde cada paquete llega a tiempo, sin tener en cuenta si el camión se sobrecarga o no. La solución voraz del problema de cargar cada paquete en el camión de menor consumo, sin sobrecargarlo, sin tener en cuenta si el paquete llega a tiempo o no. Ambas son cotas optimistas válidas.

Indica cuál es la complejidad temporal en función de n, donde A es un vector de enteros y k es una constante que no depende de n, del fragmento siguiente: for( int i = k; i < n - k; i++){ A[i] = 0; for( int j = i - k; j < i + k; j++ ) A[i] += B[j]; }. Θ(k). Θ(n^2). Θ(n).

Dado el problema del senderista, estamos interesados en obtener, para cada casilla accesible del mapa de coordenadas, el camino de coste mínimo entre el origen y esa casilla. ¿Qué esquema es el más apropiado en este caso?. La versión iterativa de programación dinámica. Memoización. Ambas técnicas resultan equivalentes.

¿Qué obtenemos con la siguiente declaración de C++: priority queue<nodo> pq; ?. Un heap o montículo de máximos. Un heap o montículo de mínimos. Un heap o montículo sin orden establecido ya que no se ha definido la función de comparación.

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

Dada la versión general del problema del senderista ¿Qué ocurre si la cota optimista de un nodo resulta ser el valor que se obtiene de una solución factible pero que no es la mejor en el subárbol generado por ese nodo?. Nada especial, las cotas optimistas se corresponden con soluciones factibles que no tienen por qué ser las mejores. Que el algoritmo sería incorrecto pues podría descartarse el 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.

¿Qué hace la siguiente función? void f( vector<int>&A ) { priority queue<int>pq; for( auto i : A ) pq.push(A[i]); A.clear(); while( !pq.empty() ) { A.push back(pq.top()); pq.pop(); } }. Invierte el vector A (el último elemento quedará el primero). Nada, deja el vector A como estaba. Ordena el vector A.

Dado el problema del senderista, si solo se desea conocer el coste mínimo para llegar al destino, ¿cuál es la mejor complejidad temporal y espacial que se puede conseguir si se aplica programación dinámica?. Temporal Θ(nm) y espacial Θ(mín(m, n)). Ninguna de las otras dos opciones es cierta. Temporal Θ(nm) y espacial Θ(nm).

Dados dos nodos cualesquiera del árbol de búsqueda de ramificación y poda, en general, ¿se puede saber con certeza cuál está más cerca de la solución óptima del problema a resolver?. Sí, el que tiene mejor cota optimista. Sí, el que tiene mejor cota pesimista. Sí, pero solo si ambos nodos son hoja.

Dada la versión general del problema del senderista, se pretende resolver mediante vuelta atrás haciendo uso de un mecanismo de poda basado en la mejor solución encontrada hasta el momento. ¿Cuándo se podaría un nodo?. Cuando el valor de su cota optimista supere al valor de la mejor cota pesimista encontrada hasta el momento. Cuando el valor de su cota pesimista supere al valor de su cota optimista. Cuando el valor de su cota optimista supere al valor de su cota pesimista.

La distancia de Manhattan (d) entre dos puntos (x1, y1) y (x2, y2) viene dada por la expresión d = |x1 - x2| + |y1 - y2|. ¿Podría utilizarse como cota optimista para resolver la versión general de problema del senderista?. No, puesto que incumple la condición para ser una cota optimista correcta. Sí, pero hay otros estimadores que se suelen comportar mejor ante este problema. Sí, y además tiene la ventaja de que se puede calcular con complejidad temporal constante.

¿De qué clase de complejidad es la solución de la siguiente relación de recurrencia? f(n) = n(n-1) + f(n-1) si n > 0 f(0) = 1 si n = 0. f(n) ∈ Θ(n^2). f(n) ∈ Θ(n^3). Ninguna de las otras dos opciones es cierta.

Estamos resolviendo el problema del senderista. Ya hemos obtenido el almacén de resultados parciales. ¿Con qué complejidad temporal podemos obtener un camino de salida de longitud mínima si es que existe?. Θ(mn). Θ(m+n). Ω(mín(n,m)) y O(mn).

Se pretende resolver la versión general del problema del senderista mediante un algoritmo de búsqueda y enumeración. Para reducir el número de nodos explorados, ¿qué mecanismo de los relacionados garantiza encontrar la solución y resulta a priori más eficaz?. Usar una matriz de enteros donde se almacena la longitud del mejor camino encontrado hasta el momento que llega a cada casilla del laberinto. Cada casilla pi, jq de la matriz se inicializa con el valor infinito. Usar una matriz de enteros donde se almacena la longitud del mejor camino encontrado hasta el momento que llega a cada casilla del laberinto. Cada casilla (i, j) de la matriz se inicializa con la solución de programación dinámica para la versión restringida del problema asumiendo que el destino es (i, j). Usar una matriz de booleanos para descartar caminos que llegan a una casilla ya visitada. Cada casilla (i, j) de la matriz se inicializa con el valor false.