Čtení: 45 + 90 minHodnotí se: testy 2 a 3 (15 a 20 b)

7 Nácvičné testy 2 a 3

Po přečtení umíš

vyzkoušet si testy v čase, na papíře a bez pomůcek
poznat, kde ztrácíš body

Testy se píší na papír bez jakýchkoli zdrojů. Nastav si čas a řešení otevři až potom.

7.1 Test 2 (45 min, 15 b)

Cvičení 7.2 (Úloha 1, 3 b)

Převeď Cejtinem $(x \vee y) \Rightarrow z$ .

Řešení

$a_2 \Leftrightarrow (x \vee y)$ : $(a_2 \vee \neg x)$ , $(a_2 \vee \neg y)$ , $(\neg a_2 \vee x \vee y)$ .

$a_1 \Leftrightarrow (a_2 \Rightarrow z)$ : $(\neg a_1 \vee \neg a_2 \vee z)$ , $(a_1 \vee a_2)$ , $(a_1 \vee \neg z)$ .

Kořen $(a_1)$ .

Cvičení 7.3 (Úloha 2, 5 b)

Formule: $(\neg a \vee b)$ , $(\neg b \vee c \vee d)$ , $(\neg b \vee e \vee d)$ , $(\neg c \vee \neg e)$ . Rozhodnutí $d = 0$ na úrovni 1 a $a = 1$ na úrovni 2. Najdi konflikt, první UIP, naučenou klauzuli a úroveň skoku.

Řešení

Propagace: $b = 1$ , $c = 1$ , $e = 1$ , konflikt v $(\neg c \vee \neg e)$ .

Rezoluce s $(\neg b \vee e \vee d)$ : $(\neg c \vee \neg b \vee d)$ . S $(\neg b \vee c \vee d)$ : $(\neg b \vee d)$ .

První UIP je $b$ , klauzule $(\neg b \vee d)$ , skok na úroveň 1.

Cvičení 7.4 (Úloha 3, 3 b)

Zapiš v logice prvního řádu: „Každý chirurg je lékař“ a „Joe nemá právníka“.

Řešení

$\forall x\, Occupation(x, Surgeon) \Rightarrow Occupation(x, Doctor)$ .

$\neg\exists l\, Customer(Joe, l) \wedge Occupation(l, Lawyer)$ .

Cvičení 7.5 (Úloha 4, 4 b)

Dokaž rezolucí $Q(A)$ z $\forall x\, P(x) \Rightarrow Q(x)$ a $P(A)$ .

Řešení

Klauzule: $\neg P(x) \vee Q(x)$ , $P(A)$ , a negace $\neg Q(A)$ . Rezoluce s $x / A$ dá $\neg P(A)$ a s $P(A)$ prázdnou klauzuli.

7.2 Test 3 (90 min, 20 b)

Cvičení 7.6 (Úloha 1, 4 b)

Hrany S→A 2, S→B 1, A→G 3, B→A 1, B→G 5 a $h(S) = 3$ , $h(A) = 2$ , $h(B) = 3$ , $h(G) = 0$ . Ukaž běh A* a ověř přípustnost.

Řešení

Skutečné ceny: $h^*(A) = 3$ , $h^*(B) = 4$ , $h^*(S) = 5$ , takže přípustná je.

Expanze: S (A 4, B 4), pak A s $g = 2$ (G 5), pak B s $g = 1$ (A $g = 2$ bez zlepšení, G 6), pak G za 5. Optimum 5.

Cvičení 7.7 (Úloha 2, 4 b)

$X, Y \in \{1, 2, 3, 4\}$ , podmínka $X + 1 = Y$ . Spočítej hranovou konzistenci.

Řešení

$X = \{1, 2, 3\}$ , $Y = \{2, 3, 4\}$ .

Cvičení 7.8 (Úloha 3, 5 b)

Vysvětli obě léčby kazů v plánování v prostoru plánů na vlastním příkladu.

Řešení

Otevřený cíl: akce Unload potřebuje In(C, P), přidáme Load a kauzální vazbu. Hrozba: jiná Unload by In(C, P) smazala, tak ji dáme před Load nebo za konzumenta.

Cvičení 7.9 (Úloha 4, 3 b)

Spočítej $P(o \mid z)$ pro apriorní 0,3, $P(z \mid o) = 0{,}9$ a $P(z \mid \neg o) = 0{,}2$ .

Řešení

$0{,}27 / (0{,}27 + 0{,}14) = 0{,}27 / 0{,}41 \approx 0{,}659$ .

Cvičení 7.10 (Úloha 5, 4 b)

Porovnej SAT, CSP a plánovací graf: kde se v nich objevuje učení ze selhání?

Řešení

SAT: naučené klauzule v CDCL. CSP: nogoody. Plánovací graf: tabulka neúspěšných cílů při extrakci.

Kapitolu mám prostudovanou