Aritmetika, seznamy, řez 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ů by ty neúspěšné případně špatné uspěly? ■ 1 + 2 =:= 2 + 1 ■ X = Y + 1 ■ X \== Y ■ X is Y + 1 ■ X =\= Y ■ X = Y ■ 1 + 2 =\= 1 - 2 ■ X == Y ■ 1 <= 2 ■ 1+1=2 ■ 1 =< 2 ■ 2 = 1+1 ■ sin(X) is sin(2) ■ 1+1=1+1 ■ sin(X) = sin(2+Y) ■ 1 + 1 is 1 + 1 ■ sin(X) =:= sin(2+Y) Hana Rudová, Logické programování I, 17. května 2007 3 Aritmetika, seznamy, řez Aritmetika Důležitý rozdíl ve vestavěných predikátech i s/2 vs. =/2 vs. =:=/2 ■ i s/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 ">="/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, 17. května 2007 2 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: ■ TastC X, S ) :- appendC _S1, [X], S). append([3,2] , [6], [3,2,6]). X=6, S=[3,2,6] ■ prefix( SI, S2 ) :- appendC SI, _S3, S2). DÚ: suffix(Sl,S2) ■ member( X, S ) :- appendC SI, [X|S2], S ). appendC[3,4,1], [2,6], [3,4,1,2,6]). X=2, S=[3,4,1,2,6] DÚ: adjacentCX.Y.S) ■ % sublistC+S,+ASB) sublistCS.ASB) :- appendC AS, B, ASB ), appendC A, S, AS ). POZOR na efektivitu, bez append lze často napsat efektivněji Hana Rudová, Logické programování I, 17. května 2007 4 Aritmetika, seznamy, řez Akumulátor a sum_l i st(S, Sum) ?- sum_1ist( [2,3,4], Sum ). bez akumulátoru: sum_list( [], 0 ). sum_list( [H|T], Sum ) :- sum_1ist( T, SumT ), Sum is H + SumT. s akumulátorem: sum_1ist( S, Sum ) :- sum_1ist( S, 0, Sum ). sum_1ist( [], Sum, Sum ). sum_list( [H|T], A, Sum ) :- AI is A + H, sunuli st( T, AI, Sum). Výpočet faktoriálu fact(N,F) s akumulátorem: fact( N, F ) :- fact ( n, 1, f ). fact( 1, F, F ) :- !. fact( N, A, F ) :- N > 1, Al i s N * A, Nl i s N - 1, fact( Nl, Al, F ). Hana Rudová, Logické programování I, 17. května 2007 Aritmetika, seznamy, řez 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) . -write(pl) . -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 X mod 3 write(cl) . write(c2). abs(X) < 10, write(dl). write(d2). I ?- X=l,r(X). rl X = 1 ? ; plr2 X = 1 ? ; alblr3 X = 1 ? ; no I ?- X=0,r(X). rl X = 0 ? ; plr2 X = 0 ? ; ala2p3r2 X = 0 ? ; r3 X = 0 ? ; no 6, rC I ?- X=3,r(X). rl X = 3 ? ; plr2 X = 3 ? ; alblc2dlp2r2 X = 3 ? ; d2p2r2 X = 3 ? ; r3 X = 3 ? ; no Hana Rudová, Logické programování I, 17. května 2007 I ?- x= rl X = -6 ? ; plr2 X = -6 ? ; alb2cldlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; c2dlp2r2 X = -6 ? ; d2p2r2 X = -6 ? ; r3 X = -6 ? ; no Aritmetika, seznamy, řez Hana Rudová, Logické programování I, 17. května 2007 Aritmetika, seznamy, řez 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 C rl). -p(X),write(r2) . -write(r3). -write(pl). -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 X mod 3 0, write(cl). 0, write(c2). abs(X) < 10, write(dl). write(d2). Prozkoumejte trasy výpočtu a navracet např. pomocí následujících dotazů (vždy : středníkem vyžádejte navracení): (1) X=l,r(X). (3) X=0,r(X). (2) X=3,r(X). (4) X= -6,r(X). Hana Rudová, Logické programování I, 17. května 2007 řez v predikátu p/1 neovlivní alternativ predikátu r/1 dokud nebyl proveden řez, alternativ predikátu a/l se uplatňují, př. neúspěc b/l v dotazu (3) při neúspěchu cíle za řezem se výpočí navrací až k volající proceduře r/1, viz (1 alternativy vzniklé po provedení řezu s zachovávají - další možnosti predikát c/1 viz (2) a (4) Aritmetika, 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, 17. května 2007 9 Aritmetika, 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]). memlCH,[H|_]). memlCH,[_|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é ■ 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, 17. května 2007 10 Aritmetika, seznamy, řez Seznamy: i nte rsecti on (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 Třídění, rozdílové seznamy Hana Rudová, Logické programování I, 17. května 2007 Aritmetika, seznamy, řez bubblesort(S,Sorted) Seznam S setřiď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; a setřiďte SI ■ pokud neexistuje žádný takový pár sousedních prvků X a Y, pak je S setříděný seznam swap([X,Y|Rest],[Y,X|Restl]) :- X>Y. % nebo obecněji X@>Y pomoci gt(X,Y) swap([Z|Rest],[Z|Restl]) :- swapCRest,Restl) . bubblesortCS,Sorted) :- swap (S,S1), ! , bubblesortCSl, Sorted). bubblesortCSorted,Sorted) . Hana Rudová, Logické programování I, 17. května 2007 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 A1 Z1 A2 Z2 L1 L2 \ -=»- L3 ?- append( [1,2,3|Zl]-Zl, [4,5|Z2]-Z2, S ). append( Al-Zl, Z1-Z2, A1-Z2 ). LI L2 L3 Hana Rudová, Logické programování I, 17. května 2007 Třídění, rozdílové seznamy qui cksort(S,Sorted) Neprázdný seznam S setřiďte tak, že ■ smažte 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 ■ setřiďte Small do SortedSmall ■ setřiďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksort([] , []) . quicksort([X|T], Sorted) + ošetření případu, kdy S je prázdný seznam splitCX, Tail, Small, Big), quicksortCSmall, SortedSmall), quicksort(Big, SortedBig), appendCSortedSmall, [XISortedBig], Sorted). splitCX, [], [], []). splitCX, [YIT], [Y|Small], Big) splitCX, [YIT], Small, [Y|Big]) Hana Rudová, Logické programování I, 17. května 2007 X>Y, !, splitCX, T, Small, Big). splitCX, T, Small, Big). 14 Třídění, rozdílové seznamy reverse(Seznam, Opacny) reverseC [], [] ) • reverseC [ H | T ], Opacny ) :- reverseC T, OpacnyT ), appendC OpacnyT, [ H ], Opacny ). reverseC Seznam, Opacny ) :- reverseOC Seznam, Opacny-[]). reverseOC [] , S-S ) . reverseOC [ H | T ], Opacny-OpacnyKonec ) :- reverseOC T, Opacny-[ H | OpacnyKonec] ). reverseC Seznam, Opacny ) :- reverseOC Seznam, [], Opacny ). reverseOC □ , S, S ). reverseOC [ H | T ], A, Opacny ) :- reverseOC T, [ H | A ], Opacny ). Hana Rudová, Logickě programování I, 17. května 2007 16 Třídění, rozdílově seznamy quicksort pomocí rozdílových seznamů Neprázdný seznam S setřiďte tak, že ■ smažte 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 ■ setřiďte Small do SortedSmall ■ setřiďte Big do SortedBig ■ setříděný seznam vznikne spojením SortedSmall a [XISortedBig] quicksort(S, Sorted) :- quicksortl(S,Sorted-[]). quicksortl([] ,Z-Z) . quicksortl([X|T], A1-Z2) :- split(X, T, Small, Big), quicksortlCSmall, A1-[X|A2]), quicksortl(Big, A2-Z2). append(Al-Zl, Z1-Z2, A1-Z2). Hana Rudová, Logické programování I, 17. května 2007 Třídění, rozdílové seznamy Čtení ze souboru process_file( Soubor ) :- seeing( StarySoubor ), see( Soubor ), repeat, read( Term ), process_term( Term ), Term == end_of_file, % zjištění aktivního proudu % otevření souboru Soubor % čtení termu Term % manipulace s termem % je konec souboru? seen, see( StarySoubor ). % uzavření souboru % aktivace původního proudu repeat. repeat repeat. % vestavěný predikát Hana Rudová, Logické programování I, 17. května 2007 Vstup/výstup, databázové operace, rozklad termu 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 I ?- wn'te(a(l)), wn'te('.'), nl, write(a(2)), wn'te('.'), ni a(l). a(2). yes ■ seeing, see, seen, read ■ telling, tell, told, write ■ standardní vstupní a výstupní stream: user Hana Rudová, Logické programování I, 17. května 2007 20 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. I ?- uloz_do_souboru( 'soubor.pl ' ). I: fakt(mi rek, 18). I: faktCpavel,4). I : yes I ?- [soubor]. % Consulting /home/hanka/soubor.pl... % consulted /home/hanka/soubor.pl in module user, O msec % 376 bytes yes I ?- 1 i sting(fakt/2). fakt(mi rek, 18). faktCpavel, 4). yes Hana Rudová, Logické programování I, 17. května 2007 21 Vstup/výstup, databázové operace, rozklad termu Implementace: vstup/výstup uloz_do_souboru( Soubor ) :-seeingC StaryVstup ), tellingC StaryVystup ), see( user ) , tel 1 C 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), writeC'.'), nl . Hana Rudová, Logické programování I, 17. května 2007 22 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 explicitně (fakty) i implicitně (pravidly) Vestavěné predikáty pro změnu databáze během provádění programu: assert( Klauzule ) asserta( Klauzule ) assertz( Klauzule ) retract( Klauzule ) přidání Klauzule do programu přidání na začátek přidání na konec smazání klauzule unifikovatelné s Klauzule Pozor: nadměrné použití těchto operací snižuje srozumitelnost programu Hana Rudová, Logické programování I, 17. května 2007 Vstup/výstup, databázové operace, rozklad termu Databázové operace: příklad Napište predikát vytvor_program/0, který načte několik klauzulí ze vstupu a uloží je do programové databáze. I ?- vytvor_program. faktCpavel, 4). pravidlo(X.Y) : fakt(X.Y). yes I ?- 1 i sting(fakt/2). faktCpavel, 4). yes I ?- listingCpravidlo/2). pravidloCA, B) :- fakt(A, B). yes I ?- clauseC pravidloCA,B), C). C = fakt(A.B) ? yes Hana Rudová, Logické programování I, 17. května 2007 Vstup/výstup, databázové operace, rozklad termu Databázové operace: implementace Konstrukce a dekompozice termu vytvo r_p rog ram :- seeingC StaryVstup ), see( user ), repeat, read C Term ), uloz_term( Term ) , Term == end_of_file, i seen, see( StaryVstup ). uloz_term( end_of_file ) :- !. uloz_term( Term ) :- assertC Term ). Hana Rudová, Logické programování I, 17. května 2007 25 Vstup/výstup, databázové operace, rozklad termu Rekurzivní rozklad termu ■ Term je proměnná (var/l), atom nebo číslo (atomic/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 ground(Term) :- atomic(Term), !. % Term je atom nebo číslo NEBO ground(Term) :- var(Term), !, fail. % Term není proměnná NEBO groundC[H|T]) :- !, ground(H), ground(T). % Term je seznam a ani hlava ani těl % neobsahují proměnné NEBO ground(Term) :- Term =.. [ _Funktor | Argumenty ], % je Term složený groundC Argumenty ). % a jeho argumenty % neobsahují 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, 1 7. května 2007 27 Vstup/výstup, databázové operace, rozklad 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 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 ) argC 2, a(9,e), e) Hana Rudová, Logické programování I, 17. května 2007 26 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 ■ subterm S je právě term T NEBO ■ subterm S se nachází v hlavě seznamu T NEBO ■ subterm S se nachází v těle seznamu T NEBO ■ Tje složený term (compound/1), není seznam (T\=[_|_]) , a S je podtermem některého argumentu T. | ?- subterm(sin(3),b(c,2,[1,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, 17. května 2007 28 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 atomic a unifikovatelné NEBO ■ A i B jsou seznamy, pak jak jejich hlava tak jejich tělo mají stejnou strukturu NEBO ■ 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)],[l,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, 1 7. května 2007 29 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á pd A NEBO ■ 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). 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 unify(A,B) :- var(A), var(B), !, A=B. unify(A,B) :- var(A), !, not_occurs(A,B), A=B. unify(A,B) :- var(B), !, not_occurs(B,A), B=A. unify(A,B) :- atomic(A), atomic(B), !, A==B. unify([HA|TA],[HB|TB]) :- !, 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, 17. května 2007 Vstup/výstup, databázové operace, rozklad termu Logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 17. května 2007 31 Vstup/výstup, databázové operace, rozklad termu Algebrogram Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platilo: SEND + MORE MONEY ■ různá písmena mají přiřazena různé cifry ■ S a M nejsou 0 Proměnné: S,E,N,D,M,0,R,Y Domény: [1 ..9] pro S,M [0..9] pro E,N,D,0,R,Y 1 omezení pro nerovnost: a"l"l_distinct([S, E, N,D,M ,0, 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 SEND + MORE MONEY Hana Rudová, Logické programování I, 17. května 2007 Omezující podmínky Algebrogram: řešení :- use_module(library(clpfd)) . donald(LD):- % domény LD=[D,0,N,A,L,C,E,R,B,T] , domain(LD,0,9), domain([D,C,R],1,9) , % omezeni a"l"l_distinct(l_D) , 100000*D + 10000*0 + 1000*N + 100*A + 10*L + D + 100000*C + 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, 17. května 2007 Omezující podmínky Jazykové prvky Nalezněte řešení pro algebrogram D0NALD + GERALD = R0BERT ■ Struktura programu algebrogramC Cifry ) :-domain(...), constrai nts(...), labelingC...). ■ Knihovna pro CLP(FD) ■ Domény proměnných ■ Omezení ■ Aritmetické omezení :- use_module(library(clpfd)). domain C Seznam, MinValue, MaxValue ) all_distinct( Seznam ) A* B + C #= D Procedura pro prohledávání stavového prostoru labeling([], [xi, X2, X3]) Hana Rudová, Logické programování I, 17. května 2007 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. Úkolyjsou zadány následujícím způsobem: % ukol(Id,Doba,MinStart,MaxKonec) ukol(l,4,8,70). ukol(2,2,7,60) . ukol(3,1,2,25). ukol(6,2,4,35). ukol(7,8,2,25). ukol(10,7,4,50). ukol(11,5,2,50). ukol(14,5,15,70). ukol(15,4,10,40). ukol(5,4,1,45). ukol(9,l,8,40). ukol(13,3,30,60). ukol(4,6,5,55). ukol(8,5,0,20). ukol(12,2,0,35). Kostra řešení: ukoly(Zacatky) domeny(Ukoly,Začátky,Doby) , se rial i zed(Začátky,Doby), labeling([],Začátky). domény(Ukoly,Začátky,Doby) findall(ukol(Id,Doba,MinStart,MaxKonec), ukol(Id,Doba,MinStart,MaxKonec), Úkoly), nastav_domeny(Úkoly,Začátky,Doby). Hana Rudová, Logické programování I, 17. května 2007 Omezující podmínky Plánování: výstup Plánování: výstup II tiskni(Úkoly,Začátky) :- priprav(Ukoly,Začátky,Vstup), quicksort(Vstup,Vystup), nl , tiskni(Vystup). priprav([] , [] , []) . při prav([ukol(Id,Doba,Mi nStart.MaxKonec)|Úkoly], [Z|Začátky], [ukol(Id,Doba,MinStart,MaxKonec,Z)IVstup]) :-priprav(Ukoly,Začátky,Vstup). tiskni ([]) :- nl . tiskni C[V|Vystup]) :- V=ukol(Id,Doba,MinStart,MaxKonec,Z), K i s Z+Doba, formatC ~d: \t~d..~d \t(~d: ~d..~d)\n', [Id,Z,K,Doba,MinStart,MaxKonec] ), ti skni(Vystup). Hana Rudová, Logické programování I, 17. května 2007 37 Omezující podmínky 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). split(_X, [], [], []). splitCX, [Y|T], [Y|Small], Big) :- greater(X,Y), !, split(X, T, Small, Big). splitCX, [Y|T], Small, [Y|Big]) :- split(X, T, Small, Big). greater(ukol(_,_,_,_,Zl),ukol(_,_,_,_,Z2)) :- Z1>Z2. Hana Rudová, Logické programování I, 17. května 2007 38 Omezující podmínky Plánování a domény Plánování a precedence 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(Úkoly,Začátky,Doby). 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)|Prec],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, 17. května 2007 Omezující podmínky Hana Rudová, Logické programování I, 17. května 2007 Omezující podmínky Plánování a lidé Modifikujte řešení předchozího problému tak, že ■ 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) ... clovek 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]). ]i de(Začátky,Doby,Lide) :- findall(clovek(Kdo,IdUkoly) ,clovek(Kdo,IdUkoly) , Lide) , omezeni_]i de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_]i de([Clovek|Lide],Začátky,Doby) :- Clovek=clovek(_Id,IdUkoly), omezeni_clovek(IdUkoly,Začátky,Doby), omezeni_1i de(Li de,Začátky,Doby). Hana Rudová, Logické programování I, 17. května 2007 41 Omezující podmínky Plánování a lidé (pokračování) omezeni_clovek(IdUkoly,Začátky,Doby) :- omezeni_clovek(IdUkoly,Začátky,Doby,[],[]). % omezeni_clovek(IdUkoly,Začátky,Doby,ClovekZ,ClovekD) 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, 17. května 2007 42 Omezující podmínky li de(Začátky,Doby,Li de) :- findal1(clovek(Kdo,Kapacita,IdUkoly),clovek(Kdo.Kapacita,IdUkoly), Lide omezeni_1i de(Li de,Začátky,Doby). omezeni_lide([],_Zacatky,_Doby). omezeni_1i de([clovek(_Id,Kapacita,IdUkoly)|Lide],Začátky,Doby) :-omezeni_clovek(IdUkoly,Kapaci ta,Začátky,Doby), omezeni_1i de(Li de,Začátky,Doby). omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby) : - omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[],[]). omezeni_clovek([],Kapaci ta,_Zacatky,_Doby,ClovekZ,ClovekD) :- 1ength(ClovekZ,Delka), 1 i stOfl(Delka,Li stOf1), cumulative(ClovekZ,ClovekD,Li stOf1,Kapacita). omezeni_clovek([U|IdUkoly],Kapacita,Začátky,Doby,ClovekZ,ClovekD) :- nth(U,Začátky,Z), nth(U,Doby,D), omezeni_clovek(IdUkoly,Kapacita,Začátky,Doby,[ZIClovekZ],[D|C1ovekD]). listOf1(0,[]) :- !. list0fl(D,[1|L]) :- Dl is D-l, 1 istOf1(D1,L). Všechna řešení, stromy, grafy Hana Rudová, Logické programování I, 17. května 2007 Omezující podmínky Všechna řešení % zOmeno, Při jmen i , Sex, Vek, Prače, Fi rma) z(petr,novak.m,30,skladni k,škoda). z(pavel,novy,m,40.mechani k,škoda). z(rošti slav,1ucensky,m,50,techni k,škoda). z(alena,veselá,z,25,sekretářka,škoda). zCjana,dankova,z,35,asi stentka,škoda). z(lenka,meri nska,z,35,ucetni,škoda). z(roman,maly,m,35.manažer,cs). z(alena,novotna,z,40,učitelka,zs_stara). z(david,novy,z,30,učitel,zs_stara). zCpetra,špičková,z,45,ředitelka,zs_stara). ■ Najděte jméno a příjmení všech lidí. ?- findall Qmeno-Pri jmeni , zQmeno, Pri jmeni ,_,_,_,_), L) . ?- bagofC Jmeno-Prijmeni, [S,V,Pr,F] A zQmeno, Pri jmeni, S, V, Pr, F) , L ). ?- bagofC Jmeno-Prijmeni, [V,Pr,F] A zQmeno, Pri jmeni , S, V, Pr, F) , L ). ■ Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs ?- findallC c(J,P,Firma), ( zQ , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ), ?- bagofC >P, [P,S,V,Pr]A(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J, [P,S,V,Pr]A(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). Hana Rudová, Logické programování I, 17. května 2007 45 Všechna řešení, stromy, grafy 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í učitelů 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(Prijmeni, z(_,Prijmeni,z,_,_,_),L). 2 . f i ndal 1 (Jméno-Pri jmeni , (zQmeno, Pri jmeni ,_, Vek,_,_) ,Vek>30) , L) . 3. setof (P-J , [S,V,Pr, F]AzQ ,P,S,V,Pr, F) , L). 4. fi ndal1(Prijmeni,(z(_,PrijmeniP,zs_stara),(P=ucitel;P=ucitelka)),L). 5. findall(b(]l-P,]2-P),( zQl.P,_,_,_,_),zQ2,P,_,_,_,_), J1@l. Hana Rudová, Logické programování I, 17. května 2007 46 Všechna řešení, stromy, grafy Stromy Uzly stromu Tree jsou reprezentovány termy ■ 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(1), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8,[]) ) Hana Rudová, Logické programování I, 17. května 2007 47 Všechna řešení, stromy, grafy Stromy: hledáni prvku in(X,Tree) Prvek X se nachází ve stromě T, jestliže ■ Xje listem stromu T, jinak leaf(X) ■ Xje kořen stromu T, jinak tree(i_eft,x,Right) ■ Xje 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 leaf(X) vpravo (vlevo je []) T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava T=tree(_,_,R) a XV, !, Tl=tree([],V,leaf(X)) ; XV, !, L1=L, add(R,X,Rl) ; X