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.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 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 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 25.10.) Napiste program, ktery ze vstupu nacte prirozena cisla a,
b a n, a nalezne prirozena cisla x a y takova, ze
a<= x <=y<=b a x3 + y3 = n (pripadne urci,
ze neexistuji). Program by mel fungovat s casovou slozitosti O(b-a), a nemel by pouzivat
necelociselnou aritmetiku (napriklad exp, ln, apod.)
- (Do 8.11.) Napiste program, ktery nacte cislo n a permutaci n prvku,
a vypise cykly, z nichz se permutace sklada. Napriklad pro vstup n = 6 a permutaci
2 3 1 5 4 6 vypise (1,2,3)(4,5)(6).
- (Do 22.11.) Napiste program, ktery pro zadane n vypise vsechna dobra uzavorkovani,
skladajici se z n oteviracich a n zaviracich zavorek.
- (Do 20.12.) Mate zadan orientovany graf, rozhodnete, zda obsahuje orientovany cyklus.
Obsah cviceni:
- (4.10.) Uvodni povidani. Priklady o vazeni (vcetne dolnich odhadu), prelevani, tunel, provazky.
- (11.10.) Imatrikulace.
- (18.10.) Hledani minima a druheho nejmensiho prvku. Jednoduche programky -- minimum, nejdelsi rostouci
usek, nejdelsi usek s nejvyse jednim poklesem.
- (25.10.) Odmocnina pulenim intervalu, logaritmus, eukliduv algoritmus a jeho slozitost.
- (1.11.) Vyhledavani pulenim intervalu, vkladani do setrideneho seznamu, permutace -- skladani,
rozklad na transpozice.
- (8.11.) Cislo permutace, nasledujici permutace, vyhledavani retezce pomoci konecneho automatu.
- (15.11.) Rekurze -- generovani permutaci, podmnozin, ... Nejdelsi rostouci podposloupnost.
- (22.11.) Orezavani backtracku -- rozmisteni dam na sachovnici.
- (29.11.) Cvicil za me Honza Kara, quicksort, batoh, rekurzi.
- (6.12.) Odpadlo.
- (13.12.) Reprezentace grafu, prohledavani do hloubky, komponenty, disjoint find-union.
- (20.12.) Prace s ukazateli, spojove seznamy.
- (3.1.) Operace s dlouhymi cisly, rychle nasobeni polynomu, vlastnosti floating-point cisel.
- (10.1.) Trideni, halda.