Kdy a kde:

• MIU/1/75 : Po 17:20 v S7

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.2004, 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 jednoho prikladu z kazde z cca tri serii, ktere zde vypisu. Pozor -- jakmile se mi sejde dostatecny pocet reseni nektereho prikladu, nebudu uz dalsi prijimat; tj. cim pozdeji se do reseni pustite, tim mene volnosti ve volbe budete mit (receno primeji -- zbydou na vas jen hnusne priklady :-)
  Reseni prikladu se 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, takze popis by se spis nez na detailni popis toho, jak je secteme, mel zamerit na vysvetleni toho, proc je vlastne chceme secist.
  Zatim vypsane priklady:
  • 1. serie.
  • 2. serie.

Obsah cviceni:

• 16.2.2004: Priklady na permutace. Rozklad permutace na cykly, znamenko permutace. Pocet inverzi v permutaci v O(n log n) -- aplikace binarnich vyhledavacich stromu. Rad permutace -- pocitani nsn a nsd, Eukliduv algoritmus & modifikace. Invarianty a pouziti na dukaz neresitelnosti hlavolamu (15-ka).
• 23.2.2004: Opakovani prace s ukazateli. Trie. Cerveno-cerne stromy (definice + dukaz, ze jejich hloubka je logaritmicka).
• 1.3.2004: Prosivane stromy. Ukladani stromu do souboru -- rekonstrukce z preorder usporadani, nahrada ukazatelu cisly vrcholu.
• 8.3.2004: Objekty. Trideni realnych cisel (prumerne) v linearnim case.
• 15.3.2004: Poznamky k domacim ukolum (sestaveni stromu, mergesort). Prohledavani grafu do hloubky, aplikace na nalezeni kostry a topologicke trideni.
• 22.3.2004: Dokonceni z minula -- overeni silne souvislosti grafu. Reseni "hlavolamu" -- invarianty, prohledavani do sirky, iterative deeping.
• 29.3.2004: Polyfazove trideni. Binomialni haldy.
• 5.4.2004: Kostrukce optimalniho vyhledavaciho stromu. Priklady na dynamicke programovani a hladove algoritmy.
• 12.4.2004: Velikonoce.
• 19.4.2004: Hledani nejkratsi cesty v grafu -- vlna, Dijkstra, Dijkstra s heuristikou. Efektivni implementace Dijkstrova algoritmu (prime vybirani minima, d-regularni haldy, Fibonacciho haldy).
• 26.4.2004: Regularni vyrazy, konecne automaty a konstrukce prekladacu.
• 3.5.2004: Diskretni simulace.
• 10.5.2004: (a,b)-stromy.