Hodnocení předmětu IBO 1 3 Logické programování I Hana Rudová jaro 2012 Základní informace Přednáška: účast není povinná, nicméně ... Cvičení: účast povinná ■ individuální doplňující příklady za zmeškaná cvičení ■ nelze při vysoké neúčasti na cvičení ■ skupina 01, sudý pátek, první cvičení 24.února ■ skupina 02, lichý pátek, první cvičení 2.března Web předmětu: interaktivní osnova v ISu ■ průsvitky dostupné postupně v průběhu semestru ■ harmonogram výuky, předběžný obsah výuky pro jednotlivé přednášky během semestru ■ elektronicky dostupné materiály ■ informace o zápočtových projektech Hana Rudová, Logické programování I, 29. února 2012 3 Organizace předmětu ■ Průběžná písemná práce: až 30 bodů (základy programování v Prologu) ■ pro každého jediný termín: 22.března ■ alternativní termín pouze v případech závažných důvodů pro neúčast ■ vzor písemky na webu předmětu ■ Závěrečná písemná práce: až 1 50 bodů ■ vzor písemky na webu předmětu ■ opravný termín možnýjako ústní zkouška ■ Zápočtový projekt: celkem až 40 bodů ■ Hodnocení: součet bodů za projekt a za obě písemky ■ známka A za cca 1 75 bodů, známka F za cca 11 0 bodů ■ známka bude zapsána pouze těm, kteří dostanou zápočet za projekt ■ Ukončení předmětu zápočtem: zápočet udělen za zápočtový projekt Hana Rudová, Logické programování I, 29. února 2012 2 Organizace předmětu Rámcový obsah předmětu Obsah přednášky ■ základy programování v jazyce Prolog ■ teorie logického programováni ■ logické programování s omezujícími podmínkami ■ implementace logického programováni Obsah cvičení ■ zaměřeno na praktické aspekty, u počítačů ■ programování v Prologu ■ logické programování ■ DCC gramatiky ■ logické programování s omezujícími podmínkami Hana Rudová, Logické programování I, 29. února 2012 4 Organizace předmětu Literatura Bratko, I. Prolog Programming for Artificial Intelligence. Addison-Wesley, 2001. ■ prezenčně v knihovně Clocksin, W. F. - Mellish, Ch. S. Programming in Prolog. Springer, 1 994. Sterling, L. - Shapiro, E. Y. The art of Prolog : advanced programming techniques. MIT Press, 1 987. Nerode, A. - Shore, R. A. Logic for applications. Springer-Verlag, 1 993. ■ prezenčně v knihovně Dechter, R. Constraint Processing. Morgan Kaufmann Publishers, 2003. ■ prezenčně v knihovně - Elektronicky dostupné materiály (viz web předmětu) Hana Rudová, Logické programování I, 29. února 2012 5 Organizace předmětu Zápočtové projekty Týmová práce na projektech, až 3 řešitelé ■ zápočtové projekty dostupné přes web předmětu Podrobné pokyny k zápočtovým projektům na webu předmětu ■ bodování, obsah předběžné zprávy a projektu ■ typ projektu: LP, CLP, DCC ■ CLP a LP: Adriana Strejčkova ■ DCC: Miloš Jakubíček, Vojtěch Kovář Předběžná zpráva ■ podrobné zadání ■ vjakém rozsahu chcete úlohu řešit ■ které vstupní informace bude program používat a co bude výstupem programu ■ scénáře použití programu (tj. ukázky dvojic konkrétních vstupů a výstupů) Průběžná písemná práce ■ Pro každého jediný termín 22. března ■ Alternativní termín pouze v závažných důvodech pro neúčast ■ Celkem až 30 bodů (1 50 závěrečná písemka, 40 projekt) ■ 3 příklady, 40 minut ■ Napsat zadaný predikát, porovnat chování programů ■ Obsah: první čtyři přednášky a první dvě cvičení ■ Oblasti, kterých se budou příklady zejména týkat ■ unifikace ■ seznamy ■ backtracking ■ optimalizace posledního volání ■ řez ■ aritmetika ■ Ukázka průběžné písemné práce na webu Hana Rudová, Logické programování I, 29. února 2012 6 Organizace předmětu Časový harmonogram k projektům ■ Zveřejnění zadání (většiny) projektů: 27. února ■ Zahájení registrace řešitelů projektu: 7. března, 19:00 ■ Předběžná analýza řešeného problému: 13. dubna ■ Termín pro odevzdání projektů: 18. května ■ Předvádění projektů (po registraci): 21.května - 22.června Hana Rudová, Logické programování I, 29. února 2012 7 Organizace předmětu Hana Rudová, Logické programování I, 29. února 2012 8 Organizace předmětu Software: SICStus Prolog Doporučovaná implementace Prologu Dokumentace: http://www.fi.muni.cz/~hanka/sicstus/doc/html Komerční produkt ■ licence pro instalace na domácí počítače studentů Nové IDE pro SICStus Prolog SPIDER ■ dostupné až od verze SICStus 4.1.3 ■ http://www.si cs.se/si cstus/spi der ■ používá Eclipse SDK Podrobné informace dostupné přes web předmětu ■ stažení SICStus Prologu (sw + licenční klíče) ■ pokyny k instalaci (SICStus Prolog, Eclipse, Spider) Hana Rudová, Logické programování I, 29. února 201 2 Organizace předmětu Úvod do Prologu SICStus IDE SPIDER 3 SICStus Debugging - My Prolog Proj«Vmy_mod e.pro - EcíipíE SDK File Edit SICStus Source Navigate Search Project Run Favorites Window Hel j es* h iBj i * # fr-O-q* ' juř* i é - 5i » ^> * ' »- b ♦ SJCSu.Debu...! " & Debug :: % D> 1. ■ 4 • IS-fJ j>^|.tv=Q' * Prolog Top-level Configuration (SJCStus Uu ch Configuration Typel] Munt Vdw 3 Prolog Target 1«. "11 cl = «11: iutfK[[),.7SSl,cl,_iaiO) = my.predlLlälO) ♦ X .isio »3 Prolog Top-level Process • my.module.pro :■: □ "í Outline . : JaB s = □ £ i- üse_nodule(libEar«iliat3>F [pq s c fix/ S, í irarns about imp soffix/2 1 inCegľaeed help ( 1 SufdsÜList, ?Suffin) s true when Lisi and Suffix are lists and Suffix is a suffi* of List, It terminsts only if Lis arns axeut Mining d^laraii n, ^ut Otília axtotia«! p my_pred2(S, Jfg) í-1 «trn about non-trivia ??? predekCrobert,P) --> ??? Hana Rudová, Logické programování I, 29. února 201 2 1. P=anna, 2. Potomek=ji rka P=petr, 3. P=jirka Úvod do Prologu Syntaxe a význam Prologovských programu Syntaxe Prologovských programů ■ Typy objektů jsou rozpoznávány podle syntaxe ■ Atom ■ řetězce písmen, čísel, „_" začínající malým písmenem: pavel , pavel_novak, x25 ■ řetězce speciálních znaků: <-->, ====> ■ řetězce v apostrofech: 'Pavel', 'Pavel Novák' ■ Celá a reálná čísla: 0, -1056, 0.35 ■ Proměnná ■ řetězce písmen, čísel, „_" začínající velkým písmenem nebo „_" ■ anonymní proměnná: ma_diteCX) :- rodicC X, _ ). ■ hodnotu anonymní proměnné Prolog na dotaz nevrací: ?- rodicC X, _ ) ■ lexikální rozsah proměnné je pouze jedna klauzule: prvni CX,X,X). prvni CX,X,_). Hana Rudová, Logické programování 1,29. února 201 2 24 Syntaxe a význam Prologovských programů Termy ■ Term - datové objekty v Prologu: datum( 1, kveten, 2003 ) ■ funktor: datum ■ argumenty: 1, kveten, 2003 ■ arita - počet argumentů: 3 ■ Všechny strukturované objekty v Prologu jsou stromy ■ trojuhelnikC bod(4,2), bod(6,4), bod(7,l) ) ■ Hlavní funktor termu - funktor v kořenu stromu odpovídající termu ■ trojuhelnikje hlavní funktor v trojuhelnikC bod(4,2), bod(6,4), bod(7,l) ) Hana Rudová, Logické programování I, 29. února 2012 25 Syntaxe a význam Prologovských programů Unifikace Termy S a T jsou unifikovatelné, jestliže 1. SaTjsou konstanty a tyto konstanty jsou identické; 2. S je proměnná a T cokoliv jiného - S je instanciována na T; Tje proměnná a S cokoliv jiného - Tje instanciována na S 3. S a T jsou termy ■ S a T mají stejný funktor a aritu a ■ všechny jejich odpovídající argumenty jsou unifikovatelné ■ výsledná substituce je určena unifikací argumentů Příklady: k = k ... yes, kl = k2 ... no, A = k(2,3) ... yes, k(s,a,1(1)) = A ... yes s(sss(2),B,ss(2)) = s(sss(2),4,ss(2),s(l))... no s(sssCA),4,ss(3)) = s(sss(2),4,ss(A))... no s(sss(A),4,ss(C)) = s(sss(t(B)),4,ss(A))... A=t(B),C=t(B)... yes Hana Rudová, Logické programování I, 29. února 2012 27 Syntaxe a význam Prologovských programů Unifikace ■ Termy jsou unifikovatelné, jestliže ■ jsou identické nebo ■ proměnné v obou termech mohou být instanciovány tak, že termy jsou po substituci identické ■ datumC Dl, Ml, 2003 ) = datumC 1, M2, Y2) operátor = Dl = 1, Ml = M2, Y2 = 2003 ■ Hledáme nejobecnější unifikátor (most generál unifler (MGU) ■ jiné instanciace? ... Dl = 1, Ml = 5 , Y2 = 2003 ... není MCU ■ ?- datumC Dl, Ml, 2003 ) = datumC 1, M2, Y2), Dl = Ml. ■ Test výskytu (occurs check) ?- X=f(X). x = fCfCfCfCfCfCfCfCfCfC ..)))))))))) Hana Rudová, Logické programování I, 29. února 201 2 26 Syntaxe a význam Prologovských programů Deklarativní a procedurální význam programů ■ p :- q, r. ■ Deklarativní: Co je výstupem programu? ■ p je pravdivé, jestliže q a r jsou pravdivé ■ Z q a r plyne p => význam mají logické relace ■ Procedurální: Jak vypočítáme výstup programu? ■ p vyřešíme tak, že nejprve vyřešíme q a pak r => kromě logických relací je významné i pořadí cílů ■ výstup ■ indikátor yes/no určující, zda byly cíle splněny ■ instanciace proměnných v případě splnění cílů Hana Rudová, Logické programování I, 29. února 201 2 28 Syntaxe a význam Prologovských programů Deklarativní význam programu Konjunce "," vs. disjunkce ";" cílů Instance klauzule: proměnné v klauzuli jsou substituovány termem ma_dite(X) :- rodic( X, Y ). ma_dite(petr) :- rodic( petr, Z ). % klauzule % instance klauzule Máme-li program a cíl C, pak deklarativní význam říká: cíl C je splnitelný právě tehdy, když existuje klauzule C v programu taková, že existuje instance I klauzule C taková, že hlava Ije identická s Ca všechny cíle v těle Ijsou pravdivé. cíl ?- ma_dite(petr) . Hana Rudová, Logické programování I, 29. února 2012 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů Ca) a(l). a(X) :- b(X,Y), a(Y). b(l,l). ?- a(l). (b) a(X) :- b(X,Y), a(Y). a(l). bCl.D. % změněné pořadí klauzulí v programu vzhledem k (a) % nenalezení odpovědi: nekonečný cyklus (c) a(X) :- b(X,Y), c(Y). ?- a(X). b(l,l). c(2). c(l). (d) a(X) :- c(Y), b(X,Y). % změněné pořadí cílů v těle klauzule vzhledem k (c) bCl.D. c(2). c(l) . % náročnější nalezení první odpovědi než u (c) V obou případech stejný deklarativní ale odlišný procedurální význam Hana Rudová, Logické programování I, 29. února 2012 Syntaxe a význam Prologovských programů Konjunce = nutné splnění všech cílů ■ p :- q, r. Disjunkce = stačí splnění libovolného cíle ■ P :- q; r. p :- q. p :- r. ■ priorita středníku je vyšší (viz ekvivalentní zápisy): p :-q, r; s, t, u. P :- Cq, r) ; (s, t, u). P :- q, r. p : - s , t, u . Hana Rudová, Logické programování I, 29. února 201 2 Syntaxe a význam Prologovských programů Pořadí klauzulí a cílů II. (1) a(X) :- c(Y), b(X,Y). (2) b(l,l). (3) c(2). (4) c(l). Vyzkoušejte si: (1) a(X) :- b(X,X), c(X). (3) a(X) :- b(Y,X), c(X). (4) b(2,2). (5) b(2,l). (6) c(l). ?- a(X). a(X) dle (1) c(Y), b(X,Y) dle (3j/Ý=2 dle (4)\Y=1 b(X,2) b(X,1) no dle (2) X=1 yes Hana Rudová, Logické programování I, 29. února 201 2 Syntaxe a význam Prologovských programů Cvičení: průběh výpočtu a :- b,c,d. b :- e,c,f,g b :- g,h. c. d. e : - i. e :- h. g- h. i. Jak vypadá průběh výpočtu pro dotaz ?- a. Hana Rudová, Logické programování I, 29. února 201 2 33 Syntaxe a význam Prologovských programu