Kdy a kde:
Za co je zapocet:
- Zapoctovy program -- tema vcetne specifikace, v niz shrnete, co ma
vami vytvoreny program umet, byste mi meli oznamit do
30.11.2005, pokud vas nic nenapada, zkuste se podivat
na muj seznam napadu na zapoctaky,
pripadne podstatne rozsahlejsi seznam na strankach Martina Marese.
(primerena obtiznost je 3-4). 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 13.10.) Na kraji pouste siroke 1000 km mame velblouda a 3000 bananu.
Velbloud unese nanejvys 1000 bananu a zere 1 banan/km. Urcete, kolik bananu
lze nejvyse dostat na druhou stranu pouste, a dokazte, ze to lepe nejde.
- (Do 3.11.) Napiste program, ktery rozhodne, zda je zadane cislo delitelne 17.
Cislo je zadano v desitkove soustave, a muze mit az stovky tisic cislic.
- (Do 10.11.) Navrhnete poradi permutaci takove, abyste dokazali urcit cislo
permutace v tomto poradi v linearnim case, a napiste program, ktery pro zadanou
permutaci toto cislo urci.
- (Do 15.12.) Napiste program, ktery pro zadany graf urci minimalni pocet hran,
ktere je k nemu potreba pridat, aby zacal byt hranove 2-souvisly.
- (Do 22.12.) Napiste funkci, ktera sleje dva setridene spojove seznamy (viz mergesort).
Obsah cviceni:
- (6.10.) Ulozky na algoritmizaci a odhady slozitosti -- vazeni,
mrakodrap.
- (13.10.) NIMy, jednoduche programky (maximum, 2. nejvetsi prvek, nejdelsi rostouci usek
v posloupnosti).
- (20.10.) Cviceni za me vzal Tomas Vyskocil; ulozky na casovou slozitost, trideni,
hledani sqrt(n) nejvetsich prvku v nesetridenem poli. Nejdelsi posloupnost s nejvyse jednim
poklesem, vyhodnoceni polynomu.
- (27.10.) Vyhledavani pulenim intervalu, pocitani odmocniny a logaritmu. Trik s dvema
"honicimi se" ukazateli -- nalezeni dvou bodu, ktere lezi naproti sobe na kruznici. Eukliduv algoritmus
a jeho slozitost.
- (3.11) Permutace -- skladani, cykly, minimalni exponent, ktery da identitu. Ocislovani permutaci.
- (10.11.) Cvicil za me Jan Kara, priklady na rekurzi.
- (17.11.) Svatek.
- (24.11.) Orezavani backtracku -- nasobeni konstantou pomoci nejmensiho poctu scitani,
algebrogramy, pruchod sachovnice jezdcem, rozvrh.
- (1.12.) Reprezentace grafu (matice sousednosti, seznam hran, seznam sousedu) a prevody mezi nimy.
Bucket sort. Hledani kruznice v grafu.
- (8.12.) Grafove algoritmy -- prohledavani do hloubky a do sirky. Kostra,
hledani mostu. Minimalni kostra, DFU.
- (15.12.) Spojove seznamy -- jednoduche operace (mazani prvku, rozdeleni na poloviny, ...)
- (22.12.) Reprezentace grafu spojovymi seznamy sousedu (+matice sousednosti). Triky pro
praci se spojovymi seznamy -- ukazatel na ukazatel, mazani prvku prekopirovanim hodnoty z naslednika.
Operace s dlouhymi cisly. Nasobeni dlouhych cisel v case O(n^{log_2 3}).