Průběh cvičení a podmínky získání zápočtu

Abyste mohli ke zkoušce z Grafových algoritmů, potřebujete získat zápočet ze cvičení. Hlavní podmínkou získání zápočtu je aktivní účast. Tím se rozumí jednak pravidelná docházka (jsou povoleny nejvýše 2 neomluvené absence), jednak vyřešení vybraného domácího úkolu a prezentace tohoto řešení na cvičení. Výjimku tvoří studenti, kteří navštěvovali tento předmět již minulý rok, získali zápočet ze cvičení avšak nepodařilo se jim složit zkoušku. Pro ty jsou účast na cvičení i řešení domácího úkolu dobrovolné (avšak doporučené).

Níže je uveden seznam příkladů z "brožurky" (brzy bude k dispozici ve studijních materiálech, rovněž by měla být k sehnání v tištěné formě v knihkupectví U Marečka a samozřejmě v knihovně FI). Pozor na to, že číslování příkladů se může u různých vydání lišit, směrodatná bude právě verze ve studijních materiálech v ISu. Pokud není u příkladu uvedeno jinak, je určen pro jediného řešitele. Každý z Vás si (pokud možno v dostatečném předstihu) vybere jeden z úkolů, který se doma pokusí vyřešit, a toto řešení posléze předvede formou referátu ve cvičení. Za jedno cvičení bychom měli stihnout 2-3 referáty, program cvičení (tj, kdo bude přednášet svůj referát) vždy určím s dostatečným předstihem. Své úkoly si můžete "rezervovat" mailem na adresu cvičícího počínaje úterým 22.9.

K formě referátů: Vaše referáty tvoří hlavní náplň cvičení, proto se snažte připravovat poctivě:-). Pamatujte, že přednášíte především pro své kolegy, nikoliv pro cvičícího, který má spíše funkci moderátora. Vždy byste měli srozumitelně vysvětlit zadání a definovat pojmy, které budete v dalším průběhu používat. Je žádoucí si připravit na papír nějakou osnovu. Vzhledem k tomu, že času je málo, je nutné, aby byl průběh Vašeho referátu plynulý a nezabíral více času, než je potřeba. Pokud se tedy jako řečníci necítíte být příliš pevní v kramflecích, vyzkoušejte si přednes referátu doma nanečisto. Snažte se o matematicky přesné vyjadřování. Je-li náplní úkolu návrh nějakého algoritmu, je nedílnou součástí řešení důkaz korektnosti a analýza časové složitosti Vámi navrženého algoritmu.

O řešení referátu byste se měli pokusit samostatně (i když pochopitelně nemám prakticky žádnou možnost, jak to zkontrolovat), přestože k některým úkolům lze jistě nalézt mnoho materiálu na internetu. Jen tak totiž pro Vás bude mít cvičení nějaký smysl. Je možné, se se Vám nepodaří vyřešit některý těžší úkol zcela. V takovém případě je možné (po domluvě se mnou) odpřednášet alespoň část řešení a následně vysvětlit, v čem je problém, který Vám znemožňuje pohnout se dál. Zbytek řešení pak můžeme diskutovat na cvičení. Toto by však měla být jen výjimečná situace týkající se těžších příkladů. Pokud se při řešení nemůžete dlouhou dobu pohnout z místa, můžete se mi ozvat mailem. Vždy však chci, abyste v takovém mailu vysvětlili, v čem spočívá problém a jaké (neúspěšné) postupy jste zatím zkoušeli. Neobracejte se na mě prosím o pomoc dřív, než si nad příkladem několik hodin posedíte:-). I v takovém případě vám však nabídnu jen malý hint. Ke konzultacím můžete rovněž využít diskusních fór. Pokud budete chtít, můžete mi v předstihu poslat osnovu svého řešení, jestli ji však nepošlete dostatečně dopředu, těžko Vám ji okomentuji dříve, než na cvičení:-).

Je možné, že ne všichni stihnete v průběhu semestru své referáty odpřednášet. Ti, na které čas nevyjde, budou muset svá řešení odevzdat v písemné podobě.

Seznam možných úkolů:

• 22.1-4 (vypracuje Andrej Podhradský)
• 22.1-6 (vypracuje Martin Adam)
• 22.2-6 + 22.1-7 (vypracuje Jan Fousek)
• 22.2-7 (možno řešit ve dvojici)
• 22.2-8
• 22.2-4 + 22.2-5
• 22.3-4 + 22.3-9
• 22.3-11
• 22.3-7 + 22.3-8 + 22.3-10
• 22.3-12 (možno řešit ve dvojici)
• 22.4-2 (vypracoval Martin Damek)
• 22.4-3 + 22.4-4
• 22.4-5 (vypracoval Michal Bureš)
• Problem 22-2 (možno řešit ve dvojici)
• Problem 22-3 (možno řešit ve dvojici)
• Problem 22-4
• 22.5-5
• 22.5-6 + 22.5-3
• 22.5-7 (vypracuje Vít Kožín)
• 23.1-8 + 23.1-9
• 23.1-7 + 23.1-10 (vypracovala Zuzana Pekarčíková)
• 23.1-5 + 23.2-1
• 23.2-7 (možno řešit ve dvojici)
• Problem 23-1 (možno řešit ve dvojici)
• 24.1-3 + 24.1-4
• 24.2-4
• 24.3-4
• 24.3-6 + 24.3-7 (možno řešit ve dvojici)
• Problem 24-2
• Problem 24-3
• 25.1-9
• 25.1-10
• Problem 25-1