Con respecto al algoritmo de Prim indique cuál de las siguientes afirmaciones es FALSA El algoritmo parte necesariamente de un nodo que hay que seleccionar y que serán la raíz del nodo de recubrimiento La función de selección en cada paso añade al árbol de recubrimiento una arista de coste mínimo para que la estructura resultante sigue siendo un árbol 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 arista cuando el grajo es denso El algoritmo finaliza cuando el árbol de recubrimiento contiene N-1 arista siendo N el número de nodos.
Sea el problema de la mochila en su versión de objetos no fraccionable solucionado mediante programación dinámica.
Supongo que se dispone de cuatro objetos con los pesos P=[1,2,5,6] y que aporta una ganancia de G=[1,5,15,20] respectivamente.
Supongo 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 P[3] de peso 6 si dichos objetos son considerados en el mismo orden en el que aparece en el vector. 0,1,5,6,6,15,16,20,21,25,26,35,36 0,1,5,6,6,15,21,25,25,26,26,35,36 Ninguna es correcta 0,1,5,6,6,15,20,21,25,25,26,35,36.
En el algoritmo de Kruskal Mientras ejecuta en todo momento hay una sola componente conexa Su eficiencia solamente depende del número de nodos del grafo No se selecciona un nodo de partida para construir el árbol generador minimal Todas son falsas.
Dijkstra
Dado el grafo de la figura indique cuál sería el orden en el que se selecciona ganado del conjunto de candidatos al aplicar el organismo de Dijkstra comenzado por el nodo 1 1, 2, 6, 5, 3, 4 1, 2, 6, 5, 4, 3 ninguna es verdadera 1, 2, 6, 4, 5, 3.
El algoritmo de Floyd La memoria necesaria está en orden cuadrático Las soluciones triviales se calculan en la etapa en la que K=1 Solo calcula la longitud de los caminos mínimos que van desde un nodo fuente hasta uno de los demás nuevos del grafo Tiene una orden de complejidad cuatrático.
Problemas de teoría de algoritmo:
Se tiene un vector de números enteros no repetidos y ordenados de menor a mayor. Sea 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 puede resolver el problema correctamente? Esquema de vuelta atrás Esquema de programación dinámica Esquema voraz Esquema divide y vencerás.
Indique cuál de las siguientes afirmaciones es falsa: En el algoritmo de vuelta atrás es posible retroceder para deshacer una decisión ya tomada 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 una base del algoritmo Dijkstra la resolución de este problema tiene la complejidad O(n^2) La programación dinámica es apropiada para resolver problemas que pueden descomponerse en su problema más sencilla en los que haya llamadas repetidas en la secuencia de llamadas recursivas La programación dinámica es aplicable a muchos problemas de optimización.
Para el mismo laberinto de entrada ¿Cuál es la primera salida que se muestra por pantalla cuando se ejecuta el siguiente código? Suponer que S es una constante que vale 4 Laberinto a Laberinto b Laberinto c Laberinto d.
En la técnica de vuelta atrás En "ELSE" solo se usa cuándo es posible que una solución parcial sea prefijo de otra solución El recorrido de un árbol de exploración se realiza en anchura Para aumentar la eficiencia del algoritmo se puede construir en memoria todo el arbol de exploración Se podan los casos que contiene una solución parcial que ya no es factible.
Sea un cra fono dirigido al representado con la matriz de adyacencia de la figura. Si se utiliza el algoritmo de Kruskal indica cuál de las siguientes respuestas representan los componentes conexas en el paso 6 (penúltimo) del algoritmo Ninguna es correcta {1,5,2}{3,4,6,7} {1,2,4}{3,5,6,7} {1,5,7}{2,3,4,6}.
Como ya estamos en la fase dos de estilo y con ello se vuelven a quedar en la casa de uno de ellos para hacer botellón.
Cuando vuelven de comprar colocan seis vasos en la fila y los rellena con las cantidades 5-9-2-0-2-1.
Listillo llama a uno de sus amigos que estudia diseño de algoritmos para que, mediante un algoritmo basado en programación dinámica le diga qué pasos tiene que elegir para beber la mayor cantidad posible.
Cuando su amigo le envía la información hay un problema en la red y solamente le llega la matriz de la imagen.
¿Podrías ayudar a Listillo a saber cuál de las cantidades máximas de líquido que puede beber? 14 Ninguna es correcta 12 16.
En el problema de la mochila resuelta con programación dinámica con "n" objetos y una capacidad "M" El valor de la celda (i, j) se calcula a partir de las celdas (i-1, j) y (i, j-pi) Los objetos siempre deben de considerarse en orden creciente de pesos El orden de complejidad es de O(n·M) La matriz necesaria para su resolución es de O(nxM).
Sea el vector de números enteros 23-29-29-31-9-41-44-10-20-40-13-35-30-31-39-40 se queda ordenada mediante el qsort Ninguna es correcta 9,13,20,10,23,41,44,31,29,40,29,35,30,31,39,40 13,29,29,31,9,31,30,10,20,23,35,40,44,41,39,40 9,10,20,13,31,41,44,29,29,40,40,35,30,31,39,23.
Al resolver un problema utilizando la técnica de divide y venceras Cuanto más problemas tengamos mejor será la eficiencia del final del algoritmo diseñado Todas son falsas La complejidad del algoritmo resultante no depende del tamaño de los subproblemas La complejidad de las funciones de descomposición y combinación no afecta a la complejidad final del algoritmo.
En la técnica de vuelta atrás Se realiza una búsqueda exhaustiva total en el patio de soluciones Los algoritmos diseñados son siempre polinomiales El número total de nodos del árbol explícito es el cardinal del conjunto de aquellos que satisfacen la función de factibilidad La función que determina si una solución parcial puede generar una solución completa se llama función de factibilidad.
El orden de complejidad en lo siguiente algoritmo divide y vencerás El elemento mayoritario es O(n·log(n)) Todas son ciertas La búsqueda de los elementos mayor y menor es lineal La exponencial discreta es logaritmico.
|
