Logické programování

Organizační záležitosti:

Zápočtové úkoly

Odevzdejte na můj email do 14.1. 2024.

  1. úkol 3 z dokumentu Olinx 3 ("Programovací jazyk PROLOG, 3. díl")
  2. úkol 3 z dokumentu Olinx 4 ("Programovací jazyk PROLOG, 4. díl"), na vhodném místě použijte řez

  3. Uzly binárního vyhledávacího stromu budeme representovat termy ve tvaru node(key, val, left, right), kde key a val representují klíč a hodnotu v uzlu a left a right je levý a pravý podstrom. Prázdný podstrom budeme značit atomem nil. Příklad stromu, kde klíče jsou znaky:

    node(d, 10, node(c, 2, node(b, 35, nil, nil), nil),
            node(f, 5, node(e, 11, nil, nil),
                       node(g, 13, nil, nil)))

    Naprogramujte efektivní vkládání do binárního vyhledávacího stromu. Napište pravidla pro predikát pridej/4, který má vstupní argumenty: klíč, hodnotu a strom. Výsledkem je strom vzniklý vložením nového uzlu. Pokud již ve stromu existuje uzel s daným klíčem, pouze přepište starou hodnotu v uzlu.

  4. Uvažte následující fragment seznamu frekvencí slov pro rozsáhlý anglický text: 
    w(5,2186369,a,det).
w(2107,4249,abandon,v).
w(5204,1110,abbey,n).
w(966,10468,ability,n).
w(321,30454,able,a).
w(6277,809,abnormal,a).
w(3862,1744,abolish,v).
w(5085,1154,abolition,n).
w(4341,1471,abortion,n).
w(179,52561,about,adv).
w(69,144554,about,prep).
w(3341,2139,above,a).
w(942,10719,above,adv).
w(786,12889,above,prep).
w(2236,3941,abroad,adv).
w(5106,1146,abruptly,adv).

    Formát je následující: w(Pořadí,Frekvence,Slovo,TřídaSlova)

    Pořadí je 1 pro nejčastější slovo. TřídaSlova je kategorie: det pro určitel, v pro sloveso, n pro podstatné jméno, a pro přídavné jméno atd.

    Program je deterministický, pokud a pouze pokud neuspěje více než jednou.

    • Napište deterministický program ambiguous (vypíše jen jedno řešení), takový, že ambiguous(Slovo) uspěje, pokud a pouze pokud Slovo je v seznamu frekvencí slov s více než jednou kategorií (lze použít standardní aritmetické predikáty).
    • Napište deterministický program display, který vytiskne n nejčastějších slov a odpovídající kategorie ve frekvenčním seznamu slov, kde n je argumentem predikátu. Pro výše uvedený fragment například: 
      ?- display(500).
a det
able a
about adv
about prep
Yes

      Lze použít standardní predikáty jako fail, write a nl.

Cvičení 5

  1. V následujícím textu lze předpokládat, že všechny prvky seznamů jsou celá čísla. Uvažujte program v Prologu s názvem cutoff, kde cutoff(Seznam1, Seznam2) uspěje pouze tehdy, když Seznam2 představuje nejdelší prefix Seznam1 bez záporných prvků. Příklady dotazů v Prologu:

    ?- cutoff([1,-2,3],[1]).
Yes
?- cutoff([1,-2,3],[1,-2,3]).
No
    • Napište verzi programu v Prologu cutoff bez použití operátorů řezu (!) nebo if-then-else.
    • Napište verzi programu v Prologu cutoff s použitím operátorů řezu (!) a s nejvýše jedním použitím aritmetických porovnávacích operátorů.
  2. úkol 2 z dokumentu Olinx 3 ("Programovací jazyk PROLOG, 3. díl"), s použitím řezu. 
    
?- slij([1,3,5],[2,3,6],X).
X = [1, 2, 3, 3, 5, 6].

Cvičení 4

  1. Modelování aritmetiky

    %% prirozene cislo
 natural(0).
 natural(s(X)) :- natural(X).
 
 %% scitani prirozenych cisel
 add(X,0,X).
 add(X,s(Y),s(Z)) :- add(X,Y,Z).
    1. Vytvořte pravidla pro predikáty even/1 (číslo je sudé), odd/1 (číslo je liché). Dále definujte predikáty leq/2 a lt/2 přirozeného uspořádání a ostrého uspořádání přirozených čísel. Predikáty otestujte.
    2. Vytvořte pravidla definující predikát mul/3 vyjadřující vztah „X krát Y je rovno Z“. Využijte známého faktu, že výsledek součinu x a následníka y je roven součinu x a y plus x. Pomocí násobení dále definujte predikát pow/3 reprezentující celočíselnou mocninu.
    3. Pomocí již hotových predikátů napište pravidla pro výpočet faktoriálu a Fibonacciho čísla.

Cvičení 3

  1. úkoly 1, 2, 3 a 4 z dokumetu "Programovací jazyk PROLOG, 2. díl"

Cvičení 2

  1. Vozidla

    Přečtěte si následující ukázkový text. Podle textu vytvořte vhodnou databázi faktů, tak, aby bylo v databázi uloženo co možná nejvíce informací z tohoto textu. Pokud nebudou fakta vhodně formalizována, v dalším příkladu bude obtížné sestavovat některé dotazy.

    Auta jsou dvoustopá vozidla, která jezdí buďto na benzin, na naftu nebo na plyn. Auta se řídí volantem. Motorky jsou jednostopá vozidla a jezdí na benzin. Motorky mají řídítka. Kola nemají motor, jsou jednostopá a mají řídítka. Pavel má kolo i auto. Mirek má motorku a auto. Petr má kolo. Vilém nemá žádný dopravní prostředek.

    Vyzkoušejte vytvořit pravidla pro následující dotazy.

    1. Která vozidla jezdí na benzin?
    2. Kteří lidé vlastní jednostopé dopravní prostředky?
    3. Kdo řídí svůj dopravní prostředek volantem?
    4. Existují některé jednostopé dopravní prostředky, které se řídí volantem?
    5. Které dopravní prostředky mají řídítka?

  2. Databáze koček

    Prolog a jeho inferenční mechanismus lze využít jako jednoduchý dotazovací jazyk. Definice faktů můžeme chápat podobně, jako jsou v relačních databázích chápány tabulky, dotazy nad daty uloženými v tabulkách jsou v PROLOGu reprezentovány vytvářením vhodných cílů, případně dalších pravidel.

    Nyní budeme uvažovat databázi informací o vybraných kočičích plemenech, viz soubor cats.pl

    3. . Základní informace o kočkách jsou reprezentovány jako fakta pomocí tří základních predikátů,


    Jméno kočky lze chápat v databázové terminologii jako primární klíč, to jest jednoznačný identifikátor každého plemene kočky. Vytvářením nových odvozovacích pravidel a vhodnými dotazy můžeme získávat informace z této databáze.

    Z databáze zjistěte následující informace. Pomozte si vytvořením dodatečných pravidel. Jména koček, názvy vlastností, barev, etc., jsou v databázi bez diakritiky.

    1. Které kočky mají aktivní povahu?
    2. Jakou barvu srsti a očí může mít tonkinská kočka?
    3. Které dlouhosrsté kočky jsou malé?
    4. Které kočky jsou velké a tiché?
    5. V jakých barvách se vyskytují polodlouhosrsté kočky?
    6. Jak se jmenují polodlouhosrsté kočky?
    7. Které kočky mohou být bílé?

Cvičení 1

  1. Popis zvířat

    Formalizujte následující slovní popis a přepište jej do prologu:

    „Medvěd je velký, slon je velký. Kočka je malá, myš je malá. Medvěd je hnědý, kočka je černá, slon je šedý, myš je šedá. Vše černé a vše hnědé je tmavé.“

    Poté (v PROLOGu) napište dotaz, kterým zjistíte, kdo všechno je šedý a druhý dotaz, kterým zjistíte, kdo je tmavý a současně velký.

  2. Databáze příbuzenských vztahů

    Uvažme následující PROLOGovský program:

    rodic(pavla,robert).
rodic(tom,robert).
rodic(tom,liza).
rodic(robert,anna).
rodic(robert,patricie).
rodic(patricie,jan).
rodic(jan,simon).
rodic(jan,ester).

zena(pavla).
zena(liza).
zena(anna).
zena(patricie).

muz(tom).
muz(simon)
muz(robert).
muz(jan).

potomek(Y,X) :- rodic(X,Y).
matka(X,Y) :- rodic(X,Y), zena(X).
prarodic(X,Z) :- rodic(X,Y), rodic(Y,Z).
sestra(X,Y) :-
  rodic(Z,X), rodic(Z,Y), zena(X), not(X=Y).
predek(X,Z) :- rodic(X,Z).
predek(X,Z) :- rodic(X,Y), predek(Y,Z).

    K právě uvedenému programu doplňte čtyři fakta obsažená ve větě „Jan je rodičem chlapce Šimon a dívky Ester.“ a definujte tři pravidla:

    • binární relaci deda,
    • binární relaci bratr,
    • binární relaci vnouce.

    Poté položte čtyři dotazy:

    • Koho je Šimon vnouče?
    • Kdo je bratr Lízy?
    • Kdo všechno je dědou?
    • Kdo všechno jsou předci Ester?