PRUBEH:
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...