• Author / Uploaded
• Daniel Prado

Citation preview

PRACTICA 2 ALUMNO:Kevin Sanchez CURSO:IA 1.

Da una gramática de la forma Backus-Naur para la sintaxis de la lógica proposicional. Tomando :

2.

Muestra que las siguientes fórmulas son tautologías:

A)

No es tautológica B)

S i es tautológica C)

Si es tautológica D)

Si es tautológica 3.

Transforma las siguientes fórmulas en la forma normal conjuntiva:

A)

B) C) No es posible 4.Chequea las siguientes oraciones para satisfacción o validación:

A) SATISFACTORIO B) VERDADERO C) NO SATISFACTORIO 5. Usando un lenguaje de programación de tu elección, programe un prover de teoremas para lógica proposicional usando el método de la tabla de verdad en la forma normal conjuntiva. Para evitar un caro chequeo sintáctico de las fórmulas, puedes representar cláusulas como lista o conjunto de literales, y las fórmulas como listas o conjuntos de cláusulas. El programa debe indicar si la fórmula es insatisfactible, satisfactible, o verdad, y mostrar el número de las diferentes interpretaciones y modelos. 6.

Resolver:

a)

Muestre que modus ponens es una regla de inferencia válida, al mostrar que

A ∧ (A ⇒ B) ⇒ B es una tautología. El teorema de deducción asegura así la corrección de la regla de inferencia. b) Muestre que la regla de resolución es una regla de inferencia válida Mostramos por el método de tabla de verdad que (A ∨ B) ∧ (¬ B ∨ C) ⇒ (A ∨ C) es una tautología 7. Muestre por aplicación de la regla de resolución que, en la forma normal conjuntiva, la cláusula vacía es equivalente a la oración falsa. Aplicando la regla de resolución a la cláusula:

(f ∨ B) y (¬B ∨ f) produce la solución (f ∨ f) ≡ (f). Ahora aplicamos la regla de resolución a las cláusulas B y ¬B y se obtiene la cláusula vacía como la solución. Como (f ∨ B) ≡ B y (¬B ∨ f) ≡ ¬B, (f) ≡ ( ). Es importante en la práctica que, siempre que el vacío cláusula se deriva, se debe a una contradicción.

8. Muestre que, con resolución, uno puede derivar cualquier cláusula arbitraria de la base de conocimiento que contiene una contradicción. Si KB contiene una contradicción, entonces hay dos cláusulas A y ¬A, que permiten derivar la cláusula vacía La contradicción en KB está claramente todavía en KB ∧ ¬Q. Por lo tanto, también permite derivar la cláusula vacía. 9. Formalice las siguientes funciones lógicas con los operadores lógicos y muestre que tu fórmula es válida. Presente el resultado en CNF. A) la operación XOR entre 2 variables : (A ∨ B) ∧ (¬A ∨ ¬B) B) la oración “por lo menos 2 de 3 variables A,B,C son verdad” : (A ∨ B) ∧ (B ∨ C) ∧ (A ∨ C) 10. Resuelva el siguiente caso con la ayuda de una prueba de resolución: “Si el criminal tiene un cómplice, luego el llegó en carro. El criminal no tiene un cómplice y no tiene la llave, o el tuvo la llave y un cómplice. El criminal tiene la llave. ¿Vino el criminal en carro o no? Formalización: Cómplice: A, Carro: C, Clave: K WB ≡ (A ⇒ C) ∧ [(¬A ∧ ¬K) ∨ (A ∧ K)] ∧ K Convirtiendo a CNF: (¬A ∧ ¬K) ∨ (A ∧ K) ≡ (¬K ∨ A) ∧ (¬A ∨ K) Intenta demostrar C y agrega ¬C al conjunto de cláusulas. El conjunto de cláusulas CNF es (¬A ∨ C)1 ∧ (¬K ∨ A)2 ∧ (¬A ∨ K)3 ∧ (K)4 ∧ (¬C)5. Resolución proof : Res(2, 4) : (A)6 Res(1, 6) : (C)7 Res(7, 5) : ()8 Se demuestra que el criminal vino en carro 11.

Muestre por resolución que las fórmulas del Ejercicio: a) b)

2(d) es una tautología 4(c) es insatisfacible o contradicción.

a) KB ≡ (A ∨ B) ∧ (¬B ∨ C), Q ≡ (A ∨ C) KB ∧ ¬Q ≡ (A ∨ B)1 ∧ (¬B ∨ C)2 ∧ (¬A)3 ∧ (¬C)4 Solución: Res(1, 3) : (B)5 Res (2, 4) : (¬B)6 Res (5, 6) : () b) ¬(¬B ∧ (B ∨ ¬A) ⇒ ¬A) ≡ (¬B)1 ∧ (B ∨ ¬A)2 ∧ (A)3

Solución: Res(1, 2) : (¬A)4 Res(3, 4) : () 12.

Pruebe las siguientes equivalencias, las que son importantes para trabajar con las cláusulas de Horn:

Usando equivalencias son probables las reclamaciones dadas

13.

Muestre por resolución SLD que el siguiente conjunto de cláusulas de Horn es insatisfacible o contradicción

PRACTICA 3 1. Prueba lo siguiente: para un árbol con factor de ramificación constante grande b, casi todos los nodos están es el último nivel de profundidad d. Muestra además que esto no es siempre cierto cuando el f.r. efectivo es grande pero no constante. En el último nivel existen b*d nodos, todos los niveles anteriores tienen:

Nodos, si b se agranda. Porque bd/bd-1 = b hay tantos nodos b en el último nivel como en todos los otros niveles juntos. 2. Calcula el f.r. promedio para el problema del puzzle-8 sin chequear los ciclos. El f.r. promedio es el f.r. que tendría un árbol de igual número de nodos en el último nivel, f.r. constante e igual de profundo. Calcula además el f.r. promedio para el puzzle-8 con búsqueda no uniforme mientras se evitan los ciclos de longitud 2. Podemos calcular el promedio del factor de ramificacion bm de b2m =8 a b2m =√8. Aquí el cálculo no es tan simple porque el nodo raíz del árbol es más pesado que todos los demás. Sin embargo, podemos decir que en el interior del árbol, el factor de ramificación es exactamente 1 más pequeño que sería sin el control del ciclo.

3.

¿cuál es la diferencia entre el f.r. promedio y el efectivo?

Para la media f.r el número de nodos hoja es fijo. Para el f.r efectivo, en contraste, el número de nodos en el árbol todo es fijo. 4. ¿por qué el f.r. efectivo encaja mejor para análisis y comparación del tiempo de computación de algoritmos de búsqueda que el f.r. promedio? Porque el número de todos los nodos en el árbol es generalmente una mejor medicióndel tiempo de cómputo para la búsqueda de un árbol comple to que el número denodos hoja. 5. Muestre que para un árbol de ramificación pesado con n nodos y profundidad d, el f.r efectivo aproximadamente igual al f.r. Promedio, así es igual a

es

Para un b grande tenemos n ≈ b¯(d+1)/b¯ = b¯(d) , rendimiento b¯ = d√ n. 6. Calcula el tamaño del espacio de estados para un problema del puzzle-8, para el análogo problema puzzle-3 (matriz 2x2), así como para el problema puzzle-15 (matriz 4x4). 3-puzzle: 4! = 24 estados, 8-puzzle: 9! = 362 880 estados, 15-puzzle: 16! = 20 922 789 888 000 estados. 7. Prueba que el gráfico de estados consiste en estados (nodos) y acciones (enlaces) para el puzzle-3 cae en 2 grafos conectados entre los cuales no hay conexiones. Después de mover el vacío cuadrado 12 veces en la dirección a vez y así crear un espacio secundario cíclico con 12 Estados.

la derecha y

alcanzar el

estado de partida otra

8.

Con la búsqueda por amplitud del puzzle-8, halla un camino (manualmente) desde el nodo inicial

hasta el nodo final h1 y la heurística h2

usando la heurística

9. Muestra que el algoritmo de búsqueda por amplitud, dado costo constante para todas las acciones, es garantizado que encontrará la solución más corta. Además muestra que esto no es el caso para costos variables. Desde un costo constante 1 el costo de todos los caminos en profundidad d son pequeños que los costos de los caminos en profundidad d+1. Desde todos los nodos en profundidad d son probados después del primer nodo en profundidad d+1, una solución de largo d es garantizada ser encontrada después de una solución de largo d+1. Para el árbol de búsqueda vecinos, se generan primero número del nodo 2 y elnúmero de nodo de solución 3 de cost o 10. La búsqueda termina. No se generan losnodos 4 y 5 con los costes de ruta de 2 cada uno. Por lo tanto, la solución óptima no se encuentra. 10.

Usando la búsqueda A* para puzzle-8, busca manualmente un camino desde el nodo inicial

final h1 y la heurística h2 Revisar ejercicio 8

usando

la

hasta el nodo

heurística

11. Construye el árbol de búsqueda A* para el grafo de ciudades de Ulm y sus alrededores (slide 31) y usa la distancia de vuelo entre Ulm y las otras ciudades como heurística. Inicia en Bern con Ulm como destino. Cuida que cada ciudad solo aparezca una vez en el camino.

12.

¿cuál es la relación entre la imagen de la pareja en el cañon (la flor) y una heurística admisible?

Al igual que un heurístico admisible, la esposa subestima la distancia a la meta. Estopodría resultar en dos de ellos en contrar la forma más rápida a la meta, aunque congran esfuerzo. Esto sólo es cierto, sin embargo, si la señora siempre subestima ladistancia.

13. El árbol de búsqueda para el juego de 2 jugadores dado en el siguiente slide con los rangos de todos los nodo hojas. Use la búsqueda minMax con alpha-beta pruning de izquierda a derecha. Cruza todos los nodos que no son visitados y da un rating resultado óptimo para cada nodo interno. Marca el camino elegido.

PRACTICA 4 EJERCICIOS 1. Prueba la proposición del Teorema 7.1



Ejemplo: En los juegos de dados, la probabilidad de lanzar un 6 es 1/6. La probabilidad de lanzar un número impar es ½ Lanzar un dado una vez: Ω = {1, 2, 3, 4, 5, 6} Lanzar un número par: Ω = {2, 4, 6} no es un evento elemental. Lanzar un número menor que 5 Ω = {1, 2, 3, 4} no es un evento elemental Razón: Con 2 eventos A y B, es un evento Ω es un evento seguro El conjunto vacío ϕ es el evento imposible En vez de escribimos por que

ENTONCES La probabilidad de lanzar un 5 o 6 es 1/3.

2. . 3. . 4. En un show sw preguntas de TV, el contestante debe escoger entre 3 puertas cerradas. Detrás de una puerta el premio espera: un automovil. Detrás de las otras puertas hay 2 cabras. El contestante escoge una, p.e, la nro 1. El anfitrión que sabe donde está el carro abre otra puerta, p.e, la nro 3 y una cabra aparece. El

contestante tiene la oportunidad de escoger entre las 2 restantes (1 y 2). Cual es la mejor elección desde su punto de vista? Quedarse con la puerta originalmente escogida? O cambiarla? 5. . 6. . 7. . Dadas las restricciones P(A)=α y P(AvB)=β, manualmente calcula P(B) usando el método MaxEnt. Usa PIT para chequear tu solución.

Marginalización:

Con solamente teoría de probabilidad clásica:

 P(B) = β. α 8. . 9. . 10. Considere usar el sistema PIT para resolver la siguiente red Bayesiana con 3 variables binarias A, B, C y P(A)=0.2, P(B)=0.9, así como CPT mostrada aquí: a) Calcula P(A|B)

PIT Input file

output

. . El jardinero Max quiere analizar estadísticamente su cosecha de guisantes anual. Cada vaina de guisante que recolectó la midió su longitud xi en cms y su peso yi en gramos. Dividió los guisantes en 2 clases, los buenos y los malos (vainas vacías). Los datos medidos (xi,yi) son:

X Y

BUENOS 122334456 234455666

MALOS 4667 2233

a) calcula las probabilidades P(y>3)|clase=bueno) y P(y3) y P(clase=bueno| y3)=7/13 P(y3)|clase=bueno)=7/9 P(y3)= P(y>3)|clase=bueno) P(clase=bueno)/P(y>3) P(clase=bueno| y>3)=(7/9*9/13)/(7/13)=1 P(clase=bueno| y 1x4 (1 valor por función) (m x n) * (n * m) X es 14 × 4, y es 14 × 1, θ es 4 × 1

Problema 14: Supongamos que tiene un conjunto de datos con m = 1000000 ejemplos y n = 200000 características para cada ejemplo. Desea utilizar la regresión lineal multivariante para ajustar los parámetros θ a nuestros datos. ¿Deberías preferir el descenso de gradiente o la ecuación normal? Responder Solucion: Descenso de gradiente, ya que (XTX) - 1 será muy lento de calcular en la ecuación normal. Con n = 200000 funciones, deberá invertir una matriz 200001 × 200001 para calcular la ecuación normal. Invertir una matriz tan grande es computacionalmente costoso, por lo que el descenso de gradiente es una buena opción. Problema 15: ¿Cuál de las siguientes son razones para usar la escala de características? Solucion: Se acelera el descenso del gradiente haciendo que requiera menos iteraciones para llegar a una buena solución. El escalado de características acelera el descenso del degradado al evitar muchas iteraciones adicionales que se requieren cuando una o más características adquieren valores mucho más grandes que el resto.

PROBLEMAS EN OCTAVE PROBLEMA 1: Supongamos que primero ejecuto los siguientes comandos de Octave: A = [1 2; 3 4; 5 6]; B = [1 2 3; 4 5 6];

¿Cuáles de los siguientes son entonces comandos válidos de Octave? Marque todo lo que corresponda. (Sugerencia: A 'denota la transposición de A.) Solucion: C = B '+ A;

PROBLEMA 2:

Dado A

¿Cuál de las siguientes expresiones de indexación da

Solucion: B = A(:, 1:2); B = A(1:4, 1:2);

PROBLEMA 3: Sea A una matriz de 10x10 yx sea un vector de 10 elementos. Su amigo quiere calcular el producto Ax y escribe el siguiente código:

v = zeros(10, 1); for i = 1:10 for j = 1:10 v(i) = v(i) + A(i, j) * x(j); ¿Cómo vectorizaría este código para ejecutar sin ningún bucle for? Marque todo lo que corresponda. end end Solucion: v = A * x;

PROBLEMA 4: Supongamos que tiene dos vectores de columna v y w, cada uno con 7 elementos (es decir, tienen dimensiones 7x1). Considera el siguiente código: z = 0; for i = 1:7 z = z + v(i) * w(i); end ¿Cuál de las siguientes vectorizaciones calcula correctamente z? Marque todo lo que corresponda. Solucion:

z = v' * w; PROBLEMA 5: En Octave, muchas funciones funcionan con números únicos, vectores y matrices. Por ejemplo, la función sin cuando se aplica a una matriz devolverá una nueva matriz con el pecado de cada elemento. Pero debes tener cuidado, ya que ciertas funciones tienen un comportamiento diferente. Supongamos que tiene una matriz X de 7x7. Desea calcular el registro de cada elemento, el cuadrado de cada elemento, sumar 1 a cada elemento y dividir cada elemento entre 4. Almacene los resultados en cuatro matrices, A, B, DISCOS COMPACTOS. Una forma de hacerlo es el siguiente código: for i = 1:7 for j = 1:7 A(i, j) = log (X(i, j)); B(i, j) = X(i, j) ^ 2; C(i, j) = X(i, j) + 1; D(i, j)de= los X(i,siguientes j) / 4; ¿Cuál calculó correctamente A, B, C o D? Marque todo lo que corresponda. end end Solucion: B = X .^ 2; C = X + 1; D = X / 4;