« Novedades IAIC « || Inicio || » Calificaciones Lógica… »

Examen Bloque I. Noviembre 2016

Última modificación: 13 de Enero de 2017, y ha tenido 234 vistas

Puedes bajar el examen aquí (click botón derecho y Guardar Como...)

Puedes encontrar el examen resuelto aquí

EJERCICIO 1. (4 ptos) Vamos a usar la siguiente representación para grafos:

Se supone que cada nodo está etiquetado con un índice consecutivo a partir de \(0\), y tenemos una función booleana, \(vecinos?\), que para cada par de índices devuelve si los nodos asociados son vecinos o no.

Fijado un grafo de \(N\) nodos con un etiquetado dado y una función \(vecinos?\) que se proporciona, vamos a trabajar con el siguiente problema como objetivo:

Colorear el grafo con \(K\) colores, de forma que dos nodos vecinos no tengan el mismo color.

Se pide explícita y formalmente:

  1. (0.75 ptos) Da una representación de los posibles estados, y describe el espacio completo de estados. ¿Qué tamaño tiene este espacio?
  2. (0.25 ptos) ¿Cuál sería el estado inicial?
  3. (1 pto) Proporciona una función para saber si un estado es final.
  4. (1 pto) Proporciona una función de transición válida para resolver el problema como una búsqueda en el espacio de estados.
  5. (1 pto) Proporciona una función heurística que pudiera usarse con el algoritmo A* para resolver este problema.

EJERCICIO 2. (2 ptos) Dado el siguiente árbol de costes de un proceso Minimax:

Responde a las siguientes preguntas:

  1. (0.5 ptos) ¿Qué valor se propaga hasta \(A\)?
  2. (0.5 ptos) ¿Qué camino sigue este valor propagado? (indica la sucesión de nodos del camino)
  3. (1 pto) ¿Qué nodos NO necesitan ser evaluados si aplicas una Poda alfa-beta?

EJERCICIO 3. (4 ptos) Resuelve el siguiente problema por medio del algoritmo de Templado Simulado haciendo uso del modelo que se proporciona:

Tenemos \(10\) cartas numeradas del \(1\) al \(10\). Separarlas en \(2\) montones de forma que la suma de las cartas del primer montón esté lo más cerca posible a \(36\) y el producto de las cartas del segundo montón esté lo más cerca posible a \(360\).

« Novedades IAIC « || Inicio || » Calificaciones Lógica… »