Diskrétní matematika - cvičení

Zde se průběžně budou objevovat nějaké informace ke cvičením ZS 2019/2020, středa 14:00 T10 a středa 15:40 T7.

Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.

Speciální (náhradní) písemka

Počítejte s náhradní písemkou v pátek 17. 1. od 9:30 v učebně S4. Body získané za domácí úkoly, docházku a aktivitu se Vám budou plně započítávat do náhradní písemky. Body za předchozí písemky se budou započítávat částečně. Na písemku budete mít dostatek času (aspoň 3 hodiny).

Výsledky 2. písemky

Zde naleznete výsledky 2. písemky a celkové bodování, skupina 14:00, skupina 15:40.

Několik důležitých poznámek:

1. V pondělí 13. 1. od 15:30 v učebně S6 na Malé Straně bude probíhat konzultace. Plán je, že předvedu řešení písemky (obou skupin) a poté bude prostor pro dotazy. Velmi doporučuju účast všem těm, kteří s písemkou trochu zápasili.

2. Úplně každému (pokud nemůžete/nechcete dorazit na konzultaci) doporočuju, ať si najde trošičku času až bude někdy na Malé Straně, a zajde se podívat na svoji opravenou písemku, kde dělal chyby. Sídlím v kanceláři 325 (třetí patro), ale silně doporučuju, ať mi prvně napíšete email. Nejsem v kanceláři pořád.

3. Kdo nemá ještě dost bodů, bude mít možnost opravy na opravné písemce. V první řadě nabízím další DÚ níže, pomocí kterého můžete získat nějaké další body. (Někomu to může stačit hned k zápočtu, někdo si tím může pomoci k tomu, aby to měl na opravné písemce snazší.) Všem, kteří nemají dostatečný počet bodů napíšu email s dotazem na termín.

Dobrovolný DÚ 3

Vytvořme náhodný graf G následujícím způsobem: Zvolíme tři množiny A={1}, B={2,3} a C={4,5,6}. Množina vrcholů G je sjednocení množin A, B a C. Hrany G vedou pouze mezi různými dvojicemi množin (tj. například z A do C, ale nikoliv z C do C). Každou takovou hranu do grafu umístíme s pravděpodobností 1/3 nezávisle na ostatních hranách. Určete střední hodnotu (a) počtu hran v G (b) počtu trojúhelníků v G (c) počtu indukovaných podgrafů H grafu G izomorfních cestě délky 2 (cestě se třemi vrcholy) (d) počtu všech podgrafů H grafu G izomorfních cestě délky 2 (cestě se třemi vrcholy).

Za zcela vyřešený DÚ nabízím 10 bodů, přesnější bodování je 2+2+3+3. . Termín DÚ je 2. 2. Prodloužení termínu je možné pouze po předchozí vzájemné domluvě před tímto datem.

Dodatečný komentář: Střední hodnotu jsme nestihli probrat na cvičeních, ale měli byste ji znát z přednášky. Úkol tedy složí i k tomu, abyste se na tu střední hodnotu podívali sami. K řešení by Vám měla pomoci linearita střední hodnoty. Kdyby s úkolem měl někdo závažné problémy, tak mi napište, co jste zkoušeli. Já se Vás budu snažit odkázat na nějaké jiné úlohy na střední hodnotu, které by Vám mohly pomoci.

Průběžné bodování

Průběžné bodování najdete zde: Skupina 14:00 a Skupina 15:40. Obsahuje už i bodování za druhý DÚ, aktivitu a docházku. Body za docházku předpokládají účast na druhé písemce, jinak se mohou ještě změnit. Kdo má u druhého DÚ otázník, potřebuju se na něco zeptat, než udělím finální body. Pokud najdete v bodování jakékoliv chyby, ozvěte se, prosím.

Druhá písemka

S druhou písemkou počítejte na posledních cvičeních 8.1. Písemka bude na celá cvičení za 60 bodů.

Dobrovolný DÚ 2

Zde nabízím dobrovolný domácí úkol 2. Mezi variantami a) a b) si vyberte jenom jednu. Bodování je 3 body za a), 4 body za b), 3 body za c) (maximálně tedy můžete získat 7 bodů). Termín odevzdání úkolu je 18. 12. 2019 (na začátku cvičení). Kdo mi však řešení úkolu odevzdá nebo pošle mailem do 11. 12. 2019 (na začátku cvičení), tomu napíšu nějaké připomínky, poud řešení nebude v pořádku (a bude mít možnost řešení ještě opravit bez ztráty bodů).

Výsledky první písemky

První písemka byla 6. 11. Bylo možné získat 40 bodů. Výsledky skupiny v 14:00 a skupiny skupiny v 15:40. Výsledky obsahují též body za 1. DÚ a za aktivitu k 6. 11. Prosím o kontrolu, jestli všichni, kdo odevzdávali DÚ ode mě dostali body.

První písemka

Počítejte s první písemkou na 6. cvičeních, tedy 6. 11. Písemka bude zhruba na 60 minut a zhruba za 40 bodů.

Dobrovolný domácí úkol 1

Nabízím dobrovolný domácí úkol s termínem odevzdání 6. 11. Úkol má varianty (a) a (b), body dostanete pouze za jednu variantu, doporučuju si tedy vybrat tu, která Vám bude lépe vyhovovat. (Varianta (b) je dle mého osobního názoru těžší. Není nutné, aby takový příklad uměl vyřešit každý.)


Varianta (a), 3 body: Nechť A, B a C jsou relace na téže množině X. 1. Jsou-li tyto tři relace reflexivní, rozhodněte, zda je také A Δ B Δ C reflexivní. 2. Jsou-li tyto tři relace symetrické, rozhodněte, zda je také A Δ B Δ C symetrická. 3. Jsou-li tyto tři relace tranzitivní, rozhodněte, zda je také A Δ B Δ C tranzitivní. Ve všech případech své tvrzení pořádně zdůvodněte (tj. dokažte nebo nalezněte protipříklad). Symbol Δ značí symetrickou diferenci množin.


Varianta (b), 4 body: Nechť A a B jsou relace ekvivalence na téže množině X. Předpokládejme, že i jejich sjednocení A∪B je relace ekvivalence. Rozhodněte, zda jejich složení A∘B musí být relace ekvivalence. Pořádně zdůvodněte.

Podmínky k zápočtu

Podmínkou k získání zápočtu je získat 70 bodů. Budou dvě písemky (na 100 možných bodů). Dále je možné získat nějaké body navíc za docházku (5 bodů), aktivitu během cvičení (není omezeno, čekejte tak kolem 8-10 bodů pro aktivnější), příležitostné domácí úkoly. V případě neúspěchu při řešení písemek bude náhradní možnost za obě písemky (speciální písemka), ale až během zkouškového. Nicméně doporučuji se připravit už napoprvé, dříve budete moci ke zkoušce a nebudete se muset trápit se získáváním zápočtu během zkouškového.

Příklady z cvičení

Zde se budou objevovat příklady z cvičení ve formátu .pdf. Jsou vytvořeny pomocí aplikace sbírka příkladů . V této sbírce naleznete i řešení některých příkladů. (Z části jsou čerpány z knihy od J. Matouška a J. Nešetřila Kapitoly z diskrétní matematiky).

2. 10.: zadání 1. série (verze pro tisk). [Matematická indukce a množiny.]

9. 10.: zadání 2. série (verze pro tisk). [Relace.]

16. 10.: zadání 3. série (verze pro tisk). [Kombinatorické počítání.]

23. 10.: Počítali jsme úlohy z minula.

30. 10.: zadání 4. série (verze pro tisk). [Princip inkluze a exkluze.]

6. 11.: Byla písemka, 60 minut. Zadání 5. série (verze pro tisk), kterému jsme se věnovali zbylých 30 minut. [Grafy, začátek.]

13. 11.: Příklady z minula.

20. 11.: zadání 6. série (verze pro tisk). [Grafy - souvislost, stromy, kostry.]

27. 11.: zadání 7. série (verze pro tisk). [Grafy - stupeň vrcholů, eulerovské grafy.]

4. 12.: zadání 8. série (verze pro tisk). [Grafy - rovinnost.]

11. 12.: zadání 9. série (verze pro tisk). [Barevnost grafů, pravděpodobnost-začátek.]

18. 12.: zadání 10. série (verze pro tisk). [Pravděpodobnost-pokračování.]