Home     Termíny     Cvičení     Projekty     Rezervace termínu
  1   2   3   4   5   6

2. cvičení

13.3.2013 12:00 v B204

Osnova

Procvičení seznamů

  1. Které z následujích termů jsou seznamem a které ne? 
    a) []
b) [1]
c) [1,2]
d) [H|T]
e) [1|2]
f) [1,2,3|[4]]
g) .(1,[])
h) .(1,2)
i) .(1,2,3)
j) .(1,.(2,.(3)))
k) [X]
l) [[X]]
m) [1,2,3,4]

  2. Které dvojice předchozích termů lze unifikovat?

  3. K čemu lze použít následující predikát s/1? 
    s([]).
s([_|T]):-s(T).

  4. Napište predikát selekce(Sez,Sez_bez_prom), který přepíše ze seznamu Sez do seznamu Sez_bez_prom jen ty prvky, které nejsou volné promenné. [Pomůcka: použijte vestavěný (built-in) predikát nonvar/1]

  5. Otestujte Váš prográmek z předchozího úkolu na tomto příkladu:
    selekce([22,Z,z,7,s(1),Prvek,b],Vysledek)
    Dokážete napsat jinou verzi tohoto prográmku tak, aby bylo pořadí prvků v seznamu Vysledek opačné, než je teď?

  6. Napište predikát rozdil(Seznam,Zakazane_prvky,Vysledek), který přepíše ze seznamu Seznam do seznamu Vysledek jen ty prvky, které nejsou v seznamu Zakazane_prvky, v podstatě se jedná o rozdíl dvou (uspořádaných) množin. [Pomůcka: použijte predikát member/2 probraný v přednásce nebo nějakou jeho modifikaci]
    Vyzkoušejte si napsat i jiné množinové operátory (sjednocení, prunik, součin,...) pro množiny reprezentované seznamy.

Procvičení řezu

  1. Je dán následující program: 
    r(X):-write(r1).
r(X):-p(X),write(r2).
r(X):-write(r3).

p(X):-write(p1).
p(X):-a(X),b(X),!,c(X),d(X),write(p2).
p(X):-write(p3).

a(X):-write(a1).
a(X):-write(a2).

b(X):- X > 0, write(b1).
b(X):- X < 0, write(b2).

c(X):- X mod 2 =:= 0, write(c1).
c(X):- X mod 3 =:= 0, write(c2).

d(X):- abs(X) < 10, write(d1).
d(X):-write(d2).
    Prozkoumejte trasy výpočtu a navracení např. pomocí následujících dotazů: 
    a) X=1,r(X).
b) X=3,r(X).
c) X=0,r(X).
d) X= -6,r(X).
    Vždy si středníkem vyžádejte navracení.

    Všimnete si zejména:
    • řez v predikátu p/1 neovlivní alternativy predikátu r/1
    • dokud nebyl proveden řez, alternativy predikátu a/1 se uplatňují, př. neúspěch b/1 v dotazu c)
    • při neúspěchu cíle za řezem se výpočet navrací až k volající proceduře r/1, dotaz a)
    • alternativy vzniklé po provedení řezu se zachovávají - další možnosti predikátu c/1 v dotazech b) a d)

  2. Jaký je rozdíl mezi následujícími definicemi predikátů member/2. Ve kterých odpovědích se budou lišit? 
    mem1(H,[H|_]).
mem1(H,[_|T]):-mem1(H,T).

mem2(H,[H|_]):-!.
mem2(H,[_|T]):-mem2(H,T).

mem3(H,[K|_]):-H==K.
mem3(H,[K|T]):-H\==K,mem3(H,T).

  3. Je tato definice predikátu max/3 korektní? 
    max(X,Y,X):-X>=Y,!.
max(X,Y,Y).
    Uveďte dvě možnosti opravy, se zachováním použití řezu a bez.

Procvičení techniky akumulátor
  1. Uvažujme program na součet prvků seznamu
    suma([],0).
suma([H|T],S):-suma(T,S1),S is S1+H.
    Pokud chceme dosáhnout optimalizaci posledního voláni, proč nestačí prohodit cíle v poslední klauzuli? 
    suma([H|T],S):-S is S1+H,suma(T,S1).

  2. Následující program při volání S=[1,2,3],suma(S,0) vypíše součet prvků seznamu S na obrazovku: 
    suma([],V):-write(V),nl.
suma([H|T],S):-S1 is H+S,suma(T,S1).
    Upravte program tak, aby vracel výsledek (součet prvků seznamu) ve svém druhém argumentu místo výpisu na obrazovku, při zachování rekurzivního volání na konci klauzule (LCO).

Modelové příklady

Kopie seznamu copy(S,T): 

copy([],[]).
copy([H|S],[H|T]):-copy(S,T).       /* prime poradi - prvek je pridan v hlave pravidla */
Obrácení seznamu rev(S,T): 
rev(S,T):-rev(S,[],T).              /* zavedeni akumulatoru */

rev([],T,T).
rev([H|S],A,T):-rev(S,[H|A],T).     /* obracene poradi - prvek je pridan v tele pravidla */
Cyklus s využitím optimalizace posledního volání (LCO - Last Call Optimization) technikou akumulátoru:

Příklad: Výpočet faktoriálu
predikát fact(N,F), pro jehož argumenty platí F=N!

^