Cvičení z diskrétní matematiky

Zde jsou informace pro studenty předmětu Diskrétní matematika (2016/2017), čtvrteční cvičení od 14:00 k přednášce J. Kynčla.

Co se dělalo na cvičení

• 1. hodina (6. 10.): Značení, matematická indukce, falešné indukční důkazy.

  Na rozmyšlení do příště: Dokažte, že počet posloupností nul a jedniček délky \(n\), které neobsahují dvě nuly těsně vedle sebe, je roven \(F_{n+2}\).

• 2. hodina (13. 10.): Relace, zobrazení, uspořádání. Největší, maximální, nejmenší a minimální prvky, řetězce a antiřetězce. Rozdával se Tahák na relace, zobrazení a uspořádání.
• 3. hodina (20. 10.): Relace, zobrazení, uspořádání.
• 4. hodina (27. 10.): Ekvivalence, uspořádání.
• 5. hodina (3. 11.): Byla písemka na relace. Kombinatorické počítání.

  Na rozmyšlení do příště: Uvažte mřížku \(m\times n\), kde \(m\) a \(n\) značí počet horizontálních a vertikálních čar. Kolik existuje obdélníků (včetně čtverců), jejichž strany leží na této mřížce?

• 6. hodina (10. 11.): Princip inkluze a exkluze, kombinatorické počítání.
• 7. hodina (24. 11.): Dirichletův princip, šatnářka a kombinatorické počítání.
• 8. hodina (1. 12.): Byla písemka na kombinatorické počítání a princip inkluze a exkluze. Pravděpodobnostní prostor, jednoduché pravděpodobnostní úlohy.
• 9. hodina (8. 12.): Pravděpodobnost, náhodné veličiny, střední hodnota, indikátorová metoda.
• 10. hodina (15. 12.): Suploval Jenda Hadrava. Byla písemka na pravděpodobnost. Základy teorie grafů.
• 11. hodina (22. 12.): Pokračování grafů, skóre, grafové reprezentace, eulerovské grafy, rovinné grafy.

Domácí úkoly

• 1. úkol – do 3. 11. 2016
• 2. úkol – do 15. 12. 2016
• 3. úkol – do 5. 1. 2017
• 4. a 5. úkol – do 12. 1. 2017

Při řešení úkolů můžete spolupracovat, řešení ale budete muset sepsat každý sám. Pokud někomu bude prokázáno opisování, nedostane zápočet. Všechny kroky se snažte pečlivě zdůvodnit, je to důležitější než mít správný výsledek. Věty z přednášek a ze cvičení můžete používat bez důkazu, jen vždy uveďte, co právě používáte.

Pokud nechcete mít zveřejněno jméno na webu, použijte k podpisu úkolu kromě svého jména i přezdívku. Řešení preferuji odevzdané v papírové podobě přímo na cvičení. Pokud nemůžete dorazit, můžete jej poslat i na můj e-mail.

Požadavky na zápočet

V průběhu semestru zadám několik sérií domácích úkolů. Deadline bude vždy minimálně dva týdny od zadání série. Celkem bude za domácí úkoly možnost získat nejméně 50 bodů.

Dále budeme v průběhu semestru budeme psát tři průběžné a jednu závěrečnou písemku. Průběžné budou krátké, cca na 15 minut, zadávat je budu zpravidla na začátku hodiny. Závěrečná bude delší, cca na 60 minut. Písemku oznámím nejméně týden předem. Za průběžnou písemku bude možno získat 10 bodů, za závěrečnou 20 bodů. Celkem tedy bude za písemky možno získat až 50 bodů.

Kromě bodů za písemky a úkoly můžete dostat ještě body za aktivitu. Tyto body jsou navíc a můžete je použít jak místo bodů za písemky, tak místo bodů za domácí úkoly, podle toho co se vám více hodí. Body za aktivitu získáte, když na cvičení předvedete správné řešení nějakého netriviálního příkladu na tabuli. Za jedno takové vystoupení můžete dostat 0.125 až 2 body, podle obtížnosti příkladu a kvality vystoupení.

Zápočet dostane ten, kdo bude mít na konci semestru alespoň 30 bodů z domácích úkolů a alespoň 30 bodů z písemek. S těmi, co budou mít alespoň 20 bodů z domácích úkolů a 24 bodů z písemek se budu ochoten bavit o možnosti doplnění bodů a dodatečném získání zápočtu.