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.2006, 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 zadam (n bude radove 6). 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 9.3.) Mame strom vyrazu, jehoz operatory jsou jen + a *. Vytvorte z nej strom ekvivalentniho
vyrazu, v nemz jsou vsechny podvyrazy tvorene jen + (*) uzavorkovany doleva, tj. z ((a+b) + (c+d))
vyrobime (((a+b)+c)+d).
- (Do 30.3.) Strom je doleva orientovany, pokud v kazdem jeho uzlu plati, ze levy podstrom ma alespon
tolik prvku jako pravy podstrom. Jak pomoci doleva orientovanych stromu implementovat efektivni haldu
(tj. s operacemi v logaritmickem case)?
- (Do 20.4.) Napiste program, ktery urci teziste (ne nutne konvexniho) mnohouhelnika (zadaneho souradnicemi
vrcholu v poradi podel jeho obvodu).
- (Do 3.5.) Napiste program, ktery v orientovanem ohodnocenem grafu urci pro dva zadane vrcholy pocet
nejkratsich cest mezi nimi.
- (Do 25.5.) Mame zadany wildcard, tj. retezec, ktery muze obsahovat znaky * -- ktere lze nahradit libovolnym (i prazdnym)
retezcem, a ? -- ktere lze nahradit prave jednim libovolnym pismenem. Pro zadany retezec rozhodnete, kolik je v nem
potreba nejmene udelat zmen (tj. odebrani, pridani ci zameneni pismena), aby odpovidal tomuto wildcardu.
Obsah cviceni:
- (23.2.) Opakovani prace se spojovymi seznamy.
- (2.3.) Obousmerne seznamy, ridke polynomy, jednoduche operace se stromy.
- (9.3.) Prace se stromy (rozdeleni, spojeni, sliti). 2-3 stromy, AVL stromy, RB stromy.
- (16.3.) Amortizovana casova slozitost. Binomialni haldy.
- (23.3.) Cvicil za me Martin Mares, ruzne druhy slozitosti (amortizovana, v prumernem pripade,
randomizovana), splay stromy.
- (30.3.) Cvicil za me Bobr, vnejsi trideni (n-cestne, polyfazove), uvod do hashovani.
- (6.4.) Hashovani, diskretni simulace.
- (13.4.) Diskretni simulace. Geometricke problemy -- kolize dvou kouli, obsah mnohouhelnika,
nalezeni nejblizsi dvojice bodu, rozhodnuti, zda bod(y) lezi uvnitr mnohouhelnika.
- (20.4.) Ulozky s posloupnostmi -- hledani nejcastejsiho vyskytu, k-te nejvetsi cislo, uniq,
nejvetsi dira, nejdelsi rostouci podposloupnost, maxima sousednich k-tic.
- (27.4.) Nejkratsi cesty v grafu -- Dijkstruv algoritmus a variace na nej (pouziti haldy a d-regularni haldy,
omezene delky hran, zaporne hrany, nejsirsi cesta).
- (4.5.) Eulerovske tahy, nejkratsi kruznice, Floyd-Warshal, 2-SAT.
- (11.5.) Dalsi grafove ulohy -- barveni intervalovych grafu, ...
- (18.5.) Dynamicke programovani -- vzdalenost retezcu, barveni grafu s omezenym path-width, ...
- (25.5.) Jeste jednou dynamicke programovani (doplneni uzavorkovani, vypis vsech uzavorkovani)