IB013 Logické programování I (průsvitky ze cvičení) Hana Rudová jaro 2009 Backtracking, unifikace, aritmetika Syntaxe logického programu Term: M univerzální datová struktura (slouží také pro príkazy jazyka) -• definovaný rekurzivně M konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaků (operátory) -• proměnné: pojmenované (alfanumerické řetězce začínající velkým písmenem), anonymní (začínají podtržítkem) M složený term: funktor, arita, argumenty struktury jsou opět termy Hana Rudová, Logické programování I, 20. května 2009 3 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu M Program: množina predikátů (v jednom nebo více souborech). -• Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity -• Klauzule: věty ukončené tečkou, se skládají z hlavy a těla. Prázdné tělo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvoří literal (složený term), tělo seznam literálů. Literálům v těle nebo v dotazu říkáme cíle. Dotazem v prostředí interpretu se spouští programy či procedury. Sémantika logického programu: procedury = databáze faktů a pravidel = logické formule Hana Rudová, Logické programování I, 20. května 2009 4 Backtracking, unifikace, aritmetika Sicstus Prolog minimum I M Spustení interpretu: V unixu přidáme modul module add sicstus a spustíme příkazem sicstus Pracovním adresářem je aktuální (tam kde byl spuštěn). V MS Windows standardně z nabídky Start/Programs nebo pomocí ikony, nastavíme pracovní adresář pomocí File/Working directory, v případě potřeby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. Hana Rudová, Logické programování I, 20. května 2009 5 Backtracking, unifikace, aritmetika Sicstus Prolog minimum II M Načtení programu: tzv. konzultace Editor není integrován, takže program editujeme externě ve svém oblíbeném editoru. Pak ho načteme z příkazové řádky v interpretu příkazem ?- consult(jmeno). nebo pomocí zkrácené syntaxe ?- [jméno]. % (předpokládá se přípona .pl) pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofu ?- ['D:\prolog\moje\programy\jmeno.pl']. V MS Windows lze také pomocí nabídky File/Consult Hana Rudová, Logické programování I, 20. května 2009 6 Backtracking, unifikace, aritmetika Sicstus Prolog minimum III -• Spouštění programů/procedur/predikátů je zápis dotazů, př. ?- muj_prech'kat(X,Y) . ?- suma(l,2,Y), vypis('Výsledek je ',Y). Každý příkaz ukončujeme tečkou. -• Přerušení a zastavení cyklícího programu: Ctrl-C -• Ukončení interpretu příkazem ?- halt. Hana Rudová, Logické programování I, 20. května 2009 7 Backtracking, unifikace, aritmetika Příklad rodič (pet r, filip). rodic(petr, lenka). rodic(pavel, j an). rodic(adam, petr). rodic(tomas, michal). rodič(michal, radek). rodic(eva, filip). rodic(jana, lenka). rodic(pavla, petr). rodic(pavla, tomas). rodic(lenka, vera). otec(Otec,Ditě) :- rodič(Otec,Ditě), Hana Rudová, Logické programování I, 20. května 2009 rodokmen muz(petr). muz(filip) . muz(pavel). muz(jan). muz(adam). muz(tomas). muz(michal). muz(radek). zena(eva). zena(lenka). zena(pavla). zena(jana). zena(vera). muz(Otec). 8 Backtracking, unifikace, aritmetika Backtracking: příklady V pracovním adresáři vytvořte program rodokmen.pl. Načtěte program v interpretu (konzultujte). V interpretu Sicstus Prologu pokládejte dotazy: -• Je Petr otcem Lenky? -• Je Petr otcem Jana? «• Kdo je otcem Petra? -• Jaké děti má Pavla? -• Ma Petr dceru? -• Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 20. května 2009 9 Backtracking, unifikace, aritmetika Backtracking: Středníkem si vyžádáme další řešení I ?- otecCpetr,lenka). yes I ?- otecCpetr,jan). no | ?- otecCKdo,petr). Kdo = adam ? ; no | ?- rodicCpavla,Dite). Ditě = petr ? ; Ditě = tomas ? ; no | ?- otecCpetr,Dcera),zenaCDcera). Dcera = lenka ? ; no Hana Rudová, Logické programování I, 20. května 2009 reseni přikladu | ?- otecC0tec,Syn),muzCSyn). Syn = filip, Otec = petr ? ; Syn = jan, Otec = pavel ? ; Syn = petr, Otec = adam ? ; Syn = michal, Otec = tomas ? ; Syn = radek, Otec = michal ? ; no I ?- 10 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty -• prababicka(Prababicka,Pravnouce) -• nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) Hana Rudová, Logické programování I, 20. května 2009 1 1 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Předek) :- rodic(Predek,Potomek). potomek(Potomek,Předek) :- rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty -• prababicka(Prababicka,Pravnouce) -• nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) Řešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodič), zena(Prababicka), rodič(Prarodič,Rodič), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 20. května 2009 1 1 Backtracking, unifikace, aritmetika Backtracking: nevlastni_bratr(Bratr,Sourozenec):-rodíc_v(X,Bratr), muz(Bratr), rodíc_v(X,Sourozenec), /* tento test není nutný, ale zvyšuje efektivitu */ Bratr \== Sourozenec, rodic_v(Y,Bratr), Y \== X, rodic_v(Z,Sourozenec), Z \== X, Z \== Y. Hana Rudová, Logické programování I, 20. května 2009 reseni přikladu II /* nevhodne umisteni testu - vypočet "bloudi" v neúspešných vetvi ch */ nevlastni_bratr2(Bratr,Sourozenec):- rodic_v(X,Bratr), rodic_v(X,Sourozenec), rodic_v(Y,Bratr), rodic_v(Z,Sourozenec), Y \== X, Z \== X, Z \== Y, muz(Bratr). 12 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru M Zkuste předem odhadnout (odvodit) pořadí, v jakém budou nalezeni potomci Pavly? -• Jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci? -• Nahraďte ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,Y):-rodic(X,Y),přint(X),přint('? '). Pozorujte rozdíly v délce výpočtu dotazu nevlastni_bratr(filip,X) při změně pořadí testů v definici predikátu nevlastni_bratr/2 Hana Rudová, Logické programování I, 20. května 2009 13 Backtracking, unifikace, aritmetika Backtracking: řešení III /* varianta la */ potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). /* varianta lb - jine poradí odpovedi, nepřímí potomci mají přednost */ potomek(Potomek,Předek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhé klauzuli, na dotaz potomek(X,pavla) výpise odpovedi, pak cykli */ potomek(Potomek,Předek):-rodic(Predek,Potomek). potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Předek):-potomek(Potomek,X),rodi c(Predek,X). potomek(Potomek,Předek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 20. května 2009 14 Backtracking, unifikace, aritmetika I ?- nevlastni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = fi lip, Y = lenka ? ; petr? pavel? pavel? adam? adam? tomas? tomas? michal? michal? eva? eva? jana? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? lenka? no I ?- nevlastni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr? jana X = fi lip, Y = lenka ? ; petr? petr? petr? petr? eva? jana? petr? eva? petr? petr? petr? jana? jana? petr? jana? pavel? pavel? pavel? pavel? adam? adam? adam? adam? pavla? pavla? adam? pavla? tomas? tomas? tomas? tomas? michal? michal? michal? michal? eva? eva? petr? petr? eva? eva? petr? eva? jana? jana? petr? petr? jana? jana? petr? jana? pavla? pavla? adam? adam? pavla? pavla? adam? pavla? pavla? adam? pavla? pavla? pavla? pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? lenka? lenka? lenka? lenka? no Hana Rudová, Logické programování I, 20. května 2009 15 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proč? Co je výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,plus) 6. s(l,a(X,q(w)))=s(Y,a(2,Z)) 7. s(l,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(l,a(P,q(R)))=s(Z,a(X,Y)) Hana Rudová, Logické programování I, 20. května 2009 16 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proč? Co je výsledkem provedených unifikací? 1. a(X)=b(X) 2. X=a(Y) 3. a(X)=a(X,X) 4. X=a(X) 5. jmeno(X,X)=jmeno(Petr,plus) 6. s(l,a(X,q(w)))=s(Y,a(2,Z)) 7. s(l,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(l,a(P,q(R)))=s(Z,a(X,Y)) Neuspěje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v případech 4),7) a 8) přestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen proměnných. Hana Rudová, Logické programování I, 20. května 2009 16 Backtracking, unifikace, aritmetika Mechanismus unifikace I Unifikace v průběhu dokazování predikátu odpovídá předávání parametrů při provádění procedury, aleje důležité uvědomit si rozdíly. Celý proces si ukážeme na příkladu predikátu suma/3. suma(0,X,X). /*klauzule A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /^klauzule B*/ pomocí substitučních rovnic při odvozování odpovědi na dotaz ?- suma(s(0),s(0),X0). Hana Rudová, Logické programování I, 20. května 2009 17 Backtracking, unifikace, aritmetika Mechanismus unifikace II suma(0,X,X). /*A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /*B*/ ?- suma(s(0),s(0),X0). 1. dotaz unifikujeme s hlavou klauzule B, s A nejde unifikovat (1. argument) suma(s(0),s(0),X0) = suma(s(Xl),Yl,s(Zl)) ==> xi = 0, Yl = s(0), s(Zl) = X0 ==> suma(0,s(0),Zl) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznačíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Zl = s(0) ==> X0 = s(sCO)) X0 = s(sCO)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 20. května 2009 18 Backtracking, unifikace, aritmetika Vícesměrnost predikátů Logický program lze využít vícesměrně, například jako M výpočet kdo je otcem Petra? ?- otec(X,petr) . kolik je 1+1??- suma(s(0),s(0),X). -• test je Jan otcem Petra? ?- otec(jan,petr) . Je 1+1 2??- suma(s(0),s(0),s( (0))). -• generátor které dvojice otec-dítě známe? ?-otec(X,Y) . Které X a Y dávají v součtu 2? ?- suma(X,Y,s(s(0))) . ... ale pozor na levou rekurzi, volné proměnné, asymetrii, a jiné záležitosti Následující dotazy ?-suma(X,s(0),Z). ?-suma(s(0),X,Z). nedávají stejné výsledky. Zkuste šije odvodit pomocí substitučních rovnic. Hana Rudová, Logické programování I, 20. května 2009 19 Backtracking, unifikace, aritmetika Aritmetika Zavádíme z praktických důvodů, ale aritmetické predikáty již nejsou vícesměrné, protože v každém aritmetickém výrazu musí být všechny proměnné instaciovany číselnou konstantou. Důležitý rozdíl ve vestavěných predikátech is/2 vs. =/2 vs. =:=/2 is/2: < konstanta nebo proměnná > is < aritmetický výraz > výraz na pravé straně je nejdříve aritmeticky vyhodnocen a pak unifkován s levou stranou =/2: < libovolný term > = < libovolný term > levá a pravá strana jsou unifikovány "=:="/2 ,,=\="/2 M>=72 M=<72 < aritmetický výraz > =:= < aritmetický výraz > < aritmetický výraz > =\= < aritmetický výraz > < aritmetický výraz > =< < aritmetický výraz > < aritmetický výraz > >= < aritmetický výraz > levá i pravá strana jsou nejdříve aritmeticky vyhodnoceny a pak porovnány Hana Rudová, Logické programování I, 20. května 2009 20 Backtracking, unifikace, aritmetika Aritmetika: příklady Jak se liší následující dotazy (na co se kdy ptáme)? Které uspějí (kladná odpověď), které neuspějí (záporná odpověď), a které jsou špatně (dojde k chybě)? Za jakých předpokladů byty neúspěšné případně špatné uspěly? l.X = Y+ 1 7. 1 + 1 = 1 + 1 13. 1 <= 2 2.X is Y+ 1 8. 1 + 1 is 1 + 1 3.X = Y 9. 1 + 2 =:= 2 + 1 4.X==Y 10. X\==Y 5. 1 + 1 = 2 H.X=\= Y 6.2 = 1+1 12.1+2 =\= 1-2 17. sin(X) =:= sin(2+Y) 14. 1 =< 2 1 5. sin(X) is sin(2) 16. sin(X) = sin(2+Y) Nápověda: '='/2 unifikace, '=='/2 test na identitu, '=:='/2 aritmetická rovnost, '\=='/2 negace testu na identitu, '=\='/2 aritmetická nerovnost Hana Rudová, Logické programování I, 20. května 2009 21 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? sl(0,X,X). sl(s(X),Y,s(Z)):-sl(X,Y,Z). s2(X,Y,Z):- Z is X + Y. Hana Rudová, Logické programování I, 20. května 2009 22 Backtracking, unifikace, aritmetika Aritmetika: příklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? sl(0,X,X). sl(s(X),Y,s(Z)):-sl(X,Y,Z). s2(X,Y,Z):- Z is X + Y. sl/3 je vícesměrný- umí sčítat, odečítat, generovat součty, ale pracuje jen s nezápornými celými čísly s2/3 umí pouze sčítat, ale také záporná a reálná čísla Hana Rudová, Logické programování I, 20. května 2009 22 Backtracking, unifikace, aritmetika Operátory Definice operátorů umožňuje přehlednější infixový zápis binárních a unárních predikátů, příklad: definice op(l 200,Y,':-') umožňuje zápis a:-print(s(s(0))),b,c). pro výraz :-(aM(print(s(s(0)))M(b,c))). Prefixovou notaci lze získat predikátem display/l. Vyzkoušejte ch'splay((a:-print(s(s(0))) ,b,c)) . di spiay(a+b+c-d-e*f*g-h+i). display([l,2,3,4,5]). Definice standardních operátorů najdete na konci manuálu. Hana Rudová, Logické programování I, 20. května 2009 23 Backtracking, unifikace, aritmetika Závěr Dnešní látku jste pochopili dobře, pokud víte -• jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci, -• jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (příklad nevlastni_bratr/2), -• k čemu dojde po unifikaci X=a(X), M proč neuspěje dotaz ?- X=2, sin(X) is sin(2). -• za jakých předpokladů uspějí tyto cíle X=Y, X==Y, X=:=Y, -• a umíte odvodit pomocí substitučních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 20. května 2009 24 Backtracking, unifikace, aritmetika Seznamy, řez Seznamy a append appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). Napište následující predikáty pomocí append/3: -• lastC X, S ) :- append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 20. května 2009 26 Seznamy, řez Seznamy a append appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). Napište následující predikáty pomocí append/3: -• lastC X, S ) :- appendC _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 20. května 2009 26 Seznamy, řez Seznamy a append appendC [], S, S ). appendC [X|S1], S2, [X|S3] ) :- appendC SI, S2, S3). Napište následující predikáty pomocí append/3: -• lastC X, S ) :- appendC _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] 1, Al is N * A, Nl is N - 1, factC Nl, Al, F ). Hana Rudová, Logické programování I, 20. května 2009 31 ■write(rl) . -p(X),write(r2). -write(r3) . ■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2). -write(p3) . ■write(al) . -write(a2) . ■ X > 0, write(bl). ■ X < 0, write(b2). ■ X mod 2 =:= 0, write(cl) ■ X mod 3 =:= 0, write(c2) ■ abs(X) < 10, write(dl). ■ write(d2) . Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si středníkem vyžádejte navracení): (1) X=l,r(X). (2) X=3,r(X). (3) X=0,r(X). (4) X= -6,r(X). r (X r (X r (X P (X P (X P (X a (X a (X b (X b (X c (X c (X d (X d (X -write(rl) . -p(X),write(r2) -write(r3) . Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů (vždy si středníkem vyžádejte navracení): (1) X=l,r(X). (2) X=3,r(X). (3) X=0,r(X). (4) X= -6,r(X) -write(pi) . -a(X),b(X),!, c(X) ,d(X) ,write(p2). M vez v predikátu p/l neovlivní alternativy -write(p3). predikátu r/l -wnte(a;. ^ dokud nebyl proveden řez, alternativy -write(a2). .. „ , „ predikátu a/l se uplatňuji, pr. neúspech - X > 0, write(bl). b/1 v dotazu (3) - X < 0, write(b2). -• při neúspěchu cíle za řezem se výpočet - X mod 2 =:= 0, write(cl). , - . . .. , , ~ /n . /ns navrací az k volající procedure r/1, viz (1) - X mod 3 =:= 0, write(c2). 3 alternativy vzniklé po provedení řezu se - abs(X) < 10, write(dl). , , N zachovávají - další možnosti predikátu - wnte(d2) . c/1 viz (2) a (4) Hana Rudová, Logické programování I, 20. května 2009 32 Seznamy, řez -write(rl). -p(X),write(r2). -write(r3). -write(pi) . -a(X),b(X),!, c(X),d(X),write(p2). -write(p3). -write(al). -write(a2). - X > 0, write(bl). - X < 0, write(b2). - X mod 2 =:= 0, write(cl). - X mod 3 =:= 0, write(c2). - abs(X) < 10, write(dl). - write(d2) . r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). - X=l,r(X). r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). rl X X=l,r(X). 1 7 ■ r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; I ?- X=l,r(X) r(X):-write(rl) . rl r(X):-p(X),write(r2). X = 1 ? ; r(X):-write(r3). plr2 p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > 0, write(bl). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). X = 1 ? ; alblr3 X = 1 ? ; -writeCrl) . -pCX),writeCr2). -writeCr3). -writeCpi) ■ -aCX),bCX),!, cCX),dCX),writeCp2). -writeCp3). -writeCal). -writeCa2). - X > O, writeCbl). - X < O, writeCb2). - X mod 2 =:= O, write Cel) - X mod 3 =:= 0, writeCc2) - absCX) < 10, write(dl). - writeCd2) . rCX). | ?- X=l,rCX) rCX) -writeCrl) . rl rCX) -pCX),writeCr2). X = 1 ? ; rCX) -writeCr3). plr2 PCX) -writeCpi) ■ X = 1 ? ; PCX) -aCX),bCX),!, alblr3 cCX),dCX),write Cp2) i X = 1 ? ; PCX) -writeCp3). no aCX) -writeCal). | ?- X=0,rCX) aCX) -writeCa2). bCX) - X > 0, writeCbl) . bCX) - X < 0, writeCb2) . cCX) - X mod 2 =:= 0, wri te(c 1). cCX) - X mod 3 =:= 0, wri te(c 2). dCX) - absCX) < 10, write(dl) ■ dCX) - write(d2) . I ?- X=l,r(X) -write(rl). rl -p(X),write(r2). X = 1 ? ; -write(r3). plr2 ■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) . X = 1 ? ; alblr3 X = 1 ? ; no -write(al). , ?_ x=0jr(x) ■write(a2). rl ■ X > 0, writeCbl). X = 0 ? ; ■ X < 0, write(b2). ■ X mod 2 =:= 0, write(cl). ■ X mod 3 =:= 0, write(c2). ■ abs(X) < 10, write(dl). ■ write(d2) . I ?- X=l,r(X) write(rl) . rl p(X),write(r2). X = 1 ? ; write(r3) . plr2 write (pi) . X = 1 ? ; a(X),b(X),!, alblr3 c(X),d(X),write(p2). X = 1 ? ; write(p3) . no write(al) . I ?- X=0,r(X) write(a2). rl X > 0, writeCbl). X = 0 ? ; X < 0, write(b2). plr2 X = 0 ? ; X mod 2 =:= 0, write(cl). X mod 3 =:= 0, write(c2). abs(X) < 10, write(dl). write(d2) . I ?- X=l,r(X) -write(rl). rl -p(X),write(r2). X = 1 ? ; -write(r3). plr2 ■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) . X = 1 ? ; alblr3 X = 1 ? ; no -write(al). , ?_ x=0jr(x) -write(a2). rl ■ X > 0, writeCbl). X = 0 ? ; ■ X < 0, write(b2). Plr2 X mod 2 =:= 0, write(cl) X mod 3 =:= 0, write(c2) abs(X) < 10, write(dl). write(d2) . X = 0 ? ala2p3r2 X = 0 ? I ?- X=l,r(X) write(rl) . rl p(X),write(r2). X = 1 ? ; write(r3) . plr2 write (pi) . X = 1 ? ; a(X),b(X),!, alblr3 c(X),d(X),write (p2) i X = 1 ? ; write(p3) . no write(al) . I ?- X=0,r(X) write(a2). rl X > 0, writeCbl). X = 0 ? ; X < 0, write(b2). plr2 X = 0 ? ; X mod 2 =:= 0, X mod 3 =:= 0, wri wri te(c te(c 1). 2). ala2p3r2 X = 0 ? ; abs(X) < 10, write(dl) ■ r3 write(d2) . X = 0 ? ; I ?- X=l,r(X) -write(rl). rl -p(X),write(r2). X = 1 ? ; -write(r3). plr2 ■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) ■write(p3) . X = 1 ? ; alblr3 X = 1 ? ; no -write(al). , ?_ x=0jr(x) ■write(a2). rl ■ X > 0, writeCbl). X = 0 ? ■ X < 0, write(b2). Plr2 X = 0 ? ala2p3r2 X = 0 ? abs(X) < 10, write(dl). r3 write(d2). X = 0 ? no X mod 2 =:= 0, write(cl) X mod 3 =:= 0, write(c2) r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no ?- X=3,r(X) ?- X=0,r(X) rl X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ? no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=3,r(X) rl X = 3 ? ; ?- X=0,r(X) rl X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ? no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=3,r(X) rl X = 3 ? ; plr2 X = 3 ? ; ?- X=0,r(X) rl X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ? no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d (X):- write(d2). | ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no | ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X). rl | ?- X= -6, r(X). X = 1 ? ; plr2 | ?- X=3,r(X). X = 1 ? ; rl alblr3 X = 3 ? ; X = 1 ? ; plr2 no X = 3 ? ; alblc2dlp2r2 | ?- X=0,r(X). X = 3 ? ; rl d2p2r2 X = 0 ? ; X = 3 ? ; plr2 r3 X = 0 ? ; X = 3 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X). rl | ?- X= -6, r(X). X = 1 ? ; rl plr2 | ?- X=3,r(X). X = -6 ? ; X = 1 ? ; rl alblr3 X = 3 ? ; X = 1 ? ; plr2 no X = 3 ? ; alblc2dlp2r2 | ?- X=0,r(X). X = 3 ? ; rl d2p2r2 X = 0 ? ; X = 3 ? ; plr2 r3 X = 0 ? ; X = 3 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). | ?- X=l,r(X) rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no ?- X=0,r(X) rl X = 0 ? plr2 X = 0 ? ala2p3r2 X = 0 ? r3 X = 0 ? | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no | ?- X= -6, r(X) rl X = -6 ? ; plr2 X = -6 ? ; no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). 1 ?- x=i, r (X). rl | ?- X= -6, r(X) X = 1 ? ; rl plr2 | ?- X=3,r(X). X = -6 ? ; X = 1 ? ; rl plr2 alblr3 X = 3 ? ; X = -6 ? ; X = 1 ? ; plr2 alb2cldlp2r2 no X = 3 ? ; X = -6 ? ; alblc2dlp2r2 1 ?- x=o, r (X). X = 3 ? ; rl d2p2r2 X = 0 ? ; X = 3 ? ; plr2 r3 X = 0 ? ; X = 3 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). 1 ?- x=i, r (X). rl | ?- X= -6, r(X) X = 1 ? ; rl plr2 | ?- X=3,r(X). X = -6 ? ; X = 1 ? ; rl plr2 alblr3 X = 3 ? ; X = -6 ? ; X = 1 ? ; plr2 alb2cldlp2r2 no X = 3 ? ; X = -6 ? ; alblc2dlp2r2 d2p2r2 1 ?- x=o, r (X). X = 3 ? ; X = -6 ? ; rl d2p2r2 X = 0 ? ; X = 3 ? ; plr2 r3 X = 0 ? ; X = 3 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). 1 ?- x=i, r (X). rl | ?- X= -6, r(X) X = 1 ? ; rl plr2 1 ?- X=3,r (X). X = -6 ? ; X = 1 ? ; rl plr2 alblr3 X = 3 ? ; X = -6 ? ; X = 1 ? ; plr2 alb2cldlp2r2 no X = 3 ? ; X = -6 ? ; alblc2dlp2 r2 d2p2r2 1 ?- x=o, r (X). X = 3 ? ; X = -6 ? ; rl d2p2r2 c2dlp2r2 X = 0 ? ; X = 3 ? ; X = -6 ? ; plr2 r3 X = 0 ? ; X = 3 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pi). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > O, write(bl). b(X):- X < O, write(b2). c(X):- X mod 2 =:= 0, write(cl) c(X):- X mod 3 =:= 0, write(c2) d(X):- abs(X) < 10, write(dl). d(X):- write(d2). 1 ?- x=i, r (X). rl | ?- X= -6, r(X) X = 1 ? ; rl plr2 1 ?- X=3,r (X). X = -6 ? ; X = 1 ? ; rl plr2 alblr3 X = 3 ? ; X = -6 ? ; X = 1 ? ; plr2 alb2cldlp2r2 no X = 3 ? ; X = -6 ? ; alblc2dlp2 r2 d2p2r2 1 ?- x=o, r (X). X = 3 ? ; X = -6 ? ; rl d2p2r2 c2dlp2r2 X = 0 ? ; X = 3 ? ; X = -6 ? ; plr2 r3 d2p2r2 X = 0 ? ; X = 3 ? ; X = -6 ? ; ala2p3r2 no X = 0 ? ; r3 X = 0 ? ; no ■write(rl) . -p(X),write(r2). ■write(r3) . ■write(pi) . -a(X),b(X),!, c(X),d(X),write(p2). ■write(p3) . ■write(al) . ■write(a2) . ■ X > 0, writeCbl). ■ X < 0, write(b2). ■ X mod 2 =:= 0, write(cl) ■ X mod 3 =:= 0, write(c2) ■ abs(X) < 10, write(dl). ■ write(d2) . 1 ?- x=i, r(X). rl I ?- X= -6, r X = 1 ? ; rl plr2 1 ?- X=3,r (X). X = -6 ? ; X = 1 ? ; rl plr2 alblr3 X = 3 ? ; X = -6 ? ; X = 1 ? ; plr2 alb2cldlp2r2 no X = 3 ? ; X = -6 ? ; alblc2dlp2 r2 d2p2r2 1 ?- x=o, r(X). X = 3 ? ; X = -6 ? ; rl d2p2r2 c2dlp2r2 X = 0 ? ; X = 3 ? ; X = -6 ? ; plr2 r3 d2p2r2 X = 0 ? ; X = 3 ? ; X = -6 ? ; ala2p3r2 no r3 X = 0 ? ; X = -6 ? ; r3 X = 0 ? ; no r (X r (X r (X P (X P (X P (X b (X b (X c (X c (X d (X d (X I ?- X=l, -write(rl). rl -p(X),write(r2). X = 1 ? ; -write(r3). plr2 -write(pi) . -a(X),b(X),!, c(X),d(X),write(p2) -write(p3). X = 1 ? ; alblr3 X = 1 ? ; no a(X):-write(al). ■ 7_ X=Q a(X):-write(a2). - - X > 0, write(bl). X = 0 ? - X < 0, write(b2). Plr2 X = 0 ? ala2p3r2 X = 0 ? :- abs(X) < 10, write(dl). r3 :- write(d2). X = 0 ? no Hana Rudová, Logické programování I, 20. května 2009 33 :- X mod 2 =:= 0, write(cl) :- X mod 3 =:= 0, write(c2) | ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no | ?- X= -6, r(X). rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no Seznamy, řez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Hana Rudová, Logické programování I, 20. května 2009 34 Seznamy, řez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Není, následující dotaz uspěje: ?- max(2 ,1,1). Uveďte dvě možnosti opravy, se zachováním použití řezu a bez. Hana Rudová, Logické programování I, 20. května 2009 34 Seznamy, řez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,!. max(X,Y,Y). Není, následující dotaz uspěje: ?- max(2 ,1,1). Uveďte dvě možnosti opravy, se zachováním použití řezu a bez. max(X,Y,X):-X>=Y. max(X,Y,Z):-X>=Y,!,Z=X. max(X,Y,Y):-Y>X. max(X,Y,Y). Problém byl v definici, v první verzi se tvrdilo: X=Z a X>=Y => Z=X správná definice je: X>=Y => Z=X Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu. Hana Rudová, Logické programování I, 20. května 2009 34 Seznamy, řez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). -• meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). -• meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) -• mem2/2 najde jenom první výskyt, taky váže proměnné Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). -• meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) M mem2/2 najde jenom první výskyt, taky váže proměnné -• mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty? Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Řez: member Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? Vyzkoušejte např. pomocí member( X, [1,2,3] ). meml(H,[H|_]). meml(H,[_|T]) :- meml(H,T). mem2(H,[H|_]) :- !. mem3(H,[K|_]) :- H==K. mem2(H,[_|T]) :- mem2(H,T). mem3(H,[K|T]) :- H\==K, mem3(H,T). -• meml/2 vyhledá všechny výskyty, při porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu) M mem2/2 najde jenom první výskyt, taky váže proměnné -• mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty? mem4(H,[K|_]):- H==K. mem4(H,[K|T]):- mem4(H,T). Hana Rudová, Logické programování I, 20. května 2009 35 Seznamy, řez Seznamy: intersection(A,B,C) DÚ: Napište predikát pro výpočet průniku dvou seznamů. Nápověda: využijte predikát member/2 DÚ: Napište predikát pro výpočtu rozdílu dvou seznamů. Nápověda: využijte predikát member/2 Hana Rudová, Logické programování I, 20. května 2009 36 Seznamy, řez Všechna řešení, třídění, rozdílové seznamy Všechna řešení % z(Jmeno,Prijmeni,Pohlavi,Vek,Prace,Fi rma) z(petr,novak,m,30,skladnik,škoda). z(pavel,novy,m,40,mechani k,škoda). z(rostislav,lucensky,m,50,technik,škoda). z(alena,vesel a,z,25,sekretárka,škoda). z(jana,dankova,z,35,asistentka,škoda). z(lenka,merinska,z,35,ucetni,škoda). z(román,malý,m,35,manažer,es). z(alena,novotna,z,40,ucitelka,zs_stara). z(david,novy,m,30,učitel,zs_stara). z(petra,špičková,z,45,uklizečka,zs_stara). M Najděte jméno a příjmení všech lidí. ?- findall(Jmeno-Prijmeni, z(Jmeno,Prijmeni,_,_,_,_),L). ?- bagof( Jmeno-Prijmeni, [S,V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L). ?- bagof( Jmeno-Prijmeni, [V,Pr,F] a z(Jmeno,Prijmeni,S,V,Pr,F) , L ). -• Najděte jméno a příjmení všech zaměstnanců firmy škoda a es ?- findall( c(J , P, Fi rma) , ( z(J , P, _,_,_, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), L ?- bagof( J-P, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 20. května 2009 38 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? Hana Rudová, Logické programování I, 20. května 2009 39 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findall(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findall(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-II, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). Hana Rudová, Logické programování I, 20. května 2009 39 Všechna řešení, třídění, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou příjmení všech žen? 2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení. 3. Nalezněte abecedně seřazený seznam všech lidí. 4. Nalezněte příjmení vyučujících ze zs_stara. 5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zaměstnance? 1. findall(Přijmeni, z(_,Přijmeni,z,_,_,_), L). 2. findall(Jmeno-Prijmeni, ( z(Jmeno,Přijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-II, [S,V,Pr,F]AzO,P,S,V,Pr,F), L ). 4. findall(Přijmeni, ( z(_,Přijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(Jl-P,J2-P), ( z(Jl,P,m,_,_,_),z(J2,P,m,_,_,_), J1@l ), S). Hana Rudová, Logické programování I, 20. května 2009 39 Všechna řešení, třídění, rozdílové seznamy bubblesort(S,Sorted) Seznam S seřaďte tak, že «Ä nalezněte první dva sousední prvky X a Y v S tak, že X>Y, vyměňte pořadí X a Y a získate SI; swap(S a seřaďte SI rekurzivně bubblesor & pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S seřazený seznam bubblesort(S,Sorted) :- swap (S,SI), !, % Existuje použitelný swap v S? bubblesort(Sl, Sorted). bubblesort(Sorted,Sorted). % Jinak je seznam seřazený swap([X,Y|Rest],[Y,X|Restl]) :- X>Y. swap([Z|Rest],[Z|Restl]) :- swap(Rest,Restl). Hana Rudová, Logické programování I, 20. května 2009 % swap prvních dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku 40 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append Hana Rudová, Logické programování I, 20. května 2009 41 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append quicksort([] , []) . quicksort([X|T], Sorted) :- spi i t(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). Hana Rudová, Logické programování I, 20. května 2009 41 Všechna řešení, třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S seřaďte tak, že konec rekurze pro S=[] M vyberte nějaký prvek X z S; např. vyberte hlavu S rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky split(X,Seznam,Small,Big) M seřaďte Small do SortedSmall rekurzivně quicksortem M seřaďte Big do SortedBig rekurzivně quicksortem M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] append quicksort([] , []) . quicksort([X|T], Sorted) :- spi i t(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). spi i t (X, [], [], []). split(X, [Y|T], [Y|Small], Big) :-X>Y, !, spi i t(X, T, Small, Big). spi i t(X, [Y|T], Small, [Y|Big]) :- spi i t(X, T, Small, Big). Hana Rudová, Logické programování I, 20. května 2009 41 Všechna řešení, třídění, rozdílové seznamy DU:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že konec rekurze pro S=[] seřaďte tělo T seznamu S rekurzivně insertsortem vložte hlavu X do seřazeného těla tak, že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insert(X,SortedT,Sorted) Hana Rudová, Logické programování I, 20. května 2009 42 Všechna řešení, třídění, rozdílové seznamy DU:insertsort(S,Sorted) Neprázdný seznam S=[X|T] seřaďte tak, že konec rekurze pro S=[] M seřaďte tělo T seznamu S rekurzivně insertsortem M vložte hlavu X do seřazeného těla tak, insert(X,SortedT,Sorted) že výsledný seznam je zase seřazený. Víme: výsledek po vložení X je celý seřazený seznam. insertsort([] , []) . insertsort([X|T],Sorted) :- insertsort(T,SortedT), % seřazeni těla insert(X,SortedT,Sorted). % vloženi X na vhodné místo insertCX,[Y|Sorted],[Y|Sortedl]) :- X > Y, !, insert(X,Sorted,Sortedl). insert(X,Sorted,[X|Sorted]). Hana Rudová, Logické programování I, 20. května 2009 42 Všechna řešení, třídění, rozdílové seznamy Rozdílové seznamy Zapamatování konce a připojení na konec: rozdílové seznamy [a,b] = L1-L2 = [a,b|T]-T = [a,b,c|S]-[c|S] = [a,b,c]-[c] Reprezentace prázdného seznamu: L-L ?- appendC [1,2,3|Z1]-Z1, [4,5|Z2]-Z2, S ). appendC Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 appendC [1,2,3,4,5]-[4,5], [4,5]-[], [1,2,3,4,5]-[] ). Hana Rudová, Logické programování I, 20. května 2009 43 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). Hana Rudová, Logické programování I, 20. května 2009 44 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverseOC Seznam, ). reverseOC [] , ) ■ reverseOC [ H | T ] , ) :- reverseOC T, ) . Hana Rudová, Logické programování I, 20. května 2009 44 Všechna řešení, třídění, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverseC [], [] ) . reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[] ). reverseOC [], S-S ). reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 20. května 2009 44 Všechna řešení, třídění, rozdílové seznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,15,12] Hana Rudová, Logické programování I, 20. května 2009 45 Všechna řešení, třídění, rozdílové seznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspěje pokud se Seznam čte stejně zezadu i zepředu, př. [a,b,c,b,a] nebo [1 2,1 5,1,1,15,12] pal indrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 20. května 2009 45 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že -M vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky M seřaďte Small do SortedSmall -• seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S, ). quicksortl([] , ) . quicksortl([X|T], ) :- spi i t(X, T, Small, Big), quicksortl(Small, ), quicksortl(Big, ). append(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 20. května 2009 46 Všechna řešení, třídění, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S seřaďte tak, že -M vyberte nějaký prvek X z S; rozdělte zbytek S na dva seznamy Small a Big tak, že: v Big jsou větší prvky než X a v Small jsou zbývající prvky M seřaďte Small do SortedSmall -• seřaďte Big do SortedBig M setříděný seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|T], A1-Z2) :- spi i t(X, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortlCBig, A2-Z2). append(Al-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 20. května 2009 46 Všechna řešení, třídění, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Ctení process_file( Soubor ) :- seeingC StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ) Term == end_of_file, i seen, see( StarySoubor ). repeat. repeat :- repeat. Hana Rudová, Logické programování I, 20. května 2009 souboru % zjištěni aktivního proudu % otevřeni souboru Soubor % čteni termu Term % manipulace s termem % je konec souboru? % uzavřeni souboru % aktivace původniho proudu % vestavěný predikát 48 Vstup/výstup, databázové operace, rozklad termu Predikáty pro vstup a výstup I ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petre!' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petre!'), D = jdeme | ?- write(a(l)), write('.'), nl, write(a(2)), write('.'), nl. a(l). a(2). yes -• seeing, see, seen, read M telling, tell, told, write -• standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 20. května 2009 49 Vstup/výstup, databázové operace, rozklad termu Příklad: vstup/výstup Napište predikát uloz_do_souboru( Soubor ), který načte několik fakt ze vstupu a uloží je do souboru Soubor. | ?- uloz_do_souboru( 'soubor.pl' ). fakt(mi rek, 18). faktCpavel,4). yes | ?- [soubor]. % consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, O msec % 376 bytes yes I ?- listing(fakt/2). fakt(mi rek, 18). faktCpavel, 4). yes Hana Rudová, Logické programování I, 20. května 2009 50 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeingC StaryVstup ), tellingC StaryVystup ), see( user ), tell( Soubor ), repeat, read( Term ), process_term( Term ), Te rm == end_of_fi 1 e, i ■ > seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- write( Term ), write('.'), ni. Hana Rudová, Logické programování I, 20. května 2009 51 Vstup/výstup, databázové operace, rozklad termu Databázové operace M Databáze: specifikace množiny relací -• Prologovský program: programová databáze, kde jsou relace specifikovány explicitně (fakty) i implicitně (pravidly) -• Vestavěné predikáty pro změnu databáze během provádění programu: assert( Klauzule ) přidání Klauzule do programu asserta( Klauzule ) přidání na začátek assertz( Klauzule ) přidání na konec retract( Klauzule ) smazání klauzule unifikovatelné s Klauzule -• Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 20. května 2009 52 Vstup/výstup, databázové operace, rozklad termu Databázové Napište predikát vytvor_program/0, uloží je do programové databáze. ?- vytvor_program. faktCpavel, 4). pravidlo(X,Y) :- fakt(X,Y). yes | ?- listing(fakt/2). faktCpavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B). yes | ?- clauseC pravidlo(A,B), C). C = fakt(A,B) ? yes Hana Rudová, Logické programování I, 20. května 2009 operace: příklad který načte několik klauzulí ze vstupu a 5 3 Vstup/výstup, databázové operace, rozklad termu Databázové operace vytvor_p rog ram :- seeingC StaryVstup ), see( user ), repeat, read( Term ), uloz_term( Term ), Te rm == encLof_fi 1 e, i ■ > seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assertC Term ). Hana Rudová, Logické programování I, 20. května 2009 54 implementace Vstup/výstup, databázové operace, rozklad termu Konstrukce a dekompozice termu M Konstrukce a dekompozice termu Term =.. [ Funktor | SeznamArgumentu ] a(9,e) =.. [a,9,e] Cil =.. [ Funktor | SeznamArgumentu ], call( Cil ) atom =. . X => X = [atom] -• Pokud chci znát pouze funktor nebo některé argumenty, pak je efektivnější: functor( Term, Funktor, Arita ) functorC a(9,e), a, 2 ) functor(atom,atom,0) functor(l,1,0) arg( N, Term, Argument ) arg( 2, a(9,e), e) Hana Rudová, Logické programování I, 20. května 2009 55 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu -• Term je proměnná (var/1), atom nebo číslo (atomi c/1) => konec rozkladu -• Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu -• Term je složený (=. ./2 , functor/3) ^> procházení seznamu argumentů a rozklad každého argumentu -• Příklad: ground/1 uspěje, pokud v termu nejsou proměnné; jinak neuspěje g round(Term) :- atomic(Term), !. % Term je atom nebo číslo NEBO ground(Term) :- var(Term), !, fail. % Term neni proměnná NEBO ground([H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani tělo % neobsahuji proměnné NEBO ground(Term) :- Term =.. [ _Funktor | Argumenty ], % je Term složený groundC Argumenty ). % a jeho argumenty % neobsahuji proměnné ?- ground(s(2,[a(l,3),b,c],X)). ?- ground(s(2,[a(l,3),b,c])). no yes Hana Rudová, Logické programování I, 20. května 2009 56 Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S aT bez proměnných, které uspějí, pokud je S podtermem termu T. Tj. musí platit alespoň jedno z -• podterm S je právě term T NEBO -• podterm S se nachází v hlavě seznamu T NEBO -• podterm S se nachází v těle seznamu T NEBO -• T je složený term (compound/1), není seznam (T\=[_|_]), a S je podtermem některého argumentu T. | ?- subterm(sin(3),b(c,2,[l,b],sin(3),a)). yes Hana Rudová, Logické programování I, 20. května 2009 57 Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S aT bez proměnných, které uspějí, pokud je S podtermem termu T. Tj. musí platit alespoň jedno z -• podterm S je právě term T NEBO -• podterm S se nachází v hlavě seznamu T NEBO -• podterm S se nachází v těle seznamu T NEBO -• T je složený term (compound/1), není seznam (T\=[_|_]), a S je podtermem některého argumentu T. | ?- subterm(sin(3),b(c,2,[l,b],sin(3),a)). yes subterm(T,T) :- !. subterm(S,[H|_]) :- subterm(S,H), !. subterm(S,[_|T]) :- subterm(S,T),!. Hana Rudová, Logické programování I, 20. května 2009 57 Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S aT bez proměnných, které uspějí, pokud je S podtermem termu T. Tj. musí platit alespoň jedno z -• podterm S je právě term T NEBO -• podterm S se nachází v hlavě seznamu T NEBO -• podterm S se nachází v těle seznamu T NEBO -• T je složený term (compound/1), není seznam (T\=[_|_]), a S je podtermem některého argumentu T. | ?- subterm(sin(3),b(c,2,[l,b],sin(3),a)). yes subterm(T,T) :- !. subterm(S,[H|_]) :- subterm(S,H), !. subterm(S,[_|T]) :- subterm(S,T),!. subterm(S,T) :- compound(T), T\=[_|_], T=..[_|Argumenty], subterm(S,Argumenty). Hana Rudová, Logické programování I, 20. května 2009 57 Vstup/výstup, databázové operace, rozklad termu same(A,B) Napište predikát same(A, B), který uspěje, pokud mají termy A a B stejnou strukturu. Tj. musí platit právě jedno z -• A i B jsou proměnné NEBO -• pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO -# A i B jsou atomi c a unifikovatelné NEBO M A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO M A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([l,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes Hana Rudová, Logické programování I, 20. května 2009 58 Vstup/výstup, databázové operace, rozklad termu same(A,B) Napište predikát same(A, B), který uspěje, pokud mají termy A a B stejnou strukturu. Tj. musí platit právě jedno z -• A i B jsou proměnné NEBO -• pokud je jeden z argumentů proměnná (druhý ne), pak predikát neuspěje, NEBO -# A i B jsou atomi c a unifikovatelné NEBO M A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO M A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([l,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes same(A,B) :- var(A), var(B), !. same(A,B) :- var(A), !, fail. same(A,B) :- var(B), !, fail. same(A,B) :- atomic(A), atomic(B), !, A==B. same C[HA|TA],[HB|TB]) :- !, same(HA,HB), same(TA,TB). same(A,B) :- A=..[FA|ArgA], B=..[FB|ArgB], FA==FB, same(ArgA,ArgB). Hana Rudová, Logické programování I, 20. května 2009 58 Vstup/výstup, databázové operace, rozklad termu unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B. | ?- unify([Y,3,sin(a(3)),s(a,3)],[l,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes Hana Rudová, Logické programování I, 20. května 2009 59 Vstup/výstup, databázové operace, rozklad termu unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B. | ?- unify([Y,3,sin(a(3)),s(a,3)],[l,3,sin(X),s(a,3)]) X = a(3) Y = 1 yes - var(A), var(B), !, A=B. - var(A), !, not_occurs(A,B), A=B. - var(B), !, not_occurs(B,A), B=A. - atomic(A), atomic(B), !, A==B. unify([HA|TA],[HBITB]) :- !, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[FA|ArgA], B=..[FB|ArgB], FA==FB, unify(ArgA,ArgB) unify(A,B) unify(A,B) unify(A,B) unify(A,B) Hana Rudová, Logické programování I, 20. května 2009 59 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A, B) uspěje, pokud se proměnná A nevyskytuje v termu B. Tj. platí jedno z -• B je atom nebo číslo NEBO -• B je proměnná různá od A NEBO M B je seznam a A se nevyskytuje ani v těle ani v hlavě NEBO -• B je složený term a A se nevyskytuje v jeho argumentech Hana Rudová, Logické programování I, 20. května 2009 60 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A, B) uspěje, pokud se proměnná A nevyskytuje v termu B. Tj. platí jedno z -• B je atom nebo číslo NEBO -• B je proměnná různá od A NEBO M B je seznam a A se nevyskytuje ani v těle ani v hlavě NEBO -• B je složený term a A se nevyskytuje v jeho argumentech not_occurs(_,B) :- atomic(B), !. not_occurs(A,B) :- var(B), !, A\==B. not_occurs(A,[H|T]) :- !, not_occurs(A,H), not_occurs(A,T). not_occurs(A,B) :- B=..[_|Arg], not_occurs(A,Arg). Hana Rudová, Logické programování I, 20. května 2009 60 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Algebrogram -• Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: 3 SEND + MORE MONEY M různá písmena mají přiřazena různé cifry i SaM nejsou 0 -• Proměnné: S,E,N,D,M,O,R,Y -• Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y M 1 omezení pro nerovnost: all_distinct([S, E,N,D,M,0,R,Y]) -• 1 omezení pro rovnosti: 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE #= 10000*M + 1000*0 + 100*N + 10*E + Y MONEY Hana Rudová, Logické programování I, 20. května 2009 62 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram DONALD + GERALD = ROBERT -• Struktura programu algebrogramC Cifry ) :-domain(. . .) , constraints(...), labeling(...)■ -• Knihovna pro CLP(FD) :- use_module(library(clpfd)) . -• Domény proměnných domain( Seznam, MinValue, MaxValue ) M Omezení all_distinct( Seznam ) -• Aritmetické omezení a*b + c #= d -• Procedura pro prohledávání stavového prostoru labeling([], [XI, X2, X3]) Hana Rudová, Logické programování I, 20. května 2009 63 Omezující podmínky Algebrogram: řešení :- use_module(library(clpfd)). donald(LD):- % domény LD=[D,0,N,A,L,G,E,R,B,T], domain(LD,0,9), domain([D,G,R],1,9), % omezeni all_distinct(LD) , 100000*D + 10000*0 + 1000*N + 100*A + 10*L + D + 100000*G + 10000*E + 1000*R + 100*A + 10*L + D #= 100000*R + 10000*0 + 1000*B + 100*E + 10*R + T, % prohledáváni stavového prostoru labeling([] , LD) . Hana Rudová, Logické programování I, 20. května 2009 64 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejdřívější čas, kdy může být zahájen. Nalezněte startovní čas každého úkolu tak, aby se jednotlivé úkoly nepřekrývaly. Ukolyjsou zadány následujícím způsobem: % úkol(Id,Doba,Mi nStart,MaxKonec) úkol(1,4,8,70). úkol(2,2,7,60). úkol(3,1,2,25). úkol(4,6,5,55). úkol(5,4,1,45). úkol(6,2,4,35). úkol(7,8,2,25). úkol(8,5,0,20). úkol(9,1,8,40). úkol(10,7,4,50). úkol(11,5,2,50). úkol(12,2,0,3 5). úkol(13,3,30,60). úkol(14,5,15,70). úkol(15,4,10,40). Kostra řešení: úkol y(Začátky) :- domeny(Ukoly,Začátky,Doby), serial i zed(Začátky,Doby), 1abeli ng([],Začátky). domény(Úkoly,Začátky,Doby) :- findall(úkol(Id,Doba,MinStart,MaxKonec), úkol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Úkol y,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 65 Omezující podmínky Plánování: výstup tiskni(Úkoly,Začátky) :- priprav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), ni, tiskni(Vystup). priprav([] , [] , []). při prav([úkol(Id,Doba,MinStart,MaxKonec)|Úkoly], [Z|Začátky], [úkol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :- priprav(Ukoly,Začátky,Vstup). tiskni ([]) : - ni . tiskni([V|Vystup]) :- V=ukol(Id,Doba,MinStart,MaxKonec,Z), K is Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), tiskni(Vystup). Hana Rudová, Logické programování I, 20. května 2009 66 Omezující podmínky Plánování: výstup II quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([],Z-Z). quicksortl([X|Tail], A1-Z2) :- split(X, Tail, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortl(Big, A2-Z2). splitCX, [], [], []). splitCX, [Y|T], [YlSmall], Big) :- greater(X,Y), !, splitCX, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). greaterCukol(_,_,_,_,Zl),úkol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 20. května 2009 67 Omezující podmínky Plánování a domény nastav_domeny([] ,[],[]). nastav_domeny([U|Úkoly],[Z|Začátky],[Doba|Doby]) :- U=ukol(_Id,Doba,MinStart,MaxKonec), MaxStart is MaxKonec-Doba, Z in MinStart..MaxStart, nastav_domeny(Úkol y,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 68 Omezující podmínky Plánování a precedence Rozšiřte řešení předchozího problému tak, aby umožňovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno před B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,l). Pro zjištění parametrů úlohy lze použít např. nth(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). Hana Rudová, Logické programování I, 20. května 2009 69 Omezující podmínky Plánování a precedence Rozšiřte řešení předchozího problému tak, aby umožňovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno před B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,l). Pro zjištění parametrů úlohy lze použít např. nth(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). precedence(Zacatky,Doby) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Začátky,Doby). omezeni_precedence([],_Zacatky,_Doby). omezeni_precedence([prec(A,B)|Přec],Začátky,Doby) :- nth(A,Začátky,ZA), nth(B,Začátky,ZB), nth(A,Doby,DA), ZA + DA #< ZB, omezeni_precedence(Prec,Začátky). Hana Rudová, Logické programování I, 20. května 2009 69 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že M odstraňte omezení na nepřekrývání úkolů -• přidejte omezení umožňující řešení každého úkolu zadaným člověkem (každý člověk může zpracovávat nejvýše jeden úkol) % clovek(Id,IdUkoly) ... človek Id zpracovává úkoly v seznamu IdUkoly clovek(l,[1,2,3,4,5]). clovek(2,[6,7,8,9,10]). clovek(3,[11,12,13,14,15]). Hana Rudová, Logické programování I, 20. května 2009 70 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že M odstraňte omezení na nepřekrývání úkolů -• přidejte omezení umožňující řešení každého úkolu zadaným člověkem (každý člověk může zpracovávat nejvýše jeden úkol) % clovek(Id,IdUkoly) ... človek Id zpracovává úkoly v seznamu IdUkoly clovek(l,[1,2,3,4,5]). clovek(2,[6,7,8,9,10]). clovek(3,[11,12,13,14,15]). li de(Začátky,Doby,Lide) :- findall(clovek(Kdo,IdUkoly),clovek(Kdo,IdUkoly), Lide), omezeni_li de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_lide([Clovek|Lide],Začátky,Doby) :- Clovek=clovek(_Id,IdUkoly), omezeni_clovek(IdUkoly,Začátky,Doby), omezeni_li de(Li de,Začátky,Doby). Hana Rudová, Logické programování I, 20. května 2009 70 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(Idllkoly,Začátky,Doby) : - omezeni_clovek(Idllkoly,Začátky,Doby, [],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,Cl ovekZ,Cl ovekD) omezeni_clovek([],_Zacatky,_Doby,ClovekZ,ClovekD) :- serialized(ClovekZ,ClovekD). omezeni_clovek([U|IdUkoly],Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(Idllkoly,Začátky,Doby, [Z|ClovekZ] , [D|C1 ovekD]) Hana Rudová, Logické programování I, 20. května 2009 71 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(Idllkoly,Začátky,Doby) : - omezeni_clovek(Idllkoly,Začátky,Doby, [],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,Cl ovekZ,Cl ovekD) omezeni_clovek([],_Zacatky,_Doby,ClovekZ,ClovekD) :- serialized(ClovekZ,ClovekD). omezeni_clovek([U|IdUkoly],Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]). Rozšiřte řešení problému tak, aby mohl každý člověk zpracovávat několik úkolů dle jeho zadané kapacity. % clovek(Id,Kapacita,IdUkoly) clovek(l,2,[1,2,3,4,5]). clovek(2,l,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). Hana Rudová, Logické programování I, 20. května 2009 71 Omezující podmínky li de(Začátky,Doby,Lide) :- fi ndal1(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo,Kapacita,IdUkoly), Lide), omezeni_li de(Li de,Začátky,Doby). omezem'_lide([] ,_Zacatky,_Doby) . omezem'_lide([clovek(_Id, Kapacita, IdUkoly) | Lide] ,Začátky,Doby) : - omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby), omezeni_li de(Li de,Začátky,Doby). omezem'_clovek(IdUkoly, Kapacita,Začátky,Doby) : - omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]). omezem'_clovek([] , Kapaci ta, _Zacatky,_Doby,ClovekZ,ClovekD) : - 1ength(ClovekZ,Delka), 1 i stOfl(Delka,Li stOf1), cumulati ve(ClovekZ,ClovekD,Li stOf1,Kapaci ta). omezem'_clovek([U | IdUkoly] , Kapaci ta, Začátky, Doby, ClovekZ,ClovekD) : - nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[Z|ClovekZ],[D|ClovekD]). listOf1(0,[]) :- !. listOfl(D,[1|L]) :- Dl is D-l, listOfl(Dl,L). Hana Rudová, Logické programování I, 20. května 2009 72 Omezující podmínky Stromy, grafy Stromy Uzly stromu Tree jsou reprezentovány termy M tree(Left,Value,Right): Left a Right jsou opět stromy, Value je ohodnocení uzlu -• leaf(Value): Value je ohodnoceni uzlu -• Příklad: 6 / \ / \ / \ 2 8 / \ / 14 7 / \ 3 5 tree(tree(leaf(l), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) ) Hana Rudová, Logické programování I, 20. května 2009 74 Stromy, grafy Stromy: hledáni prvku in(X,Tree) Napište predikát in(X,Tree), který uspěje, pokud se prvek X nachází v Tree. Prvek X se nachází ve stromě T, jestliže -• Xje listem stromu T, jinak leaf(X) M Xje kořen stromu T, jinak tree(l_eft,x,Right) M X je menší než kořen stromu T, pak se nachází v levém podstromu T, jinak -• X se nachází v pravém podstromu T Hana Rudová, Logické programování I, 20. května 2009 75 Stromy, grafy Stromy: hledáni prvku in(X,Tree) Napište predikát in(X,Tree), který uspěje, pokud se prvek X nachází v Tree. Prvek X se nachází ve stromě T, jestliže -• Xje listem stromu T, jinak leaf(X) M Xje kořen stromu T, jinak tree(l_eft,x,Right) M X je menší než kořen stromu T, pak se nachází v levém podstromu T, jinak -• X se nachází v pravém podstromu T in(X, leaf(X)) :- !. in(X, tree(_,X,_)) :- !. in(X, tree(Left, Root, Right) ) :- XV, pak má nový strom kořen V a vpravo se nachází leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(_,V,R) a XV, pak má nový strom kořen V a vpravo se nachází leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(_,V,R) a XV, !. add(leaf(V), X, tree(leaf(X),V,[]) ) :- !. Hana Rudová, Logické programování I, 20. května 2009 76 Stromy, grafy Stromy: přidávání add(Tree,X,TreeWithX) Prvek X přidej do stromu T jednou z následujících možností: M pokud T = [], pak je nový strom leaf(X) & pokud T=leaf(V) a X>V, pak má nový strom kořen V a vpravo se nachází leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(_,V,R) a XV, !. add(leaf(V), X, tree(leaf(X),V,[]) ) :- !. add(tree(L,V,R), X, tree(L,V,Rl)) :-X>V, !, add(R,X,Rl). add(tree(L,V,R), X, tree(l_l,V,R)) :- add(L,X,Ll). Hana Rudová, Logické programování I, 20. května 2009 76 Stromy, grafy Procházení stromů Napište predikát traverse(Tree, List), který projde traversálně strom Tree a v seznamu List pak obsahuje všechny prvky tohoto stromu. Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom ?- traverse(tree(tree(leaf(1),2,tree(leaf(3),4,leaf(5))),6, tree(leaf(7),8,leaf(9))), [6,2,1,4,3,5,8,7,9]). (preorder) traverse(T,Pre):- t_pre(T,Pre,[]). 6 / \ t_pre([],S,S). t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):-t_pre(L,S,Sl), t_pre(R,Sl,S2). / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] / \ / \ % S=[1|S1] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Použit princip rozdílových seznamů Hana Rudová, Logické programování I, 20. května 2009 77 Stromy, grafy Procházení stromů traverse(T,Pře):- t_pre(T,Pre,[]). t_pre([],S,S). t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2). Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] 6 / \ / \ / \ 2 8 / \ / \ 14 7 9 / \ 3 5 % V=2, S=[1,4,3,5|S2] % S=[1|S1] % S1=[4,3,5|S2] Hana Rudová, Logické programování I, 20. května 2009 78 Stromy, grafy Procházení stromů traverse(T,Pře):- t_pre(T,Pre,[]). t_pre([],S,S). t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2). Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] traverse(T,In):- t_in(T,In,[]). t_pre([],S,S). t_in(leaf(V),[V|S],S). t_in(tree(L,V,R),S,S2):- t_in(L,S,[V|Sl]), t_in(R,Sl,S2). Hana Rudová, Logické programování I, 20. května 2009 78 Stromy, grafy 6 / \ / \ / \ 2 8 / \ / \ 14 7 9 / \ 3 5 % V=2, S=[1,4,3,5|S2] % S=[1|S1] % S1=[4,3,5|S2] DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6] Hana Rudová, Logické programování I, 20. května 2009 79 Stromy, grafy DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6] traverse_post(T,Post):- t_post(T,Post,[]). 6 / \ t_pre([],S,S). / \ t_post(leaf(V),[V|S],S). / \ t_post(tree(L,V,R),S,S2):- 2 8 r, r- r-^ / \ / \ t_pOSt(L,S,Sl), 14 7 9 t_post(R,Sl,[V|S2]). / x 3 5 Hana Rudová, Logické programování I, 20. května 2009 79 Stromy, grafy Reprezentace grafu Reprezentace grafu: pole následníků uzlů Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovaný) neohodnocený graf graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6], [1,5]) 1--2 5--4 \ I II \| 6--1--2--3 3 ?- functor(Graf,graf,PocetUzlu). ?- arg(Uzel,Graf,Sousedi). (Orientovaný) ohodnocený graf [Soused-Ohodnoceni|Sousedi] graf([2-l,3-2],[1-1,3-2],[1-2,2-2]). graf([2-1,4-3,6-1],[1-1,3-2],[2-2],[1-3,5-1],[4-1,6-2],[1-1,5-2]). Hana Rudová, Logické programování I, 20. května 2009 80 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(U,G,P) pro procházení grafu G do hloubky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání do hloubky (pro každý uzel stromu známe jeho rodiče). Datová struktura pro rodiče uzlů: -• při reprezentaci rodičů lze využít term s aritou odpovídající počtu uzlů M iniciálně jsou argumentu termu volné proměnné -• na závěr je v N-tém argumentu uložen rodič N-tého uzlu (iniciální uzel označíme empty) graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6], [1,5]) . 1--2 1--2 5--4 5 4 \ I \ II II \| \ 6--1--2--3 6--1--2--3 3 3 U=4: rodič(4, 1, 2, empty, 6, 1) U=2: rodič(2,empty,1) Hana Rudová, Logické programování I, 20. května 2009 81 Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu U M Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné) -• Uzel U má prázdného rodiče a má sousedy S -• Procházíme (rekurzivně) všechny sousedy v S dfs(U,G,P) :- functor(G,graf,Počet), functor(P,rodi ce,Počet), arg(U,G,Sousedi), arg(U,P,empty), prochazej_sousedy(Sousedi,U,G,P). Hana Rudová, Logické programování I, 20. května 2009 82 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů S uzlu U 1 . Uzel Vje první soused 2. Zjistíme rodiče uzlu V 3. Pokud jsme V ještě neprošli (tedy nemá rodiče a platí var(Rodic)), tak (a) nastavíme rodiče uzlu V na U (b) rekurzivně procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu U Hana Rudová, Logické programování I, 20. května 2009 83 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů S uzlu U 1 . Uzel Vje první soused 2. Zjistíme rodiče uzlu V 3. Pokud jsme V ještě neprošli (tedy nemá rodiče a platí var(Rodic)), tak (a) nastavíme rodiče uzlu V na U (b) rekurzivně procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu U prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],U,G,P) :- arg(V,P,Rodič), ( nonvar(Rodic) -> ; Rodič = U, arg(V,G,SousediV), prochazej_sousedy(SousediV,V,G,P) ), prochazej_sousedy(T,U,G,P). Hana Rudová, Logické programování I, 20. května 2009 83 Stromy, grafy DÚ: Procházení grafu do šířky Napište predikát bfs(U,G,P) pro procházení grafu G do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu G do šířky (pro každý uzel stromu známe jeho rodiče). graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6], [1,5]) . 1--2 1--2 5--4 5--4 II II I \| | 6--1--2--3 6--1--2--3 3 3 U=4: rodič(4, 1, 2, empty, 4, 1) U=2: rodič(2,empty,2) Hana Rudová, Logické programování I, 20. května 2009 84 Stromy, grafy Poděkování Průsviky ze cvičení byly připraveny na základě materiálů dřívějších cvičících tohoto předmětu. Speciální poděkování patří -• Adrianě Strejčkové Další podklady byly připraveny -• Alešem Horákem -• Miroslavem Nepilem M Evou Žáčkovou Hana Rudová, Logické programování I, 20. května 2009 85 Poděkováni