En el problema del camino más corto de un grafo polietápico, ¿cuál de las siguientes afirmaciones es CIERTA? La solución ha de ser única. Si hay varias soluciones, éstas pueden tener distintas longitudes. Si hay varias soluciones, éstas pueden tener distinto número de etapas. Cualquier subcamino del camino solución es óptimo.
¿Cuál de las siguientes afirmaciones sobre el problema de las 8 reinas es CIERTA? Es de orden factorial. Es de orden O(n log n). Es de orden O(n) Es de orden O(n^2).
¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos, es CIERTA? Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de menos lados. Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de camino más corto. Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de camino más largo. Se puede usar para resolver el problema del viajante de comercio buscando cual es el ciclo de más lados.
¿Cuál de las siguientes afirmaciones sobre el problema de los subconjuntos es FALSA? El problema puede tener más de una solución. Para encontrar la solución óptima hay que evaluar todas las soluciones. Si los elementos están ordenados ascendentemente, si un elemento no entra en la solución, el siguiente sí podría entrar en la misma. Ordenando los elementos de manera ascendente se obtiene un criterio más eficiente al elegir los candidatos de la solución.
¿Cuál de las siguientes afirmaciones sobre el problema de los ciclos hamiltonianos, es CIERTA? Que el nodo que selecciones no haya sido seleccionado antes.
Que se conecte al último.
Si es el último, tiene que estar conectado con el primero. Que el nodo que selecciones no haya sido seleccionado antes Conectado al último Si es el último, tiene que estar conectado con el primero.
Seleccione la respuesta VERDADERA: La simplicidad e inmediatez son características deseables para un algoritmo. La simplicidad e inmediatez no son características deseables para un algoritmo.
Cuál es la llamada recursiva para el caso general del problema de la rayuela numeroCaminos(n) = numeroCaminos(n − 1) + numeroCaminos(n − 2) numeroCaminos(n) = numeroCaminos(n) + numeroCaminos(n − 1) numeroCaminos(n) = numeroCaminos(n − i) + numeroCaminos(n) numeroCaminos(i) = numeroCaminos(i) + numeroCaminos(i − 1).
Cuál es la llamada recursiva para el caso general del problema de los planos de la ciudad numeroCaminos(x, y) = numeroCaminos(x, y −1) + numeroCaminos(x−1, y) numeroCaminos(y, x) = numeroCaminos(x, y −1) + numeroCaminos(x−1, y) numeroCaminos(x, y) = numeroCaminos(x-1, y) - numeroCaminos(x, y-1) numeroCaminos(x, y) = numeroCaminos(x-1, y −1) + numeroCaminos(x−1, y-1).
El algoritmo de Hanoi es de orden O(n) O(1) O(2^m) o(n log n).
En el algoritmo de Hanoi cada llamada de orden m genera: Dos llamadas de orden m-1 Dos llamadas de orden m-2 Dos llamadas de orden m Dos llamadas de orden m^2.
En el algoritmo de la sucesión de Fibonacci por recursividad, el orden es de tipo: O(2^n) O(n) O(n^2) O(1).
La estrategia del divide y vencerás consiste en: La división de los n datos de entrada en k subconjuntos distintos, donde
1 < k ≤ n, obteniéndose k subproblemas, del mismo carácter que el original. La multiplicación de los n datos de entrada en k subconjuntos distintos, donde
1 < k ≤ n, obteniéndose k subproblemas, del mismo carácter que el original. La división de los n-1 datos de entrada en k subconjuntos distintos, donde
1 < k ≤ n, obteniéndose k subproblemas, del mismo carácter que el original.
En que consiste el algoritmo de búsqueda binaria en DyV: Siendo vk el elemento central La estrategia del método implica la división del entorno del problema inicial en 3 subentornos, originando 3 problemas del mismo carácter que el de partida. Se selecciona un índice k, que
suele ser la posición del elemento central del vector, de forma tal que ahora se tienen 3 subentornos: La solución de 2 de los 3 subproblemas correspondientes a estos entornos es inmediata, y se obtiene comparando x con vk. La estrategia del método implica la división del entorno del problema inicial en 3 subentornos, originando 3 problemas del mismo carácter que el de partida. Se selecciona un índice k, que
suele ser la posición del elemento central del vector, de forma tal que ahora se tienen 3 subentornos: La solución de 2 de los 3 subproblemas correspondientes a estos entornos es inmediata, y se obtiene comparando x con vn. La estrategia del método implica la división del entorno del problema inicial en 2 subentornos, originando 2 problemas del mismo carácter que el de partida. Se selecciona un índice k, que
suele ser la posición del elemento central del vector, de forma tal que ahora se tienen 2 subentornos: La solución de 1 de los 2 subproblemas correspondientes a estos entornos es inmediata, y se obtiene comparando x con vk.
En el algoritmo del máximo y el mínimo, el peor y mejor caso posible se da cuando: El vector está ordenado de forma decreciente y el número de comparaciones es 2(n-1) y que el vector esté ordenado de forma creciente y el número de comparaciones sea (n-1), respectivamente El vector está ordenado de forma creciente y el número de comparaciones es 2(n-1) y que el vector esté ordenado de forma decreciente y el número de comparaciones sea (n-1), respectivamente El vector está ordenado de forma creciente y el número de comparaciones es (n-1) y que el vector esté ordenado de forma decreciente y el número de comparaciones sea 2(n-1), respectivamente.
En el algoritmo del máximo y el mínimo: Este algoritmo buscará el máximo y el mínimo en el intervalo de indices que va de i a j en el vector v. Los casos en los que i = j y i = j − 1 se tratan de forma separada. Para subvectores con más de dos elementos, se hace un tratamiento similar al de la búsqueda binaria. Este algoritmo buscará el máximo y el mínimo en el intervalo de indices que va de i a j en el vector v. Los casos en los que i = j y j = i − 1 se tratan de forma separada. Para subvectores con más de dos elementos, se hace un tratamiento similar al de la búsqueda binaria. Este algoritmo buscará el máximo y el mínimo en el intervalo de indices que va de i a 2*j en el vector v. Los casos en los que i = j y i = j − 1 se tratan de forma separada. Para subvectores con más de dos elementos, se hace un tratamiento similar al de la búsqueda binaria.
En el algoritmo de los k-menores: Se usa la idea de la partición como en quicksort y se utiliza para obtener los elementos k menores de un vector, dando como resultado los k menores y el vector de forma ordenada. Se usa la idea de la partición como en quicksort y se utiliza para obtener los elementos k menores de un vector, dando como resultado los k menores y el vector de forma desordenada, pudiendo coincidir casualmente en alguna ocasión que alguno de los dos o los dos estén ordenados siempre. Se usa la idea de la partición como en quicksort y se utiliza para obtener los elementos k menores de un vector, dando como resultado los k menores y el vector de forma desordenada.
En el algoritmo de los k-menores: En cada iteración se escoge un pivote y se hacen tantas operaciones necesarias como se necesiten para que todos los elementos de la izquierda del pivote sean menores a este y los de la derecha sean mayores. En cada iteración se escoge un pivote y se hace una operación para que un elemento del lado izquierdo que sea mayor pase al lado derecho y viceversa. En cada ejecución se escoge un pivote y se hacen tantas operaciones necesarias como se necesiten para que todos los elementos de la izquierda del pivote sean menores a este y los de la derecha sean mayores.
En las operaciones de suma, resta, multiplicación y división, se puede considerar que el tiempo
que se invierte en ellas está acotado superiormente en función del ordenador utilizado. Verdadero Falso.
En caso de que se precise trabajar con enteros muy grandes y con precisión, de forma tal que puedan ser almacenados en coma flotante, es necesario
implementar su almacenamiento y manipulación mediante software. Verdadero Falso.
Según los dos algoritmos de multiplicación de enteros vistos en clase, estos son de orden: O(n^2) y o(n^log3) O(n) y o(n^log3) O(n^2) y o(n^3) O(n) y o(n).
El algoritmo de ordenación por fusión consiste en: Descomponer el vector en dos partes cuyos tamaños sean similares, ordenar las dos partes mediante llamadas recursivas y finalmente fusionar las soluciones de cada parte de forma tal que se mantenga el orden Descomponer el vector en tres partes cuyos tamaños sean similares, ordenar las tres partes mediante llamadas recursivas y finalmente fusionar las soluciones de cada parte de forma tal que se mantenga el orden Descomponer el vector en dos partes cuyos tamaños no necesariamente deben ser similares, ordenar las dos partes mediante llamadas recursivas y finalmente fusionar las soluciones de cada parte de forma tal que se mantenga el orden.
La forma más eficiente de realizar el algoritmo de fusión es usando un: Centinela Doble bucle iterativo/recursivo Bucle Hacer-Hasta.
La complejidad del algoritmo de fusión es de orden: O(nlogn) O(n) O(logn).
La complejidad de uno de los algoritmos de exponenciación es de orden: O(n) siempre y cuando las multiplicaciones se consideren como operaciones elementales. O(n) O(n) siempre y cuando las divisiones se consideren como operaciones elementales.
La complejidad de dos de los algoritmos de exponenciación son de orden: O(m^log3 n^2) y de O(m^log3 n^log3). Y O(m^2 n^2) si se usa la multiplicación clásica O(m^log2 n^3) y de O(m^3 n^log2). Y O(m^2 n^2) si se usa la multiplicación clásica O(mn) y de O(m^2 n^2). Y O(m^2 n^2) si se usa la multiplicación clásica.
Los Algoritmos Voraces dividen el problema Falso Verdadero.
Cuando es posible usar un Algoritmo Voraz: Cuando la solución se pueda obtener a trozos Cuando la solución se pueda obtener sin partirla Cuando la solución no se pueda obtener a trozos Ninguna es correcta.
En un Algoritmo Voraz: Se puede volver atrás siempre Una vez escogido un camino, no hay vuelta atrás Puedes volver hacia atrás siempre y cuando te lo permita el algoritmo Ninguna es correcta.
Un Algoritmo Voraz: Se basa en la información que se posee de modo inmediato, sin tener en cuenta las consecuencias que pueden tener en el futuro las decisiones que se toman en un momento puntual. Se basa en la información que se posee de modo regular, teniendo en cuenta que puedes volver hacia atrás siempre que quieras. Se basa en la información que se posee de modo inmediato, teniendo en cuenta las consecuencias que pueden tener en el futuro las decisiones que se toman en un momento puntual. Ninguna es correcta.
En el Algoritmo problema del cambio se dice que es VORAZ porque: Porque en cada paso selecciona la mayor de las monedas que se pueda escoger, sin preocuparse si esta decisión es la correcta a la larga. Porque cada dos pasos selecciona la mayor de las monedas que se pueda escoger, sin preocuparse si esta decisión es la correcta a la larga. Porque en cada paso selecciona la menor de las monedas que se pueda escoger, sin preocuparse si esta decisión es la correcta a la larga. Ninguna es correcta.
En que caso el Algoritmo Voraz del Cambio es optimo Para los valores dados de las monedas, pero si cambiamos estos valores o si tenemos alguna limitación en el suministro de una moneda el algoritmo puede producir una solución que no sea óptima. Para los valores dados de las monedas, pero si cambiamos estos valores o si no tenemos limitaciones en el suministro de una moneda el algoritmo puede producir una solución que no sea óptima. Para los valores dados de las monedas, pero si cambiamos estos valores o si tenemos alguna limitación en el suministro de una moneda el algoritmo puede producir una solución que sea optima. Ninguna es correcta.
En los Algoritmos Voraces, a medida que avanzamos en la solución se van acumulando dos conjuntos. Uno
contiene candidatos evaluados y seleccionados y el otro contiene los evaluados y rechazados. Verdadero Falso.
En los Algoritmos Voraces cada vez que se añade un candidato definitivamente, se comprueba si el conjunto obtenido es una solución del problema. Verdadero Falso.
Los Algoritmos Voraces funcionan siempre correctamente Verdadero Falso.
En los Algoritmos Voraces: La función de selección suele estar relacionada
con la función resolución La función de selección suele estar relacionada
con la función objetivo La función de selección suele estar relacionada
con la función inserción.
Los Algoritmos Voraces son siempre de orden O(n^2) Más falso que Alberto callado en una clase de FSIV Verdadero, pero estás seguro que es verdadero ¿?.
Los Algoritmos Voraces son de orden: O(n^2) y O(n^3) O(n) y O(n^2) O(nlogn) y O(logn) O(n^2) y O(n^3), bajo determinadas condiciones.
Los Algoritmos Voraces son de orden O(n^2) y O(n^3) siempre que: O(n^2): Cuando el tiempo consumido por
las funciones objetivo y de selección sea constante, O(n^3): Cuando el tiempo consumido por la función objetivo sea lineal. O(n^2): Cuando el tiempo consumido por
las funciones inserción y de selección sea constante, O(n^3): Cuando el tiempo consumido por la función objetivo sea lineal. O(n^2): Cuando el tiempo consumido por
las funciones objetivo y de selección sea constante, O(n^4): Cuando el tiempo consumido por la función objetivo sea lineal.
En que consiste el problema de la mochila Llenar la mochila con dichos materiales, de forma tal que se maximice el valor de la misma considerando el coste de los materiales que introduciremos en ella. Vaciar la mochila con dichos materiales, de forma tal que se maximice el valor de la misma considerando el coste de los materiales que introduciremos en ella. Llenar la mochila con comida, de forma tal que se maximice el valor de la misma considerando el coste de la comida que introduciremos en ella.
Como podemos resolver el problema de la mochila con Algoritmos Voraces: Se define el conjunto de los datos del problema y los candidatos que asociaremos a dicho conjunto de datos para obtener la solución. Se define el conjunto de los datos de la solución y los candidatos que asociaremos a dicho conjunto de datos para obtener la solución. Se define el conjunto de los datos del problema y los candidatos que asociaremos a dicho conjunto de datos para obtener el problema final.
Cual sería la estrategia general del problema de la mochila con Algoritmos Voraces: La estrategia general sería seleccionar en cada paso un material, siguiendo un orden adecuado, poniendo la mayor cantidad posible de dicho material en la mochila y acabar cuando ésta esté llena. La estrategia general sería seleccionar en cada paso un material, siguiendo un orden descendente, sacando la mayor cantidad posible de dicho material de la mochila y acabar cuando ésta esté vacía. La estrategia general sería seleccionar en cada paso un material, siguiendo un orden adecuado, poniendo la menor cantidad posible de dicho material en la mochila y acabar cuando ésta esté llena.
Cual es el criterio de elección de material en el problema de la mochila con Algoritmos Voraces: En cada etapa se seleccionará aquel material, aún no seleccionado, que haga crecer el coste de la mochila en la mayor medida posible. En cada etapa se seleccionará aquel material, aún ya seleccionado, que haga crecer el coste de la mochila en la mayor medida posible. En cada etapa se seleccionará aquel material, aún no seleccionado, que haga disminuir el coste de la mochila en la mayor medida posible.
En que consiste el Algoritmo de Kruskal Consiste en encontrar un árbol abarcador de coste mínimo en un grafo conexo y ponderado. Consiste en encontrar un árbol abarcador de coste máximo en un grafo conexo y ponderado. Consiste en encontrar un árbol abarcador de coste mínimo en un grafo conexo.
En que consiste el Algoritmo de Kruskal Se ordenan todos los lados y se van escogiendo según su coste y el número de los nodos vertice. Se van escogiendo lados según su coste y el número de los nodos vertice. Nunca se deben ordenar los lados, simplemente se van escogiendo según su coste y el número de los nodos vertice.
El problema del viajante de comercio resuelto por algoritmos voraces Siempre obtiene una solución optima. Siempre obtiene una solución no-optima. aunque cercanas a la óptima según en que ocasiones. A veces obtiene una solución no-optima.
En que consiste el problema del viajante de comercio: Consiste en ver en que orden ha de visitar esas ciudades para que la distancia total recorrida sea mínima. Verdadero Falso.
El problema de la mochila es de orden O(kn) y O(nlogn), en los siguientes casos respectivamente:
·Obtener los precios en orden decreciente 1 a 1, sin tener que ordenarlos todos
·Ordenarlos todos O(n) y O(logn), en los siguientes casos respectivamente:
·Obtener los precios en orden decreciente de 1 a n, Ordenanlos todos
·Sin ordenarlos todos O(kn) y O(nlogn), en los siguientes casos respectivamente:
·Obtener los precios en orden decreciente 1 a 1, sin tener que ordenarlos todos
·Sin ordenar ninguno.
En el problema del viajante de comercio: Si quisieramos evaluar todas las posibilidades y estimar la mínima, el algoritmo sería de orden n y sería inviable para un número elevado de ciudades Verdadero Falso.
En el problema del viajante de comercio: Podemos hacer ciclos siempre que lo necesitemos. No se pueden hacer ciclos nunca Podemos hacer ciclos pero cuando el problema nos lo indique No se pueden hacer ciclos nunca, unicamente en la última iteración para cerrar el recorrido.
En el problema del viajante de comercio, SEGUN HEMOS VISTO EN CLASE: Se puede abarcar mediante un grafo para representar las distancias y las ciudades. Se puede abarcar mediante una lista para representar las distancias y las ciudades. Se puede abarcar mediante un vector para representar las distancias y las ciudades.
|
