16

Kontrolltöö loogilises programmeerimises, 21.02.96

I.

1. Sugulassuhted on defineeritud lausetega:

isa(okeanos, uranos).
isa(koios, uranos).
isa(kronos, uranos).
isa(demeter, kronos).
isa(atlas, iapetos).
ema(iapetos, gaia).
ema(kronos, gaia).

(semantika: isa(Laps, Isa), ema(Laps, Ema). )

1. Kuidas (minimaalse arvu lausetega) defineerida predikaat meessoost(Isik) ja predikaat onu(Isik, Onu).

Lahendus. Meesoost on kõik isad; nende kohta, kelle isaksolemisest ei ole midagi teada, tuleb sugu defineerida:

meessoost(Isik):-
isa(_, Isik).
meessoost(koios).
meessost(atlas).

2. Defineeri predikaat : tagurpidi(Nimistu, Tagurpidi), mis muudab nimistu elementide järjekorra.

Elementaarne lahendus (ei ole lõpprekursiivne):

tagurpidi([],[]).
tagurpidi([Pea|Keha], Tagurpidi):-
tagurpidi(Keha, Algus),
append(Algus, [Pea], Tagurpidi).

Parem (lõpprekursiivne) lahendus:

poora(Nimistu, Tagurpidi):-
poora1(Nimistu, [], Tagurpidi).
poora1([], Tagurpidi, Tagurpidi).
poora1([Pea|Keha], Pooratud, Tulemus):-
poora1(Keha, [Pea|Pooratud], Tulemus).

Abipredikaadi poora1 liidab samm sammult esimese argumendi (nimistu veel pöörata olev osa) elemendi teise argumendi (juba pööratud osa) esimeseks elemendiks; kui esimene argument on tühi (kogu nimistu on pöör atud), saadakse kolmanda argumendi abil tulemus.

3. Defineeeri predikaat, mis liidab kaks sama (suvalise) pikkusega kahendarvu; arvud on esitatud oma bitide nimistuna, näiteks liida([0,1,1], [1,0,1], [1,0,0,0]).
Tavalise tulbaviisilise liitmise juures võetakse esimese liidetava bit X , teise liidetava bit Y , eelmisel sammul saadud ülekanne C ja arvutatakse summa bit S ja uus ülekanne CN ; lihtne on näha, et S = (X + Y + C)(mod2), CN = (X&Y) v (X&C) v (Y&C), seega

samm(X, Y, C, S, CN):-
mod2(X, Y, Xmod2Y),
mod2(Xmod2Y, C, S),
ja(X, Y, XY),
ja(X, C, XC),
ja(Y, C, YC),
voi(XY, XC, XYvXC),
voi(XYvXC, YC, CN).

Lõike (cut) ! kasutamisega võib kirjeldada Boole funktsioonid ja_elem, või_elem, mod2 väga ökonoomselt. Lõige ! välistab antud kohas tagurdamise (backtracking), seega näiteks predikaadi ja esimeses lauses paremal pool olev lõige ! tagab, et ja(1, 1, X) arvutamisel kunagi ei kasutata predikaadi ja teist lauset; sellepärast võib seal esimesed kaks muutujat jätta anonüümseteks:

ja(1, 1, 0):-
!.
ja(_, _, 1).
voi(0, 0, 0):-
!.
voi(_, _, 1).
mod2(X, X, 0):- -- kui argumendid on võrdsed, on mod2 summa 0
!.
mod2(_,_,1).

Kui liidetavad on ühekohalised, taandub kogu operatsioon esimese tulba elementidele; eelmine ülekanne on null ja summa koosneb (paremalt vasakule) summa bitist ja ülekandest. Pikemate liidetavate korral liidetakse algul liidetavad ilma esimese elemend ita ja lisatakse siis esimese tulba elementidega sooritatud operatsiooni tulemusel saadud bitid:

liida([X], [Y], [NC, S]):-
samm(X, Y, 0, S, NC).
liida([X| X1], [Y|Y1], [CN, S|S1]):-
liida(X1, Y1, [C| S1]),
samm(X, Y, C, S, CN).

II.

1. Sugulassuhted on defineeritud lausetega:

isa(okeanos, uranos).
isa(koios, uranos).
isa(kronos, uranos).
isa(demeter, kronos).
isa(atlas, iapetos).
ema(iapetos, gaia).

(semantika: isa(Laps, Isa), ema(Laps, Ema). )

Kuidas defineerida predikaat sugulane(Isik, Sugulane)?

Lahendus. Kaks isikut on sugulased, kui nad on sama isiku järglased, seega

sugulane(Isik, Sugulane):-
jarglane(Isik, Keegi),
jarglane(Sugulane, Keegi).
-- Siin ei või kasutada anonüüset muutujat, sest selle kasutamisel võivad predikaadi jarglane teise argumendi väärtused eri lausetes tulla erinevad !
jarglane(Jarglane, Isik):-
isa(Jarglane, Isik).
jarglane(Jarglane, Isik):-
ema(Jarglane, Isik).
jarglane(Jarglane, Isik):-
isa(Jarglane1, Isik),
jarglane(Jarglane, Jarglane1).
jarglane(Jarglane, Isik):-
ema(Jarglane1, Isik),
jarglane(Jarglane, Jarglane1).

2. Arvrida on määratud seosega: x1 = 1, xn = 2*xn-1 + 2. Defineeri lõpprekursiivne predikaat liige(N, X) arvrea N-da liikme X leidmiseks.

Lihtne lahendus (ei ole lõpprekursiivne):

liige(1,1).
liige(N,X):-
N > 1,
N1 is N-1,
liige(N1, X1),
X is 2*X1+2.

Lõpprekursiivne lahendus:

liige(N,X):-
liige1(1, N, 1, X).
liige1(N, N, X, X).
liige1(N1, N, X1, XT):-
N1 < N,
N2 is N1+1,
X2 is 2*X1+2,
liige1(N2, N, X2, XT).

3. Kaart on esitatud kahe linna vahelist kaugust esitavate lausetega:

tee(tallinn, rakvere,97).
tee(rakvere, kohtla_järve,73).
tee(kohtla_järve, narva,50).
tee(tallinn, paide, 97).
tee(tallinn,rakvere,96).
tee(paide, tapa, 49).
tee(tapa, rakvere, 28).
tee(rakvere, jogeva, 72).
tee(paide, poltsamaa, 39).
tee(poltsamaa, tartu, 60).
tee(poltsamaa, jogeva, 27).
tee(jogeva, mustvee, 40).
tee(kohtla_järve, mustvee, 76).
tee(jogeva, mustvee, 40).

Defineeri predikaat mintee(Linn1, Linn2, Kaugus, Linnad) kahe linna Linn1, Linn2 vahelise minimaalse pik kusega tee Linnad (läbitud linnade nimistu) ja teepikkuse Kaugus leidmiseks.

Lahendus. Predikaat mintee(Linn1, Linn2, Kaugus, Linnad) käivitab abipredikaadi mine(Linn1, Linn2, Teepikkus, Linnad) , mis leiab järjekordse marsruudi; abipredikaat otsusta(Kaugus, Linnad) võrdleb äsja leitud marsruudi pikkust seni leitud minimaalse marsuudi pikkusega, mis salvestatakse lausega reis(Kaugus, Linnad) , ja kordab sisseehitatud predikaadi faili (alati ebaõnnestub, s.t. sunnib otsima eelnevale uut lahendit) abil kogu tsüklit. Kui predikaat mine uut reisi enam ei leia, leitakse lausest reis(Kaugus, Linnad) minimaalse marsuudi pikkus.

mintee(L1,L2,_,_) :-
mine(L1,L2,0,[L1]),
fail.
mintee(L1,L2,T,Ld) :-
reis(T,Ld),
retractall(reis(_,_)).
mine(L,L,T,Ld) :-
!,
otsusta(T,Ld).
mine(L1,L2,T,Ld) :-
paaseb(L1,L,Km),
not member(L,Ld),
T1 is T + Km,
mine(L,L2,T1,[L|Ld]).
otsusta(T,Ld) :-
not clause(reis(_,_),true),
!,
assert(reis(T,Ld)).
otsusta(T,Ld) :-
reis(T1,_),
T < T1,
!,
retractall(reis(_,_)),
assert(reis(T,Ld)).
otsusta(_,_).
paaseb(L1,L2,Km) :-
tee(L1,L2,Km).
paaseb(L1,L2,Km) :-
tee(L2,L1,Km).
Küsimused, probleemid:
jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde