Post on 30-Dec-2015
description
transcript
Logické programováníLogické programování
Úvodní přednáškaÚvodní přednáška
22
Průběh výukyPrůběh výukyPřednášky/cvičení - 2/2Přednášky/cvičení - 2/2
PřednáškyPřednáškyprof. RNDr. Josef Hynek, MBA, Ph.D.prof. RNDr. Josef Hynek, MBA, Ph.D.
CvičeníCvičeníDoc. RNDr. Kamila Štekerová, Ph.D.Doc. RNDr. Kamila Štekerová, Ph.D.Ing. Barbora Tesařová, Ph.D.Ing. Barbora Tesařová, Ph.D.
33
Ukončení předmětuUkončení předmětuZápočetZápočet- dva písemné testy (polovina a konec semestru)- dva písemné testy (polovina a konec semestru)- podmínky budou specifikovány na cvičeních- podmínky budou specifikovány na cvičeních
Zkouška Zkouška - písemná a ústní, 4 úlohy- písemná a ústní, 4 úlohyVzorové zadáníVzorové zadání1.1. Zadaný seznam reálných čísel S rozdělte na dvě části (libovolným Zadaný seznam reálných čísel S rozdělte na dvě části (libovolným
způsobem) tak, aby součet čísel v obou částech byl stejný (např. způsobem) tak, aby součet čísel v obou částech byl stejný (např. pro seznam S=[1,3,2,4] bude výsledek S1 = [1,4], S2 = [3,2] ). pro seznam S=[1,3,2,4] bude výsledek S1 = [1,4], S2 = [3,2] ).
2.2. Napište program, který navrhne obarvení zadané mapy čtyřmi Napište program, který navrhne obarvení zadané mapy čtyřmi barvami (viz. skripta str. 199). barvami (viz. skripta str. 199).
3.3. Logický problém (viz. přednáška nebo skripta str. 213). Logický problém (viz. přednáška nebo skripta str. 213). 4.4. Napište program, který rozhodne, zda zadané číslo N je prvočíslo. Napište program, který rozhodne, zda zadané číslo N je prvočíslo.
44
LiteraturaLiteraturaHynek,J., Mikulecký,P.: Logické programováníHynek,J., Mikulecký,P.: Logické programovánía Prolog. (1995, 2003)a Prolog. (1995, 2003)
Kolář,J.: Jazyky pro umělou inteligenci. (1998)Kolář,J.: Jazyky pro umělou inteligenci. (1998)
Jirků,P.: Programování v jazyku Prolog. (1991)Jirků,P.: Programování v jazyku Prolog. (1991)
Polák,J.: Prolog. (1995)Polák,J.: Prolog. (1995)
Clocksin,W.F., Mellish, C.S.: Programming in Clocksin,W.F., Mellish, C.S.: Programming in Prolog. (2003) Prolog. (2003)
Bratko,I.: Prolog – programming for AI. (2000) Bratko,I.: Prolog – programming for AI. (2000)
Censki, A.: Prolog Techniques. Censki, A.: Prolog Techniques. (http://bookboon.com)(http://bookboon.com)
55
Další zdrojeDalší zdroje
kurz Logické programování I. kurz Logické programování I. http://oliva.uhk.czhttp://oliva.uhk.czNemáte-li do kurzu přístup, zašlete svůj login na adresu Nemáte-li do kurzu přístup, zašlete svůj login na adresu kamila.stekerova@uhk.czkamila.stekerova@uhk.cz
Programování v Prologu (Filip Rubáček) Programování v Prologu (Filip Rubáček) http://iris.uhk.cz/logpro/http://iris.uhk.cz/logpro/
Kryl, R.: Úvod do programovacího jazyka PrologKryl, R.: Úvod do programovacího jazyka Prologhttp://ksvi.mff.cuni.cz/~kryl/prolog.pdfhttp://ksvi.mff.cuni.cz/~kryl/prolog.pdf
Learn Prolog Now! Learn Prolog Now! http://www.coli.uni-sb.de/~kris/learn-prolog-now/http://www.coli.uni-sb.de/~kris/learn-prolog-now/
Amzi! PrologAmzi! Prolog, , Arity PrologArity Prolog, , B-PrologB-Prolog, , Strawberry Strawberry PrologProlog, , SWI – PrologSWI – Prolog, , Visual Prolog Visual Prolog … lze najít a stáhnout z webu… lze najít a stáhnout z webu
66
ÚvodÚvod
Logické programování = disciplína Logické programování = disciplína matematické informatikymatematické informatiky
Prolog = PROgramování v LOGiceProlog = PROgramování v LOGice– jazyk pro programování symbolických jazyk pro programování symbolických
výpočtů, založený na matematické logicevýpočtů, založený na matematické logice– vhodný k řešení problémů z oblasti umělé vhodný k řešení problémů z oblasti umělé
inteligenceinteligence
77
Pohled do historiePohled do historie1972 - 1. verze, A.Colmerauer na univerzitě v 1972 - 1. verze, A.Colmerauer na univerzitě v MarseillesMarseilles
1974 - R.Kowalski vytvořil teoretický model 1974 - R.Kowalski vytvořil teoretický model jazyka, na který navázaly další implementacejazyka, na který navázaly další implementace
1977 - nejúspěšnější verze D.H.D.Warrena, 1977 - nejúspěšnější verze D.H.D.Warrena, popsaná v učebnici W.F.Clocksina a popsaná v učebnici W.F.Clocksina a C.S.Mellishe "Programming in Prolog"C.S.Mellishe "Programming in Prolog"
1981 - v Japonsku byl Prolog zvolen za základní 1981 - v Japonsku byl Prolog zvolen za základní jazyk centrální jednotky počítače páté generacejazyk centrální jednotky počítače páté generace
88
Prolog je jazyk...Prolog je jazyk...
neprocedurální - postup řešení problému není to, co by neprocedurální - postup řešení problému není to, co by nás nejvíc zajímalonás nejvíc zajímalo
deklarativní - při psaní programu deklarujeme fakta a deklarativní - při psaní programu deklarujeme fakta a pravidla, jimiž popíšeme vlastnosti a vztahy mezi objektypravidla, jimiž popíšeme vlastnosti a vztahy mezi objekty
konverzační - uživatel klade dotazy, na které mu Prolog konverzační - uživatel klade dotazy, na které mu Prolog odpovídáodpovídá
interaktivní - pokud uživatel dotazy neklade, Prolog interaktivní - pokud uživatel dotazy neklade, Prolog nepracuje a čeká nepracuje a čeká
99
PříkladPříklad
kral('Premysl Otakar I.',1197,1230).kral('Premysl Otakar I.',1197,1230).
kral('Vaclav I.',1230,1253).kral('Vaclav I.',1230,1253).
kral('Premysl Otakar II.',1253,1278).kral('Premysl Otakar II.',1253,1278).
predchudce(Prvni, Druhy):-kral(Prvni,_,Do),kral(Druhy,Do,_).predchudce(Prvni, Druhy):-kral(Prvni,_,Do),kral(Druhy,Do,_).
naslednik(A,B):-predchudce(B,A).naslednik(A,B):-predchudce(B,A).
?- kral('Vaclav I.',1230,1253). ?- kral('Vaclav I.',1230,1253).
yesyes
?- kral(X, 1253,Rok).?- kral(X, 1253,Rok).
X = 'Premysl Otakar II.‚, Rok = 1278X = 'Premysl Otakar II.‚, Rok = 1278
Formální skutečnosti (fakta)
Relace (pravidla)
Konverzace s Prologem
Textový editor
Konzole
1010
LPA PrologLPA Prolog
1111
LPA PrologLPA Prolog
PROLOGPROLOG
snadno a rychlesnadno a rychle
1313
Programování v Programování v PrologProloguu
Programování v PROLOGu spočívá vProgramování v PROLOGu spočívá v– deklarování určitých faktů o objektech a deklarování určitých faktů o objektech a
relacíchrelacích
president(obama,usa).president(obama,usa).– definování pravidel vztahujících se k definování pravidel vztahujících se k
objektům a relacímobjektům a relacím
vip(Person):-president(Person,Country).vip(Person):-president(Person,Country).– kladení otázek na objekty a relacekladení otázek na objekty a relace
?-president(Who,czech_republic).?-president(Who,czech_republic).
1414
Deklarování faktůDeklarování faktů
Tom má rád Janu. Jana má ráda Toma.Tom má rád Janu. Jana má ráda Toma. Jednodušší gramatika AJ:Jednodušší gramatika AJ:
Tom likes Jane. Jane likes Tom. Tom likes Jane. Jane likes Tom. Přepis v PROLOGu:Přepis v PROLOGu:
likes(tom, jane). likes(tom, jane).
likes(jane, tom). likes(jane, tom). Jména relací (predikáty) i objektů (argumenty) Jména relací (predikáty) i objektů (argumenty)
začínají malým písmenemzačínají malým písmenem Každý predikát má pevně danou aritu (počet Každý predikát má pevně danou aritu (počet
argumentů) – predikát argumentů) – predikát likeslikes má aritu 2 má aritu 2
1515
Deklarování faktůDeklarování faktů Argumenty jsou uvedeny v závorce a na konci Argumenty jsou uvedeny v závorce a na konci
sdělení je tečkasdělení je tečka Pořadí argumentů má obvykle svůj význam a je Pořadí argumentů má obvykle svůj význam a je
třeba jej zachovávattřeba jej zachovávat
likes(tom, jane).likes(tom, jane). často neznamená často neznamená likes(jane, tom). likes(jane, tom). Jména relací mohou být libovolná, ale lépe je Jména relací mohou být libovolná, ale lépe je
používat s rozmyslem a udržet si přehledpoužívat s rozmyslem a udržet si přehled
likes(jane,tom). likes(jane,tom). jistě může být totéž co jistě může být totéž co li34(t6, j_1).li34(t6, j_1). Lze deklarovat i zjevné nepravdyLze deklarovat i zjevné nepravdy
king(obama, china). king(obama, china).
1616
Deklarování faktůDeklarování faktů Další příkladyDalší příkladygirl(jane). girl(jane). father(george, lisa).father(george, lisa).parents(george, mary, lisa).parents(george, mary, lisa).friends(angel, mary, lisa, laura, barbfriends(angel, mary, lisa, laura, barbaara).ra).president(president(`̀PutinPutin`,`Russia`).`,`Russia`).president(putinpresident(putin, russia). , russia). % POZOR% POZOR- jiné objekty!!!- jiné objekty!!!
king(carlos, spain).king(carlos, spain).
//* * soubor deklarovaných faktů a pravidel se v soubor deklarovaných faktů a pravidel se v PROLOGu nazývá PROLOGu nazývá databázedatabáze */*/
1717
Kladení otázekKladení otázek?-father(george, lisa).?-father(george, lisa). Položíme-li nějaký dotaz, PROLOG hledá odpověď v Položíme-li nějaký dotaz, PROLOG hledá odpověď v
databázi, kterou jsme mu předtím poskytlidatabázi, kterou jsme mu předtím poskytli Databáze je prohledávána shora dolů s cílem nalézt Databáze je prohledávána shora dolů s cílem nalézt
fakta a pravidla, která s dotazem souvisífakta a pravidla, která s dotazem souvisí Mluvíme o tzv. unifikaci (matching) Mluvíme o tzv. unifikaci (matching) Dvě fakta lze unifikovat, jestliže jejich predikáty jsou Dvě fakta lze unifikovat, jestliže jejich predikáty jsou
stejné, mají stejnou aritu a korespondující argumenty stejné, mají stejnou aritu a korespondující argumenty jsou také stejnéjsou také stejné
Pokud PROLOG nalezne skutečnost, kterou lze Pokud PROLOG nalezne skutečnost, kterou lze unifikovat se zadaným dotazem, odpoví YES, jinak unifikovat se zadaným dotazem, odpoví YES, jinak odpoví NOodpoví NO
1818
Kladení otázekKladení otázek Předpokládejme, že máme zadanou následující databázi:Předpokládejme, že máme zadanou následující databázi:likes(tom, mary).likes(tom, mary).likes(tom, jane).likes(tom, jane).likes(mary, money).likes(mary, money).likes(tom, food).likes(tom, food).
Nyní můžeme klást dotazyNyní můžeme klást dotazy?-likes(tom, jane).?-likes(tom, jane).yesyes % % proběhne proběhne unifikunifikaceace s 2. s 2. řádkem ve výše uvedené databázi řádkem ve výše uvedené databázi
?-likes(peter, jane).?-likes(peter, jane).no no % % nenelze unifikovat s lze unifikovat s žádným faktem ve výše uvedené databázi žádným faktem ve výše uvedené databázi
?-animal(dog).?-animal(dog).no no % % nenelze unifikovat s lze unifikovat s žádným faktem ve výše uvedené databázi žádným faktem ve výše uvedené databázi
1919
Kladení otázekKladení otázek Důležité je správně chápat odpověď na položenou otázku:Důležité je správně chápat odpověď na položenou otázku: YES znamená „na základě mých informací je to pravda“YES znamená „na základě mých informací je to pravda“?-likes(tom, jane).?-likes(tom, jane).yesyes
NO má ale hned několik významůNO má ale hned několik významů- není to pravda (skutečně NE)není to pravda (skutečně NE)- nepodařilo se ověřit „na základě mých informací“ = nevímnepodařilo se ověřit „na základě mých informací“ = nevím?-animal(dog).?-animal(dog).nono- Váš program nefunguje („nepodařilo se dojít k cíli“)Váš program nefunguje („nepodařilo se dojít k cíli“)
2020
Kladení obecnějších otázekKladení obecnějších otázek Je možné využít proměnnýchJe možné využít proměnnýchWho likes Mary? Who likes Mary? přepíšeme v PROLOGu jakopřepíšeme v PROLOGu jako ?-likes(Who, mary).?-likes(Who, mary).
Jméno proměnné začíná velkým písmenem:Jméno proměnné začíná velkým písmenem:Who, Mary, Someone_who_likes_someone_else Who, Mary, Someone_who_likes_someone_else
Proměnná může být specifikovaná (nabývá konkrétní Proměnná může být specifikovaná (nabývá konkrétní hodnotu) nebo nespecifikovaná (hodnota proměnné není hodnotu) nebo nespecifikovaná (hodnota proměnné není dosud známa)dosud známa)
Zadáme-li dotaz obsahující proměnnou, PROLOG Zadáme-li dotaz obsahující proměnnou, PROLOG prohledává databázi s cílem nalézt objekt, který by mohl prohledává databázi s cílem nalézt objekt, který by mohl stanout na místě proměnnéstanout na místě proměnné
2121
Otázka obsahující proměnnouOtázka obsahující proměnnou Předpokládejme, že máme zadanou následující databázi:Předpokládejme, že máme zadanou následující databázi:likes(tom, mary).likes(tom, mary).likes(tom, jane).likes(tom, jane).likes(mary, money).likes(mary, money).likes(tom, food).likes(tom, food).
Předpokládejme dotaz „Co či koho má Tom rád?“Předpokládejme dotaz „Co či koho má Tom rád?“?-likes(tom, X).?-likes(tom, X).X = maryX = mary;;X = jane;X = jane;X = food;X = food;nono
2222
Kladení Kladení jeještě obecnějších otázekště obecnějších otázek Často chceme položit dotaz, který vyžaduje ověření více Často chceme položit dotaz, který vyžaduje ověření více
podmínekpodmínek
Konjunkce cílů – pomocí symbolu čárkaKonjunkce cílů – pomocí symbolu čárka
Má Tom rád Mary a má Mary ráda Toma? Má Tom rád Mary a má Mary ráda Toma?
přepíšeme v PROLOGu jakopřepíšeme v PROLOGu jako
?-likes(tom, mary), likes(mary, tom).?-likes(tom, mary), likes(mary, tom).
Disjunkce cílů – pomocí symbolu středníkDisjunkce cílů – pomocí symbolu středník
?-likes(?-likes(XX, mary), mary);; likes( likes(XX, , lisalisa).).
lze lze interpretovat jako „má někdo rád Mary nebo Lisu?“ interpretovat jako „má někdo rád Mary nebo Lisu?“
2323
Splňování cílů v konjunkciSplňování cílů v konjunkciKaždý cíl v konjunkci má vlastní značku Každý cíl v konjunkci má vlastní značku
(marker)(marker)Cíle se splňují zleva dopravaCíle se splňují zleva dopravaPokud se některý cíl nepodaří splnit jinak, Pokud se některý cíl nepodaří splnit jinak,
PROLOG se vrací k cíli předchozímu, PROLOG se vrací k cíli předchozímu, příslušnou proměnnou udělá příslušnou proměnnou udělá nespecifikovanou a pokračuje od příslušné nespecifikovanou a pokračuje od příslušné značky v dalším prohledávání databázeznačky v dalším prohledávání databáze
tzv. BACKTRACKINGtzv. BACKTRACKING
2424
PříkladPříklad Předpokládejme, že máme zadanou následující databázi:Předpokládejme, že máme zadanou následující databázi:likes(jane, food).likes(jane, food).likes(jane, wine).likes(jane, wine).likes(tom, jane).likes(tom, jane).likes(tom, wine).likes(tom, wine).
Předpokládejme následující dotazyPředpokládejme následující dotazy?-likes(tom, jane), likes(jane, tom).?-likes(tom, jane), likes(jane, tom).nono?-likes(jane, X), likes(tom, X).?-likes(jane, X), likes(tom, X).X = wineX = wine;;nono
2525
PravidlaPravidla Pravidla popisují skutečnosti, které závisí na jiných Pravidla popisují skutečnosti, které závisí na jiných
skutečnostech skutečnostech likes(tom, X) :- girl(X).likes(tom, X) :- girl(X).
Pravidlo se skládá z hlavy, definičního symbolu „:-“ a tělaPravidlo se skládá z hlavy, definičního symbolu „:-“ a těla Hlava pravidla popisuje to, co chceme definovatHlava pravidla popisuje to, co chceme definovat Tělo určuje cíle, které musí být splněny, aby byla splněna Tělo určuje cíle, které musí být splněny, aby byla splněna
hlava pravidlahlava pravidla Platnost proměnné je omezena pouze na příslušné Platnost proměnné je omezena pouze na příslušné
pravidlo.pravidlo.
likes(jane, M) :- male(M), likes(M, wine), play(M, tennis).likes(jane, M) :- male(M), likes(M, wine), play(M, tennis).likes(jane, M) :- animal(M), friendly(M).likes(jane, M) :- animal(M), friendly(M).