Preguntas del examen de ingreso al doctorado de la Universidad de Jilin Respuestas de Inteligencia Computacional 2001
Principios de Inteligencia Artificial 2004
1. Responda las siguientes preguntas (30 puntos)
1. ¿Cuáles son las ventajas de la búsqueda en amplitud? ¿Cuáles son las desventajas?
2. Intenta explicar el significado y la diferencia de los símbolos lógicos " " y "→".
3. Dé ejemplos de reducción y deducción de insumos incompletos.
4. Supongamos que S={P(x),Q(f(a))} es un conjunto de cláusulas. Dé un ejemplo en el que I sea la interpretación ordinaria de S en lugar de su interpretación de Herbrand. .
5. Por favor proporcione ejemplos en los que la fórmula no sea equivalente a su forma normal de Skolem.
6. ¿Qué es el algoritmo A? ¿Qué es el algoritmo A*? ¿Cuál es el algoritmo A* aceptable? ¿Cómo se comparan los dos algoritmos A*?
2. Resuelva los siguientes problemas (30 puntos)
1. Suponga que el problema de ocho dígitos tiene una función de valoración: f(n)=d(n)+W( n); donde d (n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de números "fuera de posición" en el nodo n. Intente proporcionar el proceso de búsqueda del gráfico con lo siguiente como inicial; nodo y nodo objetivo, e indicar la valoración de cada nodo, los valores de función y las rutas de solución generales, y calcular la penetración de este proceso de búsqueda. ¿Cuál es el coeficiente de ramificación efectivo?
3 4 5
2 6
1 8 7
3 4 5
8 6
p>
2 1 7
2. Convierta la fórmula G a la forma normal de Skolem y proporcione el conjunto de cláusulas S de G.
3. Utilice el sistema de deducción anticipada basado en reglas para probar las siguientes preguntas:
Hechos conocidos; Dibuja y/o diagrama la deducción.
3. Demuestre la primera forma del teorema de Herbrand: supongamos que S es un conjunto de cláusulas, entonces S es insatisfactorio si y sólo si todo árbol semántico completo correspondiente a S tiene un árbol semántico de cierre finito. (15 puntos)
4. Resuma el proceso α-β, tome el siguiente árbol de juego como ejemplo, realice la poda α-β en el orden en que se generan los nodos secundarios izquierdos primero y señale dónde ocurre la poda. ¿Dónde está la poda alfa y dónde está la poda beta? Indica el nodo donde se produjo la poda y el cambio en el valor de retorno del nodo inicial. En la figura, □ representa el punto máximo y ○ representa el punto mínimo. (15 puntos)
5. ¿Cuál es la deducción reductiva del conjunto de andamios? Intente demostrar la integridad de la deducción reductiva del conjunto de cláusulas básicas y del conjunto de andamios. (10 puntos)
Principios de Inteligencia Artificial 2003
1. Describa el proceso del algoritmo de búsqueda de gráficos GRAPHSEARCH; suponga que el problema de ocho dígitos tiene dos funciones de valoración: f1 (n) = d(n)+W(n); f2(n)=d(n)+P(n)+3S(n). Entre ellos, d(n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de dígitos "fuera de posición" en el nodo n y P(n) es la suma de la distancia de cada dígito. desde la posición objetivo. S (n) es la puntuación de secuencia obtenida de la siguiente manera: para los números en el círculo exterior no central, gire en el sentido de las agujas del reloj. Si el número después de un número no es su sucesor en el estado objetivo, entonces proporcione esto. número Obtenga 2 puntos, de lo contrario obtenga 0 puntos para la posición central, si hay un número, obtenga 1 punto, si no, obtenga 0 puntos; Luego sume todos los puntajes anteriores para obtener el puntaje de secuencia S (n). El estado inicial y el estado objetivo existentes se describen a continuación: dibuje los respectivos diagramas de proceso de búsqueda heurística, indique los valores de la función de valoración de cada nodo en el diagrama e indique el orden de expansión de los nodos. Se calcularon la permeabilidad respectiva y el coeficiente de ramificación efectiva. (40 puntos)
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
2 Resuma el proceso minimax y el proceso α-β de búsqueda de juegos, y tome el siguiente árbol de juegos como ejemplo para dar los resultados de los dos. procesos. Cada nodo devuelve un valor y la ruta buscada (dibuje dos diagramas de proceso). Para el proceso α-β, realice la poda α-β en el orden en que se produzcan los nodos secundarios izquierdos primero. Señale dónde ocurre la poda, dónde está la poda α y dónde está la poda β. Indica el nodo donde se produjo la poda y el cambio en el valor de retorno del nodo inicial. En la figura, □ representa el punto máximo y ○ representa el punto mínimo.
(20 puntos)
3. (27 puntos)
1. Suponga el conjunto de cláusulas y encuentre el dominio H de S, el conjunto atómico de S y el conjunto de casos base. de la cláusula.
2. Utilice el algoritmo de unificación para determinar si el conjunto de expresiones W = {Q (f (a), g (x)), Q (y, y)} se puede unificar. unificado, luego encuentre la unidad más general.
3. Utilice el método de deducción de tablas para demostrar la misma implicación.
4. Supongamos que S es un conjunto de cláusulas de lógica proposicional y P es un símbolo atómico que aparece en S. Por lo tanto, las cláusulas de S se pueden dividir en tres partes: la parte que contiene la palabra P y la parte que contiene la palabra ~P, y la parte S3 que no contiene el texto P o ~P. Sea , , demuestre que S es insatisfacible si y sólo si S1' y S2' son ambos insatisfacibles. (8 puntos)
5. Dé ejemplos en los que el sistema de deducción anticipada basado en reglas esté incompleto. (5 puntos)
Principios de Inteligencia Artificial 2002
1. Responda brevemente las siguientes preguntas (24 puntos)
1. un ejemplo para explicar Los componentes básicos de los sistemas de producción.
2. ¿Qué es el algoritmo A*? ¿Cuáles son las principales propiedades del algoritmo A*?
3. En el sistema de deducción basado en reglas, ¿qué es la sustitución compuesta unificadora? ¿Por qué debería considerar la compatibilidad de reemplazo?
4. En un sistema de deducción anticipada basado en reglas, ¿qué formas se requieren para las reglas y los objetivos?
5. ¿Está completo el sistema de deducciones anticipadas basado en reglas? ¿Está completa la deducción inversa? ¿Está completa la interpretación bidireccional?
6. En la búsqueda heurística, la función de valoración generalmente se define como f(n)=g(n)+h(n). Indique el significado de cada parte de la definición y explique por qué esta definición es. usado. .
7. En el algoritmo de unificación, suponiendo que W es un conjunto de expresiones no vacío y D es un conjunto de diferencias de W, entonces, ¿cuando D tiene qué forma, W no se puede unificar?
8. ¿Cuáles son los métodos de representación del conocimiento comúnmente utilizados? Responda brevemente las características de cada uno.
2. Determinar si está bien o mal (14 puntos)
1. Eventualmente se utilizará cualquier punto con f(n)≤f*(s) en la tabla OPEN. por el algoritmo A* Nodo seleccionado para expansión.
2. Si se cumple la restricción monótona, el valor f de la secuencia de nodos expandida por el algoritmo A* aumenta monótonamente.
3. Supongamos que θ y λ son dos sustituciones, entonces θ?λ=λ?θ.
4. Conjunto de expresiones W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))} es comprensible.
5. La penetración y el coeficiente de ramificación efectiva son métricas de complejidad espacial con respecto a la capacidad heurística de los métodos de búsqueda de gráficos.
6. El conjunto de cláusulas S es siempre falso si y sólo si para cada interpretación I, el caso base C' de cada cláusula C en S es falso por I.
7. Si alguna fórmula en lógica de primer orden es siempre falsa se puede determinar mediante el método de reducción.
3. (12 puntos)
1. Si E=Q(y, f(y, g(x))), θ={a/x, b/y , y/z},λ={a/x, z/y, f(x)/z}, encuentre Eθ, Eλ, Eθ?λ
2. Problema de cuatro reinas. La clasificación de reglas utiliza la función diagonal diag(i, j). Si diag(i, j) 4. Utilice el método de reducción para demostrar que el siguiente conjunto de cláusulas es insatisfactorio (anote todo el proceso de reducción y la sustitución unificada utilizada en cada paso de la reducción). (10 puntos) 5. Supongamos el sistema de producción PS, cuyo estado es DB={a, b, c, d, e, f, g, h, i, m}, las reglas de producción son: a→b, c→m, g→h, a→c, d→e, h→i, a→d, e→f, m→i , b→g, f→m Supongamos que a es el estado inicial, el costo de aplicación de la regla es 1 y el valor de la función heurística de cada estado es: Estado a b c d e f g h i m valor h 1 1 8 2 2 2 4 4 10 4 Utilice un algoritmo para dibujar el gráfico de búsqueda y el árbol de búsqueda del nodo c antes y después de la expansión. Es necesario marcar la expansión. orden y valoración de los nodos en el gráfico Valor de función, escriba los elementos en la tabla CERRADA y ABIERTA antes de expandir el nodo c. (15 puntos) 6. Dado el conjunto de cláusulas S={P(g(x), z), ~P(f(y), h(a))}, encuentre el conjunto atómico de S, El árbol semántico de S. Si se da una explicación I de S de la siguiente manera: D={1, 2} a g(1) g(2) f(1) f(2) h(1) h(2) P ( 1, 1) P(2, 2) P(2, 1) P(1, 2) 2 2 1 1 2 2 1 F F T T Por favor construya S correspondiente a I La H explica I*. (15 puntos) Principios de Inteligencia Artificial 2002 7. Realice la poda α-β en el siguiente árbol de juegos en el orden de dar prioridad a los nodos secundarios izquierdos e indique dónde. ocurre la poda, ¿dónde está la poda alfa y dónde está la poda beta? Indica el nodo donde se produjo la poda, el cambio en el valor de retorno del nodo inicial y la ruta buscada. En la figura, □ representa el punto máximo y ○ representa el punto mínimo. Explique bajo qué circunstancias el proceso general de poda α-β es más eficiente. (10 puntos) Principios de Inteligencia Artificial 2000 1. Responda brevemente las siguientes preguntas (24 puntos) 1. sistema. 2. Responder a la clasificación de los sistemas de producción y explicar sus respectivas ventajas y desventajas. 3. Describe qué tipo de sistema de producción es un sistema de producción conmutativo. 4. Explique la diferencia entre el proceso de búsqueda de gráficos no informativos y el proceso de búsqueda de gráficos heurísticos, y cite dos métodos típicos de búsqueda de gráficos no informativos. 5. Describir la definición de explicación lógica de primer orden. 6. A la hora de demostrar semánticamente que un conjunto de cláusulas es siempre falso, ¿basta con considerar únicamente la interpretación de Herbrand de este conjunto de cláusulas? ¿Por qué? 7. En el sistema de deducción basado en reglas, ¿qué es la sustitución compuesta unificadora? ¿Por qué debería considerar la compatibilidad de reemplazo? 8. ¿Cuáles son los tipos generales de aprendizaje automático? 2. Supongamos que el problema de ocho dígitos tiene una función de valoración: f(n)=d(n)+W(n) donde d(n) es la profundidad del nodo n en la búsqueda; árbol, W(n) ) es el número de dígitos "fuera de posición" en el nodo n. La descripción del estado inicial existente y la descripción del estado objetivo son las siguientes: 3 4 5 2 6 1 8 7 3 4 5 8 6 7 2 1 Dibuje un diagrama de proceso de búsqueda heurístico, indique el valor de la función de valoración de cada nodo en el diagrama e indique el orden de expansión del nodo. (20 puntos) 3. Utilice el método de deducción de tablas para demostrar que ***la misma implicación. (16 puntos) 4. Describe el algoritmo unificado y úsalo para encontrar W={P(a, x, f(g(y))), P(z, f(z) , la unidad más general de f(u))}. (Escribe los pasos de ejecución del algoritmo, 20 puntos) 5. Si quieres probar el algoritmo A* en un determinado problema de búsqueda de gráficos con una solución, intenta demostrar que siempre hay algo en el. OPEN la tabla en cualquier momento antes de que finalice el algoritmo A*. El nodo n', n' está en la ruta de solución óptima, satisfaciendo f(n')≤f*(s), donde s es el nodo inicial. (15 puntos) 6. En el método de razonamiento de reducción, es incompleto si solo se utiliza la reducción binaria sin tomar factores. (5 puntos) Principios de la Inteligencia Artificial Año xxxx 1. Responde las siguientes preguntas (20 puntos) 1. 2. ¿Cuáles son los factores que afectan la capacidad heurística del algoritmo A? 3. Describir las reglas de poda del proceso α-β. 4. ¿Cuáles son las mejoras importantes al principio de reducción? 5. Describir la forma general del estado inicial, las reglas y los objetivos del sistema de deducción anticipada basado en reglas. 2. Utilice la función de valoración: f(n)=d(n)+W(n) para resolver el problema de ocho dígitos, donde d(n) es la profundidad del nodo n en el árbol de búsqueda, W(n) es el número de dígitos "fuera de posición" en el nodo n. 3 2 1 4 8 5 6 7 3 8 2 4 6 1 5 7 Dibuje un diagrama de proceso de búsqueda heurística, indique el valor de la función de valoración de cada nodo en el diagrama e indique el orden de expansión de los nodos. (20 puntos) 3. Describe el algoritmo de unificación y utiliza este algoritmo para encontrar el conjunto de expresiones óptimo W={R(x, x), R(f(a), g(y))} Unidad general. (20 puntos) 4. Cuando se utiliza el algoritmo AO*, ¿qué condiciones debe satisfacer la función heurística? La siguiente figura es el gráfico AND/OR dado, donde n0 es el nodo inicial, {n7, n8} es el conjunto de nodos objetivo, h es la función heurística y se supone que el costo del conector k es k. Utilice el algoritmo AO* para resolver el diagrama de solución óptima. (20 puntos) n n0 n1 n2 n3 n4 n5 n6 n7 n8 h(n) 0 2 4 4 1 1 2 0 0 Cinco. Demuestre el teorema de completitud del siguiente método de reducción: si el conjunto de cláusulas base S es insatisfactorio, entonces hay una deducción de reducción de S para deducir la cláusula vacía. (20 puntos) Principios de la Inteligencia Artificial XXX Año A 1. Responde brevemente a las siguientes preguntas 1. ? 2. ¿De qué partes se compone el sistema de producción? ¿Cuál es la función de cada parte? 3. ¿Cuáles son las estrategias de control de los sistemas de producción? 4. ¿Qué es la búsqueda en profundidad? ¿Qué es la búsqueda en amplitud? 5. ¿Qué es la información inspiradora? ¿Cómo se utiliza? 6. ¿Cuáles son los factores que afectan la capacidad heurística del algoritmo A? 7. ¿Cuáles son los métodos básicos de medición de la capacidad heurística de los métodos de búsqueda? 8. ¿Cuál es la deducción reductiva para deducir la cláusula C del conjunto de cláusulas S? 9. ¿Qué es un sistema de producción conmutativo? 10. En reducción y deducción, ¿cuál es la sustitución unificada más común? 2. Describir el proceso básico de los sistemas de producción descomponibles. 3. Los estados inicial y objetivo del conocido rompecabezas de ocho números son: 1 2 3 8 4 7. 6 5 2 8 3 1 6 4 7 5 Supongamos la función de valoración: f(n)=d( n) +W(n), donde d(n) es la profundidad del nodo n en el árbol de búsqueda y W(n) es el número de dígitos "fuera de posición" en el nodo n. Dibuje un árbol de búsqueda que utilice esta función. Un algoritmo para resolver el problema. Marque el valor de la función de evaluación de cada nodo en el árbol y el orden en que se seleccionan los nodos de expansión. 4. Gráfico AND/OR conocido, donde n0 es el nodo inicial, {n7, n8} es el conjunto de nodos objetivo, h es la función heurística y se supone que el costo del k- El conector es k. Utilice el algoritmo AO* para resolver el diagrama de solución óptima. n n0 n1 n2 n3 n4 n5 n6 n7 n8 h(n) 0 2 4 4 1 1 2 0 0 5. prueba Una fórmula es el resultado lógico de un conjunto de fórmulas . Principio de Inteligencia Artificial xxxx año B 1. Responde brevemente a las siguientes preguntas 1. ¿Cuáles son los dos métodos principales de búsqueda de gráficos sin información? 2. Describe brevemente las ventajas y desventajas de diversas estrategias de búsqueda. 3. ¿Cuáles son los factores que afectan la capacidad heurística del algoritmo A? 4. ¿Cómo se definen las fórmulas en lógica de primer orden? 5. En lógica de primer orden, ¿cómo se define la interpretación de fórmulas? 6. En lógica proposicional, ¿qué dos paradigmas de fórmulas se utilizan comúnmente? 7. En lógica de primer orden, ¿qué dos paradigmas de fórmulas se utilizan comúnmente? 8. ¿Cuál es el dominio de Herbrand de un conjunto de cláusulas? 2. Intente describir el algoritmo de búsqueda de gráficos GRAPHSEARCH. 3. Los estados inicial y objetivo del conocido rompecabezas de ocho números son: 1 2 3 8 4 7. 6 5 2 8 3 1 6 4 7 5 Supongamos la función de valoración: f(n)=d( n) +W(n), donde d(n) es la profundidad del nodo n en el árbol de búsqueda y W(n) es el número de dígitos "fuera de posición" en el nodo n. Dibuje un árbol de búsqueda que utilice esta función. Un algoritmo para resolver el problema. Marque el valor de la función de evaluación de cada nodo en el árbol y el orden en el que seleccionar los nodos de expansión. 4. Escriba la forma normal Skolem de la siguiente fórmula: 5. Utilice el método de reducción para demostrar que el conjunto de cláusulas es insatisfactorio. 6. Utilice la estrategia de búsqueda de retroceso para resolver el problema de las cuatro reinas. La clasificación de reglas utiliza la función diagonal diag(i, j). Si diag(i, j)