Cvičení z Diskrétní matematiky

Cvičení k přednáškám Martin Mareše, které probíhá každý pátek od 10:40 v místnosti N4 v budově IMPAKT.

Podmínky zápočtu

Zápočet se získá za body, body se získají za řešení domácích úloh. Nová série úkolů bude zadána zpravidla každý týden. K získání zápočtu bude potřeba získat 100 bodů 80 bodů, přičemž budou vypsány úkoly minimálně za 150 bodů. Každá série bude obsahovat úlohy za alespoň 10 bodů, ale typicky více.

Na cvičeních není vyžadována účast, ale pochopitelně je doporučena.

K řešení úkolů

Při řešení úkolů je nutné zdůvodňovat postup, a to i tehdy, kdy je úkolem pouze něco spočítat. Na věty z přednášek můžete odkazovat libovolně, ovšem je nutné uvést, kterou větu používáte a jak.

Řešení úkolu musí zformulovat a sepsat každý sám, je ovšem povoleno (a doporučeno) při řešení spolupracovat s ostatními. Ve více lidech se to lépe táhne.

Řešení úkolů posílejte na honst at iuuk.mff.cuni.cz ve formátu PDF s předmětem začínajícím “DM”.

Za jednotlivé úkoly nedávám částečné body za částečné řešení. Místo toho máte možnost iterovat svoje řešení, dokud nebude správně. Typický postup je následující: pošlete mi řešení a já ho opravím. Pokud bude správně, tak je to výborné a dostanete body. Pokud ne, pošlu vám zpět, kde je chyba, případně ukážu, jak vaše zdůvodnění vede k nějakému absurdnímu výsledku. Následně můžete svoje řešení upravit a poslat, čímž se vrátíme na začátek.

Deadline na první verzi řešení bude vždy dva týdny po vypsání úkolu. Tedy do dvou týdnů je potřeba odevzdat první verzi řešení a potom už můžeme iterovat téměř libovolně dlouho. Řešení ovšem musí být “vážně míněné”, tj. ne zjevně odfláknuté, či neúplné jen s cílem prodloužit si deadline.

Pěkný a podrobný návod na řešení domácích úkolů sepsal Vašek Končický.

V případě jakýchkoli otázek (k zadání, k řešení úkolu, k něčemu jinému) mi napište email a vyřešíme to.

Program cvičení

1. cvičení (30.9.) Opakování matematické logiky, typy důkazů, matematická indukce
2. cvičení (7.10.) Matematická indukce; DÚ (do 21.10.)
3. cvičení (14.10.) Relace a jejich vlastnosti; DÚ (do 28.10.)
4. cvičení (21.10.) Částečná uspořádání; DÚ (do 11.11.)
5. cvičení (4.11.) Kombinatorické počítání; DÚ (do 18.11.)
6. cvičení (11.11.) Pokračování počítání a úvod do grafů; DÚ (do 25.11.)
7. cvičení (18.11.) Teorie grafů; DÚ (do 2.12.)
8. cvičení (25.11.) Stále grafy; DÚ (do 9.12.)
9. cvičení (2.12.) Stromy, lesy, kostry; DÚ (do 16.12.)
10. cvičení (9.12.) Rovinné grafy; DÚ (do 6.1.)
11. cvičení (16.12.) Barvení grafů, klasická pravděpodobnost; DÚ (do 6.1.)
12. cvičení (6.1.) Bayesova věta, počítání se středními hodnotami

Výsledky

Výsledky jsou zde.

Pokud chcete svoje body zveřejněny, pošlete mi svoji přezdívku společně s nějakým řešením.

Další příklady

Nejvíce se člověk naučí řešením příkladů. Pokud se chcete potrénovat, můžete využít příkladů v následujících zdrojích.

Další odkazy