% povodne v lat2, teraz KAm (podobne aj in� s�bory)
\documentstyle[czech]{article}
\textwidth 172mm \textheight 220mm

\begin{document}
\begin{verbatim}

  subor ..\prg2\tex\cvicenia.tex , ...cvic00.txt
30.10.2001, 5.cv.

1. cv. ...
2001: rodokmen

add: vypisovanie a nacitanie obsahu dynamickej pamati
  - do termu, do XML; obecne do dobre zatvorkovanej struktury

2.cv. 9.10.2001
datumy - navrh repr.
ine repr.

3cv 2001
zoznamove operacie ...
multiappend alias concat (spojenie zoznamu zoznamov)
prefix (alebo suffix), vsetky prefixy (alebo suffixy)
kombinacie (variacie), 
  (s unarnou reprezentaciou cisel pre pocitanie velkosti)
  alebo s pripravenou dlzkou zoznamu
(n-arne stromy) NIE

DC: podmnoziny backtrakingom, vsetky podmnoziny do zoznamu

4.cv 2001
- DC podmnoziny
  idea: generuj a testuj; kedy to nie je vhodne pouzit 
- vyroba vyvazeneho stromu z usporiadaneho zoznamu
  - delenie zoznamu na polovice, rozne pristupy
  - pre neusporiadany: pouzitie v Heapsorte (asi len idea)
    - budovanie stromu
    - prebublavanie prvkov kvoli usporiadaniu 
      - tvorba haldy zo stromu
    - vypustanie prvkov pri zmensovani hlady (len idea)
- isset: interpret mnozinovych vyrazov (bude na prednaske)
*  s operatormi + zjednotenie, * prienik, - rozdiel
*  bez definicie isset ako operatora - to este nemali
 
DC: transpozicia matice
 
5.cv 2001
lookup/3 pre zoznamy (member), stromy (s @< a ->), 
 - struktura a pristupove (a budovacie) procedury si musia odpovedat
   - prolog to nepodporuje (vs. zdruzovanie v Objektoch a Moduloch)
 - s 2D klucmi : a) ako kart. sucin elementarnych klucov
		  - mozno pouzit minule programy
		b) 2 urovnova struktura, kazda uroven samostatne vyhladavanie
			(s odpovedajucou procedurou)
   - obecne n-dimenzionalne: analogicky 
     - ak to napisem rekurzivne (okrem poslednej vrstvy- kluca), potom musia
	vsetky urovne byt rovnake
 - pre obecne vyhladavanie s roznym poctom dimenzii (odpoveda Aho-Corasick)
   - hodnota musi byt dvojzlozkova: 1 cast je vlastna hodnota (pre dany kluc)
	2. cast je zostavajuca vyhladavacia struktura, pre dlhsie kluce 
	s rovnakym prefixom

boolovske vyrazy:
definicia operatorov
rek. struktura vyrazu
vyhodnocovanie, bez premennych, s premennymi (predavane v prostredi)
kazda spojka ma popis semantiky 
  (pr. and - nespravne, spravne s opakovanim, bez op.)
  - nemame moznost parametrizacie procedur (hi-or. kod)

DC: 
1. vybudovanie vyhl. stromu AC
1a. rozdelenie zoznamu na triedy ekvivalencie (podla prveho pismena)
2. uprava vyhodnocovanie na preklad do zasobnikoveho stroja

6.cv.
"xref" : vypis funktorov termu s cetnostami (bez pocitania) 
...

7cv. (priprava)
- grep(Str, Reg, Poloha) :- retazec Str odpoveda regularnemu vyrazu Reg 
od zaciatku do dlzky Poloha.
- kompilacia ofarbenia grafu do prologu
(- fold pre ine struktury)
(mozno nabuduce: setof ...: dynamicke progr., prehl. gr. do sirky)

8.cv.
dynamicke programovanie
-------------------------------------------------


1-2. cv. rodokmen:
	surodenci, rodicia, nejstarsi bratr ...
okrem predikatu rodic/2 dalsie predikaty: manzele(M,Z), rodina(M,Z,Deti), ...

dve reprezentacie pre pohlavie
1) muz(adam). zena(bozena).
2) pohlavi(muz,adam). pohlavi(zena, bozena).
Repr. je abstraktnejsia a obecnejsia. Jej prvy argument je novy "vyctovy typ".
V 2) je pohlavie ako data, napr. mozem porovnavat, v 1) je schovane v mene 
predikatu. 
- Analogicky dve reprezentacie pre bohatsie triedy: botanicky kluc, zivocisna 
hierarchia
- Prevod medzi reprezentaciami (pouzije sa len jeden - pre spravny smer)
pohlavi(muz,X) :- muz(X). ...
muz(X) :- pohlavi(muz,X). ...
  - retazec muz je v prvom a stvrtom pripade atom (konstanta, funkcny symbol 
s nulovou aritou), v 2. a 3. pripade predikatovy symbol. Sucasny vyskyt nevadi.

Q: negativne informacie: ako definovat sirotu?
zatial len: pridat do DB. (neskor negacia a CWA - predpoklad uzavreteho sveta)

DC: opravdu nevlastni sourozenec
onsour(X,Y) :- rodic(RX,X), rodic(RXY,X) , RX\=RXY, 
		rodic(RXY,Y), rodic(RY,Y), RXY\=RY, RX\=RY, X\=Y.
DC: bratranec ...
I. najstarsi bratr.
II. reprezentacia fronty

-------------------------------------------------
2.cv.
datumy: moznosti reprezentacie 
1) [2001,10,9]
2) datum(2001,10,9)
2') datum(2001,rijen,9)
3) datum(9,10,2001)
4) datum(den(9),mes(10),rok(2001))
5) [rok(2001),mes(10),den(9)]
5') datum([rok=2001,mesiac=10,den=9])
6) datum(rok=2001,mesiac=10,den=9)
7) "2001-10-9"  retazec
8) '2001-10-09' atom
a dalsie varianty

vhodne riesenie: 2) alebo 3), pre 2) bude naviac zdarma usporiadanie datumov
nevyhody:
7) a 8) - nie je to struktura, netrivialny pristup na zlozky
1) zoznam sa bude pliest s inymi zoznamami, naviac mierne pamatovo neefektivny 
	- a osetrovanie vacsej pamate stoji vacsi cas !!
4) pomenovanie v d.s. sa nevyuzije, to nie je zaznam s pomenovanymi zlozkami
	vyberanie casti/zloziek je dane polohou argumentu 
5), 5') pamatovo neefektivne, nutne postupny pristup na zlozky pomocou 
	member - ak nie je fixovane poradie; ak je fixovane, tak mozem 
	pouzit kompaktnejsiu repr. 2.)
    - nevhodne, ak mame pevny vycet poloziek; 
	ak je vycet poloziek premenny (ale to je iny pripad), potom 5) je riesenie
	(viz "zaznamy" v Haskelli)
6) pamatovo neefektivne, na polozky sa pristupuje polohou, nie menom
	
2') operaciu "za mesiac" musim zadat vyctom; v 2) staci pricitat 1

- v jednom programe je mozno pouzivat viac reprezentacii s roznymi 
	funkcnymi symbolmi
  - prevody a udrziavanie konzistencie je na programatorovi (jazyk nepodporuje)
prevod 2' na 2: 
mk_datum2(datum_r2a(R,M1,D),datum(R,M,D)):- prevodm(M1,M).
prevodm(1,leden).
...
prevodm(12,prosinec).

----------------------------------------
--navrhy d.s.
nerekurzivnych: hradla (potrebuju ZOZNAM vstupov), ...
rekurzivnych:
- pr: elektr. schema (par. a sekv.), layout 2d (novinovej) stranky, graf, 
binarny strom, 2-3 strom, polynomy, synt. strom programu a vyrazu, Html & XML
  -  layout2d: ne zcela obecny, len delenim stranky
stranka -> pod(stranka,stranka); vedle(stranka, stranka); 
		sloupek(text); fotka(binary)
	- navic: parametry: pod(params,s,s) ...

- unarne cisla: plus, krat, ...

zaver:
- pomocou termov je mozne reprezentovat d.s.
- (nizka) pamatova neefektivnost sposobuje casovu neefektivnost 

-----------------------------------------
3. CV. 20.10.2000.
opakovanie append/3

-- mappend/2 (Xs,Ys)
multiappend: spoji zoznam zoznamov Xs do jednoho zoznamu Ys. 
  Len jedna uroven vnorenia.
Zobecnenie append na viac nez dva zoznamy.
mappend([],[]).
mappend(([X|Xs],Ys):-
  append(X,Ys1,Ys), %(1)
  mappend(Xs,Ys1).  %(2)
-Q(uestion): preco append moze byt pred rek. volanim mappend
	A: Premenna Ys1 sa vyuziva ako logicka premenna, pri 
volani append ostane volna a neskor (v rek. volani) sa substituuje.
-- prehodenie (1) a (2) by bolo mozne. Z hladiska toku dat by bolo cistejsie.
?- mappend([[1,2],[],[3,4],[a]],X). % volanie
  X=[1,2,3,4,a]

-- na mappend vysvetlena strukturalne rekurzia (podla prveho argumentu)

-- prefix/2
- dve varianty: 
a) rekurzivne napisana
b) pomocou append
prefix(X,P):- % X je prefix P
  append(X,_,P).
- prefix ako specialne pouzitie append
- rekurzivne napisany prefix je "projekcia" append na prislusne argumenty (1. 
    a 3.)
- podla sub b) sa lahsie pisu podobne predikaty, napr. suffix 
  - pretoze pouziva predikaty z "kniznice"
-Q: mody: (nemali na prednaske)
	A: mozne mody 1. (+,+), 2. (+,-) 3. (-,+) 4. (-,-)
1. OK, pouzitie ako test: splni sa alebo nesplni sa
2. OK, Vysledok je jeden. 
	- analogicky mod u suffixu sa zacykli, pretoze vysledkov je vela
3. OK, pouzitie ako generator: generuje (pomocou backtrackingu) prefixy,
	od najkratsieho
4. CYKLI, nekonecne mnozstvo rieseni
?- prefix(X,P)
X=[],    P= _1
X=[_2],    P= [_2|_1]
X=[_2,_3],    P= [_2,_3|_1]
...
pozn.: volne premenne vystupuju ako podtrzitko a cislo:
syntakticky je to (volna) premenna, cislo je nejaka interna 
reprezentacia, tj. zhodne premenne maju zhodne cislo.

-- DC (supl. 18.10): preskumat chovanie member(a,X)

-- suffix/2 
- viz minule pozn.
- mody
- specialne mod (?,-) 
  riesenie v tomto pripade nejde vyjadrit v kompatnej podobe!
  pretoze rekurzia je riadena druhym argumentom, ak nie je vstupny, 
  program cykli v backtrackingu (pricom vydava nekonecne mnoho roznych! rieseni)
-Q: poradie vysledkov: od najdlhsieho
	- od najkratsieho by to slo pouzitim akumulatora

-- suffixy/2 (Xs,Sss)
	Pre vstupny zoznam Xs sa vyrobi zoznam vsetkych jeho sufixov (pripon) 
v zozname Sss. Typovo: Sss je zoznam zoznamov.
- predikat suffix mohol tiez generovat vsetky pripony, ale (len) pomocou
backtrackingu. AK taketo riesenie nevyhovuje, vydanie vysledku (v zozname,
naraz a deterministicky) je obecnejsie.
- pouzitie: vygenerujem explicitne sufixy do zoznamu a potom ich 
dalej spracovavam, napr. vyberiem z nich tiem, ktore splnaju nejaku 
dalsiu podmienku.
(ped.: suffixy su jednoduchsie nez prefixy)
suffixy([],[[]]). % (1)
suffixy([X|Xs],[[X|Xs]|Ss]):- % (2)
  suffixy(Xs,Ss).
- v (1) je vysledkom , (jednoprvkovy) zoznam, ktory obsahuje prazdny zoznam
- v (2) sa vstupny zoznam kopiruje (mierne neefektivne)
- generovane v poradi od najdlhsieho

-- prefixy/2 (Xs,Pss)
- idea rekurzivnej klauzule: strukturalne rekurzia podla vstupnehpo zoznamu Xs,
tvorim zoznam prefixov Pss1 v rekurzii, ku kazdemu prefixu musim pridat
prvy prvok, a naviac pridat pradzny prefix.
prefixy([],[[]]).
prefixy([X|Xs],[[]|Pss]):-
  prefixy(Xs,Pss1),
  map_pridejX(X,Pss1,Pss). %(1)
-Q: poradie generovanych prefixov: od najkratsieho
-Q: jednoprvkovy zoznam (resp. vsetky dlhsie) vo vysledku vznikne 
pridanim prvku X k prazdnemu zoznamu vratenemu z rekurzie (resp. k ostatnym)
- map_pridejX(X,L1,L2): konkretne v tomto pripade chceme ku kazdemu 
prvku zoznamu L1 pridat (na zaciatok) prvok X. Obecna myslienka je spracovanie 
zoznamu (L1) tak, ze na kazdy jeho prvok sa vykona ta ista operacia a vytvori 
sa novy prvok vystupneho zoznamu L2. Zatial pre obecne parametricke zadanie 
operacie nemame prostriedky, ale myslienka (progr. idiom) je obecny. Predikat 
tohoto druhu sa nazyva map.
V map_pridejX (aj map obecne) ide o transformaciu 1:1, tj. vstup aj 
vystup su rovnako dlhe.
map_pridejX(_,[],[]).
map_pridejX(X,[L|Ls],[V|Vs]):-
  V=[X|L],  % (1) 
  map_pridejX(X,Ls,Vs).
- v (1) je operacia explicitne oddelena od zvysku programu, tj. da sa zmenit,
	 ak chceme inu funkcionalitu
  - alebo zaintegrovat do hlavy klauzule, ak chceme optimalizovat

-- rozobratie reverse
- dva (klasicke) sposoby
  poroznanie asymptotickej zlozitosti
- idea akumulatora
	- mame pristup na uz spracovane casti (zoznamu)
	  - na rozdiel od skladania substitucii 
	    (resp. spracovanie vysledkov z rekurzie)
	-Q!: nutnost vystupneho argumentu
	A: Vysledky zanorene v rekurzii musime dostat na povrch.
- nutnost interface: schovanie pritomnosti akumulatora a jeho inicializacie

--generuj a testuj - pre backtracking 
--generuj a filtruj - pre zoznam moznosti
- vhodne, len ak pocet vsetkych moznosti nie je omnoho
vacsi nez pocet uspesnych moznosti.
  - ak je generovanie postupne, aj testovanie ma byt postupne 
	(odmietnutie (fail) co najskor), pr. damy
  pr: nevhodne: kombinacie z podmnozin - lepsie specialny generator

DC 18.10.: 
b) subset/2
k danemu zoznamu reprezentujucemu mnozinu generovat (/testovat) vsetky 
podmnoziny, poradie prvkov je v zhodnom poradi so vstupom
c) subsets/2 
 dtto, vratit vsetky podmnoziny v zozname

-- do buduca:
pr: sublist, subpart, halve ...
filter - idea
map obecne
--------------------------------------------------------------
-- podmnozina
moznosti: 
a) generovanie
b) zoznam podmnozin
  - v oboch pripadoch je riesenie O(exp(n)), a) cas, b) cas aj priestor
  => nie je vhodne pre metodu generuj a testuj, lepsie pouzit specialne 
generatory

% subset(+Set,?Subset)
subset([],[]).
subset([I|Is],Os):-
  subset(Is,Os).
subset([I|Is],[I|Os]):-
  subset(Is,Os).

Q: poradie generovania:
 - pridavame od poslednych prvkov
 - poradie v ramci mnozin: zdedene zo vstupu.

varianta:
- vybranie zaverecnej unifikacie "za zatvorku"
subset([],[]).
subset([I|Is],Os):-
  subset(Is,O1),
  (Os=O1 ; Os=[I|O1]).
- v tomto pripade sa "vybranim za zatvorku" neusetri cas ani pamat.
  - ak by bol predikat deterministicky, tj. z oboch vetiev sa 
uplatnila len jedna, potom takato zmena moze program zefektivnit
(napr. zjenotenie/union a prienik/...)

b) vsetky podmnoziny v zozname
- subsets(Is,Os).
subsets([],[[]]).
subsets([I|Is],Os):-
  subsets(Is,O1),
  map_pridejX(I,O1,O2),
    % map(pridej(I),O1,O2), % obecne map
  append(O1,O2,Os).
% pridej(I,L,[I|L]).
- map: obecne pouzitelny vzor rekurzie, dostava 
proceduralny(!) parameter

-----------------------------------------------------------
-- reprezentacia fronty:
- len idea, bez kodu
chceme pridavat dopredu zoznamu, uberat z konca
-Q: ako navrhnut d.s. rozumne
A: kym pridavame, OK, ak chcem ubrat, tak obratime (naraz) vsetky dosial 
pridane prvky a uberieme zase hlavu.
d.s. q(Pridane, Obratene)
prazdna fronta: init(q([],[])).
add_q(X,q(P,O),q([X|P],O).
get_q(X,q(P,[X|O]),q(P,O)). % je z coho uberat
get_q(X,q([],[]),_):- error('get_q: vybirani z prazdne fronty').
get_q(X,q(P,[]),V):-  % (kl3)
	P\=[]  %(1)
	reverse(P,O),
	get_q(X,q([],O),V). % taky moznost
- (1) obrana pred zacyklenim - nekonecnym obracanim prazdneho zoznamu
- misto kl3: 
get_q(X,q(P,[]),q([],O)):-  % (kl3)
	P\=[]  %(1)
	reverse(P,[X|O]). %(2)
-(2) vyuzivam vlastnost logickych promennych: castecne urcena vystupna 
premenna nevadi

---------------------------------------------------------------
26.10. 4.cv.
-- vyroba vyvazeneho stromu a delenie zoznamu na polovicu
- rozdelenie zoznamu na polovicu:
  - vcetne osetrenia lichej dlzky
moznosti:
a) spocitat dlzku, potom vydelit a rozdelit
b) delit postupne pri prechode zoznamu
  b1) suda - licha
  b2) prva cast, druha cast
(c) spocitat dlzku, pomocou append rozdelit a nasledne vybrat spravnu dlzku.

ad a,c) pouziva sa predikat length/2 z kniznice, resp. prednasok
- pouzivanie predikatov z kniznic, resp. obecne dopredu pripravenych 
predikatov je rozumne, vhodne a podporovane.
ad c) metoda generuj a testuj: 
generuj pomocou append (v mode (-,-,+) ), testuj - vyber spravnej dlzky.
  - v tomto pripade je tato metoda nevhodna (neefektivna), pretoze sa 
generuje prilis vela moznosti, a v podstate sa nepouzije informacia, ze 
predikat "rozdelenie na polovicu" je deterministicky. (sposobuje 
neefektivitu pri backtrackingu a spotrebu pamati - info o backtrackingu 
sa musia niekde ulozit)

ad b1) priamociare
ad b2) 1) spocitanie dlzky - viz a)
	- pouzije sa predikat rozdel - specialne pre tuto ulohu
	- pouzije sa take/3 a drop/3 (Haskell) - 
	take(+N, +-Is, -Os) vezme z Is prave N prvych prvkov do Os, ak existuju
		vsetky, ak ich je menej
	drop(+N, +-Is, -Os) zahodi z Is prave N prvych prvkov, zvysok do Os
	2) kopia zoznamu sa pouzije ako citac a bude sa prechadzat 
		dvojnasobnou rychlostou 	

- pozn.: neskor to budeme potrebovat  ako rozdelenie na prvu a druhu cast,
preto to programujeme takto.
Ina uloha je rozdelenie na sude a liche.
b2-2) %halve1(+I,+Counter,-O1,-O2)
halve1(O2,[],[],O2).
halve1(O2,[_],[],O2).
halve1([I|Is],[_,_|C],[I|O1],O2):-
  halve1(Is,C,O1,O2).
- chyba interface, ktory schova arg. Counter

a) 
halve2(I,O1,O2):-
  length(I,N),
  N1 is N div 2,
  rozdel(I,N1,O1,O2).
rozdel([],N,[],[]).
rozdel(Is,0,[],Is).
rozdel([I|Is],N,[I|O1],O2):-
  N>0, % !nutny test
  N1 is N-1,
  rozdel(Is,N1,O1,O2).
  - rozdel je obecne, nemusi platit N > |I|.
  - invariant rozdel: O1++O2 = I and (O2 = [] or N = |O1|)
  - v Haskelli su "take" a "drop", ktore vracaju (len) prvy, resp.
    druhy zoznam. 
Ak sa to robi naraz, je to efektivnejsie.

-- vyroba vyvazeneho stromu: bolo na prednaske
mk_tree([],nil).
mk_tree(I,T):-
  halve(I,I1,[X|I2]), % potrebujem |I2|>=|I1|
  mk_tree(I1,T1),
  mk_tree(I2,T2),
  T=t(T1,X,T2).
- X moze byt strukturovane, napr. Key-Value
- osetrenie jednoprvkoveho vstupu je zbytocne 
  (znizuje efektivitu a priehladnost kodu, vracia viac rieseni)

----------------------------------------------------
-- lookup(K,V,S)
- vyhladavanie podla kluca: ku klucu Key chceme v strukture Struct
  najst hodnotu Value
- mozna reprezentacia dat.str.: zoznam, strom, (kombinacie) ...
- lookup je interface pre vyhladavanie k d.s.
- lookup moze byt v principe nedeterministicky, 
  - ak nedeterminizmus d.s. nepodporuje (efektivne), mozeme vracat
    zoznam vsetkych hodnot
a) struktura je zoznam, ktory obsahuje dvojice Key-Value
lookup(K,V,S):-member(K-V,S).
b) struktura je binarny vyhladavaci strom
  - musime mat aj usporiadanie na klucoch, nielen rovnost!
struktura stromu: 
b1) bud stvorica, kde je kluc a hodnota samostatne
  vyhladava sa podla kluca
type tree(TK,TV):- nil; t(tree(TK,TV),TK,TV,tree(TK,TV))
b2) trojica, pricom kluc a hodnota su spojene, podobne ako 
vyssie v zozname, vyhladava sa len podla prvej zlozky

% lookups, stromove, pre t/3
%lookups(K, void, _V) :- fail. % nenaslo
lookups(K, t(L,K1-V1,R), V) :-
	K=K1    -> V=V1	% priradenie vystupu
      ; K @< K1 -> lookups(K,L,V) % porovnanie termov(1), rekurzia
      ; /*K@>K1*/  lookups(K,R,V) % druha rekurzia
(1) pretoze porovnavam termy (nielen cisla), je kod "polymorfny"
vzhladom k typu kluca 
(-> funguje aj pre strukturovane kluce, ale s vstavanym usporiadanim)

- lookup je (jedna z procedur pre) univerzalny interface pre vyhladavanie
  (pre pracu so strukturou potrebujeme este 
	vytvorenie/pridavanie/update struktury)
  (<- ak ma byt program nezavisly na konkretnej strukture, musi byt 
	nezavisly aj na tvorbe struktury, resp. ta musi byt schovana)
  - Prolog nepodporuje zdruzovanie struktur a kodu (v objektoch alebo moduloch)   

-- lookup2d(K,V,S)
(lookup v dvoch dimenziach, K = K_1 x K_2)
- dtto, ale kluc je strukturovany, dvojzlozkovy
  - minuly kod funguje ( je "polymorfny" vzhladom k strukture kluca)
- metody: 
a) ako lookup, nevyuziva 2d strukturu
  -> neefektivita, ak su kluce huste
	kazdy kluc sa porovnava cely
b) vyhladavanie podla prvej zlozky, ako hodnota sa vrati 
vyhl. struktura podla druhej zlozky, v nej sa hlada podla 
druhej zlozky
  - kazda uroven moze mat inu vyhl. strukturu 
	-> a pouzivat ine procedury
napr. vonkajsia uroven strom , vnutorna zoznam:
lookup2d(K1-K2,V,S) :- 
	lookups(K1,S,S1),	% vonk. strom
	lookup(K2,S1,V).	% vnut. zoznam

DC 2) prevod 2d stromu na zoznam s 2D klucom

-------------------------------------------------------
5.cv. 3.11.
- vyhladavanie s multidimenzionalnym klucom
  - ako minule: kluc je zoznam klucikov 
A) jednoduchsia varianta: vsetky kluce su rovnako dlhe 
   repr. : zoznam
priklad dvojice: [1,a]-a1 :: [klic]-hodnota
lookupD([],S,S).
lookupD([K|Ks],H,S):-
  lookup(K,HS,S),
  lookupD(Ks,H,HS).
- ak je kluc neprazdny, vyhlada sa na 1 urovni pomocou 
klasickeho lookup (v prislusnej d.s.). Tato prva uroven vrati 
vyhl. strukt. podla zbytku kluca, na ktoru sa vyhl. vola rekurzivne.
  - tentokrat na vsetkych urovniach musi byt roznaka d.s., pretoze
	vsetky kluciky vyhladavame rovnakou procedurou

B) kluce roznej dlzky
- mozna kolizia: kluc je prefix ineho -> d.s. musi vracat Hodnotu
aj zbylu vyhl. strukturu
- povodna hodnota v tvare H:S
lookupD([],H,H:_S).
lookupD([K|Ks],H,_H:S):-
  lookup(K,HS,S),
  lookupD(Ks,H,HS).
- v oboch pripadoch, aby rekurzi mohla (uniformne) ist cez kluciky,
musia byt vyhl. struktury na jednotlivych urovniach stejne.
  - v pripade klucov ako dvojic (vyz vyssie) moze byt struktura 
na kazdej urovni ina, pretoze nepotrebujeme rekurziu cez urovne.
-Q: ako odlisit: s d.s. niest (typovu) info o vyhl.s. na prislusnych
urovniach

-------------
- tvorba vyhl. strukt. (pre kluce zhodnej dlzky)
dve moznosti: 1) inkrementalne a 2) davkovo
ad 1) inkrementalne:
na zaciatku razdna d.s., postupne pridavam dvojice po jednej
- nevyhoda: pomale, mnoho medzivysledkov -> spotreba pamate (docasna)
2) davkovo: 
predpokladame, ze mame dvojice v zozname.
idea: podulohy: a) rozdelit dvojice na "triedy ekvivalencie" podla 
prveho klucika do zoznamu, b) potom vybudovat rekurzivne vyhl. struktury
pre jednotlive triedy ekv., do zoznamu, c) vybudovat vyhl. strukt. 
pre prvy klucik
  - pozn. 
a) aby dobre fungovala rekurzia, mali by sa kluce skracovat
(v triedach ekv. vzhladom k celku)
b) pomocou map(stavba_strukt) na ziskany zoznam
c) ak je jednourovnova v.d.s. zoznam, tato cast je prazdna
a) implementacia rozkladu na triedy ekv.:
  - obecna vyrovba tried ekv.
triedy ekv. su charakterizovane proc. parametrom :: a->a->Bool,
ktory urcuje, ci dva kluce patria do stejnej triedy ekv. 
  - dimenzia usporiadania
  1) usporiadane kluce: - staci usporiadanie podla prveho klucika,
potom delit na suvisle sekcie
  2) neusporiadane kluce: postupne vyberat triedy rozkladu ekv. 
s prvym este nespracovanym prvkom.
- proceduralnym parametrom Feq! 
%eqrozklad( +Feq, +Zoznam, -Triedy)
eqrozklad( _F, [], []).
eqrozklad(  F, [I|Is], [[I|T]|Ts]):-
  mk_test(F,I,TestEq), % ! progr. vyssieho radu (lambda)
  rozdel(TestEq, Is, T, Zb),
  eqrozklad(F, Zb, Ts).
- predikat rozdel je zobecneny filter, ktory rozdeli prvky Is 
na vyhovujuce a nevyhovujuce podmienke. (filter vracia len 
vyhovujuce)
  - parametry rozdel/4: v prvom moze byt kontext predavany 
podmienke alebo obecne podmienka (vcetne kontextu).
% rozdel(P, In, Out1,Out2)
rozdel(P, [], [], []).
rozdel(P, [I|Is], Same, Other):-
  (test(P,I) -> Same = [I|Same1], Other=Other1
             ;  Same = Same1, Other=[I|Other1] ),
  rozdel(P, Is, Same1, Other1).
- a jine varianty ...
  (DC) napr. sucasne rozdelovanie do "tried ekvivalencie"

- tvorba vyhl.d.s. - kluce roznej dlzky
  - ide o dopredne vyhladavanie v algoritme Aho-Corasick
- v com sa zmeni idea:   
  - zvolime nejaku hodnotu pre neexistujuce kluce (!monady)
    v nasom pripade 'nic'
a0) vyhladame a odstranime zo zoznamu dvojicu s prazdnym klucom
  jej hodnota (ak existuje, inac nic) bude prva cast vysledku (H v H:S).
- rozdelenie, rekurzia a vybudovanie prvej urovne vyhladavania su 
stejne
d) vysledok je dvojica Hodnota:Struktura 

----------------------------------------------
bool. vyrazy: (niekde by to uz malo byt spisane?!)
struktura, vyhodnoicovanie, kompilacia
(analogia k mnozinovym vyrazom, ktore su na prednaske)
	
def. d.s. - bv ako bool. vyraz
obsahuje konstanty true, false, 
	spojky and/2, or, xor, imp, ekv, non/1
	premenne - neskor
argumenty spojek su zase bv.
type bv(T) :- true;false;
	non(bv(T)); and(bv(T),bv(T)); ...
	prom(T)

- def. operatorov
umysel: non viaze najviac (najnizsia precedencia), 
and nad nim dolava asoc. , or, imp doprava, ekv neasoc
:- op(200,  fy, non).
:- op(210, yfx, and).
:- op(215, xfx, [nand,xor]). % napriklad
:- op(220, yfx, or).
:- op(230, xfy, imp). % doprava asoc.
:- op(240, xfx, ekv).

- pr.: prom(a) imp prom(b) imp prom(a) and prom(b)
se pochopi obvyklym sposobom:
imp(prom(a),imp(prom(b),and(prom(a),prom(b))))
- pr.: vyraz  true ekv true ekv true 
je syntakticky chybne, ekv je neasociativne

-- vyhodnocovanie bv, bez premennych
- pomocou strukt. rekurzie:
% eval(+vyraz, ?hodnota)
eval(true,true).
eval(false,false).
eval(non(B),V):- 
	eval(B,V1), % rekurzia
	eval_non(V1,V).	% vyh. spojky
eval(and(B1,B2),V):-
	eval(B1,V1), eval(B2,V2),
	eval_and(V1,V2,V).
... analogicky pre ostatne spojky.

- pomocne predikaty:
% eval_non - vyctom: spracuva len konstanty  
eval_non(true, false).
eval_non(false, true).

- eval_and: tri moznosti:
1) implicitna chovanie pre "ostatne" pripady (CHYBNE!)
eval_and(true, true, true).
eval_and(_,    _,    false).
- program nie je deklarativne spravne, pretoze 2. klauzula
sa splni aj pre ?- eval_and(true,true, false). !
  - pri backtrackingu vrati nespravne riesenie
  -> kazda klauzula musi mat spravne podmienky (straz)

2) neuplny rozbor pripadov (deklarativne spravne, ale)
eval_and(true, true, true).
eval_and(false,_,    false).
eval_and(_,    false, false).
- volanie ?- eval_and(false, false, X). sa splni dvakrat
  - nasledny kod sa opakovane vyhodnocuje

3) (skoro) uplny rozbor pripadov
eval_and(true, true, true).
eval_and(true, false, false).
eval_and(false,_,    false).
- deklarativne aj proceduralne spravne
- argument, podla ktoreho robime rozbor pripadov 
(a strukturalnu rekurziu) by mal byt vstupny

- eval - pokracovanie
1) kazdu spojku je mozne osetrit samostatne vs.
2) odvodene spojky popiseme pomocou uz znamych pripadov
% implikace
eval(A imp B, V):- eval(non A or B, V).

% ekvivalence
2 moznosti:
1) eval(A ekv B, V):- eval(A and B or non A and non B, V).
  - ale A a B sa vyhodnocuju dvakrat
2) eval(A ekv B, V):- 
	eval(A,VA), 
	eval(B,VB),
	eval(VA and VB or non VA and non VB, V). 
	   % obecny! eval s jednoduchsimi spojkami 

-- vyhodnocovanie s premennymi: 
- aby sme mohli spocitat hodnotu vyrazu, potrebujeme vediet 
hodnoty premennych. Tie predame v novom argumente, ako kontext.
- novy interface: eval(+Tab_prom, +BV, -Hodnota).
  - v tab prem. budeme hladat pomocou lookup a preto na konkretnej
	strukture nezalezi (z hladiska textu programu)
  - kontext sa pri spracovani spojek predava nezmeneny do rekurzie
- premenne budeme v d.s. reprezentovat pomocou funktoru prom/1
ktory ma argument meno premennej.
  - nevhodne reprezentacia: za premenne by sme mohli povazovat
	vsetky ine identifikatory nez konstanty a spojky, ale ...
  - premennu by sme odlisili len tak, ze by sme testovali, ci 
	nepatri medzi vyhradene identifikatory
    pr: eval(T, X, V) :- % X ma byt premenna
		X \= true, X\= false, X\= and(_,_), ...
		X \= non(_), vyhodnot_premennu(T,X,V).
  - pri pridani dalsej spojky, ktora by sa nahodou volala zhodne 
	s pouzivanou premennou by sa zavliekli chyby.
  - Q,A: vo vyrazoch nepouzivame Prologovske premenne, ale logicke 
premenne, ktore su reprezentovane prologovskymi termami: 
prom(meno) 

eval(_T, false, false).
eval( T, true,  true ).
eval( T, A and B, V) :-
	eval(T, A, VA), eval(T, B, VB),
	eval_and(VA,VB,V). % bez zmeny
... dalsie klauzule analogicky
% novy pripad:
eval( T, prom(X), V) :- lookup(X,V,T).

- volanie, napr.:
?- eval([a-true,b-false,c-nedef], prom(a) and non prom(b), V).
  V = true

Q: je mozne reprezentovat hodnoty premennych predikatom v databazi?
- mozne to je, ale nevhodne. 
  ak potrebujem vyhodnotit rovnaky vyraz pre dve ohodnotenia, musim
	pracovat s databazou!

---------------
DC: (kompilator bv.)
- do zasobnikoveho stroja
  - je jednoduchsi nez RAM, pretoze nealokujem pamatove bunky.
  - premenne su alokovane pod svojimi menami -> nepotrebujem ich
	ohodnotenie
comp(K, [load(const(K))]) :- K=true;K=false. % konstanty
comp(prom(X), [load(X)]).
comp(A and B, CC) :-
	comp(A,CA), comp(B,CB),
	mappend([CA,CB,[and]],CC).
comp(A imp B, CC):-
	comp(A,CA), comp(B,CB),
	mappend([CA,[non],CB,[or]],CC).
comp(A ekv B, CC):- % netrivialne (!)
	comp(A,CA), comp(B,CB),
	mappend([CA,	% ...,VA zasobnik
		 [dup,non],	% VA,nVA
		 CB,		% VA,nVA,VB,
		 [dup,non,take(3),and,  % VA,nVA,VB,nVAB
		  drop(3), 	% VA,VB,nVAB : chcem op. ne na vrcholu
	  	  store(tmp),and,load(tmp),	% VAB,nVAB
		  or]
                ],CC).
- potrebujeme nejake specialne instrukcie pre ovladanie zasobniku:
  napriklad:
  dup duplikuje vrchol (= take(1))
  take(i) vytiahne i-tu polozku zvrchu a da ju na vrchol
  drop(i) zahodi i-tu polozku zvrchu
  - (kod aj instrukcie postupnym vyvojom)

(pr: uprava vyrazov)
--------------------------------------------------------------
7.cv
- grep(Str, Reg, Poloha) :- retazec Str odpoveda regularnemu vyrazu Reg 
od zaciatku do dlzky Poloha.

pouzivane reg. vyrazy: 
RV::= *(RV), % iteracia
	RV+RV, % zjednotenie
        RV:RV, % sekvencia
	[Znaky], %mnozina jednotlivych znakov
        lam, % prazdne slovo - lambda
        ff % nesplnitelny RV !

- nesplnitelny RV (empty) potrebujeme pre vystup vysledkov

grep: moznosti: 
0) (kombinatory parserov)
1) priama interpretacia - backtrackingom => nasobne odpovede
2) konstrukcia konecneho automatu
3) kontrukcia vyrazu po prechode znakom (derivacia)

ad 2): vytvaranie prechodoveho stromu a stotoznenie rovnakych vyrazov

ad 3):
grep(Ss,RV,N):- grep1(Ss,RV,0,N). % zavedenie akumulatora
grep1(_Ss, RV, N,N):-acc_empty(RV). %koncovy pripad
grep1([S|Ss],RV,N,O):-
  next(S,RV,RV1), N1 is N+1,
  grep1(Ss,RV1,N1,O).

%next(X,RV,RV1): pocitanie derivacie RV podla X, 
%  RV1 popisuje VSETKY zvysky po prijati X.
next(X,*(RV),RV1: *(RV)):-next(X,RV,RV1).
next(X,RV1:RV2,RV0):-next(X,RV1,R1),next(RV2,R2),
  (acc_empty(RV1) -> RV0 = R1:RV2+R2
                  ;  RV0 = R1:RV2    ).
next(X,RV1+RV2,R1+R2):-next(X,RV1,R1),next(X,RV2,R2).
next(X,Zn,RV0):- 
  member(X,Zn) -> RV0 = lam % prijatie, zvysok prazdny
               ;  RV0=ff.   % odmietnutie, z. nesplnitelny
next(_,lam,ff). % nieco vratit musime, dovod zavedenia ff
next(_,ff,ff).
                
% acc_empty strukturalnou rekurziou
acc_empty(*(_)).
acc_empty(RV1+RV2):-acc_empty(RV1);acc_empty(RV2).
acc_empty(RV1:RV2):-acc_empty(RV1),acc_empty(RV2).
%acc_empty([_|_]):-fail.
acc_empty(lam).
%acc_empty(ff):-fail.

- zjednoduseni RV:
zjednodusia sa podvyrazy, potom sa pouzije pravidlo
%zjRV(RV, Zjednoduseny_RV)
zjRV(*(RV1),RV0):-zjRV(RV1,RV2),prav(*(RV2),RV0).
zjRV(RV1+RV2, RV0):-zjRV(RV1,R1),zjRV(RV2,R2),prav(R1+R2,RV0).
zjRV(RV1:RV2, RV0):-zjRV(RV1,R1),zjRV(RV2,R2),prav(R1:R2,RV0).
zjRV(RV1, RV0):-list(RV1), RV0= RV1. % RV1 je seznam
zjRV(lam, lam).
zjRV(ff,ff).

- varianta: aby zjednodusovanie bolo deterministicke:
  namiesto volanie prav(I,O) volat one(prav(I,O)):
one(X):-call(X),!. % zakaze backtracking.

% zjednodusovacie pravidla by mali byt deterministicke
% ... ale nie su. Namiesto rezov: one(
prav(*(*(RV)),*(RV)). % rozbor pripadov do druhej urovne
prav(*(lam),lam).
prav(*(ff),ff).
prav(RV1+ff,RV1). % ff je neutralne pre zjednotenie
prav(ff+RV1,RV1).
prav(RV1:lam,RV1). % lam je neutr. pre sekvenciu
prav(lam:RV1,RV1).
prav(RV1:ff,ff). % ff je "nula" pre sekvenciu
prav(ff:RV1,ff).
prav(RV1+RV2,RV0):-list(RV1),list(RV2),RV0 is_set RV1\-/RV2.
% ... atd
prav((RV1+RV2)+RV3, RV1+(RV2+RV3)). % reasociacia
% dtto pre :
prav(X,X). % zachytne pravidlo, pre vsetky ostatne pripady
	% toto sposobuje nedeterminizmus !

------------------------------
map a fold: pre binarne stromy, pre n-arne ...
- zmena myslenia: praca s celymi d.s.
- fold nie je dost obecne
  - minimum potrebuje fold1
  - vkladanie do stromu potrebuje pristup na vstupy
    - (tj. primitivna rekurzia), mozno obist, ale neefektivne
- specialne: fold niekedy nestaci a je nutne pouzivat interfaceovy
predikat. Niekedy su vnutorne struktury pouzite pri rekurzii bohatsie
nez to, co sa vyzaduje na vystupe. Napr. priemer zoznamu: musime
pracovat s dvojicou suma,dlzka , a na konci vypocitat priemer.
... i ine
- prehl. stromu do sirky: vystupy su strukturovane po urovniach, na
konci sa musime dodatocnej struktury zbavit.

-----------------------------------
kompilacia ofarbenia grafu DO Prologu

vstup: graf, orientovany, acyklicky, odzadu (hrany vedu do vrcholov, 
	ktore uz su ofarbenem (tj. su pred! akt. vrcholom), 
	reprezentacia: sousede (tj. predchodcovia)
vystup: zoznam dvojic Meno_vrcholu - Farba ako vystupna datova struktura 
	po spusteni ciela a prologovsky ciel, ktory 
	kazdemu vrcholu priradi Farbu (zdielanu cez premennu)
  - zoznam dvojich potrebujem, aby som vedel, ktora premenna odpoveda 
ktoremu vrcholu

- idea spracovania: farbenie/3 pre dany graf G vyrobi ciel C a Obarveni. 
Po spusteni ciela C sa v Obarveni vracaju mozne obarvenia.
Ciel C potrebuje run-time podporu (viz) a interface: barvy/1, ktory 
vracia povolene barvy backtrackingom

farbenie(graf2(G),C,Obarveni) :- farb1(G,C, [], Obarv).
farb1([], true, Obarv, Obarv).
farb1([V-Sousede|Vs], 
	(barvy(B),  % novy ciel; farba akt. vrcholu
         and_list(Kontrola),  % kontrola sousedu
	 C1),	% zvysny ciel
      Acc_obarv, Obarv) :-	
  mk_kontrola(B,Sousede,Acc_obarv,Kontrola), %vyroba ciela
  farb1(Vs,C1,[V-B|Acc_obarv],Obarv). % rekurzia s novym Acc

%mk_kontrola :- vyroba ciela pre kontrolu:
mk_kontrola(B,Ss,Obarv,Kontrola):- % kontrola je seznam volani
  map(preklad_hrany(B,Obarv),Ss,Kontrola).
preklad_hrany(B,Obarv,S,Kontr):-
  lookup(S,Obarv,SB), % farba k susednemu vrcholu
  Kontr=(B\=SB). % ciel: spravnost ofarbenia hrany V(B)-S(SB)

% run-time support (alias lokalne ciele):
and_list([]).
and_list([X|Xs]):- call(X),and_list(Xs).
% varianta: prelozit a zavolat:
and_list(L):- preklad_and(L,C),call(C).
 %preklad_and(L,C):- fold(true, mk_and, L, C).
 % mk_and(A,B,(A,B)).
preklad_and([X],X). % optimalizovane
preklad_and([X|Xs],(X,CXs)):- preklad_and(Xs,CXs).

%interface: barvy musia byt nejak zadane!
barvy(B):- member(B,[1..101]).

Pr:
?- G=graf2([v1-[],v2-[v1],v3-[v1,v2]]),
   farbenie(G,C,Obarv).
 vystup: (mnou pomenovane premenne budu v realnom vystupe 
	len "_cisla")
Obarv= [v3-B3,v2-B2,v1-B1] % v opacnom poradi
C = barvy(B1),and_list([]), % and_list lze rozgenerovat
    barvy(B2),and_list([B2\=B1]),
    barvy(B3),and_list([B3\=B1,B3\=B2]), 
    true

- and_list lze rozgenerovat; takto je to jednodussi
-----------------------
8. cv.
dynamicke programovanie.
po�iadavky: program nap�san� obecne, nie pre konk�tnu �lohu.
�lohy: najlep�ie naplnenie batohu, optim�lna triangul�cia ...

Vlastnosti �loh d.p.: opakuj�ce sa pod�lohy, optim�lne rie�enie �lohy sa
sklad� z optim�lnych rie�en� pod�loh (tj. budeme si pre pod�lohy pam�ta�
len jednu hodnotu, a to opt. rie�enia). Aby sme mohli zrekon�truova� aj
opt. rie�enie, m��eme si pam�ta� hodnotu parametra, pre ktor� sa
dosiahlo optima.

Idea: rekurz�vne spracovanie mus�me riadi� sami, preto�e Prolog by
po��tal opakovan� volania viackr�t. Mo�n� rie�enie: tabel�cia -
konkr�tne zavedieme akumul�tor, ktor� bude obsahova� u� spo��tan�
(definitivn�)
hodnoty (de fakto tabel�cia). Po��ta� budeme zhora, tj. od po�adovan�ho
cie�a (alebo cie�ov). Okrem uz spo��tan�ch vrcholov si budeme pamata�
otvoren� vrcholy, tj. tak�, ktor� potrebujeme spo��ta�, ale nem�me e�te
pre ne medziv�sledky.

In� mo�nost: po��tanie zdola a �pln� vypl�ovanie tabu�ky (matice, ...).

Implement�cia:
- rekurz�vne podla otvoren�ch vrcholov. V�dy sa sna��me jeden spo��ta�,
ak to ide. Ak e�te nie s� vrcholy s  medziv�sledkami spo��tan�, resp.
nie s� v zozname otvoren�ch, prid�me ich k otvoren�m (na za�iatok).
Obidva zoznamy udr�ujeme bez opakuj�cich sa prvkov.

d_p(Init,Tab):-
  d_p([Init],[],Tab), % spustenie v�po�tu
  % lookup(Init,Tab, Hodnota), % Ak n�s zauj�ma len hodnota
  % rekonstrukcia_riesenia(Init,Tab, Riesenie). % ..

%d_p(otvorene, akum, v�stup)
d_p([],Tab,Tab). % vsetko je spo��tan�, akum na v�stup
d_p([O|Os],Ds,T) :-
  element�rne(O) ->     % koncov� podmienka (1)
    spocti_elem(O,OH),  % v OH je opt. hodnota (a vo�ba param.)
    d_p(Os,[OH|Ds],T)   % pridanie do akum a rekurzia
  ; predch(O,Ps),       % n�jdeme zoznam predchodcov k O
    (su_spocitani(Ps,Ds) -> % Ps je podmno�. Ds
      spocti_vnitrni(O,Ps,Ds,OH), % vypo�et OH
      d_p(Os,[OH|Ds],T)
    ; zmen_poradi(Ps,[O|Os],Ds,Os1), %Os1:=(Ps union [O|Os])\Ds (2)
      d_p(Os1,Ds,T)
    ).

pozn.
(1) koncov� podmienky by mali byt o�etren� tak, aby sa do tabu�ky
neprid�vali fikt�vne prvky (pre umelo dodefinovan� hodnoty)
(2) Ps sa pridava na za�iatok, ak sa to nem� zacykli�
- predpoklad�me, �e z�vislosti vyd�van� pomocou predch/2 s� necyklick�
- preto�e sme pou�ili lookup pre vyh�adanie optima, predpoklad�me, �e
spo��tan� hodnoty OH s� v tvare Kluc-Hodnota, kde Kluc je jednozna�n� a
hodnota je pr�padne �trukturovan� a odsahuje hodnotu optima a hodnotu
parametra, ktor� zaru�il optimum.

- proced�ry su_spocitani a zmen_poradi su nez�visle na �lohe.
Ostatne procedury: elementarne/1, spocti_elem/2, predch/2,
spocti_vnitrn�/4 s� z�visl� na �lohe. Popis �lohy mus� by� zadan�
pomocou t�chto proced�r. Pr�padne by celkov� n�vrch mohol by�
interpreta�n�, kedy by tieto proced�ry dost�vali naviac jeden parameter
s popisom vzorcov (a medz� ...), ktor� by vhodne interpretovali.

- tabu�ka definit�vnych, prip. tabu�ka otvoren�ch, vrcholov m��e by�
�trukturovan�. Potom mus�me upravi� pr�slu�n� vyh�ad�vancie a
porovn�vacie proced�ry.

---------------------------------------------------------

zvysky 2000,2001
-OPAK:
  - backtracking vs. zoznam uspechov
  - metoda generuj a testuj
    - nie je vzdy vhodna
  - (navrh a) pouzivanie kniznic
    - zobecnenie predikatu
  - spravnost voci backtrackingu
  - efektivita
  - invariant (volania, uspechu)
  - konecnost vypoctu
  - map: obecny predikat, proceduralny param.

DC: 1) kombinacie
    2) prevod 2d stromu na zoznam s 2D klucom

ESTE
-- (zip(+I1,+I2,Out): mody (+, )
-- konstrukcia 2D stromu, 2D zoznamu
  - rozklad na triedy podla kluca, map (
-- transpozicia matice
-- kombinacie: opt. na nizkej urovni:
 - pocitat kolko prvkov este mozem vyhodit, aby som poznal 
  situaciu, ked musim vziat cely zvysok. 
  (idea: znizujem citac k nule)
-- rozkladne ulohy (?)

5.cv. 3.11.2000
Q: algebrogram
fibonnaciho cisla - logaritmicky: minule roky
  Q: rozdiel '='/2 a is/2:  vystup ako sucet jedniciek
     - typove chyby

DC: 
1) rozdel, 
  pouzitie rozdel pre prienik a zjednotenie
2) rozdel 
  v com sa zmeni davkova konstrukcia v.d.s., ak mame kluce 
premennej dlzky
--------------------------------------------------------------
6. cv, 10.11. 2000
plan:
interprety vyrazov
 bool, aritm, s premennymi, s funkciami, kompilator
and - or stromy
------------------------------------------------------------------

Prolog:
1999
  1.cv: Univerz�lny v�pis pam�ti; zlo�en� d.�.
  2.cv (4.,8.10.): un�rna repr. ��sel: skladanie subst., akumul�tor na
s��tan� a n�soben�, struktur�lna rekurzia; ot�zka: ide s��tanie pou�i�
pre od��tanie? zavedenie zoznamov, d��ka zoznamu (un�rna) - obojsmern�,
zip dvojice zoznamov do zoznamu dvoj�c (nejasn� konvencia oper�torov�ho
'-') - rekurzia cez dva argumenty, aplik�cia: tabulka druh�ch mocn�n.
DC(po): a) vyrobit zoznam druh�ch mocn�n k zoznamu ��sel (tj. map_sqr)
b) transpoz�cia matice
(p�): ot�zky: d.�. datum/3, d�vody kon�truktora (mk_datum), podtypov�
polymorf. (proced�ra na prevod z inej, bohat�ej �trukt�ry);
rodinn� vz�ahy: s�rodenci (vlastn� a nevl.) sestra, teta, DC:
bratranec; unifik�cia, occur check; un�rna repr., plus a kr�t skladan�m
subst., zlo�itos� $O(n)$ vs. $O(n^2)$ DC: ako sa chov� kr�t, ak je najprv
s��tanie a potom rekurz�vne volanie.
        3cv, 11.10'99: prefix, suffix, mappend, transpoz�cia, naviac:
flatten, zip?, kombin�cie DC: podmno�iny, prienik, zjednotenie
(15.10) ++ v�roba vyv��enej haldy zo zoznamu, kombin�cie, prienik DC:
komb s opakovan�m, zjednotenie
        4.cv 18.10'99 prienik, zjednotenie mno��n, pre usporiadanu aj
neusporiadanu reprezentaciu, idea rozdielu, predikat is_set/2:
vyhodnocovanie mnozinov�ch v�razov (s usporiadan�mi mno�inami), s
premenn�mi, is_set ako interpret, zjednotenie usporiadan�ch mn. bolo
na predn��ke ako s��as�
mergesort; aritmetika: fibonaciho ��sla zostupne, DC fib.c. vzostuone
(s akumulatorom), idea f.c. logaritmicky: delenim intervalu, umoc�ovan�m
mat�c
(22.10.) is_set/2 a operacie, potom s premennymi, zjednotenie/rozdiel aj 
akumulatorom, DC: relacne vyrazy s mnozinami, (nejasnosti okolo operatorov)
trie ako predkompilovany vyhladavaci strom pre AC alg., d.s. v tvare 
vnorenych zoznamov, vyhladavanie, DC: rozmysliet konstrukciu.
	5. cv. Po 25.10: suplovane: grafy (?)
               pa: odpadlo.
        6. cv. Po 1.11: precvicovanie vstavanych predikatov z prednasky:
- @<, ... neprecvicovane, pouzitie v triedeni
- xref: Pre dany term (s premennymi) vytvorit zoznam vsetkych funkcnych symbolov 
(s cetnostami v tvare F/N). Atomy su s cetnostou 0, premenne sa ignoruju. 
(pouzije sa funktor, =.., var, atomic, number). Vytvaranie zoznamu zdola, 
s pouzitim is_set. Varianty: dtto, ale aj s poctom vyskytov: namiesto is_set 
pouzit "is_bag" , ktore as postara aj o vyskyty.  Rez: Klauzula, ktora sa stara o zlozene 
termy v troch variantach: 1) pomocou compound, 2) pomocou negativnych testov 
(notvar(T), \+ atomic(T), ...) 3) pomocou rezu v minulych klauzulach 
- == : len idea: test vyskytu premennej v terme
- name: generovanie symbolov, pr.: generovanie mien premennych, ak chceme 
k riedkej reprezentacii termu vygenerovat vyraz s x1, x2, ...
- operatory: navrhnute operatory pre boolovske vyrazy
- precvicenie setof: prienik, (zjednotenie, rozdiel) mnozin napisany pomocou 
setof. Varianta: zjednotenie  pre multimnoziny.
        Pa: dtto
        7.cv. Po 8.11. map, fold (naz�van� na predn��ke zpracuj) pre
bin�rne stromy. Predik�t size ako aplik�cia fold. DC: map pomocou fold,
map a fold pre n-�rne stromy; pokus o v���� pr�klad: generovanie
vyh�ad�vacieho stromu Aho-Corasickov�.
        Pa 12.11: grafy: dve reprezentacie, v d.�, interface vrchol a
hrana, moznost reprezentacie v db, obsahuje meno grafu /nepou��va�/.
Nadstavba: stupen, susedia vrcholu; prevody reprezentacii - pomocou
setof. Problemy s dvomi reprzentaciami: interface ku konkretnej
reprezentacii, alebo viac interface /a mozmost prevodu/, alebo lepsie
/dynamicke/ typovanie: data si nesu typ sebou: potom interface pozna
konkretny typ argumentu /d.s./
        8.cv 15.11. Po ukoncenie Prologu: pisomka: z trie vytvorit
usporiadany zoznam slov /tj. zoznamov pismen/. Potom Scheme:
ZAklad rekurzie: sucet zoznamu, abstrakcia tejto funkcie, zavedenie
cons, car, cdr: map, fold, faktorial pomocou enum /prevod intervalu
daneho cislami na zoznam/ a fold. DC: map pomocou fold, zobecnenie enum:
s parametrom pre "krok" /a testovanie konca/
Q: co je na FP deklarativneho
 (pa): pisomka z Prologu; zoznamy, map, transpozicia matice, ...
        9.cv. 22.11. otazky: apply, eval, '(1 2) vs (list 1 2): '(1 2)
znamena d.s  a nie funkciu k vyhodnoteniu, apply umoznuje volanie
funkcii z neznamym poctom (tj. dynamicky zadanym) argumentov;
transpozicia matice, map pre matice, map pre

  PISOMKOVe priklady 15. a 19.11.1999:
Za neuspesne napisanie pisomky mate odovdzat niekolko prikladov. Vyberte
si z lahkych zapoctovych (napr. 201,203,205,210,320,321...). Odovzdajte
na papieri, za dva tyzdne (6.12. resp. 10.12.)
  10-8 bodov: ziadny
     (typicky technicke chyby)
   7-4 body: odovzdat jeden lahky zapoctovy priklad
     (typicke chyby v toku dat a predavani argumentov)
   3-0 bodov alebo neucast: dva priklady a pisomkovy, spolu tri.
     (typicky nepochopenie rekurzie)

(po): Je dana datova struktura trie, ktora reprezentuje niekolko
postupnosti pismen. Moze byt prazdna, konkretne atom void. Alebo
neprazdna s funkcnym symbolom t/4 a argumentami lavy podstrom (podtrie),
znak, vnoreny podstrom a pravy podstrom. Predpokladame a pouzivame
usporiadanie na pismenach. Reprezentacia zoznamu postupnosti pomocou
trie je takato: prazdny zoznam je void. Ak mame neprazdny zoznam,
vyberieme si nejake pociatocne pismeno lub. postupnosti. Trie bude s
funktorom t/4 a argumenty budu urcene takto. Vsetky postupnosti
zacinajuce mensim pismenom su v lavom podstrome, vsetky zacinajuce
vacsim pismenom su v pravom podstrome. Znak, tj. 2. arg., je vybrane
pismeno. Vo vnoremom podstrome su reprezentovane vsetky postupnosti
zacinajuce vybranym pismenom, ale bez tohoto pismena. Na vyvazenosti
nezalezi. (V takto navrhnutej datovej strukture nemame explicitne urceny
koniec kazdej postupnosti a preto nedokazeme reprezentovat sucasne
postupnost aj jej prefix). Ulohou je k danemu trie vyrobit
(usporiadany) zoznam postupnosti' pismen, ktory trie reprezentuje.
  Idea: trie je vyhladavaci strom, v ktorom je treti argument naviac.
Spracovanie je rekurzivne, pricom prazdny vnoreny podtrie sa osetri
zvlast. 

%main: prevod(Trie,Sez)
prevod(void,[]).        % odpoveda prazdnemu zoznamu postupnosti
prevod(t(L,X,void,R),V):- % odpoveda prazdnej postupnosti
  prevod(L,VL), prevod(R,VR),
  append([[X]],VR,V1), append(VL,V1,V).
prevod(t(L,X,P,R),V):-
  prevod(L,VL), prevod(R,VR),
  prevod(P,VP), pridej_prefix([X],P,VP),
  append(VP,VR,V1), append(VL,V1,V).
pridej_prefix(_,[],[]).
pridej_prefix(Pref,[X|L],[X0|L0]):-
  append(Pref,X,X0),
  pridej_prefix(Pref,L,L0).

(pi):
Je dany n-arny strom s funktorom s/2, kde argumenty su symbol a zoznam
postromov v zhodnej reprezentacii. V zozname postromov sa moze
vyskytovat spec. symbol void. Pre dany strom chceme vydat v jednom
(usporiadanom) zozname vsetky cesty z vrcholu do kazdeho z vrcholov,
listovych i medzilahlych. Kazda cesta je zoznam, ktory bude obsahovat
dvojice: symbol vo vrchole podstromu a poradove cislo podstromu v
zozname. Spec. symboly void v zozname podstromov pocitame do poradia,
ale ony netvoria ziadne cesty vo vystupe. Pre koren na poradi nezalezi,
napr. chceme na vystupe 0. Listy su podstromy, ktore maju zoznam symov
prazdny. Nepouzivat setof a bagof.
  Idea: Zapamatame si prefix, ktory popisuje cestu k aktualnym vrcholom
v strome a ktory musime pridat ku kazdej ceste v aktualnych stromoch.
Dalej si pamatame poradove cislo aktualneho podstromu, ktore sa
inicializuje pri vstupe do zoznamu postromov.
  Varianta: bez pamatania prefixu, ale zoznam vysledkov z podstromu
musime spracovat pomocou pridej_prefix, viz minuly priklad.

% cesty(strom,cesty)
cesty(Strom,Cesty):-              % init
  cestyl([Strom],0, Pref, Cesty). % zoznam postromov, poradie, prefix,
                                        % Out
cestyl([], _N,_P,[]).   % vysledok skladanim medzivysledkov
cestyl([s(Sym,Pod)|Ss],N,P,C):-
  append(P,[Sym-N],P1), % zmena prefixu pre podstromy
  cestyl(Pod,1,P1,C1),  % podstromy akt. stromu
  N1 is N+1,
  cestyl(Ss, N1, P, C2 ), % bratia akt. stromu
  append([P1|C1],C2,C). % spojenie vysledkov, v poradi
cestyl([void|Ss],N,P,C):-
 %  append(P,[Sym-N],P1), % zmena prefixu pre podstromy
 % cestyl(Pod,1,P1,C1),  % podstromy akt. stromu
  N1 is N+1,
  cestyl(Ss, N1, P, C ). % bratia akt. stromu
 % append([P1|C1],C2,C). % spojenie vysledkov, v poradi

volanie:
?- cesty(s(a,[s(b,[]),void,s(c,[])]), C).
C=[[a-0],[a-0,b-1],[a-0,c-3]]

-------------
- abstrakcia a parametriz�cia: zobecnenia faktori�lu (a �o to stoj�!?):
doln� hranica, zoznam ��sel (generovanie zoznamu: aritm. post., �ub.),
abstrahovanie od n�sobenia (-> fold1); stoj� to: pred�vanie hodnot,
generovanie ( a in� pomocn�), pred�vanie oper�cie ...
- program ako data, data ako program
- is-set ako interpret, varianty: multimno�iny, usporiadan� mno�iny
-------------
2.cv; 1.10.1996
pr: % rodic/2
rodic(adam,bozena).
rodic(adam,bohus).
muz(adam).
zena(bozena).

- definujte je_rodic/1 ak m� nejak� die�a:
je_rodic(X):-rodic(X,_).
% _ je anonymn� premenn�

- zistite, �i rel�cia/proced�ra rodic/2 je definovan�
je_def_rodic :- rodic(_,_).
/* ako uka�ka, �e v jednom cieli m��e by� viac (nezavisk�ch)
     anonymn�ch premenn�ch */

- mama/2:
mama(X,Y):- rodic(X,Y),zena(X).

- (nevlastn�) s�rodenci
sourozenec(X,Y):-
     rodic(R,X),
     rodic(R,Y),
     X \= Y.     % X je r�zne od Y

- vlastn� s�rodenci
a) vl_sourozenci1(X,Y):-
     rodic(R1,X), rodic(R1,Y), X  \= Y,
     rodic(R2,X), rodic(R2,Y), R1 \= R2.
b) vl_sourozenci2(X,Y):-
     otec(R1,X), otec(R1,Y), X  \= Y,
     mama(R2,X), mama(R2,Y).

-DC: bratranec/sest�enice

----- 3.cv: 8.10.1996
definicia pristupovych procedur k datovym typom:
  d.s. datum(Rok,Mes,Den)   napr. datum(1996,10,1)
pristupove proc: get, set, make:
% get___
  get_rok(datum(R,_,_),R).
  get_mes(datum(_,M,_),M).
  get_den(datum(_,_,D),D).
% set___
% musia mat tri arg.: stary datum, novy datum a menenu informaciu
  set_rok(R,datum(_,M,D),datum(R,M,D)).
  set_mes...     % analogicky
% make_datum: vytvorenie zo zloziek:
  make_datum(R,M,D,datum(R,M,D)).
pr. pouzitia:
za_rok(Dnes,Za):-get_rok(Dnes,R), R1 is R+1, set_rok(R1,Dnes,Za).

---un�rna reprezent�cia ��sel
0   ...   0
s(X)...   n+1, kde X repr. n

- test typu un�rneho ��sla (bolo na pred.)
     idea: rekurziou pod�a �trukt�ry un�rneho ��sla
je_unarne_cislo(0).
je_unarne_cislo(s(X)) :- je_unarne_cislo(X).
! pou�enie ka�d� rekurzia mus� kon�i� (faktom)

- s��tanie
a) rekurzia pod�a prv�ho arg. (je mo�n� aj pod�a druh�ho)
     v�sledok vznik� skladan�m substit�ci�
   plus1(  0, Y, Y).
   plus1(s(X),Y,s(Z)) :- plus1(X,Y,Z).
   volanie: ?- plus1( s(s(s(0))), s(s(0)), Z)
           Z  = s(s(s(s(s(0)))))
   /* Z vznik� skladan�m substit�ci�, postupne v rekurzii:
     ?- plus1( s(s(s(0))), s(s(0)), Z)
          Z = s(Z1), taky X1 = s(s(0)), Y1 = s(s(0))
     ?- plus1(  s(s(0)), s(s(0)), Z1) /* tj. plus1(X1,Y1,Z1) */
          Z1 = s(Z2), X2 = s(0), Y2=Y1=s(s(0)), proto
          Z = s(s(Z2))
     ?- plus1(    s(0), s(s(0)), Z2)
          Z2 = s(Z3), X3 = 0, Y3=Y2, proto
          Z = s(s(s(Z3)))
     ?- plus1(      0, s(s(0)), Z3)
          Z4 = Y4 = Y3 = s(s(0)), proto
          Z = s(s(s(s(s(0)))))
     konec

b) rekurzia pod�a prv�ho arg., v�sledok vznik� akumul�ciou
   plus2(  0, Y, Y).
   plus2(s(X),Y,Z) :- plus2(X, s(Y), Z).
   volanie ako minule
   /* Y je akumul�tor, v �om sa akumuluje spr�vne hodnota a na
     konci sa pred� na v�stup, Z je v�stupn� hodnota a po�as
     rekurzie sa nemen� */

- od��tanie
a) minus1(X,Y,Z):- plus1(Y,Z,X).
     prologovsk� pravidl� s� viacsmerov� (ob�as).
   minus1a(X,Y,Z):-plus1(Z,Y,X).
     obdobne ide pou�i� plus2
b) priamo, rekurzia pod�a druh�ho arg.
     minus2(X,0,X).
     minus2(s(X),s(Y),Z) :- minus2(X,Y,Z).
- nasobenie - pomocou scitania

-- pou�enia: (z 3. cv)
- tok d�t
- defin�cia "typov"
- �truktur�lna rekurzia
- dva sp�soby z�skania v�sledku
  - skladan�m substit�ci�; v�po�tom z medziv�sledkov
  - akumul�cia v ur�itom argumente

----------------------------------------------
--- 4.cv. 15.10.1996
- opakovanie z predn��ok:
  append([],L,L).
  append([X|L1],L2,[X|L3]):-append(L1,L2,L3).

operacia so zoznamami:
-- prefix(?Pref,+Zoz):- Pref je prefix zoznamu Zoz.
a) prefix([],_).
   prefix([X|Xs],[Z|Zs]):-prefix(Xs,Zs).
b) prefix(P,Z):- append(P,_,Z).

-- suffix(?S,+Z):- S je suffix (pripona) Z
a) suffix(S,S).
   suffix(S,[_Z|Zs]):-suffix(S,Zs).
b) suffix(S,Z):- append(_,S,Z).
   -- rekurz�vny prefix/2 a suffix/2 je vlastne proojekcia na prv� a
tret�, resp. druh� a tret� argument u append/3.

-- podzoznam(?P,+Z):- P je podoznam Z
podzoznam(P,Z):- append(_,X,Z),append(P,_,X).

-- DC vybran� podpostupnos�, tj. vlastne v�etky podmno�iny.
   subset(Sub, L):- ...

-- mappend(ZZ,Z):- ZZ je zoznam zoznamov, vsetky prvky ZZ (,ktore
su zoznamy,) chcem spojit do jednoho zoznamu Z v danom poradi.
Je to zobecnenie bin�rneho append na n-ticu vstupov.
mappend([],[]).
mappend([X|Xs],V):- mappend(Xs,V1), append(X,V1,V).
     %  v  tomto  pripade,   pretoze  vysledok  vznika  skladanim
substitucii, by rekurzivna klauzula mohla mat aj prehodene ciele.
Tret� argument by v tom pr�pade bol neukon�en� zoznam , tj mal na konci
voln� premenn�, do ktorej by sa v rekurzii sunstutuovalo a nakoniec  by
sa uzavrela pr�zdnym zoznamom. Napr. pri volan�
?- mappend([[a],[b,c],[],[d]],L ) by L nadob�dalo postupne hodnoty
L = L'
L = [a|L'']
L = [a,b,c|L''']
L = [a,b,c|L'''']
L = [a,b,c,d|L''''']
L = [a,b,c,d]

-- DC: mappend pomocou akumulatora.

-- scitanie cisel v zozname:
% sum(Xs,S):- S je sucet/suma cisel zo zoznamu Xs
sum([],0).
sum([X|Xs],S):- sum(Xs,S1), S is S1 + X.

-- abstrakcia oper�ci� v �truktur�lnej rekurzii:
! vsimnite si "strukturalnu" podobnost medzi sum a mappend, lisia
sa  len   operaciou,  ktorou  sa   spracovavaju  medzivysledky  a
vysledkom spracovania prazdneho zoznamu.

-- flatten:  pozbieranie prvkov zo zoznamov  bez ohladu na uroven
vnorenia
flatten([],[]).  % spracovanie prazdneho zoznamu
flatten([H|T],V):- flatten(H,VH),  % spracovanie neprazd. zoznamu
                   flatten(T,VT),
                   appent(VH,VT,V).
flatten(A,[A]):-             % spracovanie jednoho prvku
     A \= [], A \= [_|_].    % ktory neni zoznam !

pr. volania:
flatten([1,[],[[a],b],[2]],V).
     V = [1,a,b,2];
     no
  - uvedomte si dolezitost testov v poslednej klauzuli
  - tento predikat nema jednoducho popisatelny "typ"

-- rekurzia cez viac vstupn�ch argumentov.
  zip/3: dost�va dva vstupn� zoznamy zhodnej d��ky, vr�ti zoznam dvoj�c.
  Dvojice s� pre na�e ��ely �trukt�ry s funk�n�m symbolom - (m�nus),
ktor� budeme zapisova� oper�torovo, tj. X-Y namiesto -(X,Y).
  zip([],    [],    []).
  zip([X|Xs],[Y|Ys],[X-Y|Zs]):- zip(Xs,Ys,Zs).
  - predpoklad�me (a overujeme), �e zoznamy s� rovnako dlh�.
  - ak by sme chceli variantu, ktor� vyd� v�sledok pod�a d��ky
krat�ieho, nahradili by sme koncov� podmienky:
  zip([],_,[]).
  zip(X,[],[]):- X\=[].
  - Podmienka X\=[] zabezbe�uje, aby pre roznako dlh� zoznamy (volanie
?-zip([],[],[]) to neuspelo dvakr�t.
  - abstrakcia: predik�t zip/3 vyd�va pevn� datov� �trukt�ru. Ale
oper�cia, ktorou sa maj� spoji� dve hlavy, vlastne nez�vis� na rekurzii,
a mohla by sa pred�va� ako parameter. (Zatia� na to nem�me technick�
prostriedky.) Proced�ra by vyzerala:
*  zip(Oper,[],    [],    []).
*  zip(Oper,[X|Xs],[Y|Ys],[Z|Zs]):-
*    "Oper"(X,Y,Z),  % chybn� syntax
*    zip(Oper,Xs,Ys,Zs).
Pre ka�d� konkr�tnu oper�ciu m��eme nap�sa� variantu predik�tu zip.
V kontr�tnom pr�pade je oper�cia definovan� faktom mk_dvoj(X,Y,X-Y).

-- analogicky: dva v�stupn� zoznamy, napr. rozdelenie zoznamy na dva
zoznamy zhruba rovnakej d��ky. S� dve met�dy delenia: a) sud� - lich�,
b) prv� �as�, druh� �as�. Druh� met�da m� v�hodu, �e zachov�va poradie,
hod� sa teda pre usporiadan� zoznamy (, ke� to rekurzia o nich
predpoklad�)

a) rozdel1([],[],[]).
   rozdel1([X],[X],[]).
   rozdel1([X1,X2|Xs],[X1|Ys],[X2|Zs]):- rozdel1(Xs,Ys,Zs).

  - d� sa implementova� aj trochu in�m sp�sobom, ke� poradie v�sledn�ch
zoznamov prehadzujeme. Ktor� sp�sob je (�asovo) efekt�vnej�� by sa
muselo zmera�.

a2) rozdel2([],[],[]).
    rozdel2([X|Xs],[X|Ys],Zs):-rozdel2(Xs,Zs,Ys).

b) Pri delen� na prv� a druh� �as� je mo�n� spo��ta� d��ku a tu potom
pou�i� na ur��enie po�tu prvkov v oboch �astiach. (viz nesk�r) In� mo�nos�
je pou�i�
vstupn� zoznam aj ako ��ta� d��ky (v zvl��tnom argumente). Ak z neho
budeme ubera� prvky po dvojiciach, potom po�et rekurz�vnych vnoren� bude
odpoveda� po�tu prvkov prv�ho zoznamu. Pr�padn� nep�rny prvok nech�me v
druhom zozname. Inicializ�cia ��ta�a je v �vodnej klauzuli.
   rozdel3(Xs,Ys,Zs):-rozdel3_1(Xs,Ys,Zs,Zs).
   rozdel3_1(Xs,[],Xs,[]).
   rozdel3_1(Xs,[],Xs,[_Y]).
   rozdel3_1([X|Xs],[X|Ys],Zs,[_,_|Us],):-rozdel3_1(Xs,Ys,Zs,Us).

   - DC: Ako m�me zmeni� program, ak chceme, aby nep�rny prvok bol v prvej
�asti?

-- transpoz�cia matice
  Matica je zoznam zoznamov, pr jednoduchos� predpoklad�me, �e matica je
korektne zarovnan�.
  Je nieko�ko mo�nost�, ako nap�sa� transpoz�ciu matice.
a) Z danej matice vyberieme z ka�d�ho riadku prv� prvok, tie d�me do
zoznamu, ktor� bude tvori� prv� riadok v�sledku. �alej pre rekurziu
priprav�me "zost�vaj�cu" maticu, tj. �o ostane po ubran� prv�ch prvkov.
Konkr�tne chceme do zoznamu pozbiera� tel� v�etnk�ch riadov matice, a
v�sledok spracova� rekurz�vne. Obidva medziv�sledky m��eme z�ska� po�as
jednoho prechodu maticou. Pri tomto spracovan� je vonkaj�ia
rekurzia cez d��ku riadkov, vn�torn� cez po�et riadkov.

b) In� mo�nos� je prehodi� poradie rekurzi�. Vonkaj�ia by spracovala
v�dy jeden riadok povodnej matice, vn�torn� by zabezpe�ila prechod
riadkom a pridanie ka�d�ho prvku do odpovedaj�ceho zoznamu. Preto�e
d��ka riadkov v�sledku sa postupne zv���uje, mus�me si da� pozor, aby
sme nezv��ili zlo�itos� (z O(n^2) na O(n^3)).

a) transp([[]|_],[]). % pr�zdna matica je zoznam pr�zdnych riadkov
   transp(M,[R|V]):-
     vytvor_radky(M,R,M1),
     transp(M1,V).
   vytvor_radky([],[],[]).
   vytvor_radky([[H|T]|M],[H|R],[T|M1]):-
     vytvor_radky(M,R,M1).

b) t2([R],V):- listify(R,M).
   t2([R|M],V):- t2(M,V1), zip(mk_list,R,V1,V).
   mk_list(H,T,[H|T]).
   listify([],[]).
   listify([H|T],[[H]|V]):-listify(T,V).
  - pou�il som zobecnen� zip s oper�ciou mk_list. Konkr�tna verzia sa
z�ska rozpisom.
  - proced�ra listify/2 vyrob� zoznam jednoprvkov�ch zoznamov, tj.
transpoz�ciu jednoho vektora. Podobne ako u zip/3 je mo�n� z nej
abstrahova� oper�ciu, ktor� vyjadruje rel�ciu jednoho prvku vstupu a
v�stupu. V tomto pr�pade to bola rel�cia mk_jednoprvkov�(H,[H]).

-- kombin�cia a spol. bez po��tania
  Kombin�cie (a vari�cie) budeme vybera� z explicitne dan�ho zoznamu
prvkov - b�ze. V pr�pade kombin�ci� nez�le�� na porad�, tj. m��eme si ho
zvoli�. Vyberieme si poradie pod�a b�ze. Po�et prvkov v�stupu m��e by�
dan� ��slom (viz ni��ie), ale aj zoznamom s vo�n�mi premenn�mi
pr�slu�nej d��ky. Dve rekurz�vne klauzule umo��uj� (nedeterministick�)
v�ber, �i nejak� prvok do v�sledku prid�me alebo nie.
  komb(_,[]).
  komb([X|Xs],[X|Ks]):- komb(X,Ks).
  komb([X|Xs],   Ks) :- komb(X,Ks).
alebo
  komb2(_,[]).
  komb2([X|Xs],[K|Ks]):- X=K, komb2(Xs,Ks)
                       ; komb2(Xs,[K|Ks]).

  - DC: bez opakovania

-- variacie bez opakovania:
/* vari(K,N,V):- pomocou backtrackingu vydava vo V vsetky
 * variacie o K prvkoch bez opakovania zo zoznamu N
 */
     vari(0,_N,[]).
     vari(K,N,[V|Vs]):- K>0, K1 is K-1,
           delete(V,N,N1),
           vari(K1,N1,Vs).

-- DC: variacie s opakovanim
-- ? kombinacie s/bez opakovania

--- 22.10.1996
DC: kombinacie bez opakovania:
% komb(K, N, V). N je zoznam prvkov, z ktor�ch vyberame K prvkov.
V�sledky sa vydavaj� backtrackingom v premennej V.
     komb(0,_N,[]).
     komb(K,N,[V|Vs]):- K>0, K1 is K-1,
           append(_,[V|N1],N),     % podobne variaciam
           komb(K1,N1,Vs).
in� mo�nos�:
     komb1(0,_N,[]).
     komb1(K,[N|Ns],[N|Vs]):- K>0, K1 is K-1,
           komb1(K1,Ns,Vs).   % prvok N sme vybrali
     komb1(K,[_N|Ns],Vs):- K>0,
           komb1(K,Ns,Vs).    % prvok _N sme nevybrali

- fibonaciho cisla
  klasick� defin�cia:
  fib1(N,F):-fib1a(N,F,F1). % N-t� a (N-1)-t�
  fib1a(1,1,_).
  fib1a(2,1,1).
  fib1a(N,F,F1):- N>2, N1 is N-1, fib1a(N1,F1,F2), F is F1+F2.

  DC: fib cisla akumul�torom, odspodu
  - a mnoho in�ch mo�nost�: po dvoch ...

  - logaritmicky:
    (funguje to, len ak s� po�iato�n� hodnoty 1 a 1, obecnej�ie, viz
ni��ie)
  �vaha: f_n= 1* f_{n-1} + 1* f_{n-2}
            = f_2 * f_{n-1} + f_1 * f_{n-2}
            = f_3 * f_{n-2} + f_2 * f_{n-3} = ...
            = f_i * f_{n-i+1} + f_{i-1} * f_{n-i}
  �peci�lne: (ak som to dobre spo��tal)
   f_{2n+1} = f_{n+1}^2 + f_{n}^2
   f_{2n}   = f_{n+1}*f_n + f_{n} * f_n * f_{n-1}
            = f_n^2 + 2 * f_n * f_{n-1}
            = 2 * f_{n+1} * f_n - f_{n}^2

  potom v Prologu: (neodladen�)
  fib2a(1,1,0).
  fib2a(2,1,1).
  fib2a(N,F,F1):- N>2, N1 is N//2,
                 (N =:= 2*N1 -> fib2a(N1,F2,F3),  % alebo is/2 v podm.
                               F is F2^2+2*F2*F3,
                               F1 is F2^2 + F3^2  % ??
                             ; N2 is N1 +1,
                               fib2a(N2,F2,F3),
                               F is F2^2*F3^2,
                               F1 is 2*F2*F3 - F3^2
                 ).

  - p�vodn� my�lienka: n�sobenie mat�c:
    <f_{n+1}, f_n> =  / 1  1 \  f_n
                      |      |
                      \ 1  0 /  f_{n-1}
    a n�sobi� r�chle matice u� viete.
    - t�to my�lienka (resp. spo��tanie prvkov n-tej mocniny matice) sa
mus� pou�i�, ak po�iato�n� hodnoty nie s� 1 a 1.

  - (pou�i� Knuth-Bendixov alg. na zistenie/overenie t�chto vzorcov)

- mergesort - na predn��ke
  - rozdelenie zoznamu na sude a liche

DC: rozdelenie usporiadaneho zoznamu na dve zhodne �asti

-- (21.10.1999, pre Hr�zu, nedokon�en�)
-- pr�prava: Cvi�enie: aritmetika, pr�ca s maticami, dynamick�
   programovanie
- �loha: Je dan� (konvexn�) n-uholn�k. M� sa n�js� jeho triangul�cia,
ktor� m� minim�lny s��et d��ok hr�n.
  Idea: pre dva vrcholy i,j (v danom poradi) po��tame hodnotu minim�lnej
triangul�cie od i do j. Az m�me min. hodnotu pre (1,n), sme hotov�.
Minim�lnu hodnotu pre (i,j) spo��tame za predpokladu, �e u� pozn�me
hodnoty pre krat�ie pod�seky takto:
  zna�enie: t(i,j) je hodnota min. triangul�cie medzi i,j v�etne hrany
(i,j). �alej d��ka hrany medzi i,j je d(i,j), v zmysle triangul�cie, tj.
d(i,i+1)=0. Po�iato�n� podmienky: t(i,i+1)=0. (Mo�no som si neuvedomil
a nepop�sal spr�vnu okrajov� podmienku pre druh� okraj, tj. d(1,n)=0)
  Rekurz�vny vz�ah: t(i,j) = min(k=i+1 to j-1; t(i,k)+t(k,j)+d(i,j))
  Dynamick� programovanie znamen�, �e opakujuce sa �lohy t(i,j) sa
nebud� znovu po��ta� (rekurziou).
  Dve mo�nosti naprogramovania: (a) explicitne po��tanie matice, vonkaj��
cyklus cez vzdialenost i-j, vn�torn� cez i. (b) po��tanie rekurziou, ale
spo��tan� v�sledky pre t(i,j) sa pred�vaj� v akumul�tore.

  - program pre (b)
%mt(vrcholy, hodnota, Stav)
- d.�.: vrcholy: zoznam s�radn�c X-Y, stavy s� zoznamy prvkov tvaru
p(i,j,hodnota, deliaci_bod), deliaci bod je ��slo vrcholu, pre ktor� s
nadobudlo minima. Stavy sa pred�vaj� ako akumul�tor, vlastne explicitne
o�etrujeme tabel�ciu.
  mt(Vrch, N, H, S0) :- mt1(Vrch,1,N,H,[],S0).
  % mt1/4 po��ta minim�lnu hodnotu H triangul�cie medzi i,j
  mt1(Vs,I,J,H,S1,S0):- K is I+1, mt2(Vs,I,J,K,0,H,S1,S0).
  % mt2/8 po��ta vn�torn� cyklus pre minimum cez K, 5. arg. je
akumul�tor, dosial spocitan� minimum
  mt2(Vs,I,J,J,)
  ...

--------------- 29.10.1996
DC:
rozdel(I,I1,I2):- length(I,N), N1 is N div 2, rozdeln(N1,I,I1,I2).
rozdeln(0,I,[],I).
rozdeln(N,[I|Is],[I|I1s],I2):- N>0, N1 is N-1,
     rozdeln(N1, Is, I1s, I2).

- vybudovanie vyvazeneho stromu z usporiadaneho zoznamu:
sez2str([],void).
sez2str([X],t(void,X,void)).
sez2str(Sez,t(Str1,X,Str2)):-
     rozdel(Sez,Sez1,[X|Sez2]),
     sez2str(Sez1,Str1),
     sez2str(Sez2,Str2).

p�somka:
1. Dan� je binarny vyh�adavac� strom. Chceme z�ska� usporiadan�
zoznam v�etk�ch prvkov zo stromu pri prechode z�ava doprava.
  ako obvykle: strom je prazdny - void
                  alebo nepr�zdny - t(L,X,R)
2. Dan� je vyh�ad�vacia �trukt�ra trie, v ktorej s� uschovan�
postupnosti.
trie m��e by� prazdne - void, alebo nepr�zdne t(L,X,N,R), kde v L
s� v�etky postupnosti za��naj�ce prvkom men��m ne� X, R absahuje
postupnosti za��naj�ce prvkom v����m ne� X a N obsahuje
postupnosti za��naj�ce prvkom X, ktor� s� bez uvodn�ho X.
(trie je nieko�kourovn�v� vyh�ad�vac� strom, v ktorom sa
vyh�ad�va najprv pod�a prveho prvku s prechodmi do L a R, a� sa
najde prv� p�smeno X, prejde sa do �trukt�ry N a h�ad� sa zbytok
postupnosti bez X.)
trie pre [1],[3,2],[3,4],[5]
pozn�mka: tak�to �trukt�ry obvykle nep��ete ru�ne do zdroj�ku ale
generuj� sa ako (medzi)v�sledky programu.
  t( t( void, 1, void, void),      % [1]
     3, t( void,2,void,            % [3,2]
           t(void,4,void,void))    % [...,4]
     t( void, 5, void, void))      % [5]

--- 5.11.1996 : grafy

--- 12.11.1996
zad�vanie z�po�tov�ch pr�kladov

--- 19.11.1996
Anal�za vstupu:
Je zadan� zoznam vstupn�ch symbolov v predspracovanej podobe.
Vstupn� symboly s� �trukt�ry:      c(Cislo)
                                   a(Atom)
                                   '('
                                   ')'
Zoznam obsahuje z�pis �plne uz�tvorkovan�ho termu s bin�rnymi
oper�tromi. Ka�d� atom m��e by� oper�tor a preto�e v�raz je �plne
uz�tvorkovan�, nepotrebujeme  precedencie.
Pr. vstupu [c(1),a(+),'(',a(b),a(-),c(2),')']
chceme v�raz analyzova� na na v�stup vyda� nejak� jeho
strukturovan� reprezent�ciu, napr.
1) term  1+(b-2)
2) prefixn� z�pis  [+, 1, [-, b, 2]]

--- 26.11.1996
DC: pl�novanie procesov
Je k dispoz�cii jeden procesor, na ktorom m�te vykona� nieko�ko
�loh. V jednom �ase smie by� na procesore vykon�van� len jedna
�loha. U ka�dej �lohy je dan� d��ka trvania a �as dokon�enia, ak
tento �as prekro��te, plat�te pokutu. �asy s� zadan� prirodzen�mi
��slami v �asov�ch jednotk�ch. Program m� napl�nova� �lohy tak,
aby celkov� pokuta za v�etky �lohy bola minim�lna.
Pokuta za jednu �lohu je line�rna funkcia, za jednotku
oneskorenia plat�te jednu (korunu).
Probl�m rie�te preh�ad�van�m mo�n�ch rozvrhov s priebe�n�m
po��tan�m ceny.

�a��ia varianta 1: je dan� celkov� pokuta, ktor� nesmiete
prekro�i�. T�to inform�ciu sa sna��te pou�i� po�as v�po�tu.

�a��ia varianta 2: U ka�dej �lohy je stanoven� in� pen�le za
jednotku �asu.

�ah�ia varianta 3: Pokuta je stanoven� jednor�zovo za
prekro�enie. Sna��me sa minimalizova� po�et �loh, ktor� sa
nestihn�.


---------------------------
Za�iatok nakoniec
1. cv.
opakovanie OOP
dedi�nos�, zapuzdrenie, polymorfizmus
reprezentacia Tabulky Virtualnych Metod
staticke a dynamick� alokacia, priradenie a zmena strukt�ry
koercia, pre�a�enie, polymorfizmus podtypov� a parametrick�
zmena typu za behu (explicitn�)


2.cv (1.10.1996)
pr�klad: univerz�lny vypisova� a ��ta� �trukt�r
Vytvori� (pod)syst�m, ktor� umo�n� vyp�sa� �ubovo�n� d.�. do
textov�ho s�boru tak, aby sa dala sp�tne zrekon�truova�.
omedzenia: typy s� zn�me (Pascal je staticky/syntakticky typovan�)
- vypis element�rnych d�t: "typ hodnota"
- v�pis pol�: "pole velkost hodnoty"
  - �o s neinicializovan�mi �as�ami ?
- v�pis z�znamov: "typ hodnoty"
  - typ mus� byt zn�my programu, ktor� to ��ta
- v�pis pointrov: to je to zauj�mav�
  - viac pointrov m��e vies� na ten ist� objekt
  - dve mo�nosti:
     - ukazatele v s�bore na pevn� adresu (nepou�ite�n�)
     - men� objektov a ukazatele sa nahradia menami (aj ��slo je
           meno)
  - objekt sa pri prvom v�skyte ukazate�a na� zaregistruje v
     glob�lnej tabu�ke "adresa, meno" , vyp��e sa meno; a pri
     ka�dom v�pise ukazate�a najprv prezer�me tabu�ku, �i tam u�
     pointer nen�.
  - ��tanie: dvojprechodov�
     - v prvom prechode alokujeme pam��, tvor�me dvojice
           "adresa,meno" a ��tame nepointrov� hodnoty, v druhom
           dopl�ujeme pointry. V tabulke si m��eme dr�a� adresy,
           kde potrebujeme doplni� pointer, a� ho budeme pozna�.
  - lep�ie rie�enie: jednoprechodov� ��tanie
     - potrebujeme najprv alokova� v�etk�ch n�sledn�kov nejak�ho
           objektu. Ale je probl�m s cyklick�mi �trukt�rami.
     - rie�enie: objekt rozdel�me na dve �asti - "hlavi�ka"
           obsahuje info nutn� pre alok�ciu (typ a ve�kos�) a
           vypisuje sa pri prech�dzan� do h�bky v pre-order a
           vlastn� data sa vypisuj� v post-order. V�etko klape.
     - ��tanie: pod�a hlavi�ky naalokujeme a zarad�me do tabu�ky,
           potom ��tame podriaden� objekty a datami objekt
           napln�me a� nakoniec, ke� u� s� zn�me aj hodnoty
           pointrov.
- zanorenie do OOP
  - v�etky objekty v syst�me s� potomkami jednej univerz�lnej
     triedy s virtu�lnymi proced�rami
     - zaregistruj_sa do tabu�ky
     - vyp��_sa: zaregistruj_sa, vyp�� hlavi�ku, vyp��
           pointrov�ch n�sledn�kov, vyp�� seba/svoje polo�ky
           (pr�padne pomocou volania v�pisu (len) polo�iek predka
           v hierarchii)
  - podobne sa ��ta (??) : hlavi�ka ud�va typ, tak�e po alok�cii
     by sa u� dala vola� virtu�lna proced�ra, ktor� to na��ta.
- prechod �trukt�ry
     - do h�bky: obracanie pointrov (s markovac�mi bitmi)
     - do "��rky": alg. slep�ho
     - -''- : alg. jednook�ho - lok�lne do h�bky s omedzen�m
           z�sobn�kom, d�le�it� optimaliz�cia posledn�ho volania
- pou�itie
     - (kop�ruj�ci) garbage collector
     - univerz�lny v�pis �trukt�r, ktor� sa d� prezera� a
           editova�, takto sa daj� pripravi� po�iato�n� alebo
           pevn� �trukt�ry (pre programy riaden� datami)
       - pr: �trukt�ra menu namiesto alok�cie v programe.
           a) objekty, ktor� si pred�vaj� riadenie
                 vznikn� explicitnou kon�trukciou
                 vznikn� pomocou vnoren�ch kon�truktorov
           b) �pec. jazyk, ktor� sa skompiluje
           c) viz. - datov� �trukt�ru pop�dan� v dat�ch programu
                 (samozrejme ovl�dacie proced�ry musia by� v
                 programe)


--- zbytky:
- s��tanie v�razu:
je dan� reprezent�cia v�razu  pomocou un�rnych ��sel: 3+3+2,
resp. +(3,+(3,2))
a)   % pravoasociat�vne, struktur�lne pod�a 1.arg, "v�po�et
     % z medziv�sledkov"
     secti(s(X),s(X)).
     secti(0,0).
     secti(+(I,Is),V0) :- secti(Is,V1), plus(V1,I,V0).
a1) DC - pre �avoasociat�vnu d.�.
b)   % �ubovo�ne asociat�vne
     ...
     secti(+(I1,I2),V) :-
           secti(I1,V1),
           secti(I2,V2),
           plus(V1,V2,V).
c)   % akumul�cia, pre �ubovo�ne asociat�vnu d.�.
     secti(I,V):- secti_1(I,0,V).
     secti_1(0,V,V).
     secti_1(s(I),V1,V0) :- plus(s(I),V1,V0).
     secti_1(+(I1,I2),V1,V0) :-
           secti_1(I1, V1, V2),
           secti_1(I2, V2, V0).
c1) DC - pre pravo/�avo asoc. �trukt�ru s��tanie akumul�ciou.

---pre dan� premenn� (z v�razu) chceme vypusti� v�etky faktory
a zisti� s��et jej koeficientov.
% secti(+Prem, +V�raz, -Koef, -V�raz)
! v�raz sa ned� meni� na miest, mus�me ho zmeni� nov�m zlo�en�m z
     pod�ast�
idea: rekurzia pod�a 2. arg. (podv�razov)
% ukon�enie
secti1(_X, 0, 0, 0).
secti(X, +(*(C,X),V)

--- Rok 1995
--- z cvi�en�:
--- 18.10.1995, 4. cv.
- zlo�en� datov� typy
- pr: datum
  - spr�vne navrhnut� typ:
     datum(Rok,Mesiac,Den)  % alebo v opa�nom porad�
    polo�ky s� ur�en� polohou, nie menom
  - nespr�vne
     [Rok, Mesiac, Den]      % unifikuje sa s kdejakou trojicou
     datum([Rok, Mesiac, Den])
     datum(rok(Rok),Mesiac(Mesiac),den(Den))
       % zbyto�ne zlo�it� a neefekt�vne

- k typu patr� interface:
  - m��e sprostredkova� v�ber, ukladanie a zmeny d.�. pod�a mena
     polo�ky
  make_datum(R,M,D,Datum) :- Datum = datum(R,M,D).
  get_datum(den, Datum, D):- Datum = datum(_,_,D).

  % set_datum(den, D, Datum, Novy_Datum) - v Datume zmeni den na
  % D, v�sledok mus� by� nov� �trukt�ra Nov�_Datum; ! v Prologu
  % nen� zmena na mieste (tj. de�trukt�vne priradenie)
  set_datum(den, D, datum(R,M,_), datum(R,M,D))
  ...   % get_ a set_ analogicky pre mesiac, rok


--- 25.10.1995, 5. cv
- n�vrh boolovsk�ch v�razov
  - kon�tanty ano/0, ne/0
  - spojky and/2, or/2, non/1, ...
- test ,,typu" boolovsk�ho v�razu (is_bv/1)
  - pomocou �truktur�lnej rekurzie
- vyhodnotenie b.v. - na ano, ne (eval_bv/2)
  - roz��renie testu typu o argument a proced�ry na jeho
     o�etrovanie
  - vyhodnocovanie spojek - tabulkou:
    a) rozbor pr�padov
    b) skratky, probl�my s rezom
  - prevod zlo�it�ch spojek na jednoduch�ie
    - implik�cia na non a or
    - ekvivalencia na dve implik�cie
      - ! z h�adiska efektivity: nevyhodnocova� podv�razy dvakr�t
- zavedenie premenn�ch do reprezent�cie b.v.
  var(I) ... var je nov� tag, aby sme mohli ma� aj premenn� ano,
     ne, and ...
  - roz��renie is_bv - pridan�m klauzule
  - roz��renie eval_bv
    - pridan�m argumentu - kontextu, ktor� pren��a hodnoty
      premenn�ch (ako zoznam dvoj�c)
- DC (dom�ce cvi�enie)
  prevod b.v. do konjunkt�vnej norm�lnej formy
- union/3 - zjednotenie mno��n reprezentovan�ch zoznamami
  - tri varianty analogick� prieniku z predn��ok
    a) deklarat�vna
    b) s rezom
    c) s -> (if_then_else)
- lep�ia reprezent�cia mno��m - usporiadan� zoznamy
  - union je v takom pr�pade merge/3
  (m��ete si sk�si� pomocou merge nap�sa� mergesort/2)
- mno�inov� vyhodnocovanie: is_set/2 (narychlo)
  - ako v Pascale: + je zjednotenie, * prienik, - rozdiel

% budi� is_set tie� vhodn� bin�rny oper�tor
  M is_set M1+M2 :- V1 is_set M1,   % rekurzia,
                    V2 is_set M2,   % prirodzene.
                    union(V1,V2,M). % (post)spracovanie v�sledkov
  M is_set M1*M2 :- ... ,
                    intersection(V1,V2,M).
  M is_set M     :- is_list(M).  % test ,,typu", zvl�dnete?
% M is_set ...    m��eme roz�irova� o �al�ie oper�cie ...
  ?- X is_set ([1,2]+[3,4])*[4,1].
     X = [1,4]  % odpove�, v nejakom porad�

  (22.10'99)
  - mnozinovy rozdiel:
  rozdil1([],_Ys,[]).
  rozdil1([X|Xs],Ys,Zs):-
    (member(X,Ys)-> Zs=Zs1 ; Zs=[X|Zs1]),
    rozdil1(Xs,Ys,Zs1).
  
  - pomocou akumulatora:
  rozdil2(Xs,Ys,Zs):-rozdil2x(Xs,Ys,[],Zs).
  rozdil2([],_Ys,Zs,Zs).
  rozdil2([X|Xs],Ys,A1,Zs):-
    (member(X,Ys)-> A2=A1 ; A2=[X|A1]),
    rozdil1(Xs,Ys,A2,Zs).

  - vsimnite si, ze v prvom pripade je zoznam zvasceny 
o X v hlave (virtualne), v druhom pripade v rekurzivnom volani.
  - v pripade zjednotenia mozeme pouzit Ys ako akumulator 
(pretoze ma spravnu pociatocnu hodnotu)
  - add: symetricky rozdiel ako prevedenie na minuly pripad
syntax pre symetricky rozdiel: --(X,Y)
  is_set(V, --(X,Y)):- is_set(V,(X+Y)-(X*Y)). % samozrejme neefektivne.


--- 1.11.1995, 6. cv.
- grafy:
  dve rozumn� reprezant�cie
  (jedna nerozumn� - v datab�zi)
  - vrchol(Graf, V), hrana(Graf, X, Y)
    - nem� sl��i� ako reprezent�cia, ale ako interface
- naprogramovanie interface k dan�m dvom reprezent�ci�m
- prevody medzi preprezent�ciami
  - niektor� oper�cie sa lep�ie robia v jednej reprezent�cii, in�
     v druhej; niekedy je efekt�vnej�ie zmeni� reprezent�ciu,
     vykona� oper�ciu a vr�ti� reprezent�ciu
- minim�lna kostra:
  - roz��renie druhej reprezent�cie o ohodnotenie hr�n
  - algoritmus:
    usporiadanie hr�n (presko�en�)
    a potom prid�vanie
    - pomocn� predik�t:
    % cesta(Z, Do, Graf, Cesta) cesta je dosial prejden� �as�
    cesta(X, X, _, _).
    cesta(X, Y, G, C):-
      not(member(X,C)),            % aby sme sa nezacyklili
      (hrana(G,X,Z); hrana(G,Z,X)) % n�jdenie susedov
      cesta(Z,Y,G,[Z|C]).          % rekurzia
    - volanie: ?- cesta(1,99, graf2(...), [1]).
    - prehl. do hlbky, s testom proti zacykleniu - C
    - ak sa chceme dozvediet cestu, mus�me prida� jeden
      (v�stupn�) argument

--- 8.11.1995, 7. cv.
--- Pr�klad :
Dijkstrov algoritmus n�jdenia najkrat��ch ciest z dan�ho vrcholu
do v�etk�ch ostatn�ch

- reprezent�cia grafu
  - nepodstatn�, podstatn� je interface
  - napr. funktor graf/2,
    graf(ZoznamVrcholov, ZoznamHran)
    - ZoznamHran -> zoznam troj�c Vrchol-Vrchol-CenaHrany

- interface n�zky:     hrana(Graf, X,Y,H)
  vyd�va pri backtrackingu postupne v�etky hrany
     Mus� odpoveda� zvolenej reprezent�cii

- interface vy���:
  okolie(Graf, X, L) :-      % okolie vrcholu X v grafe G bude v L
    setof(Y-H, hrana(Graf, X,Y,H), L).

- vlastn� alg.
?- dijkstra(Graf, Vrchol, V�sledn�_zoznam).
   V�sledn�_zoznam je v tvare zoznamu dvoj�c: Vrchol-Vzdialenos�

dijkstra(G,V,L):-      % interface na predik�t, ktor� bude
  d(G,[],[V-0],L).     % po��ta�

- Idey v�po�tu: d(Graf, Uzavrete, Otvorene, L)
  - Graf je vstup
  - L je v�stup
  - stav preh�ad�vania grafu je mo�n� pop�sa� dvomi stavov�mi
premenn�mi:
  mno�ina uzavret�ch vrcholov - s� zn�me konkr�tne ceny do V
  mno�ina otvoren�ch vrcholov - s� zn�me odhady ceny
  (v grafe m��u by� aj �al�ie vrcholy - e�te nezn�me)

  rekurz�vna klauzula pre d/4 vykon� ,,lok�lnu" zmenu stavu:
  - vyberie a expanduje (rozvinie) jeden vrchol a pod�a jeho
okolia uprav� stavov� premenn�

d(G,L,[],L).     % preh�ad�vame v�etky vrcholy,
                 % kon��me, a� nie je �iadny otvoren�
d(G, Uz, Otv, L):-      % vlastn� rekurzia
     zvol_v(Otv, V-H, Otv1), % vo�ba vrcholu, zvy�ok otv. budeme
                             % potrebova� (v Otv1)
     okolie(G, V, L1),       % expanzia zvolen�ho V
     vypust(L1, Uz, L2)      % z okolia L1 vypust�me uzavret�
     zluc(L2, Otv1, Otv2, H), % nov� otvoren� Otv2
     d(G, [V-H|Uz], Otv2, L). % �al�ia iter�cia s nov�mi hodnotami

- pozn�mky:
  pop�san� algoritmus je obecn� a pod�a vo�by vrcholu je mo�n�
    implementova� r�zne strat�gie preh�ad�vania grafu:
  - prioritn� (to je aj na�e)
  - do h�bky, do ��rky, ...

,,pomocn� predik�ty"
zvol_v([X],X,[]).      % X = V-H
zvol_v([V1-H1|L1], V-H, L):-
  zvol_v(L1, V2-H2, L2),     % rekurzia
  ( H2 =< H1 ->              % porovnanie ako test v if->then;else
     V = V2, H = H2, L=[V1-H1|L2]      % ,,v�stupn�" unifik�cie
  ;  V = V1, H = H1, L=[V2-H2|L2]      % ,,v�stupn�" unifik�cie
  ).

vypust([], _, []).           % v podstate mno�inov� rozdiel
vypust([V-H|L1], L2, L3):-
  ( member(V-_,L2) ->
    L3 = L4            % v�stupn� unifik�cie, vznikaj� skladan�m
  ; L3 = [V-H|L4]      % substit�ci�, L4 sa spo��ta v rekurzii
  ),
  vypust(L1,L2,L4).

zluc([],L,L,_).        % podobn� mno�inov�mu zjednoteniu
zluc([X1|L1],L2,L3,H):- % H je ,,kontext", cena ,,aktu�lneho" vrch.
  X1 = V1-H1,
  ( delete(V1-H2, L2, L4) -> % test a pr�prava men�ieho L2 do L4
    L3 = [V1-Hmin|L5],       % v�stupn� unifik�cia
    Hmin is min(H1+H,H2)    % vo�ba novej vzdialenosti (minima)
                            % min je v LPA aj funkcia
  ; L4 = L2            % delete neuspelo
    L3 = [X1|L5]       % v�stupn� unifik�cia
  ),
  zluc(L1,L4,L5,H).

- zapisovanie predik�tov v takom tvare, �e rekurz�vne volanie je
posledn�m cie�om v klauzuli, je vhodn�, preto�e umo�n�
interpretu v niektor�ch pr�padoch zmeni� rekurziu (tj. rekurz�vnu
pr�cu so z�sobn�kom) na iter�ciu (tj. pr�cu s nieko�k�mi
,,stavov�mi" premenn�mi v kon�tantnej pam�ti)

- Grafika v LPA Prologu
Pred spusten�m prologu z �rovne syst�mu:
C:> gfx                in�talovanie podpory
C:> exit               odin�talovanie ...

v Prologu: na��ta� s�bory: z adres�ra ...\prolog\gfx\
?- ensure_loaded(grafix),    % grafika
   ensure_loaded(turtle).    % ,,�elv�" grafika a la LOGO

?- go.     % spustenie �elv� grafiky

- �elva m� ur�it� aktu�lnu polohu, smer a farbu pera:
  pr�kaz go okrem spustenia nastav� �tandardn� polohu:
  na za�iatku je poloha (0,0) - stred obrazovky
                 smer 0 - na sever, nahor
                 farba pera 15 - biela
- pr�kazy �elv� grafiky:
  go
  draw(Vzdialenost)    % nakresl� �iaru z akt. poz�cie v akt.
                             smere akt. perom
  right(Uhol)          % zmeni akt. smer doprava o dan�
                             po�et stup�ov
  left(Uhol)           % analogicky, ale ot��a sa do�ava
  do(N, Cie�)          % opakuje Cie� N-kr�t
  for(Index, Od, Do, Krok, Cie�)
                       % opakuje Cie� pre r�zne hodnoty premennej
                             Index
  pen( Farba)          % nastav� farbu pera, 1..16
  move(Vzdialenos�)    % pohyb bez kreslenia
  goto(X,Y)            % presun na dan� polohu
  head(Smer)           % oto�enie do dan�ho smeru

----- prevzate z prednasok
--- Reprezent�cie grafov
     - a pou�itie bagof ...
- uk��eme si tri mo�n� reprezent�cie grafov, ktor� sa daj�
pou��va� pre grafy s ohodnoten�m aj bez ohodnotenie vrcholov
a hr�n. S� mo�n� aj in� reprezent�cie, ale obecne, preto�e nem�te
polia, niektor� reprezent�cie s� neprirodzen�.
1) graf je reprezentovan� �trukt�rov, ktor� obsahuje zoznam
   vrcholov a zoznam hr�n
   (pou�it� funk�n� symboly "graf", "-" a "hr" s� zvolen�
    �ubovolne, ale pou��va� sa musia konzistentne)
     d.�.: graf([Vrchol-Hodnota], [hr(Vrch1,Vrch2,Hodnota)])
     pr. graf([a-1, b-2, c-4],
              [hr(a,b,11), hr(a,c,1.1), hr(b,c, "Hodnota")] )

2) graf je reprezentovan� ako zoznam troj�c (alebo dvoj�c - bez
ohodnotenia) Vrchol, Hodnota, Zoznam_susedov
  d.�.: [Vrch1 - Hodnota_vrcholu - [Vrch2 - Hodn_hrany]]
  pr.: [a-1-[b-11,c-1.1],
        b-2-[c- "Hodnota"],
        c-[]]

3) graf je ulo�en� v datab�ze. Toto rie�enie je nev�hodn�,
preto�e zmena alebo vytvorenie grafu znamen� z�sah do datab�ze.
Na druhej strane, my�lienku z tejto reprezent�cie m��eme pou�i�
ako (n�zky) interface nez�visl� na konkr�tnej reprezent�cii.
V tekom pr�pade mus�me nap�sa� proced�ry, ktor� umo�nia pr�stup
k skuto�nej reprezent�cii cez zvolen� interface.
     % reprezent�cia: (nepou��va�)
     vrchol(g1, a, 1).
     vrchol(g1, b, 2).
     hrana(g1, a, b, 1.1).

  - interface:
     vrchol(+Graf, ?Vrch1, ?Hodnota_vrcholu).
     hrana(+Graf, ?Vrch1, ?Vrch2, ?Hodnota_hrany).
   graf je vstupn� parameter, je to reprezent�cia pod�a 1) alebo
     2)
   v�sledky sa vracaj� backtrackingom

   - implement�cia interface pre repr. 2):
     vrchol(G,V,H):-
           member(V - H - _, G).
     hrana(G,V1,V2,H):-
           member(V1-_-Vs, G),     % ur�� / h�ad� prv� vrchol
           member(V2-H, Vs).       % -''- druh� a hodnotu hrany
     % ak nem�me ohodnotenie v repr.
     vrchol(G,V):-
           member(V-_,G).
     hrana(G,V1,V2):-
           member(V1-Vs,G),
           member(V2,Vs).

 - na z�klade n�zkeho interface m��eme vybudova� �al�ie pomocn�
proced�ry, u� nez�visl� na interface
Proced�ry vrchol a hrana (n�zky interface) vracaj� v�sledky
pomocou backtrackingu. Z jednotliv�ch v�sledkov potrebujeme
vytvori� datov� �trukt�ry, preto pou�ijeme setof, bagof...

   - okolie: k vrcholu vytvor� zoznam jeho susedov
     % okolie(Graf, Vrch, Sousede):- S je zoznam v�etk�ch
           susedov vrcholu Vrch
     okolie(G,V,S):- bagof(V2,hrana(G,V,V2), S).
    - volanie:
     ?- okolie(..., V,S).
           V=a   S=[b,c];
           V=b   S=[c];
           no                % riesenie V=c nevyd�, preto�e
                                   S sa nevracia pr�zdne

   - repr2: vytvorenie reprezent�cie 2) z interface
     % repr2(+G,-R):- R je vytvoren� reprezent�cia grafu G
     repr2(G,R):-
       bagof(V1-S, (vrchol(G,V1),
                    (okolie(G,V1,S) -> true
                                    ;  S = [] )),
             R).
     - pozn.:
       - bez ohodnotenia
       - 2. argument, cie�, je zlo�en�
       - je o�etren� pr�pad, ak S = []

   - vytvorenie reprezent�cie 1) z interface, pr�klad pou�itia
           existen�n�ch premenn�ch
     % repr1(G,R):- R je reprezent�cia grafu G
     repr1(G, graf(Vs,Hs)):-
           bagof(V, HV^vrchol(G,V,HV), Vs),
           bagof(hr(V1,V2), HH^hrana(G,V1,V2,HH), Hs).

- pr�klad: Dijkstrov algoritmus
% dijkstra(+G,+V,-L):- pre ka�d� vrchol V2 v grafe G spo��ta
% vzdialenost od V  a vr�ti zoznam L dvoj�ch V2-Vzdialenost
dijkstra(G,V,L) :-
     d(G,[], [V-0], L).
d(G,Uz,Otv,L):-
     zvol_v(otv, V-H, Otv1),
     okolie(G,V,L1),
     vypust(L1,Uz,L2),
     zluc(L2,Otv1,Otv2, H),
     d(G,[V-H|Uz], Otv2,L).
d(G,L,[],L).     % ak sa nepodar� zvolit vrchol

% zvol_v :- vyberie vrchol s minimalnou docasnou hodnotou
zvol_v([X],X,[]).
zvol_v([V1-H1|L1], V-H,L):-
     zvol_v(L1,V2-H2,L2),
     ( H2 =< H1 -> V = V2, H = H2, L=[V1-H1|L2]
                 ; V = V1, H = H1, L=[V2-H2|L2]
     ).

% mno�inov� rozdiel, bez ohladu na hodnotu
vypust([],_,[]).
vypust([V-H|L1],L2,L3):-
     ( member( V-_,L2) -> L3 = L4
                       ;  L3 = [V-H|L4] ),
     vypust(L1,L2,L4).

% cosi ako zjednotenie
zluc([],L,L,_).
zluc([X1|L1],L2,L3,H):-
     X1 = V1-H1,
     ( delete(V1-H2,L2,L4) ->
           L3 = [V1-HM|L5], HM is min(H1, H2+H)
         ; L3 = [X1|L5], L4 = L2),
     zluc(L1,L4,L5,H).
---------------------------------
Dodatky:
A. reprezent�cia d�t v algoritme Aho-Corasickov�
B. fibonacciho ��sla ...

A. Reprezent�cia d�t v algoritme Aho-Corassickov�
(autotest na 2. predn��ke)
  Reprezent�cia stroja sa sklad� z doprednej funkcie F, sp�tnej funkcie
g a v�stupnej fce. out. Stavy s� implicitn�, ��slovan�.
S� tri mo�n� reprezent�cie: 1) strukturovan�, 2) bytecode a 3)
vykonate�n� k�d. �trukturovan� m� nieko�ko mo�nost� konkr�tnej
�trukt�ry: a) riedky vektor b) hust�
vektor, c) dvojvrstevn� vektor (pod�a stavov a abecedy), d) pointrov�
�trukt�ra (pointry ako viazan� premenn� - hack), e) �trukturovan� pod�a
f (trie)
  pr�klad: vzorky he, her, his, she
stavy 0h1e2"he"r3"her", 1i4s5"his", 0s6h7e8"she,he", g:5->6, 7->1, 8->2
  Bytek�d je symbolick� (v C++ mo�n�), �trukturovan�, a s symbolick�mi
pointrami (nem�me pole).

reprezent�cie:
1) dvoj�rov�ov� zoznam, prv� �rove� pod�a stavu, druh� pod�a p�smena
(riedka). $�slo stavu je meno, na ktor� sa odkazujeme.
% d.�. [stav(Meno,N�sledn�ci,G, [Out_vzorky])]
[stav(0,[h-1,s-6],0,[]),
 stav(1,[e-2,i-4],0,[]),
 stav(2,[r-3],0,["he"]),
 stav(3,[],0,["her"]),
  ...
 stav(8,[],2,["she","he"]) ]

2) zcela rozp�san�:
- toto je "interface", impl. m��e to by� v DB alebo v d.� (ako u grafov)
f(0,h,1). f(0,s,6). f(1,e,2). ...
g(0,0). g(1,0). ... g(5,6). g(6,0). g(7,1). g(8,2). % g(0,0) sa nevyu�ije
% pr�padne g(_,0). % nutn� o�etri� v programe
% vlastn� interpret; volanie ?- ac(0,Chars, Out). ) ako po�. stav
ac(S,[C|Cs], Out):- f(S,C,S1),!, Out=[O1|Out1], ac(S1,Cs,Out1).
ac(0,[C|Cs], [[]|Out]):- /* g(0,0)) �peci�lne, preto�e uber�m p�smeno*/
                        ac(0,Cs,Out).
ac(S,Cs,Out):- S\=0,g(S,S1),ac(S1,Cs,Out).

3) vykonate�n� k�d: (Prolog-ify)
 - pre jednoduchos�: ku ka�d�mu znaku vstupu bude zoznam n�jden�ch
vzorkov na tomto znaku.
ac(Chars,Out):- f_0(Chs,Out).
f_0([],[]). %ukon�enie
f_0([C|Cs],Out):- C=h, f_1(Cs,Out)
                ; C=s, f_6(Cs,Out).
f_0([_|Cs],[[]|Out]):- /* _\=h,s */
                       f_0(Cs,Out).
f_4([s|Cs],[[his]|Out]) :- f_5(Cs,Out).
f_5(Cs,Out) :- g_5(Cs,Out).
...
g_5(Cs,Out):- f_6(Cs,Out).
...

4) previazan� (cyklick�) �trukt�ra
 - pointry s� "priame", ��slo stavu nepotrebujeme
S0=s([h-S1,s-S6],S0,[]),
S1=s([e-S2,i-S4],S0,[]), ...
Strom=[S0,S1,S2,...] % potrebujeme
volanie: ?- ac(S0, Chars,Out).
ac(S,[C|Cs],Out):- next(S,C,S1,Out1), append(Out1,Out2, Out),
  ac(S\,Cs,Out2). % rozdielov� zoznamy (pre zmenu)
ac(_,[],[]).
next(s(Next,G,Out),C,S1,Out1):-
  member(C-S1,Next) -> Out1= ...
                     ; next(G,C,S1,Out1).


B. Fibonacciho ��sla.
Exponenci�lne. Zapam�tanie posledn�ho: line�rne - zdola, zhora.
Omedzenie dvoch po�iato�n�ch podmienok - sta�� jedna (s dvoma
hodnotami - jedna je umel�, dopo��tan�). Po��tanie po dvoch (s v�berom
na konci alebo za�iatku). Pomocou n�sobenia mat�c: logaritmick�!,
motiva�ne: po��tania s�be�ne spredu aj zozadu.

- iter�tory, for -cyklus ,...
- program ako data, a naopak ...

\end{verbatim}
\end{document}
\end
