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

2. cvičení

úterý 4.3.2008 a 11.3.2008 8:00 v B311

Osnova

Procvičení seznamů

  1. Které z následující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]
    Nejsou seznamy:
    e,h,i,j

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

    Například:
    b=d=g=k, c=d, d=f=m,
    l,k lze unifikovat, ale vznikne nekonečná struktura
    e=h ale nejsou seznamy

  3. K čemu lze použít následující predikát s/1? 
    s([]).
s([_|T]):-s(T).
    Pokud v dotazu zadáme částečně instanciovaný argument, můžeme testovat, jestli je seznamem nebo nikoliv. Pokud zadáme volnou promennou, můžeme generovat prázdné seznamy různých délek.

  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] 

    selekce([],[]).
selekce([H|S],[H|T1]):- 
	nonvar(H),
	selekce(S,T1).
selekce([H|S],T1):-
	var(H),
	selekce(S,T1).
    nebo pro zkušenějsí pomocí středníku 
    selekceD([],[]).
selekceD([H|S],T0):-
	( nonvar(H) ->
	  T0=[H|T1]
	;
	  T0=T1
	),	
	selekceD(S,T1).

  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ď? 

    selekceR(S,T):-selekceR(S,[],T).

selekceR([],Vysl,Vysl).
selekceR([H|S],A,T):- 
	nonvar(H),
	selekceR(S,[H|A],T).
selekceR([H|S],A,T):-
	var(H),
	selekceR(S,A,T).
    nebo pro zkušenější pomocí středníku (ale pozor - zde není rozdíl v konstrukci výsledného seznamu tak dobře vidět, jako v klasické verzi) 
    selekceDR(S,T):-selekceDR(S,[],T).

selekceDR([],Vysl,Vysl).
selekceDR([H|S],A0,T):-
	( nonvar(H) ->
	  A1=[H|A0]
	;
	  A0=A1
	),	
	selekceDR(S,A1,T).

  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).
    mem1/2 vyhledá všechny výskyty, pri porovnávání hledaného prvku s prvky seznamu může dojít k vázání proměnných (může sloužit ke generování všech prvků seznamu)
    mem2/2 najde jenom první výskyt, taky váže proměnné
    mem3/2 najde jenom první výskyt, proměnné neváže (hledá pouze identické prvky)
    Dokážete napsat variantu, která hledá jenom identické prvky a přitom najde všechny výskyty?

    Například po tomto dotazu se budou výsledky lišit: 

    ?- mem1(X,[1,2,3]).

X = 1 ;

X = 2 ;

X = 3 ;

No
?- mem2(X,[1,2,3]).

X = 1 ;

No
?- mem3(X,[1,2,3]).

No
?-

  3. Je tato definice predikátu max/3 korektní? 
    max(X,Y,X):-X>=Y,!.
max(X,Y,Y).
    Není, příklad dotazu: 
    ?- max(2,1,1).

Yes
    Uveďte dvě možnosti opravy, se zachováním použití řezu a bez.

    Bez použití řezu: 

    max(X,Y,X):-X>=Y.
max(X,Y,Y):-Y>X.
    S řezem: 
    max(X,Y,Z):-X>=Y,!,Z=X.
max(X,Y,Y).
    Problém byl v definici, v první verzi se tvrdilo: 
    X=Z & X>=Y => Z=X
    správná definice je: 
    X>=Y => Z=X
    Při použití řezu je třeba striktně oddělit vstupní podmínky od výstupních unifikací a výpočtu.

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).
    Protože S1 je volná proměnná v aritmetickém výrazu.

  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). 
    suma(S,V):-suma(S,0,V).

suma([],V,V).
suma([H|T],S,V):-S1 is H+S,suma(T,S1,V).

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!

^