Kdy a kde:

• I/2-X/36 : Po 10:40 v M6

Za co je zapocet:

• Zapoctovy program (v Prologu) -- tema vcetne specifikace, v niz shrnete, co ma vami vytvoreny program umet, byste mi meli oznamit do 30.11.2005. Doporucuji se inspirovat seznamem uloh na strankach RNDr. J. Hrice. Samozrejme fantazii se meze nekladou a pokud mi dodate rozumne tema zapoctaku, urcite se nejak dohodneme. Soucasti zapoctaku je dokumentace. Rady jak ji napsat (a nepsat) od RNDr R. Kryla a RNDr. J. Hrice.
• Ucast na cviceni neni povinna; na druhou stranu, pokud po me bude chtit zapocet nekdo, koho jsem na cviceni nikdy nevidel, asi bude mit problem.
• Vyreseni alespon 2*n/3 domacich ukolu, kde n je pocet domacich ukolu, ktere zadam (n bude radove 5). Ukol dodany po terminu (kterym obvykle byva pristi cviceni) se pocita za 2/3 -- tj. pokud behem semestru nebudete nic delat, nezbyva vam, nez ve zkouskovem obdobi vyresit a odevzdat vsechny ukoly. Reseni prikladu se obvykle sklada z popisu algoritmu, programu v zadanem programovacim jazyce (Prolog nebo Haskel), ktery ho implementuje, a zduvodneni spravnosti a casove slozitosti. Zduraznuji: je pozadovan popis algoritmu, nikoliv programu. Priklad:
  Spatne: Pouziji vyraz foldl 0 (+) (elems a).
  Lepe: Sectu zadane prvky (ulozene v poli a).
  Spravne: Zalezi na okolnostech. Scitat cisla v poli jen tak pro radost je vicemene k nicemu. Spise nez na detailne popisovat to, jak je secteme, je lepsi se zamerit na vysvetleni toho, proc je vlastne chceme secist.
  Zatim vypsane priklady:
  • (Do 17.10.) Napiste predikat rec_conc(+Seznamy,-Spojene), ktery do Spojene vlozi seznam vsech atomu, ktere jsou prvky seznamu Seznamy, nebo prvky prvku seznamu Seznamy, nebo prvky prvku prvku, atd. Tj. napriklad ?-rec_conc ([a,[b,[c,d],e,[f]],g], X). vrati X=[a,b,c,d,e,f,g]. Pro reseni muzete vyuzit standardni predikat atom(+X), ktery je splnen pro atomy (a pro prazdny seznam), ale ne pro neprazdne seznamy.
  • (Do 31.10.) Mejme ridkou matici reprezentovanou seznamem neprazdnych radku. Kazdy radek obsahuje seznam nenulovych prvku. Napiste predikat transpose(+Mat,-TMat), ktery ji transponuje. Reprezentace matice muze vypadat napriklad takto: matice(4,5,[radek(2,[prvek(1,7),prvek(3,5)]), radek(4, [prvek(2,2)])]) -- tj. matice se 4 radky a 5 sloupci, ktera ma tri nenulove prvky: [2,1]=7, [2,3]=5 a [4,2]=2.
  • (Do 7.11.) Mejme setrideny seznam cisel. Vytvorte z nej perfektne vyvazeny binarni vyhledavaci strom (Prolog).
  • (Do 21.11.) Napiste predikat numvars(+T,-NT), ktery nahradi promenne v termu T poradovymi cisly, a pritom T nezmeni. Tj. numvars(a(X,Y,b(X,Y,Z),Z), T). vrati T = a(1,2,b(1,2,3),3).
  • (Do 19.12.) Mejme setrideny seznam cisel. Vytvorte z nej vyvazeny binarni vyhledavaci strom (Haskell).
  • (Do 8.1.) Mejme graf zadany seznamem sousedu (type Graf=Array Int [Int]). Prevedte ho na matici sousednosti (type MS=Array (Int,Int) Bool), tj. napiste funkci toMS::Int->Graf->MS, kde prvni parametr je pocet vrcholu n (vrcholy jsou cislovany od 1 do n).

Obsah cviceni:

• (3.10.) "Neproceduralni" programovani v Pascalu (bez cyklu a modifikace existujicich promennych). Prace se seznamy (spojovani, obraceni, quicksort, atd.).
• (10.10.) Uvod do Prologu -- rodinne vztahy, jednoduche operace se seznamy.
• (17.10.) Odpadlo.
• (24.10.) Diskuse rec_conc -- efektivita, reversibilita. Transpozice huste matice.
• (31.10.) Trideni (quicksort), operace s ridkymi maticemi (transpozice, soucin), vkladani do binarniho vyhledavaciho stromu.
• (7.11.) Cvicil za me Ondrej Zajicek, praci s vyrazy.
• (14.11.) Rozklad termu, prace s volnymi promennymi, rozdilove seznamy.
• (21.11.) call, apply, setof, bagof, findall. Funkce vyssiho radu -- map, fold -- s volaci konvenci jako apply, nebo s explicitnim vyznacenim vstupnich a vystupnich promennych -- plus(1) versus X^plus(1,X,Y)->Y.
• (28.11.) assert a retract. Implementace bagof jejich pomoci. Generovani unikatniho jmena pro pomocny predikat. Interpretovani Prologu v Prologu, aplikace na ukladani mezivysledku.
• (5.12.) Lisp. Jednoduche funkce, operace se seznamy.
• (12.12.) Uvod do Haskellu. Typy, jednoduche funkce, operace se seznamy, stromy.
• (19.12.) Implementace fronty pomoci dvou zasobniku. Prace s maticemi -- transpozice, nasobeni.
• (2.1.) Typove tridy. Pole.
• (9.1.) Vstup a vystup. Vyhodnocovani vyrazu, obecne funkce zjednodusujici pripadna rozsireni.