Kdy a kde:

• I/1-Z/48, MIU/1/75 : Po 9:00 v S6

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 30.3.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 4-5). 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:

  • Mate zadany text T slozeny ze slov (neprazdne posloupnosti pismen anglicke abecedy, oddelene mezerami) a delku radku R. Muzete predpokladat, ze delka kazdeho slova je nanejvys (R/2 - 1). Napiste program, ktery naformatuje T do radku delky R. Program mezi slova doplni mezery tak, aby delka kazdeho radku krome posledniho byla presne R a aby zadny radek nekoncil mezerou. Zvoli takove rozvrzeni mezer, aby soucet kvadratu poctu mezer mezi slovy byl minimalni (priklad -- pro rozvrzeni a,mezera,mezera,mezera,b,mezera,c,mezera,mezera,d je tento soucet 3²+1²+2²=14).

  • Mate zadano k a posloupnost cisel. Pro kazdou k-prvkovou souvislou podposloupnost najdete jeji minimum. Pozadovana casova slozitost alespon O(n log k).

  • Zakoreneny strom na vrcholech 1,...,N je zadan seznamem svych hran (orientovanych smerem ke koreni). Prevedte tuto reprezentaci bud na reprezentaci pomoci seznamu synu, nebo pomoci odkazu na nejlevejsiho syna a praveho bratra, a vypiste strom v postorderu.

  • Mate zadanu mnozinu bodu na primce S(v nejakem nespecifikovanem poradi). Naleznete v linearnim case dvojici sousednich (tj. takovych, ze mezi nimi nelezi zadny jiny prvek mnoziny S) prvku mnoziny S takovou, ze jejich vzdalenost je nejvetsi mozna.

  • Je dan (ne nutne konvexni) mnohouhelnik (souradnicemi svych vrcholu v poradi podel jeho obvodu). Urcete jeho teziste.

  • Mate zadany cetnosti pismenek v abecede. Naleznete optimalni rozlozeni pismenek na klavesnici mobilu (tj. takove, ktere vyzaduje nejmene stisku tlacitek). Pismena na klavesach musi jit podle abecedy a na kazdou klavesu se vejdou nejvyse 4 znaky.

Obsah cviceni:

• (21.2.) Vstup a vystup do souboru, formatovani textu, prace se spojovymi seznamy.
• (28.2.) Hintik k domacimu ukolu (jiny priklad na dynamicke programovani, naznak reseni). Vnejsi trideni, hledani nejcastejsiho prvku.
• (7.3.) Polyfazove trideni a jeho srovnani s rozdelovanim na vice pasek. Hledani k-teho nejmensiho prvku. Vypis stromu v pre/postorderu.
• (14.3.) Vyrotovani prvku do korene. Nerekurzivni pruchod stromem, pokud mame odkaz na otce.
• (21.3.) Pisemka na spojaky. Pridavani a odebirani z AVL stromu. Kompilace vyrazu, trivialni CSE, pouziti hashovaci tabulky.
• (28.3.) Velikonoce.
• (4.4.) Druhy pokus o pisemku na spojaky. Hashovani a dalsi zpusoby reseni problemu typu uniq.
• (11.4.) Geometricke ulohy -- urcovani, zda bod(y) lezi uvnitr mnohouhelniku, obsah mnohouhelniku, nejmensi kruh obsahujici vsechny zadane body.
• (18.4.) 2-3-stromy -- podrobne pridavani, v naznaku merge a split.
• (25.4.) Dynamicke programovani -- batoh, mapovani telefonich cisel na slova.
• (2.5.) Konstrukce optimalniho binarniho a 2-3-stromu. Huffmanovo kodovani.
• (9.5.) Parsovani vyrazu odshora.
• (16.5.) Parsovani vyrazu odspoda (regularnich), vyhodnocovani jejich vlastnosti. Hledani nejkratsi cesty vlnou.