Markéta Popelová - Výuka

• Zkontrolujte, že jste zapsani na příslušné cvičení v rozvrhu v SISu.
• Vytvořte si účet do labu v Karlíně.
• Zaregistrujte se do CodExu.
• Tento nebo nejpozději příští týden si stáhněte a nainstalujte Vývojové prostředí Pascalu. Asi nejsnazší je stáhnout si FreePascal. Máte-li možnost, můžete používat i BorlandPascal či TurboPascal.

K úloze se váže legenda...

Za devatero horami a devatero řekami stojí hrad téměř v nebesích. Na něm bydlí krásná princezna, která žije jen se svým otcem, tatíčkem panem králem. Její maminka jí zemřela, když byla dcerunka ještě dítko - a má po mamince jedinou památku - náhrdelník s korály. Sama si pamatuje, jak jí maminka kdysi kladla na srdce, že je nesmí nikdy poztrácet. Jelikož byla maminka chytrá, nechala je očíslovat, aby se lépe zjistilo, zda se nějaký neztratil (a případně který to byl). Nejlepší řemeslíci z podhradí na korále tedy drobným stříbrným písmem vyryli jejich čísla. A tak zjistili, že jich je 100. Jednou si však princezna hrála na louce, zakopla o kořen a náhrdelník se roztrhl a korále se rozsypaly. Když je všechny posbírala, zjistila, že jeden chybí. Tatínek hned nařídil, aby jí ho znovu vyrobili. Ale který to byl?

Našim úkolem je, abychom princezně poradili, jak nejrychleji zjistí, který korálek ztratila. Když si princeznin problém převedeme na algoritmickou úložku, máme na vstupu zadané číslo n (tedy počet korálů) a následně n - 1 čísel (čísla neztracených korálů). A máme vymyslet nějaký algoritmus, který co nejrychleji vydá číslo chybějícího korálku. Zároveň musíme evidovat, co vše k tomu potřebujeme (odpovídá paměti algoritmu). Cílem je samozřejmě vymyslet algoritmus, který spotřebuje času i paměti co nejméně.

Vymyslete nějaký algoritmus, který tuto úlohu řeší, zapište ho v nějakém pseudokódu (podobně jako hledání v seznamu na hodině). Hodnotit se bude kromě správnosti algoritmu především srozumitelnost. Zároveň si rozmyslete a zapište, jakou má váš algoritmus časovou složitost (v nejhorším případě). (Tzn. zajímá nás, kolik nejhůře kroků udělá, ale nemusíme počítat ty kroky přesně, stačí nám mít představu, zda to bude O(n), či O(n²), nebo třeba O(n!)). Vše mi pošlete e-mailem.

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

Na cvičení jste vymysleli algoritmus na hledání jména v setříděném telefonním seznamu. Hlavní myšlenka: vždy se podíval doprostřed prohledávané části seznamu a podle toho, zda se jméno 1) shodovalo s hledaným, 2) bylo blíže v abecedě než hledané, 3) bylo dále v abecedě, tak se 1) skončilo s úspěšně najitým jménem, 2) podívalo na pravou polovinu prohledávané části (opět doprostřed atd.), 3) podívalo na levou polovinu prohledávané části. Algoritmus skončil, jakmile jsme buď hledaný záznam našli, nebo jakmile se nám prohledávaný interval zúžil na jednobodovou množinu s jediným záznamem (který nebyl hledaný).

Rozmyslete, jakou má tento algoritmus časovou složitost. Můžete počítat s tím, že operace - podívej se na jméno uprostřed seznamu - trvá konstantně dlouho (O(1)). Stejně tak porovnání jmen, i přepočítání mezí prohledávané části seznamu. Zkuste najít nejlepší horní odhad časové složitosti. Výsledek včetně odůvodnění mi pošlete e-mailem.

Termín: do 17.10. (23:59).

Mějme funkce:

• f₁ = nⁿ
• f₂ = 2ⁿ
• f₃ = n!
• f₄ = log₂n
• f₅ = log₁₀n

Pro každou dvojici funkcí rozhodněte, zda platí f_i ∈ O(f_j) a/nebo f_j ∈ O(f_i). Zároveň pomocí definice symbolu O daný vztah dokažte. Za každý správně dokázaný vztah získáte 1 bonusový bod. Nejvíce můžete za tento bonusový úkol získat 20 bodů.

Řešení sepište ideálně ve Wordu pomocí vzorců - či ještě lépe, kdo umíte, v TeXu (kvůli této úloze se ho ale učit nemusíte;) - nicméně časem by se Vám mohl hodit). Případně můžete řešení sepsat rukou a odevzdat ho příště před cvičením.

Termín: do 18.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.