AP ULPGC preguntas profesores

En general Tabulation es más rápido que Memoization: V. F.

En los algoritmos genéticos, usando como puntos de corte, [p1 = 5to, p2 = 9no] y los siguientes progenitores: (e, a, c,j, d, f, b, g, i, h) Padre (h, d, c, g, i, f, j, e, b, a) Madre ¿Cuál es el sucesor resultante de aplicar el operador de cruce PARCIAL para TSP?. (e,a,c,j, d,|f b, g, i|,h). (h,d,c,j,e,|f,b,g,i|,a). (h,d,c,e,j,|f,b,g,i|,a).

¿Cuál es una heurística de selección de valores?. Indomain_random. most_constrained. input_order.

Dado: Array[N] of var int: f; Array[N] of var int: invf; ¿Cuál sería la restricción equivalente a inverse(f, invf)?. Forall(i in Ninvf[]=1/f[1);. Forall(i,j in N)Cf[] =]j -> invf(] = 1);. Forall(ij in NCf[] = invf[] -> il=));.

La estrategia voraz: (marca todo lo que sea cierto). Es la estrategia del algoritmo de Prims. Es una estrategia de fuerza bruta con poda. Puede utilizarse para resolver el problema de la mochila 0/1. Se conoce también como estrategia avida. Es la estrategia del algoritmo de Kruskal. Es la estrategia del algoritmo de Dijkstra. Se conoce también como estrategia a lo ancho.

Indicar cuál de las siguientes estrategias constituye ruptura de simetría de valor. Input_order. Aplicar orden lexicográfico. Most_constrained. Smallest. Indomain Split. Indomain min.

¿Para qué sirve circuit en minizinc(array[int] of var int: x)?. Restringe los elementos de x para definir un circuito que x[i] = j signifique que j es el sucesor de i. Restringe los elementos de x tal forma que x [i] < x[i+1]. restringe los elementos de x para que sean todos distintos.

La programación dinámica se utiliza: (marca todo lo que sea cierto) Seleccione una o más de una: Cuando hay solapamiento entre los subproblemas y el problema tiene subestructuras óptimas. Cuando hay solapamiento entre los subproblemas y el problema no tiene subestructuras óptimas. Cuando no hay solapamiento entre los subproblemas y el problema tiene subestructuras óptimas. Cuando no hay solapamiento entre los subproblemas y el problema no tiene subestructuras óptimas. Las otras opciones son falsas.

En el análisis abreviado hay que identificar: La sección crítica. La operación crítica. La función crítica.

En el análisis asintótico. Se elimina el comportamiento transitorio del algoritmo. Se establece un umbral a partir del cual se tiene en cuenta el orden de la complejidad. Se define una función matemática que relaciona la secuencia de pasos de nuestro algoritmo con los datos que procesa del algoritmo.

¿En qué consiste el uso de Element Constraint?. Todas son falsas. Consiste en añadir una restricción a una variable de decisión. Consiste en hacer uso de variables de decisión como índices de otras variables de decisión. Consiste en usar como índices los valores de una variable de decisión.

La reificación consiste en utilizar una variable de decisión como índice de un array. V. F.

Una de las principales diferencias entre usar una restricción global como "Alldiferent" frente a varias restricciones de dominios , por ejemplo, x!= y, x!=z, y!= z, para los dominios: xe[1.2],ye[1..2],z€[1..3]. Alldiferent tiene en cuenta todos los dominios simultaneamente. Las restricciones de dominio tienen en cuenta todos los dominios simultaneamente. No existe diferencia alguna.

Indicar cuál de los siguientes problemas es NP-completo. Dado un grafo, obtener el número cromático. Máximo número de parejas estables. Circuito euleriano. Dado un grafo, encontrar la distancia más corta entre 2 nodos. Circuito hamiltoniano.

Si tenemos un primer algoritmo que coge los elementos de la mochila en orden decreciente en función de valor partido por el peso, y un segundo algoritmo, que simplemente ordena por orden decreciente los elementos en función de su valor. ¿Qué garantizará un tercer algoritmo que coge el máximo de los dos primeros algoritmos? Seleccione una: que llegamos como mínimo a dos veces del óptimo. No hay garantía de optimalidad. que llegamos como mínimo a 1/4 del óptimo. que llegamos como mínimo a la mitad del óptimo.

El algoritmo de consistencia de arco basicamente se realiza en tres pasos. ¿Cual será el tercer paso?. dividir cada restriccines en dos arcos. verificar, para cada arco, que las restricciones se pueden cumplir con el dominio de variable. añadir todos los arcos a una lista de trabajo.

Pregunta 1 En el problema del agente viajero (TSP) con algoritmos genéticos, , dado un corte establecido entre 2 puntos aleatorios, ¿qué estrategia de cruzamiento finalizado (crossover) permuta la zona cortada del padre con los correspondientes de la madre?. Cruce parcial. Cruce de ciclo. Cruce de orden.

¿En minizinc qué heurística de selección de variable, comienza por el dominio de cardinalidad menor y en caso de empate mayor cantidad de restricciones?. largest. most_constrained. input_order. first_fail.

¿Qué tipos de programación se encuentran bajo el paradigma de la programación declarativa? (marca todos los que sean verdaderos). Programación lógica. Programación con restricciones. Las otras opciones son falsas.

El recorrido BFS: (marca todo lo que sea cierto). Es la base del algoritmo de Dijkstra. Tiene una estrategia de conquista. Realiza una exploración en profundidad. Todas las otras opciones son correctas. Se programa con una cola. Se programa con un pila.

El algoritmo de Dijkstra (marca todo lo que sea cierto): Elige la arista de menor peso a uno de los vértices no visitados. Es un algoritmo voraz. Es un algoritmo BFS. Las otras opciones son falsas.

La estrategia voraz (marca todo lo que sea correcto): Poda los elementos que no llevan a la solución. Utiliza una pila para evitar bloquearse y procesar todos los casos. Nunca deshace las decisiones tomadas. Las otras opciones son falsas.

Cuando hablamos de "Orden lexicográfico” en simetría de variable nos referimos a: Un orden que se establece para máximizar la solución del problema. Un orden que se establece para conseguir la ruptura de simetría. Un orden que se establece para minimizar la solución del problema.

El orden de una sentencia condicional es: Ninguno de los anteriores. El orden de la rama más costosa. El orden de la rama más larga. El orden de la rama menos costosa. El órden de su condición.

La estrategia de fuerza bruta (marca todas las soluciones correctas). Las otras opciones son falsas. Puede programarse con funciones generadoras de evaluación perezosa. No se debe programar con generadores de evaluación perezosa. Puede programarse fácilmente en Python con iteradores.

Aplicaciones de DFS (marca todo lo que sea cierto): Camino más corto. Componentes conectados (grafo no dirigido). Orden topologico. Componentes conectados (grafo dirigido).

El recorrido DFS: (marca todo lo que sea cierto). Es la base del algoritmo de Dijkstra. Tiene una estrategia de conquista. Realiza una exploración en profundidad. Todas las otras opciones son correctas. Se programa con una cola. Se programa con un pila.

Los siguientes algoritmos implementan una estrategia de Reduce y Vencerás: (marca todo lo que sea correcto) Seleccione una o más de una: Merge Sort. Binary Search. QuickSort. Merge. Ninguna de las otras opciones. Linear Search. Quick Select. Partition.

Si podemos reducir un problema X a un problema Y, entonces: Y es tan difícil de resolver como X. No podemos concluir nada con la reducción. Ambas son correctas. X es tan difícil de resolver como Y.

¿Para qué sirve convertir las restricciones binarias en 2 arcos en el algoritmo AC-3?. Para permitir centrarse en una sola variable cada vez que se comprueba la consistencia de un arco. realmente no es necesario. para obtener restricciones redundantes, lo que no aporta información adicional, pero ayuda al resolutor a reducir el espacio de búsqueda.

¿Para qué sirve indomain_split?. divide el dominio en dos, y elige primero la mitad inferior. divide el dominio en dos, y elige primero la mitad superior. divide el dominio separando por el valor que pases como parámetro, si no pasas ninguno no hace nada.

Al programar el algoritmo genérico de búsqueda en un grafo ¿por qué recordamos los vértices que hemos visitado? (marca todo lo que sea cierto). Para asegurar que el algoritmo finaliza su ejecución. Es una optimización opcional del algoritmo que no es realmente necesaria. Para evitar procesar las aristas varias veces. Para evitar bucles en el procesamiento de las aristas. Para evitar procesar los vértices varias veces.

En análisis asintótico denominamos ejemplar: (marca todo lo que sea cierto). A cada uno de los posibles casos que se pueden dar como datos iniciales del problema. Ninguna es correcta. A cada uno de los posibles ficheros de entrada. A cada uno de los posibles casos que se pueden dar como datos iniciales del problema agrupados por ejemplar.

¿Qué contenedores son no mutables en python? (marca todos los que sean verdaderos). List(). String(). Tupla(). Dict().

En los algoritmos genéticos, usando como puntos de corte, [p1 = 5to, p2 = 9no] y los siguientes progenitores: (e, a, c,j, d, f, b, g, i, h) Padre (h, d, c, g, i, f, j, e, b, a) Madre ¿Cuál es sucesor resultante de aplicar el operador de cruce de ORDEN para TSP? Seleccione una: (e, a,c,j,d,|f,b,g,i|,h). (h,d,c,j,e,|f,b,g,i|,a). (h,d,c,e,j,|f,b,g,i|,a).

La estrategia de fuerza bruta: (marca todo lo que sea cierto). Es una estrategia basada en la definición del problema. Descarta las combinaciones que no llevan a la solución. Todas las otras opciones son verdaderas. Genera todas las combinaciones posibles de la solución. Requiere generar todas las combinaciones antes de procesarlas. Evalúa todas las combinaciones posibles de la solución. Genera algoritmos poco eficientes. En la práctica no se utiliza nunca.

Cual es el comando de Minizinc que usa como heurística de selección de variables el dominio con cardinalidad menor y en caso de empate mayor cantidad de restricciones?. input_order. most_constrained. largest domain_most restrictions. first fail.

En el algoritmo AC3, si se toma el arco (x1, x2) ¿Cuál de las variables puede ver su dominio afectado en este paso? ¿Y si se modifica el dominio, que arcos vuelven a la cola de trabajo?. Ninguna ve su dominio afectado. Se modifica el dominio de x1 y los arcos cuyo destino sea x1 vuelven a la cola. Se modifica el dominio de x2 y los arcos cuyo origen sea x1 vuelven a la cola. Se modifica el dominio de x1 y los arcos cuyo origen sea x2 vuelven a la cola.

En el algoritmo de Gale y Shapley, si una mujer m, tiene asignado un hombre h*, y recibe la propuesta de otro hombre, h, ¿puede m rechazar a h* en favor de h?. Verdadero. Falso.

¿En qué consiste la reificación de una restricción? *. En dividir una restricción para formar dos nuevas. En combinar dos restricciones para formar una nueva. Ninguna respuesta es correcta. En la transformación de la restricción en una variable booleana.

¿Cual podría ser el mejor principio para aplicarlo en el coloreado de mapas?. input_order. most_constrained. first_fail.

La programación dinámica (marca todo lo que sea correcto): Mejora la solución obtenida mediante la estrategia voraz. Mejora la solución obtenida mediante la estrategia divide y vencerás. Mejora la solución obtenida mediante la estrategia de fuerza bruta. Las otras opciones son falsas.

La programación dinámica es: (marca todo lo que sea cierto). Una estrategia que se aplica a problemas que se resuelven mediante la estrategia Divide y Vencerás cuando hay solapamiento de subproblemas. Una técnica que se aplica a problemas que se resuelven mediante la estrategia Divide y Vencerás cuando hay solapamiento de subproblemas. Es una estrategia de programación. Todas las otras opciones son falsas. Una técnica que evita repetir cálculos consumiendo memoria. Es una técnica específica para resolver el problema de la mochila. Es una metodología de programación. Una técnica que se utiliza en problemas sin solapamiento para evitar repetir cálculos.

Para obtener la solución óptima de un problema puedo utilizar: (marca todo lo que sea cierto). Divide y vencerás. Todas las otras opciones son válidas. Reduce y vencerás. Backtracking. Fuerza bruta. Programación dinámica. Greedy.

La estrategia de backtracking (marca todo lo que sea correcto): Se puede implementar de forma iterativa. Se puede implementar de forma recursiva. Se debe implementar de forma iterativa. Se debe implementar de forma recursiva.

El recorrido DFS (marca todo lo que sea cierto): Las otras opciones son falsas. Se programa con una pila. Es una estrategia de conquista. Realiza una exploración en profundidad.

El orden de una operación elemental es: N (por definición). Dependiente del coste de la operación. Las otras opciones son falsas. 1.

¿En el algoritmo AC-3, puede un arco eliminado previamente de la lista de trabajo volver a entrar?. Verdadero. Falso.

En el teorema maestro: n es el número de llamadas recursivas. a es el número de llamadas recursivas. b es el número de divisiones. a es el tamaño de cada subproblema. n/b es el tamaño de cada subproblema.

Para resolver eficientemente el problemas de una mochila con capacidad 200 mediante tabulation, si tenemos 300 items, ¿cual es el numero de columnas de la tabla?. 300. 201. 301. 200.

El Teorema Maestro se utiliza principalmente para: Resolver ecuaciones diferenciales. Determinar la complejidad temporal de algoritmos de tipo divide y vencerás. Calcular la memoria requerida por un programa. Analizar el comportamiento de algoritmos lineales.

¿Cuándo se aceptan soluciones que empeoran la actual en el algoritmo de Simulated annealing?. δ < 0. u < exp(-δ/T). No se aceptan soluciones que empeoran la actual. δ ≥ 0 y u < exp(-δ/T).

¿Cómo evita la búsqueda tabú quedarse atrapada en los óptimos locales?. Intercambia aristas aleatorias. Permite hacer movimiento que empeoran y con la lista tabú recuerda los movimientos que ha hecho recientemente y no los repite, por lo tanto, no vuelve al optimo local. Genera un número aleatorio y si supera un umbral realiza un movimiento que empeora la solución actual.

¿Qué característica tiene la búsqueda Tabú con el uso de la memoria a largo plazo?. Puede encontrar una solución satisfactoria en los óptimos locales. Diversifica la búsqueda sobre regiones vecinas sin explorar en búsqueda de soluciones globales más factibles. Almacena la historia de los últimos movimientos registrados en la lista tabú.

¿A qué nos referimos cuando hablamos de tenor del tabú en el método Tabu Search?. Número de iteraciones que un movimiento tabú no puede ser utilizado. Es otra manera de referirnos al criterio de aspiración. A la estructura donde se almacenan los movimientos recientes.

¿Qué aspecto de la búsqueda tabú intenta mejorar el criterio de aspiración?. Guarda las frecuencias de los movimientos y penaliza a los más frecuentes. La lista tabú puede ser excesivamente restrictiva y para que esto no penalice en la búsqueda, permite hacer un movimiento, aunque sea tabú, si es mejor que la mejor solución encontrada hasta el momento. Siempre que un movimiento sea mejor que el actual, ignora la lista tabú.