Pisemna cast: napred je hodina na maly priklad z okruhu : spojaky (mergovani, zasobniky, fronty.......), stromy (vypisy, vytvareni, prochazeni, ....), neco malo z dlouhych cisel,... V zasade jde v malych prikladech o praci s dynamickymi strukturami a jejich konkretni pouziti (pascal) – dereferencovani, atp; tedy prakticke programovaci skills.
pak 5 minut pauza a dve hodiny na velky priklad.
Ustni zkouska probiha ( moje tak probehla ) tak ze nejdriv projde maly priklad zepta se na nejasnosti, necha vas abyste vymysleli napravu pripadnych chyb,... Pak prejde k velkemu – diskuse, ....
A nakonec se taze na nektere veci typu : reknete mi neco o : haldach, objektech, dynamickem programovani, ...
Zadani velkeho prikladu: Mate ctvercovou cokoladu 10 * 10 s policky o stranach 1. V cokolade je nekolik (<= 1000) orisku a hrozinek kruhoveho tvaru. U kazdeho orisku a hrozinky znate jejich souradnice(realne) a polomer(realny). PROBLEM: rozdelte cokoladu na libovolne velke tri dily, s co nejmensi namahou (na rezani) a to tak, ze rezat muzete jen po hranach jednotlivych dilku a v cokolade nesmi byt vyriznuty otvor. Rezani cokolady stoji 1, rezani pres cast s oriskem 5 a rezani pres hrozinku 1/2 energie na jednu hranu (tzn kdyz pulku hrany zabira orisek a zbytek je cokolada, tak hrana stoji 3 j. energie)... Mate k dispozici 1MB pameti. (Napsal Pepa Moudřík, já to sem jen přesunul.)
Reseni: (aneb ja jsem to delal takhle) Napraed se vhodne ohodnoti hrany podle toho kolik je na nich orisku/hrozinek. ( treba pomoci delky tetivy ) Tim se problem prevede na grafovou ulohu, kterou lze resit ruznymy zpusoby. Delal jsem to pomoci F-W a vhodnym prozkoumanim minimalnich cest z okraje na okraj ( namalujte si to na papir a nemel by to byt velky problem ) – 1 rez – a pak vsech cest z (okraje + uzly prvni cesty) na (okraje + uzly prvni cesty) – minimum ze souctu delek je reseni. Bohuzel vsak tenhle algotritmus muze minout optimalni reseni pri zakerne zvolenem rozlozeni orisku a hrozinek. Holan to ale stejne celkem uznal ( prodiskutovali jsme taky nejake chyby a jejich napravu, ... ) a celkove se mi zdal na zkousce velmi prijemny...
Střední kvadratická odchylka: Průměr čtverců rozdílů hodnot a střední hodnoty.
Úvaha: soubory se nám nechce číst moc často, ale asi to bude třeba
Zřejmě bude třeba třídit podle klíčů (Učitel, Předmět) (tzn. jeden průchod, dva klíče).
Postřeh: Σ (xi – R)2 / N = Σ (xi2 – 2xiR – R2) / N = (Σ xi2 – RΣ2xiR – NR2)/N
U – délka souboru Učitelé
L – délka souboru Lístky
UP – počet platných kombinací (Učitel, Předmět)
Návrh algoritmu:
Tip: Neměl jsem foťák, ale bylo nám doporučeno, abychom si kreslili obrázky (aka data-flow diagramy) jako Holan na tabuli – data a akce pospojované šipečkami.
Do Upřesnění nebo postřehů:
Do Diskuse:
Do Shrnutí:
Jako příklad úlohy uváděl problém s letištěmi, který snad je/bude na jeho stránkách, ovšem s tím, že na zkoušku je tenhle příklad naddimenzovaný.