Test UNED PREDA - Examenes 2012-2021

Dado el grafo no dirigido de la figura, la aplicación del algoritmo de cálculo de los puntos de articulación (y de su árbol de recubrimiento asociado) da como resultado el vector bajo[] siguiente: [1,1,3,1,5,5,5]. [1,2,3,4,1,6,7]. [1,3,3,1,1,3,3]. Ninguna de las anteriores.

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado con programación dinámica. Supongamos que se dispone de 5 objetos con pesos: 1,3,4,5,7 y beneficios: 2,5,10,14,15 respectivamente, y un volumen máximo de 8. Identifica cuál de las siguientes respuestas correspondería al contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 5, si dichos objetos se consideran en orden creciente de pesos. 0 2 2 5 10 12 12 15 15. 0 2 2 5 10 14 16 16 19. 0 2 2 5 10 12 14 16 19. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Se pide detallar el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=7, tomando como nodo origen el nodo 1. [10,15,12,6,15,7]. [10, ∞, ∞,6,15,7]. [10,∞,∞,6,∞,∞]. Ninguna de las anteriores.

En un problema de mochila con objetos fraccionables tenemos n = 8 objetos disponibles. Los pesos de los objetos son w= (8, 7, 6, 5, 4, 3, 2, 1) y los beneficios son v= (10, 9, 8, 7, 6, 5, 4, 3). ¿Cuál es el beneficio óptimo para este ejemplo, suponiendo que la capacidad de la mochila es M = 9?. 12. 15. 16.5. Ninguna de las anteriores.

Considérese el vector v[1..n] = [6,5,5,2,5,5,3,2,2] cuál de las siguientes opciones es cierta: El vector v es un montículo de máximos. El vector v no es un montículo de máximos porque el elemento v[4] = 2 debe ser flotado. El vector v no es un montículo de máximos porque el elemento v[4] = 2 debe ser hundido. Ninguna de las anteriores.

Se dispone de un vector, V, que almacena números enteros en orden estrictamente creciente, y se desea averiguar si existe algún elemento que cumpla V[i]=i. ¿Cuál sería la estrategia más eficiente para resolver el problema?. Algoritmo voraz. Divide y vencerás. Programación dinámica. Ninguna de las anteriores es aplicable al problema.

Una empresa de mensajería tiene n repartidores con distintas velocidades según el tipo de envío. Se trata de asignar los próximos n envíos, uno a cada repartidor, minimizando el tiempo total de todos los envíos. Para ello se conoce de antemano la tabla de tiempos T[1..n,1..n] en la que el valor tij corresponde al tiempo que emplea el repartidor i en realizar el envío j. Se pide: Voraz. Dinámica. Vuelta atrás. Ramificación y poda. Divide y vencerás.

Identifique cuál de las siguientes secuencias de código implementa un recorrido en anchura de una componente conexa de un grafo: a. b. c. ninguna de las opciones.

En una carrera de coches por el desierto uno de los principales problemas es el abastecimiento de gasolina. Uno de los participantes está decidido a ganar y ha calculado que con el tanque de gasolina lleno puede recorrer M km. sin parar. El participante dispone de un mapa que le indica las distancias entre las gasolineras que hay en la ruta y cree que, parándose a repostar el menor número de veces posible, podrá ganar. Para ayudarle hay que diseñar un algoritmo que le sugiera en qué gasolineras debe hacerlo. Hay que tener en cuenta que hay una única ruta posible. Indique de los esquemas siguientes cuál es el más adecuado: El esquema voraz. El esquema programación dinámica. El esquema de vuelta atrás. El esquema de ramificación y poda.

¿Cuántos componentes fuertemente conexos existen en el grafo de la siguiente figura?. Uno solo, formado por todo el grafo. Dos. Tres. Más de tres.

Dado el grafo no dirigido de la figura, indique cuál sería el orden en que se seleccionarían (pasan a pertenecer al árbol) los nodos al aplicar el algoritmo de Prim comenzando por el nodo A: A, F, E, C, B, D. A, B, C, E, D, F. A, C, D, B, F, E. Ninguno de los anteriores.

Dado el vector v=[5,6,9,3,4,1] y el algoritmo Quicksort, los vectores argumento de la primera invocación recursiva, con pivote v[1] = 5, son: [1,3,4,5] y [6,9]. [5,6,9] y [5,3,4,1]. [5] y [6,9,3,4,1]. [1] y [5,6,9,3,4].

Dado el problema de la mochila donde tenemos una mochila de capacidad M, n objetos con beneficios b1, b2, b3, … bn y pesos p1, p2, p3, … pn. y siendo el objetivo maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M, en el caso de que los objetos sean fraccionables, la resolución del mismo: Debe resolverse mediante un esquema voraz ya que no es eficiente realizarlo mediante ramificación y poda. Debe hacerse mediante ramificación y poda, ya que no es posible resolverlo utilizando un esquema voraz. Sólo puede resolverse mediante un esquema de programación dinámica. Puede hacerse mediante un esquema voraz pero no es posible resolverlo mediante ramificación y poda.

Se quiere realizar en un soporte secuencial (cinta de dos caras) una recopilación de canciones preferidas. Se dispone de una lista de n canciones favoritas, junto con la duración individual de cada una. Lamentablemente, la cinta de T minutos no tiene capacidad para contener todas las canciones, por lo que se les ha asignado una puntuación (cuanto más favorita es, mayor es la puntuación). Se pretende obtener la mejor cinta posible según la puntuación, teniendo en cuenta que las canciones deben caber enteras y no es admisible que una canción se corte al final de una de las caras. Voraz. Ramificación y poda. Divice y vencerás. Programación dinámica. Vuelta atrás.

Considérese el vector [10,7,7,4,3,1] que representa un montículo. ¿Cuál sería la representación resultante de insertar en este montículo el valor 11 usando la función flotar?. [11,7,7,4,3,1,10]. [10,7,11,4,3,1,7]. [10,7,11,4,3,1,7]. Ninguna de las opciones anteriores.

Los residentes de una ciudad no quieren pavimentar todas sus calles (que son de doble sentido), sino sólo aquellas que les permitan ir de una intersección a otra cualquiera de la ciudad con comodidad. Quieren gastarse lo menos posible en la pavimentación, teniendo en cuenta que el coste es directamente proporcional a la longitud de las calles que hay que pavimentar. El alcalde querría saber qué calles tiene que pavimentar para gastarse lo menos posible. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

Suponga un algoritmo que dadas dos listas de tamaños n y m: A = a1,. . .an y B = b1,. . . ,bm dé como resultado la lista de aquellos elementos que pertenecen a A pero no a B. Se asume que A y B no contienen elementos duplicados, pero no que éstos estén acotados. Indique cuál de los siguientes costes se ajusta más al del algoritmo que puede resolver el problema con menor coste: O(n log m + m log m). O(n log m + m2). Máx (O (n log n), O(m log m)). O(nm).

Dado un grafo con n vértices y a aristas sobre el que se pueden realizar las siguientes operaciones: esAdyacente, borrarVertice y añadirVertice. ¿Cuál es la complejidad de cada una de las operaciones anteriores según se utilice una matriz de adyacencia (MA) o una lista de adyacencia (LA)?. a. b. c. d.

Indique cuál de las siguientes afirmaciones es cierta: La programación dinámica se puede emplear en muchos de los problemas que se resuelven utilizando el esquema divide y vencerás. La programación dinámica tiene como principal ventaja que supone un decremento tanto en coste computacional como en espacio de almacenamiento. El esquema de programación voraz se aplica a problemas de optimización en los que la solución se puede construir paso a paso comprobando, en cada paso, la secuencia de decisiones tomadas anteriormente. El esquema de ramificación y poda es el más indicado a utilizar en el caso que se deseen encontrar todas las soluciones posibles a un problema dado.

En el recorrido mediante doble hashing, la función h’(x) debe cumplir: Necesariamente debe ser h’(x) ≠ 0. h’(x) debe tener la forma h’(x) = 2h(x) + c, con c constante. Se debe cumplir que h’(x) < h(x) + c, con c constante. Ninguna de las anteriores es cierta.

Teseo se adentra en el laberinto en busca de un minotauro que no sabe dónde está. Se trata de implementar una función ariadna que le ayude a encontrar el minotauro y a salir después del laberinto. El laberinto debe representarse como una matriz de entrada a la función cuyas casillas contienen uno de los siguientes tres valores: 0 para “camino libre”, 1 para “pared” (no se puede ocupar) y 2 para “minotauro”. Teseo sale de la casilla (1,1) y debe encontrar la casilla ocupada por el minotauro. En cada punto, Teseo puede tomar la dirección Norte, Sur, Este u Oeste siempre que no haya una pared. La función ariadna debe devolver la secuencia de casillas que componen el camino de regreso desde la casilla ocupada por el minotauro hasta la casilla (1,1). Voraz. Divide y vencerás. Ramificación y poda. Vuelta atrás. Programación dinámica.

Sea el grafo dirigido de la siguiente figura. ¿Cual de las siguientes afirmaciones es cierta?. Un posible recorrido en anchura visitaria los nodos en orden {D,B,C,E,F,A,G}, si se toma el nodo D como nodo de partida. Un posible recorrido en profundidad visitaria los nodos en orden {D,B,E,A,G,C,F}, si se toma el nodo D como nodo de partida. El nodo E es un punto de articulación. Todas las afirmaciones son ciertas.

Indique cual de las siguientes afirmaciones es cierta. El coste del algoritmo para fusionar dos subvectores ordenados que se utiliza en la ordenación por fusión es O(n), siendo n la suma de los tamaños de los vectores. El coste del algoritmo que soluciona el problema del coloreado de grafos mediante el esquema de vuelta atrás es O(N^M) siendo m el número de colores y n el número de nodos. El coste del algoritmo de Kruskal es O(N^2) siendo n el número de nodos del grafo. El coste del algoritmo de ordenación rápida en el caso mejor es O(n^2) siendo n el número de elementos de larray.

Considéres el vector v[1..n] = [2,3,5,3,4,5,7,5,6]. Indica cuál de las siguientes opciones es cierta: Es un montículo de mínimos. No es un montículo de mínimos porque v[5] = 4 debe ser flotado. No es un montículo de mínimos porque v[5] = 4 debe ser hundido. Ninguna de las anteriores.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad M, n objetos con beneficios b1,b2,b3,...,bn y pesos p1,p2,p3,...,pn. El objetivo es maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M. Indica, de los esquemas siguientes, cuál es el más adecuado y eficiente en el caso de que cada objeto pueda meterse en la mochila entero o fraccionado. El esquema voraz utilizando como criterio de selección escoger el objeto de más valor de los que quedan. El esquema voraz utilizando como criterio de selección el objeto cuyo valor por unidad de peso sea el mayor de las que quedan. El esquema de vuelta atrás calculando todas las soluciones posibles y escogiendo la mejor. El esquema de ramificación y poda.

Para resolver un determinado problema hemos diseñado un algoritmo de tipo divice y vencerás. ¿Cuál de las siguientes afirmaciones es falsa?. La resolución debe alcanzar un caso trivial que se pueda resolver sin realizar nuevas descomposiciones. El problema se resuelve por divisiones sucesivas en subproblemas, que pueden ser demayor o de menor tamaño que el de partida. Los algoritmos basados en este esquema pueden requerir un paso de combinación de las soluciones parciales. El algoritmo de la búsqueda binaria aplica la estrategia divide y vencerás.

Sea un procesador que ha de atender n procesos. Se conoce de antemano el tiempo que necesita cad aproceso. Se desea determinar en qué orden se han de atender los procesos par aminimizar la suma del tiempo que los procesos permanecen en el sistema. En relación a este problema, ¿cuál de las siguientes afirmaciones es cierta?. El coste del algoritmo voraz que resuelve el problema es, en el mejor de los casos, O(N^2). Suponiendo tres clientes con tiempos de servicio t1=5, t2=10 y t3=3, el tiempo mínimo de estancia posible es de 26 segundos. Suponiendo tres clientes con tiempos de servicio t1=5, t2=10 y t3=3, el tiempo mínimo de estancia posible es de 31 segundos. Todas las afirmaciones anteriores son falsas.

Dado el conjunto de carácteres alfabéticos, se quieren generar todas las palabras de cuatro letras que cumplan las siguientes condiciones: La primera letra debe de ser vocal, Solo pueden aparecer dos vocales seguidas si son diferentes, No puede haber ni tres vocales ni tres consonantes seguidas, Existe un conjunto C de parejas de consonantes que no pueden aparecer seguidas. Desarrolla un algoritmo que permita solucionar este problema con el menor coste. Voraz. Dinamica. Ramificación y poda. Vuelta atrás. Divide y vencerás.

Se tiene una tabla hash con n= 23 índices ocupados y de tamaño M= 1000. El factor de carga δ será: 0,023, es decir n/M. 0,046, es decir 2n/M. -3,7723, es decir Ln (n/M). Ninguna de las anteriores.

Dado el siguiente grafo dirigido indique cuál sería el valor del vector especial[] en el primer y penúltimo paso del algoritmo de Dijkstra: [50,30,100,10] y [35,30,20,10]. [50,30,100,10] y [40,30,20,10]. [50,30,100,10] y [35,30,100,10]. Ninguna de las anteriores.

Considere dos vectores f y g de n elementos que representan los valores que toman dos funciones en el intervalo [0..n-1]. Los dos vectores están ordenados, pero el primero f es un vector estrictamente creciente (f[0] < f[1] < … < f[n-1]), mientras g es un vector estrictamente decreciente (g[0] > g[1]>…> g[n-1]). Las curvas que representan dichos vectores se cruzan en un punto concreto, y lo que se desea saber es si dicho punto está contenido entre las componentes de ambos vectores, es decir, si existe un valor i tal que f[i] = g[i] para 0 ≤ i ≤ n 1. La figura muestra un ejemplo en el que las gráficas se cruzan en i=8 que se corresponde con el valor 25 en ambas curvas. Se busca un algoritmo que compruebe si el punto de cruce está contenido en las componentes de ambos vectores. ¿Cuál de las siguientes opciones es cierta?. Se puede encontrar un algoritmo recursivo de coste logarítmico. El algoritmo más eficiente que se puede encontrar es O(n). El algoritmo más eficiente que se puede encontrar es O(n2). Ninguna de las anteriores.

¿Cuál de las siguientes afirmaciones es falsa?. El algoritmo de ordenación por fusión (mergesort) es O(n log n). La eficiencia del algoritmo de ordenación rápida (quicksort) es independiente de que el pivote sea el elemento de menor valor del vector. El algoritmo de ordenación rápida en el caso peor es O(n2). El algoritmo de ordenación basada en montículos (heapsort) es O(n log n).

¿Cuál de las siguientes afirmaciones es falsa?. El grado de un vértice de un grafo no dirigido es el número de aristas que salen o entran en él. Un camino en un grafo dirigido es una secuencia finita de arcos entre dos vértices, tal que el vértice del extremo final de cada arco coincide con el del extremo inicial del arco siguiente. Un grafo nulo es un grafo sin vértices. La longitud de un camino es el número de aristas y nodos que contiene.

Dado el siguiente montículo indique cual de las siguientes afirmaciones es falsa. El montículo propuesto es un montículo de máximos. El vector que lo representa de forma correcta es [15,13,12,8,9,5,8,7,5,3,4,2]. El orden de complejidad de la operación de inserción de un nuevo elemento en el montículo es O(n). Los montículos son estructuras de datos de gran utilidad a la hora de implementar colas de prioridad.

Se tienen 3 palos verticales y n discos agujereados por el centro. Los discos son todos de diferente tamaño y en la posición inicial están insertados en el primer palo ordenados en tamaños en sucesión decreciente desde la base hasta la altura. El problema consiste en pasar los discos del 1er al 3er palo, utilizando el segundo como auxiliar, observando las siguientes reglas: a) Se mueven los discos de 1 en 1. b) Nunca un disco puede colocarse encima de uno menor que éste. Voraz. Ramificación y poda. Divide y vencerás. Programación dinámica. Vuelta atrás.

¿Cuál de las siguientes afirmaciones es cierta con respecto al coste de algunos algoritmos y su eficiencia?. El algoritmo de Kruskal tiene un coste que está en O(n log n). El algoritmo de Prim cuando se combina el uso de la lista de adyacencia con el uso de un montículo es más eficiente cuando el grafo es denso porque de esta manera el coste está en O(n2 log n). El coste del algoritmo Quicksort en el caso peor es de orden O(n log n). La función que crea un montículo a partir de una colección de valores, si se utiliza el procedimiento Hundir puede llegar a tener un coste lineal.

Sea un grafo no dirigido representado con la siguiente matriz de adyacencia: Si se utiliza el algoritmo de Kruskal para calcular un árbol de recubrimiento mínimo, indica cuál de las siguientes secuencias de aristas (que incluye las rechazadas) representa el orden en el que las evalúa el algoritmo: {5,7},{2,4},{4,6},{3,4},{2,3},{1,5},{6,7}. {5,7},{2,4},{4,6},{3,4},{1,5},{6,7},{5,6}. {5,7},{1,5},{6,7},{4,6},{2,4},{4,3}. {1,5},{5,7},{6,7},{4,6},{2,4},{4,3}.

Con respecto a la resolución de colisiones en las funciones Hash, indicar cuál de las siguientes afirmaciones es cierta: El recorrido lineal permite mayor dispersión de las colisiones que el cuadrático. Si el factor de carga es 1 se puede resolver mediante hashing cerrado. El hashing abierto contempla un método de resolución conocido como “recorrido mediante doble hashing”. Ninguna de las anteriores es correcta.

Durante la ejecución de un algoritmo de Ramificación y Poda se halla una solución que es mejor que la mejor solución existente en ese momento y que mejora la estimación optimista de la cima del montículo. Esto implica que: Definitivamente el algoritmo ha encontrado la solución. Se actualiza la cota y se sigue con la exploración porque no hemos terminado. Se actualiza la cima del montículo y se sigue con la exploración porque no hemos terminado. Ninguna de las anteriores es correcta.

Dado el siguiente grafo, indique cuál sería el orden en que se seleccionarían los nodos (pasan a estar explorados) al aplicar el algoritmo de Dijkstra para encontrar todos los caminos de menor coste desde el nodo 1: {1, 2, 4, 3, 5}. {1, 4, 3, 5, 2}. {1, 2, 3, 4, 5}. Ninguna de las anteriores.

Considérese el vector [10,6,3,5,2,3,2] que representa un montículo. ¿Cuál sería la representación resultante de insertar (función Insertar del texto base) en este montículo el valor 6 usando la función flotar?. [10,6,6,3,3,2,5,2]. [10,6,5,3,6,2,2,3]. [10,6,3,6,2,3,2,5]. Ninguna de las opciones anteriores.

Una pareja decide divorciarse tras 10 años de matrimonio. Deciden repartir su patrimonio a partes iguales. Cada uno de los n activos (indivisibles) que hay que repartir tiene un valor entero positivo. Los cónyuges quieren repartir dichos activos a medias y, para ello, primero quieren comprobar si el conjunto de activos se puede dividir en dos subconjuntos disjuntos, de forma que cada uno de ellos tenga el mismo valor. Voraz. Divide y vencerás. Ramificación y poda. Programación dinámica. Vuelta atrás.

Indique cuál de las siguientes afirmaciones es cierta: El esquema de divide y vencerás obtiene siempre soluciones eficientes de coste O(log n) o O(n·log n). La búsqueda en profundidad recursiva obtiene siempre una eficiencia logarítmica. La ordenación por Quicksort tiene coste O(n2) en el caso peor. Ninguna de las anteriores es cierta.

¿Cuántos componentes fuertemente conexos existen en el grafo de la siguiente figura?. Uno solo, formado por todo el grafo. Dos. Tres. Más de tres.

El enemigo ha desembarcado en nuestras costas invadiendo n ciudades. Los servicios de inteligencia han detectado del número de efectivos enemigos en cada ciudad, ei. Para contraatacar, se dispone de n equipos listos para intervenir y hay que distribuirlos entre las n ciudades. Cada uno de estos equipos consta de dj efectivos entrenados y equipados. Para garantizar el éxito de la intervención en una ciudad es necesario que contemos al menos con tantos efectivos de defensa como el enemigo. Se busca un algoritmo que indique qué equipo debe intervenir en cada ciudad, de forma que se maximice el número de éxitos garantizados. Indica cuál de las siguientes afirmaciones es cierta: El esquema de ramificación y poda es el único que puede resolver de forma óptima el problema. Se puede encontrar una estrategia voraz que permita resolver el problema. El esquema de programación dinámica es el único que puede resolver de forma óptima el problema. El esquema de vuelta atrás es el más apropiado para resolver este problema.

Indica de entre los siguientes, cuál sería el coste mínimo de un algoritmo que dado un vector C[1..n] de números enteros distintos no ordenado, y un entero S, determine si existen o no dos elementos de C tales que su suma sea exactamente S. O(N). O(N^2). O(n log(n)). O(N^2 log(n)).

Dado el siguiente grafo no dirigido: Indique cuál sería el orden en que se seleccionarían las aristas al aplicar el algoritmo de Kruskal: {{A,C},{C,D},{C,B},{B,E},{D,F}}. {{A,C},{B,E},{C,D},{C,B},{A,F}}. {{A,C},{C,D},{A,B},{B,E},{A,F}}. Ninguna de las anteriores.

Indique cuál de las siguientes afirmaciones es cierta: El enfoque de vuelta atrás realiza un recorrido en anchura del árbol implícito que representa el espacio de posibles soluciones del problema. Si se utiliza el enfoque de programación dinámica para calcular el camino de coste mínimo entre cada par de nodos de un grafo, la complejidad temporal es de O(n2). Cuando ambos son aplicables, el enfoque de ramificación y poda se comporta de manera más eficiente que el enfoque voraz en la resolución de problemas de optimización. El hecho de utilizar un algoritmo voraz para obtener la solución de un problema no garantiza que la solución obtenida sea la óptima.

Se considera un tablero n x n y un conjunto de n colores. Cuando a cada casilla se le asigna un color de los n disponibles de tal manera que no se repiten colores en ninguna fila ni en ninguna columna, el tablero se conoce como cuadrado latino. La siguiente figura muestra un ejemplo para n = 5: Se pide diseñar un algoritmo que dados n colores presente todos los cuadrados latinos para un tablero nxn. Voraz. Ramificación y poda. Programación dinámica. Divice y vencerás. Vuelta atrás.

Considérese el vector v=[2,6,8,12,7,5,4]. ¿Cuál de las siguientes opciones es cierta?. El vector v es un montículo de mínimos. v sería un montículo de mínimos si se flotara el elemento de valor 5. v sería un montículo de mínimos si se hundiera el elemento de valor 8. Ninguna de las opciones anteriores.

En el problema de colorear un grafo con n nodos utilizando m colores, de manera que no haya dos vértices adyacentes que tengan el mismo color, una cota superior ajustada del coste de encontrar una solución utilizando un esquema adecuado es del orden de: O(n^2). O(m^n). O(m log n). O(n^m).

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 5 objetos con volúmenes {1,2,5,6,7} y que aportan unos beneficios de {1,6,18,22,28}, respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 11. Indique cuál sería el contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 7, si dichos objetos se consideran en orden creciente de pesos. 0 1 6 7 7 18 19 24 25 25 28 29. 0 1 6 7 7 18 22 24 28 29 29 40. 0 1 6 7 7 18 22 28 29 34 35 40. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Indique el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=4, tomando como nodo origen el nodo 1: [∞, 30,40, ∞]. [50, 30,40, ∞]. [55, 30,40, 80]. Ninguna de las anteriores.

Indica cuál de las siguientes afirmaciones es cierta con respecto a la resolución de colisiones: El método de hashing abierto es siempre más eficiente que el hashing cerrado para la resolución de colisiones. En el método de hashing cerrado con recorrido lineal existe una probabilidad muy baja de colisiones independientemente de los patrones de las claves. En el método de hashing cerrado con recorrido cuadrático es posible garantizar que se van a recorrer todos los elementos de la tabla cuando el número de elementos de la tabla, m, cumple determinadas condiciones. En el método de hashing cerrado con recorrido mediante doble hashing la función h y h’ que se aplican pueden ser iguales cuando el número de elementos de la tabla, m, cumple determinadas condiciones.

Se dispone de cuatro tipos de monedas de valores 1, 2, 4 y 8. Se desea resolver el problema de pagar una cantidad C > 0 utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

La agencia matrimonial Celestina & Co. quiere informatizar parte de la asignación de parejas entre sus clientes. Cuando un cliente llega a la agencia se describe a sí mismo y cómo le gustaría que fuera su pareja. Con la información de los clientes la agencia construye dos matrices M y H que contienen las preferencias de los unos por los otros, tales que la fila M[i, .] es una ordenación de mayor a menor de las mujeres cliente según las preferencias del i-ésimo hombre, y la fila H[i, .] es una ordenación de mayor a menor de los hombres cliente según las preferencias de la i-ésima mujer. Por ejemplo, M[i,1] almacenaría a la mujer preferida por el hombre i y M[i,2] a su segunda mujer preferida. Dado el alto índice de divorcios, la empresa se ha planteado como objetivo que los emparejamientos sean estables. Se considera que una pareja (h , m) es estable si no se dan las siguientes situaciones: 1. Que exista una pareja (h’, m’) con una mujer m’ tal que el hombre h la prefiere sobre la mujer m y además la mujer m’ también prefiere a h sobre h’. 2. Que exista una pareja (h’’, m’’) con un hombre h’’ tal que la mujer m lo prefiere sobre el hombre h y además el hombre h’’ también prefiere a m sobre m’’. La agencia quiere que dadas las matrices de preferencia, un programa establezca parejas evitando las dos situaciones descritas anteriormente. Se pide: Voraz. Ramificación y poda. Programación dinámica. Divide y vencerás. Vuelta atrás.

Dos socios que conforman una sociedad comercial deciden disolverla. Cada uno de los n activos que hay que repartir tiene un valor entero positivo. Los socios quieren repartir dichos activos a medias y, para ello, primero quieren comprobar si el conjunto de activos se puede dividir en dos subconjuntos disjuntos, de forma que cada uno de ellos tenga el mismo valor. ¿Cuál de los siguientes esquemas de los que puedan resolver el problema correctamente es más eficiente?. Esquema voraz. Esquema de divide y vencerás. Esquema de vuelta atrás. Esquema de ramificación y poda.

Dadas las matrices: A1 (2x2), A2 (2x5) y A3 (5x3) y A4 (3x1) siendo E(i,j) el número de operaciones mínimo para resolver la operación Ai x Ai+1 x … x Aj mediante programación dinámica, se pide indicar cuál de las siguientes opciones es cierta. E(2,4) = 25. E(3,4) = 10. E(1,2) = 40. E(2,2) = 10.

Aplicando el algoritmo de Dijkstra al grafo con conjunto de vértices {1,2,…8} y aristas con pesos (entre paréntesis) representadas por la lista de adyacencia adjunta, ¿Cuál de las siguientes NO es un valor correcto para el vector “Especial” D[i] generado por el algoritmo de Dijkstra a lo largo de las iteraciones, representando en cada iteración la distancia mínima hasta el momento entre los vértices 1 e i:?. D = [4,10,2, ∞,8, ∞,∞]. D = [4,10,2, 4,3, 7,∞]. D = [4,9,2, 4,3, 7,∞]. D = [4,10,2, 4,3, 7,19].

Dado el vector M= [5, 6, 12, 1, 7, 9, 3, 7, 1, 11, 3, 2, 8, 6, 5, 9] al que aplicamos el algoritmo de ordenación Quicksort tomando como pivotes los valores M[0] y para una ordenación de menor a mayor. Se pide contestar la opción verdadera: La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [3 5 2 1 3 1 ] y [7 9 11 7 12 8 6 6 9 ] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [6 12 1 7 9 3 7] y [1 11 3 2 8 6 5 9] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [1 1 2 3 3 5] y [6 6 7 7 8 9 9 11 12] con pivote M[0] = 5. La primera recursión del algoritmo genera dos llamadas a quicksort con argumentos [1 3 6 7 7 9 12] y [1 2 3 5 6 8 9 11] con pivote M[0] = 5.

El problema de la liga de equipos consiste en que dados n equipos con n= 2k, se desea realizar una liga de forma que cada equipo puede jugar un partido al día y la liga debe celebrarse en n-1 días, suponiendo que existen suficientes campos de juego. El objetivo sería realizar un calendario que indique el día que deben jugar cada par de equipos. Si este problema se resuelve con un esquema divide y vencerás, considerando que el caso trivial se da cuando la liga consta de 2 equipos, la descomposición se realiza dividiendo el problema en dos partes similares, y la combinación se produce dando los subproblemas por resueltos y aplicando el principio de inducción. Indica de entre los siguientes, cuál sería el coste mínimo de dicho algoritmo. O(N). O(N^2). O(N*logn). O(N^2logn).

Sea un grafo denso no dirigido representado con la siguiente matriz de adyacencia, en la que puede haber pesos de valor 0: Si se utiliza el algoritmo de Prim para calcular un árbol de recubrimiento mínimo tomando como raíz del árbol el nodo 1, indica cuál de las siguientes secuencias de aristas representa el orden en el que las selecciona el algoritmo de Prim como integrantes del árbol de recubrimiento mínimo: {1,6},{1,7},{6,2},{6,3},{4,6},{6,5},{6,8}. {1,6},{6,2},{2,3},{3,8},{4,6},{6,5},{6,7}. {1,7},{1,6},{6,3},{6,2},{4,6},{6,5},{6,8}. {1,6},{1,2},{2,3},{4,6},{6,5},{6,8},{6,7}.

Se tiene una colección de n objetos “moldeables”, cada uno con un volumen vi, para i entre 1 y n, que hay que empaquetar utilizando envases de capacidad E. Se busca un algoritmo que calcule el empaquetamiento óptimo, es decir, que minimice la cantidad de envases utilizados, teniendo en cuenta que los objetos no se pueden fraccionar. Se pide. Voraz. Ramificación y poda. Programación dinámica. Divide y vencerás. Vuelta atrás.

Una filmoteca ha organizado un maratón de cortometrajes. Durante 24 horas se proyectarán cortos de cine (todos diferentes) en las n salas disponibles. Un cinéfilo ha conseguido la programación completa donde aparecen todas las películas que se van a proyectar durante el maratón, incluyendo el título, duración del corto, sala en la que se proyecta y hora de comienzo. Si se quiere planificar el maratón del cinéfilo de forma que pueda ver el máximo número posible de Cortos, ¿Cuál es el esquema más apropiado para hacer la planificación eficientemente?. Esquema voraz. Divide y vencerás. Esquema de vuelta atrás. Esquema de ramificación y poda.

Considérese el vector v1.n) = 8,6,5,5,4,3,2,2). Indique cuál de las siguientes opciones es Cierta: El vector v es un montículo de máximos. El vector v no es un montículo de máximos porque el elemento v5) = 4 debe ser flotado. El vector v no es un montículo de máximos porque el elemento v4) = 5 debe ser hundido. Ninguna de las anteriores.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad M, n objetos con beneficios b1, b2, b3, ... bn y pesos p, p2 p3. p. El objetivo es maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M. Indica de los esquemas siguientes cuál es el más adecuado en el caso de que cada objeto puede meterse en la mochila, no meterse, o meter la mitad del objeto obteniendo la mitad del beneficio. El esquema voraz. El esquema divide y vencerás. El esquema de vuelta atrás. El esquema de ramificación y poda.

Sea el grafo de la figuraIndique cuál sería el orden en que se seleccionan los nodos del conjunto de candidatos al aplicar el algoritmo de Dijkstra comenzando por el nodo A: A C B D E F. A B C D E F. A B D C F E. Ninguna de las anteriores.

En relación a la representación de grafos mediante listas de adyacencia, indique cuál de las siguientes afirmaciones es falsa. Sean el número de nodos del grafo, necesitaremos n listas para representarlo. Si el grafo presenta pocas aristas, es más eficiente en espacio representarlo mediante listas de adyacencia que representarlo mediante una matriz de adyacencia. El coste asociado a la operación Borrar Arista es O(n+a), siendo n el número de nodos del grafo y siendo a el número de aristas. El coste asociado a la operación Añadir Vértice es O(1).

Indica cuál de las siguientes afirmaciones es cierta: Un árbol libre es un grafo acíclico, conexo y dirigido. Un ciclo es un camino simple que empieza y termina en el mismo vértice. Si un grafo tiene pocas aristas las listas de adyacencia resultan una estructura más costosa en espacio que la matriz de adyacencia. Ninguna de las definiciones anteriores es completa y cierta.

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 NxN a partir de una determinada casilla dada como entrada y sin repetir ninguna casilla. Vuelta atrás. Ramificación y poda. Voraz. Programación dinámica. Divide y vencerás.

Considérese el vector v=[2,6,8,12,7,5,4]. ¿Cuál de las siguientes opciones es cierta?. El vector v es un montículo de mínimos. v sería un montículo de mínimos si se flotara el elemento de valor 5. v sería un montículo de mínimos si se hundiera el elemento de valor 8. Ninguna de las opciones anteriores.

En el problema de colorear un grafo con n nodos utilizando m colores, de manera que no haya dos vértices adyacentes que tengan el mismo color, una cota superior ajustada del coste de encontrar una solución utilizando un esquema adecuado es del orden de: O(n^2). O(m^n). O(m log n). O(n^m).

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 5 objetos con volúmenes {1,2,5,6,7} y que aportan unos beneficios de {1,6,18,22,28}, respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 11. Indique cuál sería el contenido de la tabla de resultados parciales en la fila correspondiente al objeto de peso 7, si dichos objetos se consideran en orden creciente de pesos. 0 1 6 7 7 18 19 24 25 25 28 29. 0 1 6 7 7 18 22 24 28 29 29 40. 0 1 6 7 7 18 22 28 29 34 35 40. Ninguna de las anteriores.

Dado el siguiente grafo dirigido: Indique el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=4, tomando como nodo origen el nodo 1: [∞, 30,40, ∞]. [50, 30,40, ∞]. [55, 30,40, 80]. Ninguna de las anteriores.

Indica cuál de las siguientes afirmaciones es cierta con respecto a la resolución de colisiones: El método de hashing abierto es siempre más eficiente que el hashing cerrado para la resolución de colisiones. En el método de hashing cerrado con recorrido lineal existe una probabilidad muy baja de colisiones independientemente de los patrones de las claves. En el método de hashing cerrado con recorrido cuadrático es posible garantizar que se van a recorrer todos los elementos de la tabla cuando el número de elementos de la tabla, m, cumple determinadas condiciones. En el método de hashing cerrado con recorrido mediante doble hashing la función h y h’ que se aplican pueden ser iguales cuando el número de elementos de la tabla, m, cumple determinadas condiciones.

Se dispone de cuatro tipos de monedas de valores 1, 2, 4 y 8. Se desea resolver el problema de pagar una cantidad C > 0 utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

Un servidor tiene que atender tres clientes que llegan todos juntos al sistema. El tiempo que requerirá dar servicio a cada cliente es conocido, siendo t,=5, t2=10 y t3=3. El objetivo es minimizar el tiempo medio de estancia de los clientes en el sistema. Se quiere implementar un algoritmo voraz que construya la secuencia ordenada óptima de servicio a los distintos clientes. Según este algoritmo, el tiempo mínimo de estancia en el sistema del conjunto de clientes es: 26. 29. 31. 34.

Sea el problema de la devolución de cambio con monedas de valores 1,6 y 10 solucionado con programación dinámica para pagar una cantidad de 12 unidades. Identifica cuál de las siguientes respuestas correspondería al contenido de la tabla de resultados parciales de cantidades en la fila correspondiente a la moneda de valor 6, si dichas monedas se consideran por orden creciente de valores: 0 1 2 3 4 5 6 2 3 4 5 6 3. 0 1 2 3 4 5 6 2 3 4 5 6 7. 0 1 2 3 4 5 1 2 3 4 5 6 2. Ninguna de las anteriores.

Indique cuál sería el orden en que se seleccionan los nodos del conjunto de candidatos al aplicar el algoritmo de Dijkstra comenzando por el nodo 1: 1 2 6 5 3 4. 1 2 6 5 4 3. 1 2 6 4 5 3. Ninguna de las anteriores.

A. B. C. D.

Indique cuál de las siguientes afirmaciones con respecto a los grafos es falsa: Un grafo es simple si entre cada par de vértices existe a lo sumo una arista. La longitud de un camino es el número de aristas que contiene. Un grafo dirigido es conexo si al reemplazar todas sus aristas dirigidas por aristas no dirigidas resulta un grafo conexo no dirigido. Se denomina componente conexa de un grafo a un subgrafo conexo maximal.

En el problema de colorear un grafo con n nodos utilizando m colores, de manera que no haya dos vértices adyacentes que tengan el mismo color, una cota superior ajustada del coste de encontrar una solución utilizando un esquema adecuado es del orden de: O((n^(m/2))*log n). O(m log n). O(n^m). O(n(m^n)).

Un peluquero pretende dar servicio a n clientes y conoce el tiempo requerido por cada uno de ellos, siendo t;, i= 1,2,...,n el tiempo requerido por el cliente /. El objetivo es minimizar el tiempo total que todos los clientes están en el sistema, y como el número de clientes es fijo, minimizar la espera total equivale a minimizar la espera media. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema Voraz. Esquema de Programación Dinámica. Esquema de Vuelta Atrás. Esquema de Ramificación y Poda.

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 3 objetos con pesos(9, 6, 5) y que aportan unos beneficios de (38,40,24), respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 15. Considere que, al aplicar el algoritmo, los objetos se consideran en el orden dado en el enunciado ((9,6, 5). Indique qué afirmación es cierta: El beneficio máximo final obtenido es 80. La tabla de resultados parciales en la fila correspondiente al objeto de peso 6 es: 0 0 0 0 0 0 24 24 24 40 40 40 64 64 64 78. La tabla de resultados parciales en la fila correspondiente al objeto de peso 5 es: 0 0 0 0 0 24 40 40 40 40 40 64 64 64 64 78. El problema propuesto se resuelve más eficientemente utilizando un enfoque voraz.

Dadas las siguientes matrices (cuyas dimensiones se especifican entre paréntesis): A: (3x5), Az (5x2), Az (2x3) y Ay (3x2) y siendo E(i,j) el número de operaciones mínimo para resolver la operación Aj x Aj+1 x ... x A¡ mediante programación dinámica, se pide indicar cuál de las siguientes opciones es cierta. E(2,3) = 15. E(1,3) = 30. E(2,4) = 32. E(2,2) = 10.

¿Cuál de las siguientes afirmaciones es falsa con respecto al coste de las funciones de manipulación de grafos?. La función AñadirVertice que añade un vértice a un grafo y devuelve el grafo con dicho vértice incluido, tiene un coste constante cuando el grafo se implementa con una matriz de adyacencia. La función BorrarArista es menos costosa cuando el grafo se implementa mediante una matriz de adyacencia. La operación Adyacente?, que comprueba si dos nodos son adyacentes, es más costosa cuando el grafo se implementa con una lista de adyacencia. La función Adyacentes, que devuelve una lista con los vértices adyacentes a uno dado, es más costosa cuando el grafo se implementa con una matriz de adyacencia.

Dado el siguiente montículo de máximos, ¿Cuál de los siguientes vectores lo representa de forma correcta?. 23, 15, 21, 11, 6, 14, 9, 3, 5, 4. No es un montículo de máximos, sino de mínimos. 23, 15, 11, 3, 5, 6, 4, 21, 14, 9. 23, 15, 21, 11, 6, 3, 5, 4, 14, 9.

Aplicando el algoritmo de Dijkstra al grafo, indicar cuál de las siguientes NO es un valor correcto para el vector “Especial” D[i] generado por el algoritmo de Dijkstra a lo largo de las iteraciones, representando en cada iteración la distancia mínima hasta el momento entre los vértices 1 e i: [NOTA: "00" es el símbolo infinito]. D=[5, 10, 00, 2]. D=[5, 7, 00, 2]. D=[5, 10, 9, 2]. D=[5, 7, 9, 2].

Sea un grafo denso no dirigido representado con la siguiente matriz de adyacencia, en la que puede haber pesos de valor 0... ...Si se utiliza el algoritmo de Prim para calcular un árbol de recubrimiento mínimo tomando como raíz del árbol el nodo 1, indica cuál de las siguientes secuencias de aristas representa el orden en el que las selecciona el algoritmo de Prim como integrantes del árbol de recubrimiento mínimo: {1,6}, {1,7}, {6,2}, {6,3}, {4,6}, {6,5}, {6,8}. {1,7}, {1,6}, {6,3}, {6,2}, {4,6}, {6,5}, {6,8}. {1,6}, {6,2}, {2,3}, {3,8}, {4,6}, {6,5}, {6,7}. {1,6}, {1,2}, {2,3}, {4,6}, {6,5}, {6,8}, {6,7}.

Indica cuál de las siguientes afirmaciones es falsa: En un algoritmo de vuelta atrás es posible retroceder para deshacer una decisión ya tomada. La programación dinámica es aplicable a muchos problemas de optimización cuando se cumple el Principio de Optimalidad de Bellman. El problema de calcular el camino de coste mínimo entre cada par de nodos de un grafo (es decir, desde todos los nodos hasta todos los restantes nodos) se resuelve utilizando como base el algoritmo de Dijkstra. La resolución de este problema completo tiene una complejidad de O(n?). La programación dinámica es apropiada para resolver problemas que pueden descomponerse en subproblemas más sencillos en los que haya llamadas repetidas en la secuencia de llamadas recursivas.

Tenemos una tabla hash de tamaño 7 para almacenar mediante recorrido lineal valores naturales con h(x) = x mod 7. Indicar la respuesta correcta sobre la tabla resultante de insertar en este orden los valores: 0, 11, 3, 7, 1, 9. El índice 3 tiene clave 3. El índice 1 tiene clave 1. El índice 2 no está ocupado por ningún valor. El índice 6 tiene valor 9.

Considérese el vector [7, 10, 5, 2, 20, 15, 1, 5]. Los vectores argumento de la primera invocación recursiva del algoritmo de quicksort, cuando se toma el elemento 7 de la primera posición como pivote, son: [5, 2, 5, 1] y [15, 20, 10]. [1, 5, 5, 2] y [15, 20, 10]. [5, 2, 5, 1] y [10, 20, 15]. Ninguna de las opciones anteriores.

Considérese el vector v=[3, 6, 4, 7, 9, 2, 5]. ¿Cuál de las siguientes opciones es cierta?. El vector v es un montículo de mínimos. v sería un montículo de mínimos si se flotara el elemento de valor 2. v sería un montículo de mínimos si se hundiera el elemento de valor 6. Ninguna de las opciones anteriores.

Una filmoteca ha organizado un maratón de cine de terror. Durante 24 horas se proyectarán películas (todas diferentes) en las n salas disponibles. Un aficionado a este género de películas ha conseguido la programación completa donde aparecen todas las películas que se van a proyectar durante el maratón. Junto con el título, nombre del director, duración de la película y otros datos de interés, se indica la sala de proyección y la hora de comienzo. Indique qué tipo de algoritmo de entre los siguientes sería el más eficiente para el aficionado planifique su maratón de cine, teniendo en cuenta que su único objetivo es ver el máximo número de posible de películas: Esquema voraz. Esquema divide y vencerás. Esquema de vuelta atrás. Esquema de ramificación y poda.

Un dentista pretende dar servicio a n pacientes y conoceel tiempo requerido por cada uno de ellos, siendo ti, i= 1,2,...,n, el tiempo requerido porel paciente i. El objetivo es minimizar el tiempo total que todos los clientes están en el sistema, y como el número de pacientes es fijo, minimizar la espera total equivale a minimizar la espera media. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema voraz. Esquema de programación dinámica. Esquema de vuelta atrás. Esquema de ramificación y poda.

Respecto a la estructura de datos montículo de mínimos, cuál de las siguientes afirmaciones es falsa: Con un montículo de mínimos disponemos de una estructura de datos en la que encontrar el mínimo es una operación de coste constante. El montículo sirve de apoyo a la creación de un algoritmo de ordenación eficiente conocido como Heapsort. El montículo es un árbol binario que puede estar o no balanceado. Cuando se extrae el primer elemento de un montículo, restaurar la propiedad de montículo tiene coste O(log n).

Se dispone de un vector, V, que almacena números enteros en orden estrictamente creciente, y se desea averiguar si existe algún elemento que cumpla V[i]=i. ¿Cuál sería la estrategia más adecuada para resolver el problema?. Algoritmo voraz. Divide y vencerás. Vuelta atrás. Ramificación y poda.

Sobre el algoritmo de Dijkstra, cuál de las siguientes afirmaciones es falsa: El algoritmo de Dijkstra sigue el esquema voraz. El algoritmo de Dijkstra determina la longitud del camino de coste, peso o distancia mínima que va desde el nodo origen a cada uno de los demás nodos del grafo. El coste del algoritmo de Dijkstra es O(n log n). En el algoritmo de Dijkstra un camino desde el nodo origen hasta otro nodo es especial si se conoce el camino de coste mínimo desde el nodo origen a todos los nodos intermedios.

Indica cuál de las siguientes afirmaciones es cierta con respecto a la resolución de colisiones: El método de hashing abierto es siempre más eficiente que el hashing cerrado para la resolución de colisiones. En el método de hashing cerrado con recorrido lineal existe una probabilidad muy baja de colisiones independientemente de los patrones de las claves. En el método de hashing cerrado con recorrido mediante doble hashing, la función h y h' que se aplican deben ser iguales cuando el número de elementos de la tabla, m, cumple determinadas condiciones. El método de hashing cerrado con recorrido cuadrático permite una mayor dispersión de las colisiones por la tabla que el hashing cerrado con recorrido lineal.

Selecciona la afirmación más ajustada de las siguientes. Las siguientes tres figuras corresponden a: Las tres corresponden a tres grafos no dirigidos sin ninguna posible relación entre ellos. La de la izquierda es un grafo y a los grafos no dirigidos conexos con aristas de igual coste no se les puede asociar más de un árbol de recubrimiento mínimo. La de la izquierda es un grafo y las de la derecha son dos posibles árboles de recubrimiento mínimo asociados a él. Ninguna de las anteriores es correcta.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad con beneficios b1, b2 b3, . bn y pesos p1, p2, p3, ... pn. El objetivo es maximizar objetos transportados, respetando la limitación de la capacidad impuesta M. esquemas siguientes, cuál es el más adecuado en el caso de que cada meterse en la mochila entero o fraccionado. El esquema voraz. El esquema divide y vencerás. El esquema de vuelta atrás. El esquema de ramificación y poda.

Indica cuál de las siguientes afirmaciones es cierta con respecto al problema de la devolución de cambio de moneda utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada: El problema de la devolución de cambio de moneda se puede resolver para todo sistema monetario utilizando una estrategia voraz, siempre que en el sistema se disponga de un tipo de moneda de 1. Si se dispone de n tipos de moneda T = { m0, m1, m2, ... m^(n-1)} siendo m > 1 y n > 0, el problema de la devolución de cambio de moneda no se puede resolver utilizando una estrategia voraz. El problema de la devolución de cambio de moneda para cualquier sistema monetario, siempre que en el sistema se disponga de un tipo de moneda de 1, se puede resolver utilizando los esquemas de programación dinámica y de ramificación y poda. El problema de la devolución de cambio de moneda para cualquier sistema monetario, siempre que en el sistema se disponga de un tipo de moneda de 1, se puede resolver utilizando el esquema de programación dinámica pero no el de ramificación y poda.

Indica cuál de las siguientes afirmaciones es cierta con respecto al algoritmo Quicksort para un vector de tamaño n. Se compone de dos invocaciones recursivas con tamaño n/2 más un procedimiento que combina los subvectores ordenados resultantes que es de coste lineal. Su coste en el caso peor es O(n”), pero existe una versión mejorada eligiendo como pivote la mediana del vector, lo que daría que el coste del Quicksort en el caso peor sería O(n). Está compuesto de dos recorridos lineales del vector y posteriormente una llamada recursiva al subvector no ordenado. Ninguna de las anteriores es cierta.

Una filmoteca ha organizado un maratón de cortometrajes. Durante 24 horas se proyectarán cortos de cine (todos diferentes) en las n salas disponibles. Un cinéfilo ha conseguido la programación completa donde aparecen todas las películas que se van a proyectar durante el maratón, incluyendo el título, duración del corto, sala en la que se proyecta y hora de comienzo. Si se quiere planificar el maratón del cinéfilo de forma que pueda ver el máximo número posible de cortos, ¿Cuál es el esquema más apropiado para hacer la planificación eficientemente?. Esquema Voraz. Divide y Vencerás. Esquema de Vuelta Atrás. Esquema de Ramificación y Poda.

Sea un grafo denso no dirigido representado con la siguiente matriz de adyacencia, en la que puede haber pesos de valor 0...si se utiliza el algoritmo de Prim para calcular un árbol de recubrimiento mínimo tomando como raíz del árbol el nodo A, indique cuál de las siguientes secuencias de aristas representa el orden en el que las selecciona el algoritmo de Prim como integrantes del árbol de recubrimiento mínimo: {A,C}, {C,D}, {C,E}, {B,C}, {B,F}. {A,C}, {C,D}, {B,F}, {C,E}, {B,C}. {A,C}, {C,D}, {C,E}, {B,F}, {B,C}. Ninguna de las anteriores.

Considérese el vector [15, 7, 10, 5, 3, 8, 2] que representa un montículo de máximos. ¿Cuál sería la representación resultante de insertar en este montículo el valor 11 usando la función flotar?. [15, 11, 10, 7, 5, 8, 2, 3]. [15, 11, 10, 7, 3, 8, 2, 5]. [15, 10, 11, 7, 3, 8, 2, 5]. Ninguna de las opciones anteriores.

Un dentista pretende dar servicio a n pacientes y conoce el tiempo requerido por cada uno de ellos, siendo ti, i= 1, 2, ..., n el tiempo requerido por el paciente /. El objetivo es minimizar el tiempo medio de estancia de los pacientes en la consulta. En relación a este problema, ¿cuál de las siguientes afirmaciones es falsa?. El esquema más eficiente para resolver este problema correctamente es el esquema voraz. El coste del algoritmo voraz que resuelve el problema es O(n log n). Suponiendo tres pacientes con tiempos de servicio t1=15, t2=60 y t3=30, el tiempo mínimo de estancia total posible es de tres horas. Suponiendo tres pacientes con tiempos de servicio t1=15, t2=20 y t3=30, el tiempo mínimo de estancia total posible es de 115 minutos.

Se dispone de un vector, V, que almacena n números naturales, y se desea averiguar si existe algún elemento que aparezca al menos n/2 + 1 veces en el vector. ¿Cuál sería la estrategia más adecuada para resolver el problema?. Algoritmo Voraz. Divide y Vencerás. Vuelta Atrás. Ramificación y Poda.

En relación a los montículos, ¿cuál de las siguientes afirmaciones es cierta?. La ordenación mediante el algoritmo Heapsort tiene un coste O(log n). El vector m=[6, 5, 4, 4, 1, 3, 2] es un montículo de mínimos. La función insertar tiene un coste O(n log n). Con un montículo de mínimos disponemos de una estructura de datos en la que encontrar el mínimo es una operación de coste constante.

Dado el siguiente grafo, indique cuáles serían, de acuerdo al algoritmo de Dijkstra, las longitudes de los caminos de coste mínimo que unen el nodo 1 con el resto de nodos del grafo: {3, 4, 6, 7}. {3, 5, 7, 8}. {3, 6, 5, 7}. Ninguna de las anteriores.

Con respecto a las tablas y funciones Hash, indicar cuál de las siguientes afirmaciones es cierta: Una función Hash asocia unívocamente una clave a un elemento. El recorrido lineal permite mayor dispersión de las colisiones que el cuadrático. El factor de carga se calcula como el tamaño de la tabla dividido por el número de elementos ya insertados. Es deseable mantener el factor de carga de la tabla por debajo del 50%.

Dadas las matrices: A1 (3x5), A2 (5x2), A3 (2x3) y A4 (3x2), y siendo E(ij), ¡<j, el número de Operaciones mínimo para resolver la operación Ai x Ai+1 x ... x Aj mediante programación dinámica, se pide indicar cuál de las siguientes opciones es cierta: E(2,3) = 15. E(1,3) = 30. E(2,4) = 32. E(2,2) = 10.

Dado el siguiente grafo, indique el valor del vector de distancias especial[] en el paso del algoritmo de Dijkstra en el que se selecciona el nodo v=3, tomando como nodo origen el nodo1: [19, 12, 5, 7]. [20, 12, 5, 7]. [20, 19, 5, 7]. Ninguna de las anteriores.

Un lejano país emite n sellos diferentes de valores naturales positivos S1, S2,...,Sn. Se quiere enviar una carta y se sabe que la correspondiente tarifa postal es 7. Se quiere saber de cuántas formas diferentes se puede franquear exactamente la carta, si el orden de los sellos no importa. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema Voraz. Esquema de Programación Dinámica. Esquema de Vuelta Atrás. Esquema de Ramificación y Poda.

Respecto a la estructura de datos grafo, ¿Cuál de las siguientes afirmaciones es falsa?. El máximo número de aristas en un grafo no dirigido de n vértices es n(n-1). Los recorridos en profundidad o en anchura de un grafo conexo le asocian un árbol de recubrimiento. La búsqueda en profundidad puede dar lugar a diferentes árboles o bosques de recubrimiento. Dado un grafo conexo, un nodo u es un punto de articulación si al eliminar u y todas las aristas que inciden en él el grafo deja de ser conexo.

Con respecto al esquema divide y vencerás indique cuál de las siguientes afirmaciones es verdadera: En algunos casos permite la paralelización de la resolución de los subproblemas del mismo tipo. El coste de este tipo de algoritmos depende del número de subproblemas en los que se descompone el problema pero no de la reducción del tamaño en las sucesivas llamadas recursivas. Siempre es necesario combinar las soluciones de los subproblemas. Este esquema aplica el principio de deducción sobre los diversos ejemplares del problema.

Considérese el vector [5, 3, 7, 6, 3, 9, 2, 4, 8, 2]. Los vectores argumento de la primera invocación recursiva del algoritmo de Quicksort, cuando se toma el elemento 5 de la primera posición como pivote, son: [2, 2, 3, 4, 3] y [9, 6, 7, 8]. [2, 3, 2, 4, 3] y [9, 6, 8, 7]. [2, 2, 3, 3, 4] y [6, 8, 7, 9]. Ninguna de las opciones anteriores.

Sea una tabla hash con m=5 y h(x) = x mod 5 usando para la resolución de colisiones un hashing abierto con 3 niveles combinado con encadenamiento directo. En ella se van insertando en orden los siguientes valores: 41, 58, 16, 66, 77, 12, 25, 21, 31, 14. Indique cuál de las siguientes afirmaciones es cierta: Tras insertar el 25 la tabla hash no ha necesitado realizar encadenamiento. Tras insertar el 14 la posición O de la tabla carece de valores. Tras insertar el valor 77 la tabla hash tiene la posición 1 incompleta. Tras insertar el valor 21 la tabla tiene todos los niveles completos.

Con respecto la resolución de colisiones en las funciones Hash se puede afirmar que: El recorrido cuadrático es aplicable siempre que se trate de hashing abierto. Si el factor de carga es 1 se puede resolver mediante hashing cerrado. El hashing abierto contempla un método de resolución conocido como “recorrido mediante doble hashing”. Ninguna de las anteriores es correcta.

Durante la ejecución de un algoritmo de minimización por Ramificación y Poda, la estimación optimista de la cima del montículo es mayor o igual que la cota superior hasta el momento. Esto implica: Definitivamente el algoritmo ha terminado. Se actualiza la cota superior con la cima del montículo y se sigue con la exploración porque no hemos terminado. Se descarta la cima del montículo y se sigue con el siguiente elemento del montículo porque no hemos terminado. Ninguna de las anteriores es correcta.

Sea el problema de la mochila en su versión de objetos no fraccionables solucionado mediante programación dinámica. Suponga que se dispone de 4 objetos con volúmenes {1, 2, 5, 6} y que aportan unos beneficios de {1, 5, 15, 20}, respectivamente. Suponga también que dispone de una mochila con una capacidad máxima de 12. Indique cuál sería el contenido de la tabla de resultados en la fila correspondiente al objeto de volumen 6, si dichos objetos se consideran en orden creciente de volúmenes. 0 1 5 6 5 15 16 20 21 25 26 35 36. 0 1 5 6 6 15 20 21 25 25 26 35 36. 0 1 5 6 6 15 21 25 25 26 26 35 36. Ninguna de las anteriores.

En relación al esquema algorítmico de vuelta atrás. ¿Cuál de las siguientes afirmaciones es cierta?: Implementa un recorrido en amplitud de forma recursiva sobre el grafo implícito del problema. El esquema de Vuelta Atrás siempre encontrará una solución al problema, si es que ésta existe. Siempre es más eficiente que el esquema Voraz, de forma que, si ambos son aplicables, nos decantaremos por utilizar el esquema de Vuelta Atrás. Todas las afirmaciones anteriores son falsas.

Con respecto al algoritmo de Prim indique cuál de estas afirmaciones es falsa: El algoritmo parte necesariamente de un nodo que hay que seleccionar y que será la raíz del árbol de recubrimiento. El algoritmo finaliza cuando el árbol de recubrimiento contiene n-1 aristas, siendo n el número de nodos. Si para representar el grafo se utiliza una lista de adyacencia junto con un montículo para representar los candidatos pendientes el coste del algoritmo es O(a log n), lo que resulta más apropiado que usar una matriz de adyacencia cuando el grafo es denso. La función de selección en cada paso añade al árbol de recubrimiento una arista de coste mínimo tal que la estructura resultante sigue siendo un árbol.

Indique cuál de las siguientes afirmaciones es falsa con respecto al esquema de programación dinámica: El objetivo de este esquema es la reducción del coste del algoritmo mediante la memorización de soluciones parciales que se necesitan para llegar a la solución final. Es igual de eficiente que el esquema divide y vencerás cuando en este último esquema se dan llamadas recursivas que se repiten en la secuencia de llamadas recursivas. El problema de la multiplicación asociativa de matrices resuelto con programación dinámica tiene un coste temporal de O(N^3), siendo N el número de matrices para multiplicar. El problema de la distancia de edición entre dos cadenas resuelto con programación dinámica tiene un coste temporal de O(nm), siendo n la longitud de una cadena y m la longitud de la otra.

Se tiene un vector de números enteros no repetidos y ordenados de menor a mayor. Se desea diseñar un algoritmo que compruebe si existe algún elemento del vector que coincida con su índice. ¿Cuál de los siguientes esquemas es más eficiente de los que puedan resolver el problema correctamente?. Esquema Voraz. Esquema de Vuelta Atrás. Esquema Divide y Vencerás. Esquema de Ramificación y Poda.

Indica cuál de las siguientes afirmaciones es cierta con respecto al problema de la devolución de cambio de moneda utilizando un número mínimo de monedas y suponiendo que la disponibilidad de cada tipo de moneda es ilimitada: El problema de la devolución de cambio de moneda se puede resolver para todo sistema monetario utilizando una estrategia Voraz, siempre que en el sistema se disponga de un tipo de moneda de 1. Si se dispone de n tipos de moneda T =(m^0, m^1, m^2...m^n) siendo m > 1 y n >0, el problema de la devolución de cambio de moneda no se puede resolver utilizando una estrategia Voraz. El problema de la devolución de cambio de moneda para cualquier sistema monetario, siempre que en el sistema se disponga de un tipo de moneda de 1, se puede resolver utilizando los esquemas de Programación Dinámica y de Ramificación y Poda. Ninguna de las anteriores es cierta.

Con respecto al esquema de ramificación y poda, indica cuál de las siguientes afirmaciones es falsa: En el problema de la distancia de edición entre dos cadenas, si se consideran tres operaciones de transformación, siendo n y m la longitud de las cadenas en caracteres, y n menor o igual que m, una cota superior del espacio de búsqueda generado por el algoritmo de ramificación y poda sería 3^m. El montículo se utiliza en este esquema porque permite establecer una cola de prioridad de los nodos que aún no se han explorado. Los nodos en el montículo se mantienen ordenados en orden decreciente si la optimización es minimización o creciente si la optimización es maximización del valor de la función objetivo. En la fase de poda se eliminan las ramas que no pueden llegar a una solución y las que no pueden mejorar el valor de la función objetivo de la mejor solución alcanzada.

Sea un grafo no dirigido representado con la siguiente matriz de adyacencia...si se utiliza el algoritmo de Kruskal, indica cuál de las siguientes respuestas representan las componentes conexas en el paso 6 (penúltimo) del algoritmo: {1, 5, 2}, {3, 4, 6, 7). {1, 5, 7}, {2, 3, 4, 6}. {1, 2, 4}, {13, 5, 6, 7}. Ninguna de las anteriores.

En relación a los algoritmos de ordenación, ¿cuál de las siguientes afirmaciones es verdadera?. La ordenación mediante el algoritmo Heapsort tiene un coste O(log n). El coste del algoritmo Quicksort en el caso peor es de orden O(n log n). El coste del algoritmo de ordenación Mergesort es O(n). Todas las anteriores son falsas.

Sean A1..A6 matrices de dimensiones 30x35, 35x15, 15x5, 5x10, 10x20 y 20x25; y sea m[i,j] el número mínimo de productos escalares para multiplicar Ai..Aj, es decir, el subrango i..j con i,j € {1..6}, siendo i la abscisa y j la ordenada, y siendo la matriz con los diferentes valores mli,j] la siguiente: ¿Cuál de las siguientes opciones es la parametrización óptima del producto de las seis matrices A1..A6? [NOTA: el símbolo del € representa el "pertenece a"]. (A1(A2A3)(A4A5)A6). (A1A2)(A3A4)(A5A6). (A1(A2(A3A4)A5)A6). Ninguna de las anteriores.

Considérese el vector v[1..n] = [8, 6, 5, 5, 4, 3, 2, 2] cuál de las siguientes opciones es cierta: El vector v es un montículo de máximos. El vector v no es un montículo de máximos porque el elemento v[5] = 4 debe ser flotado. El vector v no es un montículo de máximos porque el elemento v[4] = 5 debe ser hundido. Ninguna de las anteriores.

Dado el grafo dela figura, indique cuál sería el orden en que se seleccionan los nodos del conjunto de candidatos al aplicar el algoritmo de Dijkstra comenzando por el nodo 1: 4 2 5 3. 4 3 5 2. 4 2 3 5. 4 3 2 5.

Sea el problema de la mochila, en el que tenemos una mochila de capacidad M, n objetos con beneficios b1, b2, b3... bn y pesos p1, p2, p3... pn. El objetivo es maximizar el valor de los objetos transportados, respetando la limitación de la capacidad impuesta M. Indica de los esquemas siguientes cuál es el más adecuado en el caso de que cada objeto puede meterse en la mochila entero, en cualquier fracción, o bien no meterse. El esquema Voraz. El esquema Divide y Vencerás. El esquema de Vuelta Atrás. El esquema de Ramificación y Poda.

Indica cuál de las siguientes afirmaciones es falsa con respecto al esquema de Ramificación y Poda: Una vez realizada la ramificación de un nodo (extensiones de su solución parcial) solo se podan aquellas ramas que no pueden mejorar el valor de la mejor solución alcanzada hasta ese momento. Se suele utilizar una cota pesimista que es el valor de una solución cualquiera, de forma que se buscan soluciones que puedan mejorar ese valor. El problema de la mochila entera, con objetos que no se pueden fraccionar, cuando se resuelve con este esquema tiene un coste del orden de O(2^n). Se dejan de buscar soluciones cuando el montículo está vacío o cuando el elemento de la cima del montículo tiene una estimación optimista que es peor que la estimación pesimista o que la mejor solución alcanzada hasta el momento.

Con respecto al algoritmo de Kruskal indica cuál de estas afirmaciones es falsa: En los pasos intermedios del algoritmo el conjunto de aristas del árbol de recubrimiento mínimo que se va formado constará de varias componentes conexas. El algoritmo finaliza cuando el árbol de recubrimiento contiene n-1 aristas, siendo n el número de nodos. El coste de este algoritmo es O(a log n). La función de selección en cada paso añade al árbol de recubrimiento una arista de coste mínimo no evaluada si une dos nodos pertenecientes a la misma componente conexa.

En una tabla de dispersión hash, ¿cuál de las siguientes afirmaciones es cierta?. Dos o más claves diferentes del dominio inicial pueden proporcionar la misma clave en el índice de la tabla hash. El uso de tablas hash siempre mejora la eficiencia temporal de los algoritmos. Las tablas hash permiten un ahorro considerable de memoria independientemente de la proporción entre los tamaños del dominio inicial y del dominio de claves hash. Ninguna de las afirmaciones anteriores es cierta.

En relación a los montículos, indique cuál de las siguientes afirmaciones es falsa: El vector [10, 6, 6, 3, 3, 2, 5, 2] es un montículo de máximos. Al insertar el valor 6 (función Insertar del texto base) utilizando la función flotar en el montículo [10, 6, 3, 5, 2, 3, 2], la representación resultante es [10,6, 3, 6, 2, 3, 2, 5]. Sea el montículo [6, 5, 4, 4, 1, 3, 2], al obtener la cima del mismo (función ObtenerCima del texto base) y restaurar la propiedad de montículo, la representación resultante es[5, 4, 4, 2, 1, 3]. Todas las anteriores son falsas.

Sea el grafo de la figura, indique cuál sería la primera arista que rechaza el algoritmo de Kruskal en la creación del árbol de expansión mínimo: Ninguna arista. La arista (E, B). La arista (C, E). Ninguna de las anteriores respuestas es válida.

Con respecto al recorrido en amplitud o en anchura de un grafo indica cuál de las siguientes afirmaciones es falsa: El coste del recorrido en anchura es O(n^2) cuando se representa mediante una matriz de adyacencia y O(n+a) si se representa con listas de adyacencia. Se emplea para realizar exploraciones parciales de un grafo potencialmente infinito. El recorrido en anchura es de naturaleza recursiva y la estructura de datos que se corresponde con el recorrido es de tipo pila. Se puede considerar un recorrido por niveles del grafo ya que dado un nodo inicial primero se visitan los nodos que están a una arista de distancia.

En relación a los esquemas algorítmicos, ¿cuál de las siguientes afirmaciones es falsa?. El esquema de Vuelta Atrás realiza un recorrido en profundidad del grafo implícito de un problema. El esquema de Ramificación y Poda utiliza un montículo para establecer una cola de prioridad de los nodos aún sin explorar. Preferiremos el esquema de Ramificación y Poda al esquema Voraz siempre que ambos sean aplicables. El objetivo del esquema de Programación Dinámica es reducir el coste del algoritmo mediante la memorización de las soluciones parciales.

Respecto a la estructura de datos grafo, ¿cuál de las siguientes afirmaciones es falsa?. El máximo número de aristas en un grafo dirigido de n vértices es n(n-1). Un recorrido en profundidad de un grafo es equivalente al recorrido en postorden de un árbol. Si el grafo no es conexo, el recorrido en profundidad le asocia un bosque de árboles, uno por cada componente conexa del árbol. En un grafo representado mediante una matriz de adyacencia el coste de la búsqueda en profundidad es de O(n^2).

Sea el problema de planificación con plazos en el que se han de realizar cuatro trabajos, cada uno de los cuales ha de finalizarse antes de la fecha fi indicada para producir el beneficio b;. Cada trabajo se realiza en una máquina que consume una unidad de tiempo y solo hay una máquina disponible. Se han de seleccionar los trabajos y la secuencia en la que deben realizarse para que el beneficio total sea máximo...indicar cuál de las siguientes afirmaciones es cierta: [NOTA: LA PREGUNTA FUE ANULADA]. La secuencia (2, 1, 3) es una solución factible. La solución (1, 3) es óptima. El beneficio máximo alcanzable es 115. El algoritmo Voraz que resuelve este problema considera los trabajos en orden creciente de beneficios siempre que el conjunto de trabajos sea una solución factible.

Considérese el vector v[1..n] = [6,6,7,6,7,8,7,8,6,7,7,9,8,9,8]. ¿Cuál de las siguientes opciones es cierta?. El vector v no es un montículo porque el elemento v[4] = 6 debe ser hundido. El vector v es un montículo de máximos. El vector v no es un montículo porque el elemento v[12] = 9 debe ser flotado. Ninguna de las anteriores.

Dado el grafo de la figura, indique cuál de las siguientes afirmaciones es cierta con respecto a las componentes fuertemente conexas que contiene: Tiene 3 componentes fuertemente conexas: {1,2} {3,5,6,7} {4}. Ninguna de las otras opciones es cierta. Tiene 2 componentes fuertemente conexas: {1,2} {3,4,5,6,7}. No tiene ninguna componente fuertemente conexa.

Dado el grafo ­–en el que se entienden todas las aristas como dirigidas en ambos sentidos– con origen en el nodo 0 y al que se aplica el algoritmo de Dijkstra. ¿Cuál de los siguientes valores del vector especial[] no se corresponde con ninguno de los que genera el algoritmo?. especial []= [ 4,∞,∞,∞,∞, 9,8,14]. especial []= [4,12,∞ ,∞ ,11,9,8,15]. especial []= [4,12,19,21,11,9,8,14]. especial []= [4,12,25,21,11,9,8,15].

Con respecto al algoritmo de búsqueda binaria en un vector ordenado, indica cuál de las siguientes afirmaciones es cierta: El coste del algoritmo de búsqueda binaria es del orden exacto n log n. Una vez que se ha localizado el valor buscado en un subvector, se combinan las soluciones parciales. La descomposición del vector en dos subvectores se realiza de forma que en un subvector quedan los valores mayores que el valor que se busca y en el otro los menores o iguales. Ninguna de las otras opciones es cierta.

Dado el problema del cambio de moneda solucionado mediante programación dinámica, indica cuál de las siguientes tablas sería correcta si se parte de 3 tipos de moneda: {1,2,8} y se quiere devolver la cantidad 10: |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1} |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1,2} |0 |1 |1 |2 |2 |3 |3 |3 |4 |5 |5 {1,2,8} |0 |1 |1 |2 |2 |3 |3 |4 |1 |2 |2. Ninguna de las otras opciones es correcta. |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1} |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1,2} |0 |1 |1 |2 |2 |3 |3 |4 |4 |5 |6 {1,2,8} |0 |1 |1 |2 |2 |3 |3 |4 |1 |2 |2. |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1} |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10 {1,2} |0 |1 |1 |2 |2 |3 |3 |4 |4 |5 |5 {1,2,8} |0 |1 |1 |2 |2 |3 |3 |4 |1 |2 |2.

Dado el siguiente grafo, indique cuál de las siguientes afirmaciones es cierta: Se puede colorear todos los vértices de cualquier grafo conexo utilizando únicamente 3 colores, de forma que no haya 2 vértices adyacentes que tengan el mismo color. Para colorear todos los vértices del grafo de la figura, de forma que no haya 2 vértices adyacentes que tengan el mismo color, es necesario utilizar al menos 4 colores. Ninguna de las anteriores es cierta. Es posible colorear todos los vértices del grafo de la figura utilizando únicamente 3 colores, de forma que no haya 2 vértices adyacentes que tengan el mismo color.

Una empresa de fabricación de muebles dispone de un catálogo y una vez ha aceptado un pedido se compromete a entregarlo antes de una fecha límite. En la actualidad tiene activos N pedidos. Para cada mueble, se conoce el beneficio bi que obtendría por fabricarlo y venderlo, así como el tiempo que se tarda en fabricarlo, que es ti. También sabe los días di que quedan antes de la fecha tope fijada por el cliente para recibir el mueble. La empresa requiere un algoritmo para decidir qué muebles debe escoger para maximizar el beneficio total obtenido. Indique cuál de las siguientes afirmaciones es cierta si se resuelve mediante un algoritmo de Ramificación y Poda: Podemos obtener una estimación optimista sumando el beneficio de todos los muebles que se pueden fabricar sin llegar a su fecha límite después de los que ya se han elegido, como si cada uno se fuera a empezar a fabricar justo después de terminar el último fabricado. Para determinar si un conjunto de muebles se puede fabricar hay que comprobar que cada uno se termine sin superar su límite de días di. Para realizar esta comprobación hay que ordenar los muebles por fecha tope decreciente. Una estimación superior del coste es el tamaño del árbol que representa el espacio de búsqueda, que en el peor caso crece en función de las 2 opciones de fabricar o no un mueble y de los n muebles como O(n^2). Ninguna de las otras opciones es verdadera.

Unos agentes A1...An deben realizar las tareas T1...Tn. En la realización de la misma, cada agente obtiene el beneficio B[i, j] tras completar la tarea j por el agente i. ¿Qué esquema permite realizar eficicentemente la asignación que maximice el beneficio?. Esquema Divide y Vencerás. Esquema Voraz. Esquema de Vuelta Atrás. Esquema de Ramificación y Poda.