IB013 Logické programování I (průsvitky ze cvičení) Hana Rudová jaro 2010 Backtracking, unifikace, aritmetika Syntaxe logického programu Term: JS> univerzální datová struktura (slouží také pro příkazy jazyka) ii> definovaný rekurzivně & konstanty: číselné, alfanumerické (začínají malým písmenem), ze speciálních znaku (operátory) proměnné: pojmenované (alfanumerické retezce začínající anonymní (zacínají podtržítkem) složený term: funktor, arita, argumenty struktury jsou opet termy Hana Rudová, Logické programování I, 19. kvetna 2010 Backtracking, unifikace, aritmetika Anatomie a sémantika logického programu & 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: vety ukonCené teCkou, se skládají z hlavy a tela. Prázdné telo mají fakta, neprázdné pak pravidla, existují také klauzule bez hlavy - direktivy. Hlavu tvorí literál (složený term), telo seznam literálu. Literálum v tele nebo v dotazu ríkáme cíle. Dotazem v prostredí interpretu se spouští programy Ci procedury. Sémantika logického programu: procedury = databáze faktu a pravidel = logické formule Hana Rudová, Logické programování I, 19. kvetna 2010 4 Backtracking, unifikace, aritmetika Sicstus Prolog minimum I & Spuštění 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 standardne z nabídky Start/Programs nebo pomocí ikony, nastavíme pracovní adresár pomocí File/Working directory, v prípade potreby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings. Hana Rudová, Logické programování I, 19. kvetna 2010 5 Backtracking, unifikace, aritmetika Sicstus Prolog minimum II & Načtení programu: tzv. konzultace Editor není integrován, takže program editujeme externe ve svém oblíbeném editoru. Pak ho naCteme z príkazové rádky v interpretu příkazem ?- consult(jmeno). nebo pomocí zkrácené syntaxe ?- [jmeno]. % (předpokládá se prípona .pl) pokud uvádíme celé jméno prípadne cestu, dáváme jej do apostrofů ?- ['D:\prolog\moje\programy\jmeno.pl']. V MS Windows lze také pomocí nabídky File/Consult Hana Rudová, Logické programování I, 19. kvetna 2010 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(1,2,Y), vypis('Vysledek je ',Y). Každý příkaz ukončujeme teckoů. JS> Prerušení a zastavení cyklícího programu: Ctrl-C UkonCení interpretu příkazem ?- halt. Hana Růdová, Logické programování I, 19. května 2010 7 Backtracking, unifikace, aritmetika Příklad rodokmen rodicCpetr, filip). rodicCpetr, lenka). rodicCpavel, jan). rodic(adam, petr). rodic(tomas, michal). rodic(michal, radek). rodic(eva, filip). rodic(jana, lenka). rodic(pavla, petr). rodic(pavla, tomas). rodic(lenka, vera). otec(Otec,Dite) :- rodic(Otec,Dite), 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). Hana Rudová, Logické programování I, 19. května 2010 8 Backtracking, unifikace, aritmetika Backtracking: príklady V pracovním adresári vytvorte program rodokmen.pl. Nactete program v interpretu (konzultujte). V interpretu Sicstus Prologu pokládejte dotazy: Je Petr otcem Lenky? & Je Petr otcem Jana? -í* Kdo je otcem Petra? & Jaké deti má Pavla? JS> Ma Petr dceru? C- Které dvojice otec-syn známe? Hana Rudová, Logické programování I, 19. kvetna 2010 9 Backtracking, unifikace, aritmetika Backtracking: rešení príkladu St redníkem si vyžádáme další rešení | ?- otec(petr,lenka). yes | ?- otec(petr,jan). no | ?- otec(Kdo,petr). Kdo = adam ? ; no | ?- rodic(pavla,Dite). Dite = petr ? ; Dite = tomas ? ; no | ?- otec(petr,Dcera),zena(Dcera). Dcera = lenka ? ; no Hana Rudová, Logické programování I, 19. kvetna 2010 | ?- otec(Otec,Syn),muz(Syn). 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,Predek) roch'c(Predek,Potomek). potomek(Potomek,Predek) rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nev1astni_bratr(Nev1astni_bratr,Nev1astni_sourozenec) Hana Rudová, Logické programování I, 19. května 2010 11 Backtracking, unifikace, aritmetika Backtracking: příklady II Predikát potomek/2: potomek(Potomek,Predek) rodic(Predek,Potomek). potomek(Potomek,Predek) rodic(Predek,X), potomek(Potomek,X). Naprogramujte predikáty & prababicka(Prababicka,Pravnouce) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec) Rešení: prababicka(Prababicka,Pravnouce):-rodic(Prababicka,Prarodic), zena(Prababicka), rodic(Prarodic,Rodic), rodic(Rodic,Pravnouce). Hana Rudová, Logické programování I, 19. kvetna 2010 11 Backtracking, unifikace, aritmetika Backtracking: řešení příkladů II nevlastni_bratr(Bratr,Sourozenec):-rodic_v(X,Bratr), muz(Bratr), rodic_v(X,Sourozenec), /* tento test neni nutny, ale zvyšuje efektivitu */ Bratr \== Sourozenec, rodic_v(Y,Bratr), Y \== X, rodic_v(Z,Sourozenec), Z \== X, Z \== Y. /* nevhodne umisteni testu - vypocet "bloudi" v neuspesnych vetvich */ 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). Hana Rudová, Logické programování I, 19. kvetna 2010 12 Backtracking, unifikace, aritmetika Backtracking: prohledávání stavového prostoru -í* 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? Nahrad'te ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2 rodic_v(X,y):-rodicCX,Y),printCX),printC'? '). Pozorujte rozdíly v délce výpoctu dotazu nev1astni_bratr(fi1ip,X) pri zmene poradí testů v definici predikátu nev1astni_bratr/2 Hana Rudová, Logické programování I, 19. kvetna 2010 13 Backtracking, unifikace, aritmetika Backtracking: rešení III /* varianta 1a */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). /* varianta 1b - jine poradi odpovedi, neprimi potomci maji prednost */ potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). /* varianta 2a - leva rekurze ve druhe klauzuli, na dotaz potomek(X,pavla) vypise odpovedi, pak cykli */ potomek(Potomek,Predek):-rodic(Predek,Potomek). potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). /* varianta 2b - leva rekurze v prvni klauzuli, na dotaz potomek(X,pavla) hned cykli */ potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X). potomek(Potomek,Predek):-rodic(Predek,Potomek). Hana Rudová, Logické programování I, 19. května 2010 14 Backtracking, unifikace, aritmetika | ?- nev1astni_bratr(X,Y). petr? petr? petr? petr? eva? petr? jana? X = filip, 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 | ?- nev1astni_bratr2(X,Y). petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr? jana X = filip, 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, 19. kvetna 2010 15 Backtracking, unifikace, aritmetika Unifikace:příklady Které unifikace jsou korektní, které ne a proC? 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,p1us) 6. s(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Hana Rudová, Logické programování I, 19. kvetna 2010 16 Backtracking, unifikace, aritmetika Unifikaceipříklady Které unifikace jsou korektní, které ne a proc? 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(1,a(X,q(w)))=s(Y,a(2,Z)) 7. s(1,a(X,q(X)))=s(W,a(Z,Z)) 8. X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y)) Neuspeje volání 1) a 3), ostatní ano, cyklické struktury vzniknou v prípadech 4),7) a 8) prestože u posledních dvou mají levá a pravá strana unifikace disjunktní množinyjmen promenných. Hana Rudová, Logické programování I, 19. kvetna 2010 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 príkladu predikátu suma/3. suma(0,X,X). /*klauzule A*/ suma(s(X),Y,s(Z)):-suma(X,Y,Z). /*klauzule B*/ pomocí substituCních rovnic pri odvozování odpovedi na dotaz ?- suma(s(0),s(0),X0). Hana Rudová, Logické programování I, 19. kvetna 2010 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(X1),Y1,s(Z1)) ==> X1 = 0, Y1 = s(0), s(Z1) = X0 ==> suma(0,s(0),Z1) 2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznacíme jako další možnost suma(0,s(0),Z1) = suma(0,X2,X2) X2 = s(0), Z1 = s(0) ==> X0 = s(s(0)) X0 = s(s(0)) ; 2' dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument) no Hana Rudová, Logické programování I, 19. kvetna 2010 18 Backtracking, unifikace, aritmetika Vícesměrnost predikátů Logický program lze využít vícesmerne, například jako JS> výpoCet kdo je otcem Petra? ?- otec(X,petr). kolikje 1+1? ?- suma(s(0),s(0),X). iS* 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íte známe? ?-otec(X,Y). Které X a Y dávají v souctu 2? ?- suma(X,Y,s(s(0))). ... ale pozor na levou rekurzi, volné promenné, 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 si je odvodit pomocí substitucních rovnic. Hana Rudová, Logické programování I, 19. kvetna 2010 19 Backtracking, unifikace, aritmetika Aritmetika Zavádíme z praktických důvodů, ale aritmetické predikáty již nejsou vícesmerné, protože v každém aritmetickém výrazu musí být všechny promenné instaciovány císelnou konstantou. Důležitý rozdíl ve vestavených predikátech is/2 vs. =/2 vs. =:=/2 is/2: < konstanta nebo promenná > is < aritmetický výraz > výraz na pravé strane je nejdríve aritmeticky vyhodnocen a pak unifkován s levou stranou =/2: < libovolný term > = < libovolný term > levá a pravá strana jsou unifikovány "=:="/2 "=\="/2 ">="/2 "=<"/2 < 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, 19. kvetna 2010 20 Backtracking, unifikace, aritmetika Aritmetika: príklady Jak se liší následující dotazy (na co se kdy ptáme)? Které ůspějí (kladná odpověd ' ), které neůspejí (záporná odpoved'), a které jsoů špatne (dojde k chybe)? Za jakých předpokladů by ty neúspešné prípadne špatné ůspely? 1. X = Y+ 1 2. X is Y+ 1 3. X = Y 4. X== Y 5. 1 + 1 = 2 6. 2 = 1 + 1 7. 1 + 1 = 1 + 1 8. 1 + 1 is 1 + 1 9. 1 + 2 =:= 2 + 1 10. X \== Y 11. X=\= Y 12.1+2 =\= 1-2 13. 1 <= 2 14. 1 =< 2 15. sin(X) is sin(2) 16. sin(X) = sin(2+Y) 17. sin(X) =:= sin(2+Y) Nápoveda: '='/2 ůnifikace, '=='/2 test na identitů, '=:='/2 aritmetická rovnost, '\==' /2 negace testů na identitů, '=\=' /2 aritmetická nerovnost Hana Růdová, Logické programování I, 19. kvetna 2010 21 Backtracking, unifikace, aritmetika Aritmetika: príklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. Hana Rudová, Logické programování I, 19. kvetna 2010 22 Backtracking, unifikace, aritmetika Aritmetika: príklady II Jak se liší predikáty sl/3 a s2/3? Co umí sl/3 navíc oproti s2/3 a naopak? s1(0,X,X). s1(s(X),Y,s(Z)):-s1(X,Y,Z). s2(X,Y,Z):- Z is X + Y. sl/3 je vícesmerný- umí scítat, odecítat, generovat soucty, ale pracuje jen s nezápornými celými císly s2/3 umí pouze scítat, ale také záporná a reálná císla Hana Rudová, Logické programování I, 19. kvetna 2010 22 Backtracking, unifikace, aritmetika Operátory Definice operátoru umožnuje prehlednejší infixový zápis binárních a unárních predikátů, príklad: definice op(1200,Y,':-') umožnuje zápis a:-pn'nt(s(s(0))),b,c). pro výraz :-(a,,(pnnt(s(s(0))),,(b,0)). Prefixovou notaci lze získat predikátem display/1. Vyzkoušejte display((a:-pn'nt(s(s(0))),b,c)). display(a+b+c-d-e*f*g-h+i). Definice standardních operátoru najdete na konci manuálu. Hana Rudová, Logické programování I, 19. kvetna 2010 23 Backtracking, unifikace, aritmetika Zaver Dnešní látku jste pochopili dobre, pokud víte -i* jaký vliv má poradí klauzulí a cílu v predikátu potomek/2 na jeho funkci, -í* jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (príklad nevlastni_bratr/2), -i* k cemu dojde po unifikaci X=a(X), -i* proc neuspeje dotaz ?- X=2, sin(X) is sin(2). za jakých predpokladu uspejí tyto cíle X=Y, X==Y, X=:=Y, & a umíte odvodit pomocí substitucních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z). Hana Rudová, Logické programování I, 19. kvetna 2010 24 Backtracking, unifikace, aritmetika Seznamy, řez Reprezentace seznamu -i* Seznam: [a, b, c], prázdný seznam [] & Hlava (libovolný objekt), telo (seznam): .(Hlava, Telo) A všechny strukturované objekty stromy - i seznamy ± funktordva argumenty .(a, .(b, .(c, []))) = [a, b, c] i> notace: [ Hlava | Telo ] = [a|Te1o] Telo je v [a|Te1o] seznam, tedy píšeme [ a, b, c ] = [ a | [ b, c ] ] & Lze psát i: [a,b|Te1o] pred "|"je libovolný pocet prvků seznamu , za "|"je seznam zbývajících prvků [a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]] pozor: [ [a,b] | [c] ] = [ a,b | [c] ] & Seznam jako neúplná datová struktura: [a,b,c|T] A Seznam = [a,b,c|T], T = [d,e|S], Seznam = [a,b,c,d,e|S] Hana Rudová, Logické programování I, 19. kvetna 2010 26 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) :-DÚ: suffix(S1,S2) Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: Ü> prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) Hana Rudová, Logické programování I, l9. kvetna 2GlG 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) M last( X, S ) :- append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: Jí* prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) :- append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: & prefix( S1, S2 ) append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) append( S1, S2, S3). Napište následující predikáty pomocí append/3: prefix( S1, S2 ) append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) % sublist(+S,+ASB) sublist(S,ASB) Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Seznamy a append append( [], S, S ). append( [X|S1], S2, [X|S3] ) :- append( S1, S2, S3). Napište následující predikáty pomocí append/3: & prefix( S1, S2 ) :- append( S1, _S3, S2). DÚ: suffix(S1,S2) last( X, S ) :- append( _S1, [X], S). append([3,2], [6], [3,2,6]). X=6, S=[3,2,6] & member( X, S ) :- append( S1, [X|S2], S ). append([3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacent(X,Y,S) % sublist(+S,+ASB) sublist(S,ASB) :- append( AS, B, ASB ), append( A, S, AS ). POZOR na efektivitu, bez append lze casto napsat efektivneji Hana Rudová, Logické programování I, 19. kvetna 2010 27 Seznamy, rez Optimalizace posledního volání Last Call Optimization (LCO) Implementacní technika snižůjící nároky na pamet' Mnoho vnorených rekůrzivních volání je nárocné na pamet' Poůžití LCO ůmožnůje vnorenoů rekůrzi s konstantními pametovými nároky Typický príklad, kdy je možné poůžití LCO: A procedůra můsí mít poůze jedno rekůrzivní volání: v posledním cíli poslední klauzule A cíle predcházející tomůto rekůrzivnímů volání můsí být deterministické -i> p( ... ) :- ... % žádné rekurzivní volání v tele klauzule p( ...):- ... % žádné rekurzivní volání v tele klauzule p(...) :- !, p( ... ). % rez zajišťuje determinismus & Tento typ rekurze lze prevést na iteraci Hana Růdová, Logické programování I, 19. kvetna 2010 28 Seznamy, rez LCO a akumulátor -í* Reformulace rekurzivní procedury, aby umožnila LCO VýpoCet délky seznamu 1ength( Seznam, Delka ) 1ength( [], 0 ). 1ength( [ H | T ], Delka ) :- 1ength( T, DelkaO ), Delka is 1 + DelkaO. Hana Rudová, Logické programování I, 19. kvetna 2010 29 Seznamy, rez LCO a akumulátor -í* Reformulace rekurzivní procedury, aby umožnila LCO & Výpocet délky seznamu 1ength( Seznam, Delka ) 1ength( [], 0 ). 1ength( [ H | T ], Delka ) :- 1ength( T, DelkaO ), Delka is 1 + DelkaO. -í* Upravená procedura, tak aby umožnila LCO: % 1ength( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvků v Seznam'' Hana Rudová, Logické programování I, 19. kvetna 2010 29 Seznamy, rez LCO a akumulátor J& Reformulace rekurzivní procedury, aby umožnila LCO Výpocet délky seznamu length( Seznam, Delka ) length( [], 0 ). length( [ H | T ], Delka ) length( T, DelkaO ), Delka is 1 + DelkaO. & Upravená procedura, tak aby umožnila LCO: % length( Seznam, ZapocitanaDelka, CelkovaDelka ): % CelkovaDelka = ZapocitanaDelka + ,,počet prvku v Seznam'' length( Seznam, Delka ) length( Seznam, 0, Delka ). % pomocný predikát length( [], Delka, Delka ). % celková délka = zapocítaná délka length( [ H | T ], A, Delka ) A0 is A + 1, length( T, A0, Delka ). JS* Prídavný argument se nazývá akumulátor Hana Rudová, Logické programování I, 19. kvetna 2010 29 Seznamy, rez Akumulátor a sum_1ist(S,Sum) ?- sum_1ist( [2,3,4], Sum ). bez akumulátoru: Hana Rudová, Logické programování I, 19. kvetna 2010 30 Seznamy, rez Akumulátor a sům_1ist(S,Sům) ?- sum_list( [2,3,4], Sum ). bez akumulátoru: sum_list( [], 0 ). sum_list( [H|T], Sum ) :- sum_list( T, SumT ), Sum is H + SumT. s akumulátorem: sum_list( S, Sum ) :- sum_list( S, 0, Sum ). sum_list( [], Sum, Sum ). sum_list( [H|T], A, Sum ) :- A1 is A + H, sum_list( T, A1, Sum). Hana Rudová, Logické programování I, 19. kvetna 2010 30 Seznamy, rez Výpočet faktoriálu fact(N,F) s akumulátorem: Hana Rudová, Logické programování I, 19. kvetna 2010 31 Seznamy, rez VýpoCet faktořiálu fact(N,F) s akumulátorem: fact( N, F ) :- fact ( N, 1, F ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, A1 is N * A, N1 is N - 1, fact( N1, A1, F ). Hana Rudová, Logické programování I, 19. kvetna 2010 31 Seznamy, rez r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). Prozkoumejte trasy výpoctu a navracení napr. pomocí následujících dotazů (vždy si stredníkem vyžádejte navracení): p(X):-write(p1). p(X):-a(X),b(X),!, (1) X=1,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). 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). Prozkoumejte trasy výpoctu a navracení nap r . pomocí následujících dotazu (vždy si stredníkem vyžádejte navracení): (1) X=1,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). rez v predikátu p/1 neovlivní alternativy predikátu r/1 dokud nebyl proveden rez, alternativy predikátu a/1 se uplatnují, p r . neúspech b/1 v dotazu (3) p r i neúspechu cíle za rezem se výpocet navrací až k volající procedu r e r/1, viz (1) alternativy vzniklé po provedení rezu se zachovávají - další možnosti predikátu c/1 viz (2) a (4) Hana Rudová, Logické programování I, 19. kvetna 2010 32 Seznamy, rez r(X)i-write(r1). r(X)i-pCX),write(r2). rCX)i-writeCr5). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). pCX)i-writeCp5). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(d). c(X)i- X mod S =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). r(X)i-write(r1). r(X)i-p(X),write(r2). r(X)i-write(r3). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =:= 0, write(c2). I ?- X=1,r(X). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; j ?- X=l,r(X). r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). X= plr2 rl 1 ? ■ X= p(X):-write(pl). p(X):-aCX),b(X),i, c(X),dCX),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > G, write(bl). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(cl). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(dl). d(X):- write(d2). r(X)i-write(r1). r(X)i-pCX),write(r2). rCX)i-writeCr5). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). pCX)i-writeCp5). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(d). c(X)i- X mod S =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,r(X). r1 X = 1 ľ ; p1r2 X = 1 ľ ; a1b1rS X = 1 ľ ; r(X)i-write(r1). r(X)i-p(X),write(r2). r(X)i-write(r3). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =:= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). I ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > G, write(b1). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(c1). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ ; p1r2 X = 1 ľ ; a1b1r3 X = 1 ľ ; no | ľ- X=G,r(X). r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; r(X)i-write(r1). r(X)i-pCX),write(r2). rCX)i-writeCr5). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). pCX)i-writeCp5). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(d). c(X)i- X mod S =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rS X = 1 ľ i no j ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pSr2 X = 0 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > G, write(b1). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(c1). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no | ľ- X=G,r(X). r1 X = G ľ i p1r2 X = G ľ i a1a2p3r2 X = G ľ i r3 X = G ľ i r(X)i-write(r1). r(X):-p(X),write(r2). r(X)i-write(r3). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod 3 =:= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). I ?- X=1,r(X). r1 X = 1 ? i p1r2 X = 1 ? i a1b1r3 X = 1 ? i no I ?- X=0,r(X). r1 X = 0 ? i p1r2 X = 0 ? i a1a2p3r2 X = 0 ? i r3 X = 0 ? i no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-aCX),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > G, write(bl). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(cl). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(dl). d(X):- write(d2). j ľ- X=l,r(X). rl X = 1 ľ i plr2 j ľ- X=3,r(X). X = 1 ľ i alblr3 X = 1 ľ i no j ľ- X=G,r(X). rl X = G ľ i plr2 X = G ľ i ala2p3r2 X = G ľ i r3 X = G ľ i no r(X)i-write(r1). r(X)i-pCX),write(r2). rCX^-writeCrS). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). pCX^-writeCpS). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod S =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,r(X). r1 X = 1 ľ i p1r2 j ľ- X=5,r(X). X = 1 ľ i r1 a1b1rS X = S ľ i X = 1 ľ i no j ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pSr2 X = 0 ľ i rS X = 0 ľ i no r(X)i-write(r1). r(X):-p(X),write(r2). r(X)i-write(r3). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > O, write(bl). b(X)i- X < O, write(b2). c(X)i- X mod 2 =i= O, write(cl). c(X)i- X mod 3 =:= O, write(c2). d(X)i- abs(X) < 1O, write(dl). d(X)i- write(d2). I ľ- X=1,r(X). rl X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no I ľ- X=O,r(X). rl X = O ľ i p1r2 X = O ľ i a1a2p3r2 X = O ľ i r3 X = O ľ i no I ľ- X=3,r(X). r1 X = 3 ľ i p1r2 X = 3 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 | ?- X=3,r(X). X = 1 ? ; r1 a1b1r3 X = 3 ? ; X = 1 ? ; p1r2 no X = 3 ? ; a1b1c2d1p2r2 | ?- X=0,r(X). X = 3 ? ; r1 X = 0 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ?- X=1,r(X). r1 X = 1 ? i p1r2 I ?- X=3,r(X). X = 1 ? i r1 a1b1r3 X = 3 ? i X = 1 ? i p1r2 no X = 3 ? i a1b1c2d1p2r2 I ?- X=0,r(X). X = 3 ? i r1 d2p2r2 X = 0 ? i X = 3 ? i p1r2 X = 0 ? i a1a2p3r2 X = 0 ? i r3 X = 0 ? i no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > G, write(b1). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(c1). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ i p1r2 | ľ- X=3,r(X). X = 1 ľ i r1 a1b1r3 X = 3 ľ i X = 1 ľ i p1r2 no X = 3 ľ i a1b1c2d1p2r2 | ľ- X=G,r(X). X = 3 ľ i r1 d2p2r2 X = G ľ i X = 3 ľ i p1r2 r3 X = G ľ i X = 3 ľ i a1a2p3r2 X = G ľ i r3 X = G ľ i no r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-aCX),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > G, write(bl). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(cl). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(dl). d(X):- write(d2). j ľ- X=l,r(X). rl X = 1 ľ i plr2 X = 1 ľ i alblr3 X = 1 ľ i no j ľ- X=G,r(X). rl X = G ľ i plr2 X = G ľ i ala2p3r2 X = G ľ i r3 X = G ľ i no j ľ- X=3,r(X). rl X = 3 ľ i plr2 X = 3 ľ i alblc2dlp2r2 X = 3 ľ i d2p2r2 X = 3 ľ i r3 X = 3 ľ i no r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X= -6, r(X). | ?- X=3,r(X). r1 X=3?; p1r2 X=3?; a1b1c2d1p2r2 X=3?; d2p2r2 X=3?; r3 X=3?; no r(X)i-write(r1). r(X):-p(X),write(r2). r(X)i-write(r3). pCX)i-write(pl). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). p(X)i-write(p3). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > O, write(bl). b(X)i- X < O, write(b2). c(X)i- X mod 2 =i= O, write(cl). c(X)i- X mod 3 =:= O, write(c2). d(X)i- abs(X) < 1O, write(dl). d(X)i- write(d2). I ľ- X=1,r(X). rl X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no I ľ- X=O,r(X). r1 X = O ľ i p1r2 X = O ľ i a1a2p3r2 X = O ľ i r3 X = O ľ i no I ľ- X=3,r(X). r1 X = 3 ľ i p1r2 X = 3 ľ i a1b1c2d1p2r2 X = 3 ľ i d2p2r2 X = 3 ľ i r3 X = 3 ľ i no I ľ- X= -6, r(X). r1 X = -6 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ?- X=1,r(X). r1 X = 1 ? i p1r2 X = 1 ? i a1b1r3 X = 1 ? i no I ?- X=0,r(X). r1 X = 0 ? i p1r2 X = 0 ? i a1a2p3r2 X = 0 ? i r3 X = 0 ? i no I ?- X=3,r(X). r1 X=3?i p1r2 X=3?i a1b1c2d1p2r2 X=3?i d2p2r2 X=3?i r3 X=3?i no I ?- X= -G, r(X). r1 X = -G ? i p1r2 X = -G ? i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > G, write(b1). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(c1). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(d1). d(X):- write(d2). | ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1r3 X = 1 ľ i no | ľ- X=G,r(X). r1 X = G ľ i p1r2 X = G ľ i a1a2p3r2 X = G ľ i r3 X = G ľ i no | ľ- X=3,r(X). r1 X=3ľi p1r2 X=3ľi a1b1c2d1p2r2 X=3ľi d2p2r2 X=3ľi r3 X=3ľi no | ľ- X= -6, r(X). r1 X = -6 ľ i p1r2 X = -6 ľ i a1b2c1d1p2r2 X = -6 ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). I ?- X=1,r(X). r1 X = 1 ? i p1r2 X = 1 ? i a1b1r3 X = 1 ? i no I ?- X=0,r(X). r1 X = 0 ? i p1r2 X = 0 ? i a1a2p3r2 X = 0 ? i r3 X = 0 ? i no I ?- X=3,r(X). r1 X=3?i p1r2 X=3?i a1b1c2d1p2r2 X=3?i d2p2r2 X=3?i r3 X=3?i no I ?- X= -G, r(X). r1 X = -G ? i p1r2 X = -G ? i a1b2c1d1p2r2 X = -G ? i d2p2r2 X = -G ? i r(X)i-write(r1). r(X)i-pCX),write(r2). rCX^-writeCrS). p(X)i-write(p1). p(X)i-a(X),b(X),!, c(X),d(X),write(p2). pCX^-writeCpS). a(X)i-write(a1). a(X)i-write(a2). b(X)i- X > 0, write(b1). b(X)i- X < 0, write(b2). c(X)i- X mod 2 =i= 0, write(c1). c(X)i- X mod S =i= 0, write(c2). d(X)i- abs(X) < 10, write(d1). d(X)i- write(d2). j ľ- X=1,r(X). r1 X = 1 ľ i p1r2 X = 1 ľ i a1b1rS X = 1 ľ i no j ľ- X=0,r(X). r1 X = 0 ľ i p1r2 X = 0 ľ i a1a2pSr2 X = 0 ľ i rS X = 0 ľ i no j ľ- X=5,r(X). r1 X=Sľi p1r2 X=Sľi a1b1c2d1p2r2 X=Sľi d2p2r2 X=Sľi X=Sľi no j ľ- X= -G, r(X). r1 X = -G ľ i p1r2 X = -G ľ i a1b2c1d1p2r2 X = -G ľ i d2p2r2 X = -G ľ i c2d1p2r2 X = -G ľ i r(X):-write(r1). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(p1). p(X):-a(X),b(X),!, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(a1). a(X):-write(a2). b(X):- X > 0, write(b1). b(X):- X < 0, write(b2). c(X):- X mod 2 =:= 0, write(c1). c(X):- X mod 3 =:= 0, write(c2). d(X):- abs(X) < 10, write(d1). d(X):- write(d2). | ?- X=1,r(X). r1 X = 1 ? ; p1r2 X = 1 ? ; a1b1r3 X = 1 ? ; no | ?- X=0,r(X). r1 X = 0 ? ; p1r2 X = 0 ? ; a1a2p3r2 X = 0 ? ; r3 X = 0 ? ; no | ?- X=3,r(X). r1 X=3?; p1r2 X=3?; a1b1c2d1p2r2 X=3?; d2p2r2 X=3?; r3 X=3?; no | ?- X= -6, r(X). r1 X = -6 ? ; p1r2 X = -6 ? ; a1b2c1d1p2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2d1p2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). p(X):-aCX),b(X),i, c(X),d(X),write(p2). p(X):-write(p3). a(X):-write(al). a(X):-write(a2). b(X):- X > G, write(bl). b(X):- X < G, write(b2). c(X):- X mod 2 =:= G, write(cl). c(X):- X mod 3 =:= G, write(c2). d(X):- abs(X) < 1G, write(dl). d(X):- write(d2). j ľ- X=l,r(X). rl X = 1 ľ i plr2 X = 1 ľ i alblr3 X = 1 ľ i no j ľ- X=G,r(X). rl X = G ľ i plr2 X = G ľ i ala2p3r2 X = G ľ i r3 X = G ľ i no j ľ- X=3,r(X). rl X = 3 ľ i plr2 X = 3 ľ i alblc2dlp2r2 X = 3 ľ i d2p2r2 X = 3 ľ i r3 X = 3 ľ i no j ľ- X= -G, r(X). rl X = -G ľ i plr2 X = -G ľ i alb2cldlp2r2 X = -G ľ i d2p2r2 X = -G ľ i c2dlp2r2 X = -G ľ i d2p2r2 X = -G ľ i r3 X = -G ľ i r(X):-write(rl). r(X):-p(X),write(r2). r(X):-write(r3). p(X):-write(pl). 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) < l0, write(dl). d(X):- write(d2). Hana Rudová, Logické programování I, 19. května 2010 | ?- X=l,r(X). rl X = l ? ; plr2 | ?- X=3,r(X). X = l ? ; rl alblr3 X = 3 ? ; X = l ? ; 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 ? ; no 33 | ?- 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, rez Řez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,l. max(X,Y,Y). Hana Rudová, Logické programování I, 19. kvetna 2010 34 Seznamy, rez Rez: maximum Je tato definice predikátu max/3 korektní? max(X,Y,X):-X>=Y,l. max(X,Y,Y). Není, následující dotaz uspeje: ?- max(2,1,1). Uved'te dve možnosti opravy, se zachováním použití r ezu a bez. Hana Rudová, Logické programování I, 19. kvetna 2010 34 Seznamy, rez Ř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 uspeje: ?- max(2,1,1). Uved'te dve možnosti opravy, se zachováním použití r 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 Pr i použití r ezu je tr eba striktne oddelit vstupní podmínky od výstupních unifikací a výpoctu. Hana Rudová, Logické programování I, 19. kvetna 2010 34 Seznamy, rez Ř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 r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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, 19. května 2010 35 Seznamy, rez Rez: 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 r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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 r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) Hana Rudová, Logické programování I, 19. kvetna 2010 35 Seznamy, rez Rez: 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 r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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 r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) -í* mem2/2 najde jenom první výskyt, taky váže promenné Hana Rudová, Logické programování I, 19. května 2010 35 Seznamy, rez Rez: member Jaký je rozdíl mezi následůjícími definicemi predikátů member/2. Ve kterých odpovedích se bůdoů lišit? Vyzkoůšejte napr. pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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). & mem1/2 vyhledá všechny výskyty, pri porovnávání hledaného prvků s prvky seznamů může dojít k vázání promenných (může sloůžit ke generování všech prvků seznamů) -í* mem2/2 najde jenom první výskyt, taky váže promenné & mem3/2 najde jenom první výskyt, promenné neváže (hledá poůze identické prvky) Dokážete napsat variantů, která hledá jenom identické prvky a pritom najde všechny výskyty? Hana Růdová, Logické programování I, 19. kvetna 2010 35 Seznamy, rez Rez: member Jaký je rozdíl mezi následujícími definicemi predikátu member/2. Ve kterých odpovedích se budou lišit? Vyzkoušejte nap r . pomocí member( X, [1,2,3] ). mem1(H,[H|_]). mem1(H,[_|T]) :-mem1(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). & mem1/2 vyhledá všechny výskyty, p r i porovnávání hledaného prvku s prvky seznamu muže dojít k vázání promenných (může sloužit ke generování všech prvků seznamu) -í* mem2/2 najde jenom první výskyt, taky váže promenné & mem3/2 najde jenom první výskyt, promenné neváže (hledá pouze identické prvky) Dokážete napsat variantu, která hledá jenom identické prvky a p r itom najde všechny výskyty? mem4(H,[K|_]) :- H==K. mem4(H,[K|T]):- mem4(H,T). Hana Rudová, Logické programování I, 19. kvetna 2010 35 Seznamy, rez Řez: delete de1ete( X, [X|S], S ). de1ete( X, [Y|S], [Y|S1] ) :- de1ete(X,S,S1). Napište predikát de1ete(X,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje). Hana Rudová, Logické programování I, l9. kvetna 2GlG 36 Seznamy, rez Řez: delete deleteC X, [X|S], S ). deleteC X, [Y|S], [Y|S1] ) :- deleteCX,S,S1). Napište predikát deleteCX,S,S1), který odstraní všechny výskyty X (pokud se X v S nevyskytuje, tak predikát uspeje). deleteC _X, [], [] ). deleteC X, [X|S], S1 ) :- !, deleteCX,S,S1). deleteC X, [Y|S], [Y|S1] ) :- deleteCX,S,S1). Hana Rudová, Logické programování I, 19. kvetna 2010 36 Seznamy, rez Seznamy: intersection(A,B,C) DÚ: Napište predikát pro výpoCět průniku dvou sěznamU. Nápověda: využijte predikát měmběr/2 DÚ: Napiště prědikát pro výpoCtu rozdílu dvou sěznamU. Nápověda: využijtě prědikát měmběr/2 Hana Rudová, Logické programování I, 19. května 2010 37 Sěznamy, rěz Všechna řešení, třídění, rozdílové seznamy vsecnna reseni % z(Jmeno,Prijmeni,Pohlavi,Vek,Prace,Firma) z(petr,novak,m,30,skladnik,skoda). z(pavel,novy,m,40,mechanik,skoda). z(rostislav,lucensky,m,50,technik,skoda). z(alena,vesela,z,25,sekretarka,skoda). z(jana,dankova,z,35,asistentka,skoda). z(lenka,merinska,z,35,ucetni,skoda). z(roman,maly,m,35,manazer,cs). z(alena,novotna,z,40,ucitelka,zs_stara). z(david,novy,m,30,ucitel,zs_stara). z(petra,spickova,z,45,uklizecka,zs_stara). Najděte jméno a p ríjmení všech lidí. ?- findallOmeno-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 ). Najdete jméno a p ríjmení všech zamestnanců firmy skoda a cs ?- findall( c(J,P,Firma), ( z(J,P,_,_,_,Firma), ( Firma=skoda ; Firma=cs ) ), L ?- bagof( J-P, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setof( P-J, [S,V,Pr]A(z(J,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 19. kvetna 2010 39 Všechna řešení, t rídení, rozdílové seznamy Všechna rešení: príklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 roků? Naleznete jejich jméno a p ríjmení 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? Hana Rudová, Logické programování I, 19. kvetna 2010 40 Všechna rešení, t rídení, rozdílové seznamy Všechna rešení: príklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 roku? Naleznete jejich jméno a p ríjmení 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). Hana Rudová, Logické programování I, 19. kvetna 2010 40 Všechna rešení, t rídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou p r íjmení všech žen? 2. Kte rí lidé mají více než 30 roku? Naleznete jejich jméno a p ríjmení. 3. Naleznete abecedne se razený seznam všech lidí. 4. Naleznete p ríjmení vyucujících ze zs_stara. 5. Jsou v databázi dva brat r i (mají stejné p r íjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). Hana Rudová, Logické programování I, 19. kvetna 2010 40 Všechna řešení, t rídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou p r íjmění všěch žěn? 2. Ktě rí lidé mají vícě něž 30 roků? Nalezněte jějich jméno a p ríjmění. 3. Nalěznětě aběcědně sě razěný sěznam všěch lidí. 4. Nalěznětě p ríjmění vyucujících zě zs_stara. 5. Jsou v databázi dva brat r i (mají stějné p r íjmění a různá jména)? 6. Ktěré firmy v databázi mají vícě něž jědnoho zaměstnancě? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). Hana Rudová, Logické programování I, 19. května 2010 40 Všěchna rěšění, t rídění, rozdílové sěznamy Všechna rešení: príklady 1. Jaká jsoů príjmení všech žen? 2. Kterí lidé mají více než 30 roků? Naleznete jejich jméno a príjmení. 3. Naleznete abecedne serazený seznam všech lidí. 4. Naleznete príjmení vyůcůjících ze zs_stara. 5. Jsoů v databázi dva bratri (mají stejné príjmení a různá jména)? 6. Které firmy v databázi mají více než jednoho zamestnance? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). Hana Růdová, Logické programování I, 19. kvetna 2010 40 Všechna rešení, trídení, rozdílové seznamy Všechna řešení: příklady 1. Jaká jsou p r íjmění všěch žěn? 2. Ktě rí lidé mají vícě něž 30 roků? Nalěznětě jějich jméno a p ríjmění. 3. Nalěznětě aběcědně sě razěný sěznam všěch lidí. 4. Nalěznětě p ríjmění vyucujících zě zs_stara. 5. Jsou v databázi dva brat r i (mají stějné p r íjmění a různá jména)? 6. Ktěré firmy v databázi mají vícě něž jědnoho zaměstnancě? 1. findall(Prijmeni, z(_,Prijmeni,z,_,_,_), L). 2. findallOmeno-Prijmeni, ( z(Jmeno,Prijmeni,_,Vek,_,_), Vek>30 ), L). 3. setof(P-O [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(J1-P,J2-P), ( z(J1,P,m,_,_,_),z(J2,P,m,_,_,_), J1@30 ), L). 3. setof(P-II, [S,V,Pr,F]Az(J,P,S,V,Pr,F), L ). 4. findall(Prijmeni, ( z(_,Prijmeni,_,_,P,zs_stara), (P=ucitel;P=ucitelka) ), L). 5. findall(b(J1-P,J2-P), ( z(J1,P,m,_,_,_),z(J2,P,m,_,_,_), J1@1 ), S). Hana Rudová, Logické programování I, 19. kvetna 2010 40 Všechna rešení, t rídení, rozdílové seznamy bubblesort(S,Sorted) Seznam S se rad'te tak, že naleznete první dva sousední prvky X a Y v S tak, že X>Y, vymente po radí X a Y a získate S1; a se rad'te S1 pokud neexistuje žádný takový pár sousedních prvku X a Y, pak je S se razený seznam swap(S,Sl) rekurzivne bubblesortem bubblesort(S,Sorted) i- swap (S,S1), !, bubblesort(S1, Sorted). bubblesort(Sorted,Sorted). % Existuje použitelný swap v S? % Jinak je seznam serazený swap([X,Y|Rest],[Y,X|Rest1]) i-X>Y. swap([Z|Rest],[Z|Rest1]) i-swap(Rest,Rest1). % swap prvních dvou prvků % nebo obecněji X@>Y, resp. gt(X,Y) % swap prvků až ve zbytku Hana Rudová, Logické programování I, 19. kvetna 2G1G 41 Všechna rešení, t rídení, rozdílové seznamy quicksort(S,Sorted) Neprázdný seznam S se rad'te tak, že vyběrtě nějaký prvěk X z S; rozděltě zbytěk S na dva sěznamy Small a Big tak, žě: v Big jsou větší prvky něž X a v Small jsou zbývající prvky koněc rěkurzě pro S=[] nap r . vyběrtě hlavu S split(X,Seznam,Small,Big) se rad'te Small do SortedSmall rekurzivne quicksortem se rad'te Big do SortedBig rekurzivne quicksortem sět ríděný sěznam vznikně spojěním SortědSmall a [X|SortědBig] append Hana Rudová, Logické programování I, 19. května 2010 42 Všěchna rěšění, t rídění, rozdílové sěznamy quicksort(S,Sorted) Něprázdný sěznam S sě rad'tě tak, žě & vyběrtě nějaký prvěk X z S; rozděltě zbytěk S na dva sěznamy Small a Big tak, žě: v Big jsou větší prvky něž X a v Small jsou zbývající prvky J5> sě rad'tě Small do SortědSmall & sě rad'tě Big do SortědBig & sět ríděný sěznam vznikně spojěním SortědSmall a [X|SortědBig] koněc rěkurzě pro S=[] nap r . vyběrtě hlavu S split(X,Seznam,Small,Big) rekurzivně quicksortem rekurzivně quicksortem append quicksort([],[]). quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Small, SortědSmall), quicksort(Big, SortědBig), append(SortedSmall, [X|SortedBig], Sorted). Hana Rudová, Logické programování I, 19. května 2010 42 Všěchna rěšění, t rídění, rozdílové sěznamy quicksort(S,Sorted) Neprázdný seznam S se rad'te tak, že & vyberte nejaký prvek X z S; rozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky J5> se rad'te Small do SortedSmall & se rad'te Big do SortedBig & set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] konec rekurze pro S=[] nap r . vyberte hlavu S split(X,Seznam,Small,Big) rekurzivne quicksortem rekurzivne quicksortem append quicksort([],[]). quicksort([X|T], Sorted) :- split(X, Tail, Small, Big), quicksort(Small, SortedSmall), quicksort(Big, SortedBig), append(SortedSmall, [X|SortedBig], Sorted). splitCX, [], [], []). split(X, [Y|T], [Y|Small], Big) :-X>Y, !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). Hana Rudová, Logické programování I, 19. kvetna 2010 42 Všechna rešení, t rídení, rozdílové seznamy DÚ:insertsortCS,Sorted) Neprázdný seznam S=[X|T] se rad'te tak, že & se rad'te telo T seznamu S JS> vložte hlavu X do se razeného tela tak, že výsledný seznam je zase se razený. Víme: výsledek po vložení X je celý se razený seznam. konec rekurze pro S=[] rekurzivne insertsortem insert(X,SortedT,Sorted) Hana Rudová, Logické programování I, 19. kvetna 2010 43 Všechna řešení, t rídení, rozdílové seznamy DÚ:insertsort(S,Sorted) Neprázdný seznam S=[X|T] se rad'te tak, že konec rekurze pro S=[] se rad'te telo T seznamu S vložte hlavu X do se razeného tela tak, že výsledný seznam je zase se razený. Víme: výsledek po vložení X je celý se razený seznam. rekurzivne insertsortem insert(X,SortedT,Sorted) insertsort([],[]). insertsort([X|T],Sorted) :-insertsort(T,SortedT), insert(X,SortedT,Sorted). insert(X,[Y|Sorted],[Y|Sorted1]) :-X > Y, !, insert(X,Sorted,Sorted1). insertCX,Sorted,[X|Sorted]). % seřazení těla % vložení X na vhodné místo Hana Rudová, Logické programování I, 19. kvetna 2010 43 Všechna rešení, t rídení, 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 A1 Z1 A2 Z2 1 \ i L2 \ L3 M ?- append( [1,2,3|Z1]-Z1, [4,5|Z2]-Z2, A1-[]). M append( A1-Z1, Z1-Z2, A1-Z2 ). L1 L2 L3 append( [1,2,3,4,5]-[4,5], [4,5]-[], Hana Růdová, Logické programování I, 19. kvetna 2010 44 [1,2,3,4,5]-[] ). Všechna rešení, t rídení, rozdílové seznamy reverseCSeznam, Opacny) % kvadratická složitost reverseC [], [] )■ reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). Hana Rudová, Logické programování I, 19. kvetna 2010 45 Všechna rešení, t rídení, rozdílové seznamy reverseCSeznam, Opacny) % kvadratická složitost reverseC [], [] ). reverse( [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverse( Seznam, Opacny ) :- reverse0( Seznam, ). reverse0( [], ). reverse0( [ H | T ], ) :- reverse0( T, ). Hana Rudová, Logické programování I, 19. kvetna 2010 45 Všechna rešení, t rídení, rozdílové seznamy reverse(Seznam, Opacny) % kvadratická složitost reverse( [], [] ). reverse( [ H | T ], Opacny ) :- reverse( T, OpacnyT ), append( OpacnyT, [ H ], Opacny ). % lineární složitost, rozdílové seznamy reverse( Seznam, Opacny ) :- reverse0( Seznam, Opacny-[] ). reverse0( [], S-S ). reverse0( [ H | T ], Opacny-OpacnyKonec ) :- reverse0( T, Opacny-[ H | OpacnyKonec] ). Hana Rudová, Logické programování I, 19. května 2010 45 Všěchna rěšění, t rídění, rozdílové sěznamy DÚ: palindrom(L) Napiště prědikát palindrom(Sěznam), ktěrý uspějě pokud sě Sěznam ctě stějně zězadu i zěp r ědu, p r . [a,b,c,b,a] něbo [12,15,1,1,15,12] Hana Rudová, Logické programování I, 19. května 2010 46 Všěchna rěšění, t rídění, rozdílové sěznamy DÚ: palindrom(L) Napište predikát palindrom(Seznam), který uspeje pokud se Seznam cte stejne zezadu i zep r edu, p r . [a,b,c,b,a] nebo [12,15,1,1,15,12] palindrom(Seznam) :- reverse(Seznam,Seznam). Hana Rudová, Logické programování I, 19. kvetna 2010 46 Všechna rešení, t rídení, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S se rad'te tak, že & vyberte nejaký prvek X z S; rozdeite zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky ií* se rad'te Small do SortedSmall JS* se rad'te Big do SortedBig set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksort1(S, ). quicksort1([], ). quicksort1([X|T], ) :- split(X, T, Small, Big), quicksort1(Small, ), quicksort!(Big, ). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, l9. kvetna 2GlG 47 Všechna rešení, t rídení, rozdílové seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S se rad'te tak, že & vyberte nejaký prvek X z S; rozdelte zbytek S na dva seznamy Small a Big tak, že: v Big jsou vetší prvky než X a v Small jsou zbývající prvky ií* se rad'te Small do SortedSmall JS* se rad'te Big do SortedBig set rídený seznam vznikne spojením SortedSmall a [X|SortedBig] quicksort(S, Sorted) :- quicksort1(S,Sorted-[]). quicksort1([],Z-Z). quicksort1([X|T], A1-Z2) :- split(X, T, Small, Big), quicksort1(Small, A1-[X|A2]), quicksort1(Big, A2-Z2). append(A1-A2, A2-Z2, A1-Z2). Hana Rudová, Logické programování I, 19. kvetna 2010 47 Všechna rešení, t rídení, rozdílové seznamy Vstup/výstup, databázové operace, rozklad termu Ctení ze process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, i seen see( StarySoubor ). repeat. repeat :- repeat. souboru % zjištění aktivního proudu % otevrení souboru Soubor % ctění termu Term % manipulace s termem % je konec souboru? % uzavrení souboru % aktivace puvodního proudu % vestavený predikát Hana Rudová, Logické programování I, 19. května 2010 49 Vstup/výstup, databázové opěracě, rozklad těrmu Predikáty pro vstup a výstup I ?- read(A), read( ahoj(B) ), read( [C,D] ). |: ahoj. ahoj( petre ). [ ahoj( 'Petrel' ), jdeme ]. A = ahoj, B = petre, C = ahoj('Petrel'), D = jdeme | ?- write(a(1)), write('.'), nl, write(a(2)), write('.'), nl. a(1). a(2). yes seeing, see, seen, read telling, tell, told, write -i* standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 19. kvetna 2010 50 Vstup/výstup, databázové operace, rozklad termu Příklad: vstup/výstup Napište predikát u1oz_do_souboru( Soubor ), který naCte nekolik fakt ze vstupu a uloží je do souboru Soubor. | ?- u1oz_do_souboru( 'soubor.pl' ). |: fakt(mirek, 18). |: fakt(pave1,4). |: yes | ?- consult(soubor). % consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, 0 msec % 376 bytes yes | ?- 1isting(fakt/2). % pozor:1isting/1 lze použít pouze pri consult/1 (ne u compile/1) fakt(mirek, 18). fakt(pave1, 4). yes Hana Rudová, Logické programování I, 19. kvetna 2010 51 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeing( StaryVstup ), telling( StaryVystup ), see( user ), tell( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, i ■ > seen, told, tell( StaryVystup ), see( StaryVstup ). process_term(end_of_file) :- !. process_term( Term ) :- write( Term ), write('.'), nl. Hana Rudová, Logické programování I, 19. května 2010 52 Vstup/výstup, databázové operace, rozklad termu Databázové operace & Databáze: specifikace množiny relací & Prologovský program: programová databáze, kde jsou relace specifikovány explicitne (fakty) i implicitne (pravidly) JS> Vestavené predikáty pro zmenu databáze behem provádení programu: assertzC Klauzule ) p r idání na konec retractC Klauzule ) smazání klauzule unifikovatelné s Klauzule JS> Pozor: retract/1 lze použít pouze pro dynamické klauzule (p r idané pomocí assert) a ne pro statické klauzule z programu -i* Pozor: nadmerné použití techto operací snižuje srozumitelnost programu assertC Klauzule ) assertaC Klauzule ) p r idání Klauzule do programu p r idání na zacátek Hana Rudová, Logické programování I, 19. kvetna 2010 53 Vstup/výstup, databázové operace, rozklad termu Databázové operace: príklad Napište predikát vytvor_program/0, který nacte nekolik klaůzůlí ze vstůpů a ůloží je do programové databáze. | ?- vytvor_program. |: fakt(pavel, 4). |: pravidlo(X,Y) :- fakt(X,Y). |: yes | ?- listing(fakt/2). fakt(pavel, 4). yes | ?- listing(pravidlo/2). pravidlo(A, B) :- fakt(A, B), yes | ?- clause( pravidlo(A,B), C). % clause/2 poůžitelný poůze pro dynamické klaůzůle C = fakt(A,B) ? yes Hana Růdová, Logické programování I, 19. kvetna 2010 54 Vstůp/výstůp, databázové operace, rozklad termů Databázové operace: implementace vytvor_program :- seeing( StaryVstup ), see( user ), repeat, read( Term ), uloz_term( Term ), Term == end_of_file, i ■ > seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assert( Term ). Hana Rudová, Logické programování I, 19. května 2010 55 Vstup/výstup, databázové opěracě, rozklad těrmu Konstrukce a dekompozice termu ü> 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 nekteré argumenty, pak je efektivnejší: functor( Term, Funktor, Arita ) functor( a(9,e), a, 2 ) functor(atom,atom,0) i functor(1,1,0) arg( 2, a(9,e), e) arg( N, Term, Argument ) Hana Rudová, Logické programování I, 19. kvetna 2010 56 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu -i* Term je seznam ([_|_]) => procházení seznamu a rozklad každého prvku seznamu JS> Term je složený (=../2, functor/3) => procházení seznamu argumentu a rozklad každého argumentu JS> Príklad: ground/1 uspeje, pokud v termu nejsou promenné; jinak neuspeje ground(Term) :- atomic(Term), !. % Term je atom nebo Číslo NEBO ground(Term) :- var(Term), !, fail. % Term není proměnná NEBO ground([H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani telo % neobsahují promenné NEBO ground(Term) :- Term =.. [ _Funktor | Argumenty ], % je Term složený ground( Argumenty ). % a jeho argumenty % neobsahují promenné ?- ground(s(2,[a(1,3),b,c],X)). ?- ground(s(2,[a(1,3),b,c])). Hana no Rudová, Logické programování I, 19. kvetna 2010 57 yes Vstup/výstup, databázové operace, rozklad termu subterm(S,T) Napište predikát subterm(S,T) pro termy S aT bez promenných, které uspejí, pokud je S podtermem termu T. Tj. musí platit alespon jedno z & podterm S je práve term T NEBO podterm S se nachází v hlave seznamu T NEBO & podterm S se nachází v tele seznamu T NEBO JS> T je složený term (compound/1), není seznam (T\=[_|_]), a S je podtermem nekterého argumentu T. pokud nepoužijeme (T\=[_|_]), pak dotaz :- subterm(a,[1]). cyklí! pokud nepoužijeme (compound/1), pak dotaz :- subterm(1,2). cyklí! | ?- subterm(sin(3),b(c,2,[1,b],sin(3),a)). yes Hana Rudová, Logické programování I, 19. kvetna 2010 58 Vstup/výstup, databázové operace, rozklad termu subtermCS,T) Napište predikát subtermCS,T) pro termy S aT bez promenných, které uspejí, pokud je S podtermem termu T. Tj. musí platit alespon jedno z & podterm S je práve term T NEBO podterm S se nachází v hlave seznamu T NEBO & podterm S se nachází v tele seznamu T NEBO JS> T je složený term (compound/1), není seznam CT\=[_|_]), a S je podtermem nekterého argumentu T. pokud nepoužijeme CT\=[_|_]), pak dotaz :- subtermCa,[1]). cyklí! pokud nepoužijeme Ccompound/1), pak dotaz :- subtermC1,2). cyklí! | ?- subtermCsinC3),bCc,2,[1,b],sinC3),a)). yes subtermCT,T) :- 1. subtermCS,[H|_]) :- subtermCS,H), 1. subtermCS,[_|T]) :- subtermCS.T),!. subtermCS,T) :- compoundCT), T\=[_|_], T=..[_|Argumenty], subtermCS,Argumenty). Hana Rudová, Logické programování I, 19. kvetna 2010 58 Vstup/výstup, databázové operace, rozklad termu same(A,B) Napište predikát same(A,B), který ůspeje, pokůd mají termy A a B stejnoů strůktůrů. Tj. můsí platit práve jedno z JS* A i B jsoů promenné NEBO pokůd je jeden z argůmentů promenná (drůhý ne), pak predikát neůspeje, NEBO JS* A i B jsoů atomic a ůnifikovatelné NEBO & A i B jsoů seznamy, pak jak jejich hlava tak jejich telo mají stejnoů strůktůrů NEBO JG* A i B jsoů složené termy se stejným fůnktorem a jejich argůmenty mají stejnoů strůktůrů | ?- same([1,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes Hana Růdová, Logické programování I, 19. kvetna 2010 59 Vstůp/výstůp, databázové operace, rozklad termů same(A,B) Napište predikát same(A,B), který uspeje, pokud mají termy A a B stejnou strukturu. Tj. musí platit práve jedno z JS* A i B jsou promenné NEBO pokud je jeden z argumentu promenná (druhý ne), pak predikát neuspeje, NEBO Jl> A i B jsou atomic a unifikovatelné NEBO & A i B jsou seznamy, pak jak jejich hlava tak jejich telo mají stejnou strukturu NEBO J5> A i B jsou složené termy se stejným funktorem a jejich argumenty mají stejnou strukturu | ?- same([1,3,sin(X),s(a,3)],[1,3,sin(X),s(a,3)]). yes same(A,B) :- var(A), var(B), 1. same(A,B) :- var(A), 1, fail. same(A,B) :- var(B), 1, fail. same(A,B) :- atomic(A), atomic(B), 1, A==B. same([HA|TA],[HB|TB]) :- 1, 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, 19. kvetna 2010 59 Vstup/výstup, databázové operace, rozklad termu D.Ú. unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B a provede zároven kontrolu výskytu. | ?- unify([Y,3,sin(a(3)),s(a,3)],[1,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes Hana Rudová, Logické programování I, 19. kvetna 2010 60 Vstup/výstup, databázové operace, rozklad termu D.Ú. unify(A,B) Napište predikát unify(A,B), který unifikuje termy A a B a provede zároven kontrolu výskytu. | ?- unify([Y,3,sin(a(3)),s(a,3)],[1,3,sin(X),s(a,3)]). X = a(3) Y = 1 yes unify(A,B) :- var(A), var(B), I, A=B. unify(A,B) :- var(A), I, not_occurs(A,B), A=B. unify(A,B) :- var(B), I, not_occurs(B,A), B=A. unify(A,B) :- atomic(A), atomic(B), I, A==B. unify([HA|TA],[HB|TB]) :- I, unify(HA,HB), unify(TA,TB). unify(A,B) :- A=..[FA|ArgA], B=..[FB|ArgB], FA==FB, unify(ArgA,ArgB). Hana Rudová, Logické programování I, 19. kvetna 2010 60 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Predikát not_occurs(A,B) uspeje, pokud se promenná A nevyskytuje v termu B. Tj. platí jedno z & B je atom nebo císlo NEBO JS> B je promenná různá od A NEBO & B je seznam a A se nevyskytuje ani v tele ani v hlave NEBO B je složený term a A se nevyskytuje v jeho argumentech Hana Rudová, Logické programování I, 19. kvetna 2010 61 Vstup/výstup, databázové operace, rozklad termu not_occurs(A,B) Prědikát not_occurs(A,B) uspějě, pokud sě proměnná A něvyskytujě v těrmu B. Tj. platí jědno z & B jě atom něbo císlo NEBO JS> B jě proměnná různá od A NEBO & B jě sěznam a A sě něvyskytujě ani v tělě ani v hlavě NEBO B jě složěný těrm a A sě něvyskytujě v jěho arguměntěch 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, 19. května 2010 61 Vstup/výstup, databázové opěracě, rozklad těrmu Logické programování s omezujícími podmínkami Algebrogram Pr i rad'te cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY M mzná písmena mají p r i razena různé cifry & S a M nejsou 0 Promenné: S,E,N,D,M,O,R,Y Domény: [1..9] pro S,M [0..9] pro E,N,D,O,R,Y 1 omezení pro nerovnost: all_distinct([S,E,N,D,M,O,R,Y]) 1 omezení pro rovnosti: 1000*S + 100*E + 10*N + D + 1000*M + 100*0 + 10*R + E #= 10000*M + 1000*0 + 100*N + 10*E + Y Hana Rudová, Logické programování I, 19. kvetna 2010 63 SEND + MORE M0NEY Omezující podmínky Jazykové prvky Naleznete r ešení pro algebrogram DONALD + GERALD = ROBERT & Struktura programu algebrogram( [D,O,N,A,L,D,G,E,R,B,T] ) :- domain(...), % domény proměnných all_distinct(...), ...#=..., % omezení laběling(...). % prohledávání stavového prostoru Knihovna pro CLP(FD) :- use_module(library(clpfd)). Domény promenných domain( Seznam, MinValue, MaxValue ) Omezení all_distinct( Seznam ) C Aritmetické omezení A*B + C #= D Procedura pro prohledávání stavového prostoru labeling([],Seznam) Hana Rudová, Logické programování I, 19. kvetna 2010 64 Omezující podmínky ř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), % omezení 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ání stavového prostoru labeling([],LD). Hana Růdová, Logické programování I, 19. kvetna 2010 65 Omezůjící podmínky Disjunktivní rozvrhování (unární zdroj) -í* cumu1ative([task(Start, Duration, End, 1, Id) | Tasks]) & Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nep r ekrývaly Hana Rudová, Logické programování I, 19. kvetna 2010 66 Omezující podmínky Disjunktivní rozvrhování (unární zdroj) cumulative([task(Start, Duration, End, 1, Id) | Tasks]) Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration) a identifikátorem (Id) tak, aby se nep r ekrývaly -fc p r íklad s konstantami: cumulative([task(0,2,2,1,1), task(3,1,4,1,2), task(5,1,6,1,3)]) Start, Duration, End, Id musí být doménové promenné s konecnými mezemi nebo celá císla Hana Rudová, Logické programování I, 19. kvetna 2010 66 Omezující podmínky Plánování Každý úkol má stanoven dobu trvání a nejd rívejší cas, kdy muže být zahájen. Naleznete startovní cas každého úkolu tak, aby se jednotlivé úkoly nep r ekrývaly. Úkolyjsou zadány následujícím zpusobem: % ukol(Id,Doba,MinStart,MaxKonec) ukol(1,4,8,70). ukol(2,2,7,60). ukol(5,4,1,45). ukol(6,2,4,35). ukol(9,1,8,40). ukol(10,7,4,50). ukol(3,1,2,25). ukol(7,8,2,25). ukol(11,5,2,50). ukol(4,6,5,55). ukol(8,5,0,20). ukol(12,2,0,35). ukol(13,3,30,60). ukol(14,5,15,70). ukol(15,4,10,40). Kostra r ešení: ukoly(Zacatky) :- domeny(l)koly,Zacatky,Tasks), cumulative(Tasks), labeling([],Zacatky). domeny(lkoly,Zacatky,Tasks) :- findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Ikoly), nastav_domeny(lkoly,Zacatky,Tasks). Hana Rudová, Logické programování I, 19. kvetna 2010 67 Omezující podmínky Plánování: výstup tiskni(Uko1y,Zacatky) :- priprav(Uko1y,Zacatky,Vstup), quicksort(Vstup,Vystup), nl, tiskni(Vystup). priprav([],[],[]). priprav([uko1(Id,Doba,MinStart,MaxKonec)|Uko1y], [Z|Zacatky], [uko1(Id,Doba,MinStart,MaxKonec,Z)|Vstup]) :-priprav(Uko1y,Zacatky,Vstup). tiskni([]) :- nl. tiskni([V|Vystup]) :- V=uko1(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, 19. kvetna 2010 68 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]), quicksort1(Big, A2-Z2). splitC_X, [], [], []). splitCX, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- splitCX, T, Small, Big). greaterCukolC_,_,_,_,Z1),ukolC_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 19. května 2010 69 Omezující podmínky Plánování a domény Napište predikát nastav_domeny/3, který na základe datové struktury [ukol(Id,Doba,MinStart,MaxKoněc)|Ukoly] vytvo rí doménové promenné Zacatky pro zacátky startovních dob úkolu a strukturu Tasks vhodnou pro omezení cumulativě/1, jejíž prvky jsou úlohy ve tvaru task(Zacatěk,Doba,Koněc,1,Id). % nastav_doměny(+Ukoly,-Zacatky,-Tasks) Hana Rudová, Logické programování I, 19. kvetna 2010 70 Omezující podmínky Plánování a domény Napište predikát nastav_domeny/3, který na základe datové strůktůry [ukol(Id,Doba,MinStart,MaxKonec)|Ukoly] vytvorí doménové proměnné Zacatky pro zacátky startovních dob úkolů a strůktůrů Tasks vhodnoů pro omezení cumulative/1, jejíž prvky jsoů úlohy ve tvarů task(Zacatek,Doba,Konec,1,Id). % nastav_domeny(+Ukoly,-Zacatky,-Tasks) nastav_domeny([],[],[]). nastav_domeny([ukol(Id,Doba,MinStart,MaxKonec)|Ukoly],[Z|Zacatky], [task(Z,Doba,K,1,Id)|Tasks]) :-MaxStart is MaxKonec-Doba, Z in MinStart-.MaxStart, K #= Z + Doba, nastav_domeny(Ukoly,Zacatky,Tasks). Hana Růdová, Logické programování I, 19. kvetna 2010 70 Omezůjící podmínky D.Ú. Plánování a precedence: precedence(Tasks) Rozši rtě r ěšění p r ědchozího problému tak, aby umožnovalo zahrnutí prěcěděncí, tj. jsou zadány dvojicě úloh A a B a musí platit, žě A má být rozvrhováno p r ěd B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,1). Pro urcění úlohy vTasks lzě použít nth1(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). Hana Rudová, Logické programování I, 19. května 2010 71 Omězující podmínky D.Ú. Plánování a precedence: precedence(Tasks) Rozši rte r ešení p r edchozího problému tak, aby umožnovalo zahrnutí precedencí, tj. jsou zadány dvojice úloh A a B a musí platit, že A má být rozvrhováno p r ed B. % prec(IdA,IdB) prec(8,7). prec(6,12). prec(2,1). Pro urcení úlohy vTasks lze použít nth1(N,Seznam,NtyPrvek) z knihovny :- use_module(library(lists)). precedence(Tasks) :- findall(prec(A,B),prec(A,B),P), omezeni_precedence(P,Tasks). omezeni_precedence([],_Tasks). omezeni_precedence([prec(A,B)|Prec],Tasks) :- nth1(A,Tasks,task(ZA,DA,_KA,1,A)), nth1(B,Tasks,task(ZB,_DB,_KB,1,B)), ZA + DA #=< ZB, omezeni_precedence(Prec,Tasks). Hana Rudová, Logické programování I, 19. kvetna 2010 71 Omezující podmínky Kumulativní rozvrhování & cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks], [limit(Limit)]) & Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nep r ekrývaly a aby celková kapacita zdroje nikdy nep r ekrocila Limit Hana Rudová, Logické programování I, 19. kvetna 2010 72 Omezující podmínky Kumulativní rozvrhování & cumu1ative([task(Start,Duration,End,Demand,TaskId) | Tasks], [limit(Limit)]) & Rozvržení úloh zadaných startovním a koncovým casem (Start,End), dobou trvání (nezáporné Duration), požadovanou kapacitou zdroje (Demand) a identifikátorem (Id) tak, aby se nepřekrývaly a aby celková kapacita zdroje nikdy neprekrocila Limit ií> Príklad s konstantami: cumu1ative([task(Q,4,4,1,1),task(1,2,3,2,2),task(3,3,6,2,3),task(4,2,6,1,4)],[1imit(3)]) 2 4 3 1 T Hana Rudová, Logické programování I, 19. května 2010 ^ 72 ^ ^ ° u Omezující podmínky Plánování a lidé Modifikujte rešení p redchozího problému tak, že & odstrante omezení na nep r ekrývání úkolu JS> p r idejte omezení umožnující r ešení každého úkolu zadaným Clovekem (každý Clovek může zpracovávat nejvýše tolik úkolů jako je jeho kapacita) % clovek(Id,Kapacita,IdUkoly) ... clovek Id zpracovává úkoly v seznamu IdUkoly clovek(1,2,[1,2,3,4,5]). clovek(2,1,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). Hana Rudová, Logické programování I, 19. kvetna 2010 73 Omezující podmínky Plánování a lidé Modifikujte rešení p redchozího problému tak, že & odstrante omezení na nep r ekrývání úkolu JS> p r idejte omezení umožnující r ešení každého úkolu zadaným clovekem (každý clovek může zpracovávat nejvýše tolik úkolu jako je jeho kapacita) % clovek(Id,Kapacita,Idlkoly) ... clovek Id zpracovává úkoly v seznamu Idlkoly clovek(1,2,[1,2,3,4,5]). clovek(2,1,[6,7,8,9,10]). clovek(3,2,[11,12,13,14,15]). lide(Tasks,Lide) :- findall(clovek(Kdo,Kapacita,lkoly),clovek(Kdo,Kapacita,lkoly), Lide), omezeni_lide(Lide,Tasks). omezeni_lide([],_Tasks). omezeni_lide([clovek(_Id,Kapacita,lkolyCloveka)|Lide],Tasks) :-omezeni_clovek(lkolyCloveka,Kapacita,Tasks), omezeni_lide(Lide,Tasks). Hana Rudová, Logické programování I, 19. kvetna 2010 73 Omezující podmínky Plánování a lidé (pokračování) Napište predikát oměZěni_clověk(UkolyClověka,Kapacita,Tasks), který ze seznamu Tasks vybere úlohy uníené seznamem UkolyClověka a pro takto vybrané úlohy sešle omezení cumulativě/2 s danou kapacitou cloveka Kapacita. Pro nalezení úlohy v Tasks lze použít nth1(N,Tasks,NtyPrvěk) z knihovny :- usě_modulě(library(lists)). Hana Rudová, Logické programování I, 19. kvetna 2010 74 Omezující podmínky Plánování a lidé (pokračování) Napište predikát omezeni_clovek(UkolyCloveka,Kapacita,Tasks), který ze seznamu Tasks vybere úlohy uníené seznamem UkolyCloveka a pro takto vybrané úlohy sešle omezení cumulative/2 s danou kapacitou cloveka Kapacita. Pro nalezení úlohy v Tasks lze použít nth1(N,Tasks,NtyPrvek) z knihovny :- use_module(library(lists)). omezeni_clovek(UkolyCloveka,Kapacita,Tasks) :- omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[]). omezeni_clovek([],Kapacita,_Tasks,TasksC) :- cumulative(TasksC,[limit(Kapacita)]). omezeni_clovek([U|UkolyCloveka],Kapacita,Tasks,TasksC) :- nth1(U,Tasks,TU), omezeni_clovek(UkolyCloveka,Kapacita,Tasks,[TU|TasksC]). Hana Rudová, Logické programování I, 19. kvetna 2010 74 Omezující podmínky Stromy, grafy Stromy Uzly stromu Tree jsou reprezentovány termy & tree(Left,Value,Right): Left a Right jsou opet stromy, Value je ohodnocení uzlu & leaf(Value): Value je ohodnoceni uzlu 6 Ji Príklad: / \ / \ / \ 2 8 / \ / 14 7 / \ 3 5 tree(tree(leaf(1), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) ) Hana Růdová, Logické programování I, 19. kvetna 2010 76 Stromy, grafy Stromy: hledáni prvku in(X,T) Prědikát in(X,T) uspějě, pokud sě prvěkX nachází vě stromu T. Prvěk X sě nachází vě stromě T, jěstližě C Xjě listěm stromu T, jinak lěaf(X) & Xjě ko rěn stromu T, jinak trěě(Lěft,X,Right) JS> X jě měnší něž ko rěn stromu T, pak sě nachází v lěvém podstromu T, jinak & X sě nachází v pravém podstromu T Hana Rudová, Logické programování I, 19. května 2010 77 Stromy, grafy Stromy: hledáni prvku in(X,T) Predikát in(X,T) uspeje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve strome T, jestliže C Xje listem stromu T, jinak leaf(X) & Xje ko ren stromu T, jinak tree(Left,X,Right) -í* X je menší než ko ren stromu T, pak se nachází v levém podstromu T, jinak & X se nachází v pravém podstromu T in(X, 1eaf(X)) :- 1. in(X, tree(_,X,_)) :- 1. in(X, tree(Left, Root, Right) ) :- XV, pak vznikne nový strom s korenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X pokud T=tree(L,V,_) a X>V, pak v novém strome L ponechej a X pridej doprava (rekurzivne) pokud T=tree(_,V,R) a XV, pak vznikne nový strom s ko renem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X pokud T=tree(L,V,_) a X>V, pak v novém strome L ponechej a X p r idej doprava (rekurzivne) pokud T=tree(_,V,R) a XV, !. add(leaf(V), X, tree(leaf(X),V,[]) ) :- !. Hana Rudová, Logické programování I, 19. kvetna 2010 78 Stromy, grafy Stromy: pridávání add(T,X,TWithX) Prvek X p r idej do stromu T jednou z následujících možností: pokud T = [], pak je nový strom leaf(X) & pokud T=leaf(V) a X>V, pak vznikne nový strom s ko renem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a X pokud T=tree(L,V,_) a X>V, pak v novém strome L ponechej a X p r idej doprava (rekurzivne) pokud T=tree(_,V,R) a XV, 1. add(lěaf(V), X, trěě(lěaf(X),V,[]) ) :- 1. add(trěě(L,V,R), X, trěě(L,V,R1)) :-X>V, 1, add(R,X,R1). add(trěě(L,V,R), X, trěě(L1,V,R)) :- add(L,X,L1). Hana Rudová, Logické programování I, 19. kvetna 2010 78 Stromy, grafy Procházení stromů Napiště prědikát travěrsě(Trěě, List), ktěrý projdě travěrsálně strom Trěě. Sěznam List pak obsahujě všěchny prvky tohoto stromu. Po radí prěorděr: nějprvě uzěl, pak lěvý podstrom, nakoněc 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]). (prěorděr) traverse(T,Pre):- 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,S1), t_pre(R,S1,S2). Použit princip rozdílových seznamů Hana Rudová, Logické programování I, 19. května 2010 6 / \ / \ /\ 28 / \ / \ 1479 /\ 35 % V=2 S=[1 4 3 5|S2] % S=[1|S1] % S1=[4 3 5|S2] 79 Stromy, grafy Procházení stromu traverse(T,Pre):- 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,S1), t_pre(R,S1,S2). 6 / \ / \ /\ 2 8 / \ / \ 14 7 9 /\ 3 5 % V=2, S=[1,4,3,5|S2] % S=[1|S1] % S1=[4,3,5|S2] Modifikůje algoritmůs tak, aby byly ůzly vypsány v poradí inorder (nejprve levý podstrom, pak ůzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] Hana Růdová, Logické programování I, 19. kvetna 2010 80 Stromy, grafy Procházení stromů traverse(T,Pre):- 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,S1), t_pre(R,S1,S2). 6 / \ / \ /\ 2 8 / \ / \ 14 7 9 /\ 3 5 % V=2, S=[1,4,3,5|S2] % S1=[4,3,5|S2] Modifikuje algoritmus tak, aby byly uzly vypsány v poradí 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|S1]), t_in(R,S1,S2). Hana Rudová, Logické programování I, 19. kvetna 2010 80 Stromy, grafy DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v po radí 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, 19. kvetna 2010 81 Stromy, grafy DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v poradí 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(1eaf(V),[V|S],S). / \ t_post(tree(L,V,R),S,S2):- 2 8 / \ / \ t_post(L,S,S1), 1 4 7 g t_post(R,S1,[V|S2]). / \ 3 5 Hana Rudová, Logické programování I, 19. kvetna 2010 81 Stromy, grafy Reprezentace grafu Reprezentace grafu: pole následníku uzlů Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovany) neohodnocený graf graf([2,3],[1,3],[1,2]). 1-- 2 \ | \| 3 ?- functor(Graf,graf,PocetUzlu). ?- arg(Uzel,Graf,Sousedi). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 5- -4 | | 6- -1--2--3 (Orientovany) ohodnocený graf [Soused-OhodnocenijSousedi] graf([2-1,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, 19. kvetna 2G1G 82 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(Uzel,Graf,Parents) pro procházení grafu Graf do hloubky z uzlu Uzel. Výsledkem je datová struktura Parents, která reprezentuje strom vzniklý pri prohledávání do hloubky (pro každý uzel stromu známe jeho rodiCe). Datová struktura pro rodiCe uzlu: pri reprezentaci rodiCu lze využít term s aritou odpovídající poCtu uzlu ií> iniciálne jsou argumentu termu volné promenné C- na záver je v N-tém argumentu uložen rodic N-tého uzlu (iniciální uzel oznacíme empty) graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1--2 \ | \| 3 1-- 2 \ \ 3 5- -4 | | 6- -1--2--3 U=2: rodic(2,empty,1) Hana Rudová, Logické programování I, 19. kvetna 2010 83 54 || 6--1--2-- 3 U=4: rodic(4, 1, 2, empty, 6, 1) Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu Uzel Vytvo ríme term pro rodice (všichni rodici jsou zatím volné promenné) JS> Uzel Uzel má prázdného rodice a má sousedy Sousedi Procházíme (rekurzivne) všechny sousedy v Sousedi dfs(Uzěl,Graf,Parěnts) :- functor(Graf,graf,Pocět), functor(Parěnts,rodicě,Pocět), arg(Uzěl,Parěnts,ěmpty), arg(Uzěl,Graf,Sousědi), prochazěj_sousědy(Sousědi,Uzěl,Graf,Parěnts). Hana Rudová, Logické programování I, 19. kvetna 2010 84 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházění sousědů uzlu Uzěl (pokud Uzěl němá sousědy, tj. Sousědi=[], koncímě) 1. Uzěl Vjě první sousěd 2. Zjistímě rodicě uzlu V ... pomocí arg(V,Parěnts,Rodic) 3. Pokud jsmě V jěště něprošli (tědy němá rodicě a platí var(Rodic)), tak (a) nastavímě rodicě uzlu V na Uzěl (b) rěkurzivně procházěj všěchny sousědy uzlu V 4. Procházěj zbývající sousědy uzlu Uzěl Hana Rudová, Logické programování I, 19. května 2010 85 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedu uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], koncíme) 1. Uzel Vje první soused 2. Zjistíme rodice uzlu V ... pomocí arg(V,Parents,Rodic) 3. Pokud jsme V ješte neprošli (tedy nemá rodice a platí var(Rodic)), tak (a) nastavíme rodice uzlu V na Uzel (b) rekurzivne procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodic), ( nonvar(Rodic) -> true ; Rodic = Uzel, arg(V,Graf,SousediV), prochazej_sousedy(SousediV,V,Graf,Parents) prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 19. kvetna 2010 85 Stromy, grafy DÚ: Procházení grafu do šírky Napište predikát bfs(U,G,P) pro procházení grafu G do šírky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý pri prohledávání grafu G do šírky (pro každý uzel stromu známe jeho rodice). graf([2,3],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1-- 2 \ I \I 3 1-- 2 5- -4 I I 6- -1--2--3 3 U=2: rodic(2,empty,2) 5- -4 | 6- -1--2-- 3 U=4: rodic(4, 1, 2, empty, 4, 1) Hana Rudová, Logické programování I, 19. kvetna 2010 86 Stromy, grafy Poděkování Průsviky ze cvicení byly pripraveny na základe materiálů drívejších cvicících tohoto predmetů. Speciální podekování patrí -í* Adriane Strejckové Další podklady byly pripraveny Jí* Alešem Horákem -í* Miroslavem Nepilem iS> Evoů Žáckovoů Hana Růdová, Logické programování I, 19. kvetna 2010 87 Podekovani