Kdy a kde:
Za co je zapocet:
- Zapoctovy program -- mel by byt psan v Delphi a mit clickoidni
uzivatelske rozhrani (tyto pozadavky je mozne v oduvodnenych pripadech
po domluve se mnou modifikovat). Tema vcetne specifikace, v niz shrnete, co ma
vami vytvoreny program umet, byste mi meli oznamit do
31.3.2007, pokud vas nic nenapada, zkuste se podivat
na muj seznam napadu na zapoctaky,
pripadne podstatne rozsahlejsi seznam na strankach Martina Marese.
(primerena obtiznost je 5 ci vyssi). I pokud uz nejake tema mate, stejne se vyplati tam podivat --
vicemene vsechny tam uvedene informace (dokumentace, osetreni vstupu, ...)
plati i u me (jen jsem liny je sem psat).
Presto zduraznim: 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 jsem zadal (n=4). 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 (neni-li receno jinak) sklada z popisu algoritmu, programu v Pascalu, ktery ho implementuje,
a zduvodneni spravnosti a casove slozitosti. Zduraznuji: je pozadovan popis algoritmu,
nikoliv programu. Priklad:
Spatne: Nastavim sum na 0 a pak pro i od 1 do n pricitam a[i] k sum.
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 26.2.) Napiste funkci, ktera vydeli (se zbytkem) dva polynomy zadane jako spojovy seznam;
napriklad 5*x^3 + x + 10 je reprezentovan jako seznam (10,0) -> (1,1) -> (5,3) -> nil.
- (Do 12.3.) Napiste program, ktery pro zadany regularni vyraz rozhodne, zda matchuje
prazdny retezec.
- (Do 26.3.) Strom je doleva orientovany, pokud v kazdem jeho uzlu plati, ze levy podstrom ma alespon
tolik prvku jako pravy podstrom. S pomoci doleva orientovaneho stromu lze reprezentovat haldu
(prvky jsou ulozeny ve vrcholech a prvek ulozeny v synovi je vzdy vetsi nez prvek ulozeny v otci).
Napiste program, ktery sjednoti dve doleva orientovane haldy v logaritmickem case.
- (Do 7.5.) Napiste program, ktery pro zadane k nalezne v neorientovanem grafu s ohodnocenymi hranami
nejkratsi cestu pouzivajici nanejvys k hran mezi dvema zadanymi vrcholy.
Obsah cviceni:
- (19.2.) Opakovani prace se spojovymi seznamy (scitani a nasobeni polynomu).
- (26.2.) Jeste jednou spojaky (vytvoreni ctvercove mrizky, prohledavani do sirky).
- (5.3.) Pisemka na spojaky. Binarni vyhledavaci stromy.
- (12.3.) Intervalove stromy, DFU.
- (19.3.) Binomialni haldy, amortizovana casova slozitost.
- (26.3.) Nahodne ulozky (nejdelsi vybrana rostouci podposloupnost, nejvetsi dira
v posloupnosti, nejblizsi body v rovine).
- (2.4.) Polyfazove trideni (porovnani s presypavanim mezi dvema polovinami souboru).
Trideni retezcu, aplikace na uniq. Trie.
- (9.4.) Velikonoce.
- (16.4.) Odpadlo.
- (23.4.) 2-3-stromy, hashovani, Dijkstra s ruznymi haldami.
- (30.4.) Grafove algoritmy -- topologicke trideni a overeni 2-souvislosti pomoci
dfs. Dynamicke programovani (pocet cest, vzdalenost retezcu, minimalni triangulace).
- (7.5.) Souvislosti okolo cest v grafech (mocniny matice sousednosti, zmena potencialu vrcholu
a heuristika pro Dijkstru, odstraneni zapornych hran), kriticka cesta pri planovani. Dynamicke
programovani (nezavisla mnozina v grafu na primce s omezenou vzdalenosti sousedu).
- (14.5.) Nejkratsi cyklus v grafu. Diskretni simulace (fronty u prepazek).
- (21.5.) Zalamovani textu. Kompilace vyrazu.