Na zápočet je potřeba získat 40 bodů.
Kdo získá zápočet, tomu ho zapíšu do sisu. O zapsání do indexu si pak požádejte zkoušejícího na zkoušce.
Zdrojem bodů je závěrečná písemka a domácí úkoly. Průběžné úkoly byly zadávány z hodiny na následující hodinu, na jejímž začátku řešení každé úlohy některý z úspěšných řešitelů předvedl. Úkoly je také možno posílat elektronicky, nejlépe ve formátu pdf nebo jpg, nebo jako prostý text (pokud to charakter úlohy umožňuje). Od 4.6. do 24.7. budu v zahraničí a úlohy bude možné odevzdávat pouze elektronicky.
Písemka se psala na cvičení 22.5..
Zadání DÚ: 1.série 2.série 3.série 4.série 5.série 6.série 7.série 8.série
Úkoly na doplnění bodů. (poslední úlohy přidány 22.5., žádné další už nepřibydou, mohou přibývat pouze upřesnění a opravy zadání) Odevzdávat můžete kdykoli do konce září, počítejte ale s tím, že mi opravení může trvat i týden, v létě i více. U každého příkladu jsou jen 2 možná bodová hodnocení - plný počet bodů nebo 0; u příkladu vyřešeného zčásti nebo s chybou napíšu, co je potřeba doplnit/opravit a vrátím ho k doplnění/opravení. U příkladů rozdělených na samostatně bodované části a), b) ... se každá jedna část považuje za jeden příklad.
V řešeních příkladů všechna netriviální tvrzení řádně zdůvodněte. Můžete bez důkazu používat tvrzení z přednášky a ze cvičení, vždy ale napište znění takového tvrzení.
Co jsme probrali:
21. a 28.2: Suploval Tomáš Valla, opakování z diskrétní matematiky: základy pravděpodobnosti a počítání kombinatorických objektů (grafů, sudých a lichých podmnožin, nejkratších cest mezi dvěma body mřížky ...)
6.3.: Kombinatorické počítáni, zejména za použití principu inkluze a exkluze (PIE), zadání a nástiny řešení
13.3. Vytvořující funkce: Simulace hodu standardní dvojicí šestistěnných kostek pomocí dvojice šestistěnných kostek s jinak očíslovanými stěnami (zmínka, že šlo využít funkci factor v Maple-u, který je k dispozici například v linuxovém labu Rotunda). Zopakování operací s vytvořujícími funkcemi a zadání příkladů na příště.
20.3. Hledání vytvořující funkce k zadané posloupnosti a naopak. Řešení rekurencí. Řešení úloh na VF a rekurencí včetně rekurencí, kterě se nestihly na cvičení.
27.3. Catalanova čísla: Počet korektních uzávorkování s n páry závorek. Při "posunutí rekurence" v definici (D_1 = 1; D_n = suma od 1 do n-1 z D_i*D_{n-i}) vyjde D_n = C_{n-1}. Šatnářka přes vytvořující funkce (zopakování z přednášky). Konečné projektivní roviny: příklady splňující (P1) a (P2), ale ne (P0).
3.4.Alternativní znění (P0), tedy podmínka (P0') splňující, že (P1)&(P2)&(P0') je ekvivalentní s (P1)&(P2)&(P0), kde (P0'): Žádná přímka ani dvojice přímek nepokryjí celou X.
10.4. Hallova věta a její formulace pro bipartitní grafy a pro (0,1)-matice. Hrany k-regulárního bipartitního grafu lze rozložit na k disjunktních perfektních párování a důsledek: Pokud máme v tabulce nxn vyplněna čisla k+1 až n tak, že v každém řádku i sloupci se každé z nich vyskytuje právě jednou, můžeme tabulku vždy doplnit na latinský čtverec. V bipartitním grafu je velikost nejmenšího vrcholového pokrytí rovna velikosti maximálního párování - důkaz z Hallovy věty a zmínka o důkazu přes toky.
17.4 Suploval Martin Tancer: Toky: v konkrétních grafech; varianta s kapacitami ve vrcholech. Stupeň souvislosti grafu: Úlohy 1-6.
24.4. Důsledky Mengerovy věty: Ve vrcholově k-souvislém grafu (k≥2) lze každou k-tici vrcholů propojit kružnicí a pro každou dvojici hran lze najít kružnici, na které obě leží. Varianta s trojicí hran a varianty s hranovou souvislostí namísto vrcholové neplatí. Hrubé, ale zato jednoduché odhady na počet koster úplného grafu: zdola ½(n/e)n (z počtu hamiltonovských cest) a shora (en)n (z počtu podgrafů s n-1 hranami).
15.5. Triviální varianta Ramseyovy věty s barvením vrcholů namísto hran. Počítání dvěma způsoby: Identita 3^n = suma pres k od 0 do n ze sumy pres l od 0 do k z (n nad k)*(k nad l). Maximální počet hran v grafu bez K_{2,t}.
22.5. Písemka