Diskrétní matematika - cvičení ZS 2020/2021

Zde se průběžně budou objevovat nějaké informace ke cvičením vedemných mnou, ZS 2020/2021, pondělí 12:20. V tento moment výuka probíha distančně.

Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku. Pokud hledáte stránku k přednášce, najdete ji zde.

Důležité informace k online výuce

• Zde jsou údaje pro přihlášení se na cvičení přes Zoom: "Meeting id" je 954 0692 0180, zároveň je potřeba se registrovat přes tento odkaz, stačí jednou za semestr. Zároveň by přihlášeným účastníkům mělo dorazit heslo. Pokud Vám heslo nedorazilo do středy 30. září 16:00, napište mi email.
• Velmi doporučuji se online cvičení pravidelně účastnit, hodně Vám při porozumění látky jak u cvičení, tak i k přednášce. Na druhou stranu distanční výuka a vládní omezení kvůli koronaviru moho leckomu přinést nečekané problémy. Pokud Vás cokoliv omezuje při online výuce ozvěte se mi emailem, viz moje domovská stránka. Domluvíme se individuálně, jak například bude možné získat zápočet. Ozvěte se mi, prosím, i pokud máte technické potíže s k online výuce přes zoom připojovat. Opět se to budeme snažit nějak vyřešit.
• Cvičení se nebudou nahrávat.

Podmínky k zápočtu

• Budu průběžně zadávat domácí úkoly, za které bude možné získávat body.
• Bude možné získávat body za různé formy aktivity.
• Pokud se stane, že nám v průběhu semestru bude povolena osobní účast na cvičeních, tak bude možné získat body i pomocí písemky "na přilepšenou". (Cílem je, abyste nemuseli vypracovat tolik domácích úkolů, pokud se Vám u písemky bude dařit.)
• V každém případě, ať se bude dít cokoliv, bude možnost dostatek bodů získat pouze pomocí domacích úkolů.

Domácí úkoly

• Domácí úkoly mi, prosím, zatím posílejte emailem. (Je možné, že časem budu mít lepší systém, ale zatím není.) Do předmětu emailu uveďte DM2020 DUn, kde n je číslo úkolu. Například pro první úkol uveďte DM2020 DU1 (bez diakritiky). Je to kvůli tomu, abych zvládl úkoly snadno najít, jinak neslibuju, že Váš úkol nepřehlédnu. Úkoly odevzdávejte ve formátu PDF. (Rozumně čitelné, pokud je fotíte mobilem.)
• Je povoleno se o domácím úkolu s kýmkoliv bavit (osobně) včetně toho si nechat trochu poradit. V takovém případě je ale na vypracovaný úkol potřeba uvést s kým jste se o úkolu bavili. Není ale povoleno, aby Vám kdokoliv pomáhal s vypracováním řešení. (Speciálně tedy není povoleno odněkud/od někoho opsat řešení ani není povoleno si navzájem ukazovat vypracovaná řešení či sepisovat spolu, pokud se s některými spolužáky budete mít možnost potkat.)
• Nehlejte řešení na internetu ani se neptejte na řešení v jakémkoliv diskuzním fóru. (Kdybyste potřebovali trochu poradit, a nemáte koho se zeptat, tak je lepší se zeptat mne.) Pokud omylem řešení někde uvidíte, tak je opět nutné to uvést a domluvím se s Vámi na spravedlivém ohodnocení úkolu podle okolností.
• Termíny odvzdání u úkolů typicky uvádím dva. Kdo odevzdá úkol před prvním termínem, bude mít ještě možnost případně úkol opravit a odevzdat znovu, pokud se mi něco nebude líbit (bez bodového postihu). Čas odevzdání úkolů je tak, aby mi úkoly přišly před 23:59 daný den.
• Pokud někdo má dobré důvody, proč termíny úkolů nestíhá (například komplikace kvůli koronaviru), napište mi, prosím, a na něčem se domluvíme.

• 1. domácí úkol. Termín odevzdání 19. 10. (s možností korekce), 26. 10. (finální termín).

  2. domácí úkol. Termín odevzdání 2. 11. (s možností korekce), 8. 11. (finální termín). Pozor změna: finální termín je tentokrát neděle, kvůli tomu, abychom si už v pondělí mohli ukázat řešení.

  3. domácí úkol. Termín odevzdání 16. 11. (s možností korekce), 22. 11. (finální termín). Finální termín je opět neděle. Pokud si nebudete vědět rady s tím, jak začít s úlohou (b), tak se můžete podívat na drobnou nápovědu. Ale spíš doporučuju, ať prvně chvilku zkusíte přijít na řešení bez nápovědy, více se naučíte (i když se pak třeba na nápovědu podíváte).

  4. domácí úkol. Termín odevzdání 30. 11. (s možností korekce), 6. 12. (finální termín, opět neděle). DÚ má tentokrát tři varianty, ale neočekávám, že budete řešit vše (spíš se snažím nabídnou nějakou rozmanitost, samozřejmě všechny varianty řešit můžete, pokud chcete). Těm, kterým jde získávání bodů ztěžka doporučuji varianty a) a b), měly by to být relativně snadno získatelné body. Těm, kteří naopak mají bodů celkem hodně, doporučuji si zkusit důkazovou úlohu c).

  5. domácí úkol. Termín odevzdání 14. 12. (s možností korekce), 20. 12. (finální termín, opět neděle). DÚ má opět tři varianty, ale opět neočekávám, že byste měli řešit všechny. Nějaké hinty: S úlohou a) by si měl poradit každý (alespoň se dvěma grafy ze tří), pokud si vzpomenete, co jsme dělali na cvičeních (jak jsme ukazovali rovinnost, popř. nerovinnost některých grafů). U úlohy b) doporučuju postup s cvičení u podobné úlohy, co jsem ukazoval pomocí skóre. Úloha c) by měla být velmi jednoduchá pro někoho, kdo pochopil znění věty o počtu sledů (ale těžko řešitelná pro někoho, kdo té větě nerozumí). Je to tedy skvělá možnost si vyzkoušet, jestli větě o počtu sledů rozumíte.

  6. domácí úkol. Termín odevzdání 4. 1. (s možností korekce), 10. 1. (finální termín, opět neděle). Nějaké hinty: U úlohy a1) může pomoci počítání s Eulerovou formulí, principem sudosti a principem sudosti pro stěny. Úloha a2) se dá vyřešit trikem, ale může být těžké na něj přijít. Je za málo bodů, protože si myslím, že kdo vyřeší a2), tak bude umět vyřešit i a1). Variantu a2) doporučuju pouze těm, kteří mají bodů hodně, jako výzvu. Úlohu b) by měl umět vyřešit opravdu každý. Toto není poslední DÚ. Pokud někomu budou chybět body, tak ještě po posledním cvičení dám nějaké další domácí úkoly k dispozici, aby chybějící body stále bylo možné získat.

  7. domácí úkol. Termín odevzdání 18. 1. (s možností korekce), 14. 2. (finální termín, jako vždy neděle). Termín je možné prodloužit po domluvě emailem před termínem odevzdání. V případě potřeby mohu nabídnout další DÚ na žádost. Nicméně chtěl bych, aby té žádosti předcházela alespoň částečně snaha poradit si s DÚ6 a DÚ7.

Probrané úlohy

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

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

19. 10.: Pokračování příkladů z minule.

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

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

9. 11.: zadání 5. série (verze pro tisk). [Grafy, začátek.]

16. 11.: Příklady z minule.

23. 11.: zadání 6. série (verze pro tisk). [Grafy, stupně, eulerovské grafy, matice sousednosti.]

30. 11.: zadání 7. série (verze pro tisk). [Grafy, souvislost, stromy.]

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

14. 12.: zadání 9. série (verze pro tisk). [Pravděpodobnost.]

21. 12.: Příklady z minule.

4. 1.: Většina příkladů ještě z minule. Tři příklady navíc:

1. Nechť π je náhodná permutace n prvků (prvních n přirozených čísel). Určete střední hodnotu počtu i takových, že π(i) = i+1.
2. Nechť G je graf sestávající ze dvou čtyřcyklů spojených za hranu. Vytvořme náhodný podgraf H grafu G tak, že H obsahuje všechny vrcholy grafu G a každou hranu G umístíme do H s pravděpodobností p nezávisle na ostatních hranách. Určete pravděpodobnost, že H obsahuje čtyřcyklus.
3. Nechť G je (jediný) strom se skórem (4, 3, 1, 1, 1, 1, 1). Vytvořme náhodný podgraf H grafu G tak, že H obsahuje všechny vrcholy grafu G a každou hranu G umístíme do H s pravděpodobností p nezávisle na ostatních hranách. Určete pravděpodobnost, že H obsahuje K_1,3 jako podgraf.

Průběžné bodování

• Průběžné body za aktivitu a DÚ naleznete zde. Teď jsou body k datu 26. 12. (včetně všech bodů za 5. úkol.) Kdo má dostatek bodů, už by měl mít zápočet v SISu. Pokud si myslíte, že je někde v bodování chyba (ať už u aktivity či DÚ), tak mi, prosím, dejte vědět.
• Někteří z Vás už mají potřebných 70 bodů. Nicméně doporučuju řešit úkoly dále, alespoň ty, u kterých nevidíte okamžitě řešení. Stále je co se naučit.
• Pravidla bodování za aktivitu jsou následující. (Berte je ale, prosím, jako rámcová pravidla, asi nelze popsat všechny možné formy ativity.) Předvedení 1. řešení (spravného): 4 body za snadnou úlohu, 5 bodů za střední nebo těžkou (dle mého subjektivního hodnocení). Předvedení 2. řešení (správného) během téhož cvičení: 1 bod za variantu téhož příkladu nebo velmi podobnou úlohu; 2 body za odlišný příklad. Předvedení 3. a dalšího (správného) řešení: 1 bod. Nakonec se vše zpermutuje tak, aby to maximalizovalo Váš bodový zisk. Když třeba někdo předvede od snadné úlohy 1 varianty (a) a (b) a potom později předvede řešení středně těžké úlohy 5, tak dostane 5+2+1 bodů, 5 bodů je za řešení úlohy 5, 2 body jsou za řešení odlišné úlohy 1(a), a 1 bod za další variantu 1(b). U nesprávného řešení bude bodů o něco méně, podle toho, jak daleko se dostanete. Nicméně dostanete alespoň 1,5 bodu za první řešení a 0,5 bodu za každé další, i kdyby bylo nesprávné, ale je jasné, že jste se úlohu snažili vyřešit (předvedete alespoň něco). Dále dostanete 1 bod za aktivitu, pokud se u nějakého příkladu budete hlásit, že ho chcete předvést, ale ten den se na Vás vůbec nedostane, kvůli tomu, že budou řešení ukazovat ostatní. Maximální možný bodový zisk za aktivitu během semestru je 40 bodů. (Pozn. Už na druhých cvičeních se ukázalo, že je těžké měřit aktivitu úplně objektivně podla zadaných pravidel. Některé úlohy jsou snazší některé těžší, některé mají více variant, někdo má horší podmínky s předvedením úlohy. Každopádně věřím, že ti, kteří budou aktivní nebudou mít problém získat 40 bodů za aktivitu.)