Markéta Popelová - Výuka

Vymyslete algoritmus (obecný postup) pro setřídění N čísel. U tohoto úkolu řešení prosím určitě nikde nehledejte (na internetu, v knížkách, u kamarádů apod.). Jde o to, abyste se nad tím každý sám zamyslel a promyslel, jak by se to dalo dělat co nejlépe a nejrychleji a zkusili to zapsat, aby to bylo co nejpochopitelnější a nejobecnější.

Zároveň se zamyslete nad tím, jak je váš algoritmus dobrý. A jak je rychlý...? Jak vůbec porovnávat, který algoritmus je lepší než jiný?

Vše sepište a pošlete mi to mailem. Za výjimečně jasné či chytré algoritmy můžete získat i nějaké body navíc.

Termín: do 10.10. (23:59) za plný počet bodů, či do 17.10. (23:59) za poloviční.

Hrají dva hráči a střídají se po tazích. Mají jednu tabulku čokolády, která má levý horní čtvereček otrávený (to oba hráči vědí). V jednom tahu označí hráč libovolný dílek čokolády (na obrázku žlutá kvězdička) a odlomí celou část čokolády, která je pod ním a vpravo od něj (na obrázku obdélník 8 kostiček ohraničených červenými čarami). Ten, kdo odlomí kus obsahující otrávený čtvereček, prohrál. Tentokrát si rozmyslete strategii pro čtercovou čokoládu, tzn. tvaru NxN.

Vy máte vymyslet co nejlepší strategii pro začínajícího hráče a rozhodnout, jak je tato stategie dobrá (jestli je tzv. vyhrávající, tedy ať bude hrát druhý hráč sebelépe, tak prohraje; nebo je to jen heuristika - tedy "hloupého" hráče byste s ní porazili, chytrého ne nutně, apod.).

Budete-li potřebovat v rámci řešení něco kreslit, stačí, když řešení přinesete na papíře na příští cvičení - a odevzdáte ho PŘED začátkem příštího cvičení. (Ale samozřejmě můžete řešení poslat již v průběhu týdne e-mailem.)

Termín: do 11.10. (15:40).

Máme dvě nádoby o objemech V1 a V2. Dále máme kohoutek s vodou, které můžeme spotřebovat libovolné množství. Našim cílem je odměřit V3 vody v jedné z nádob. K tomu můžeme využít následující operace: naplnit (doplnit) jednu nádobu až po okraj, vylít obsah jedné nádoby, přelít jednu nádobu do druhé + všechno to samé s druhou nádobou). Najděte postup, jak objem V3 odměřit - a to tak, aby Váš postup měl nejmenší možný počet operací. Je zaručeno, že váš algoritmus najde postup s nejmenším počtem operací?

Na hodině jste si poslechli nápovědu k obecnému algoritmickému řešení. Ta nápověda se týkala tzv. prohledávání stavového prostoru. Stačí si chytře nadefinovat stavy, přechody mezi stavy, počáteční stav a koncové stavy - a pak už jen procházet mezi stavy nějakým rozumným způsobem směrem od počátečního ke koncovým.

Budete-li potřebovat v rámci řešení něco kreslit, stačí, když řešení přinesete na papíře na příští cvičení - a odevzdáte ho PŘED začátkem příštího cvičení. (Ale samozřejmě můžete řešení poslat již v průběhu týdne e-mailem.)

Termín: do 11.10. (15:40).

Na první lednové hodině 3.1.2013 budeme psát závěrečnou větší písemku (pozor, to není ta zápočtová, na kterou se budete hlásit přes SIS a podrobnější informace k ní dostanete od Vašich přednášejících.) Budete na ni mít čas celé cvičení. Bude na počítačích, tedy ne klasicky jako malé testíky na papír. Měla by být lehčí než ta zápočtová, také na ni bude méně času - ale tématicky podobná. Což je výhodné především z toho důvodu, že učením se na ni tzv. "zabijete dvě mouchy jednou ranou". Neboť o to kratší bude Vaše příprava na zápočtový test (ale ten nepodceňte!). Napsat tuto písemku, je nutná podmínka k zápočtu.

Komu se nepodaří napsat správně písemku na první lednové hodině, ten bude mít ještě možnost si to opravit. Ale samozřejmě ne zadarmo. Dostane dvě větší úlohy, které bude muset vypracovat. Ovšem pro každého budou pevně zadané a nebudou patřit k těm nejlehčím. Tedy doporučuji se na tuto možnost nespoléhat.

A ještě je tu jedna možnost, jak se této písemce "vyhnout". Abyste měli, jak se na písemku připravovat, máte v CodExu zadaných 5 úloh označených jako "Předpracování písemky 3.1.2013.". Zkuste si všechny z nich projít, promyslet a co nejvíce z nich si zkuste i napsat. No - a jak si je budete zkoušet napsat, tak když libovolné dvě z nich dovedete do funkčního stavu včetně slovního popisu řešení v úvodu a dostatečných komentářů, můžete je odevzdat do CodExu - a pokud budou správně, nebudete muset psát tu lednovou písemku. (Resp. si ji napsat můžete, abyste si to zkusili, ale povinnost k zápočtu budete mít už splněnou.) Ovšem pozor, na každou úlohu máte povolená nejvýše 3 odevzdání, takže si prvně pořádně zkontrolujte, zda Vám úloha funguje na vzorovém vstupu a i na dalších vstupech, které vymyslíte. Termín pro odevzdání těchto úloh do CodExu je 31.12.2011 (23:59) (nenechávejte je na poslední chvíli - byla by škoda programovat o Silvestru ;)). Pokud vyřešíte například jednu úlohu ze dvou, budete to mít jako bonus k lednové písemce.

Doporučuji všem na lednovou písemku dorazit. I kdybyste měli "předpracováno" dostatek na zápočet, tak si zkusíte, jaké je to psát program v časově omezeném prostoru a mimo pohodlí domova/koleje. Zároveň tam s Vámi mohu probrat Vaše chyby z doma vypracovaných úloh.