Cvičení z Diskrétní matematiky

Cvičení k přednáškám Martina Tancera, které probíhá ve čtvrtky od 15:40 v místnosti N2 v budově IMPAKT.

Podmínky zápočtu

Ke zdárnému ukončení předmětu je potřeba získat zápočet, na zápočet je potřeba získat minimálně 100 bodů z alespoň 150 možných. Body lze získat na řešení domácích úkolů (budou vypsány za alespoň 90 bodů) a za dvě písemné práce (obě po 30 bodech).

Úkoly budu zadávat každý týden. Úlohy nemají žádný deadline (resp. konec zkouškového), ovšem doporučuji řešení odevzdávat cca do dvou týdnů (ke konci semestru toho bývá hodně). Další informace k úkolům viz níže.

Písemné práce se budou psát přibližně v půlce a na konci semestru. Obě budou na 45 minut a budou testovat probranou látku v příslušné části semestru. Přesná témata včas upřesním.

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 prostřednictvím systému Owl.

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 váš postup 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.

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) či problémů mi napište email na honst at iuuk.mff.cuni.cz a vyřešíme to.

Program cvičení

1. cvičení (5.10.) Matematická indukce;
2. cvičení (12.10.) Pár poznámek k indukci, úvod do relací;
3. cvičení (19.10.) Částečná uspořádání;
4. cvičení (26.10.) Částečná uspořádání, funkce a trochu kombinatorického počítání;
*** 2.11. se necvičí, ale sportuje ***
5. cvičení (9.11.) Kombinatorické počítání, princip inkluze a exluze;
6. cvičení (16.11.) Opakování, úvod do grafů;
7. cvičení (23.11.) Písemka (indukce, relace včetně ekvivalencí a částečných uspořádání, kombinatorické počítání a PIE), pokračování grafů; Dnes bez úkolu
8. cvičení (30.11.) Matice sousednosti, věta o skóre, Eulerovské grafy;
9. cvičení (7.12.) Stromy, kostry;
10. cvičení (14.12.) Kostry, zmínka o prostoru cyklů, rovinné grafy; ; Bonusový úkol
11. cvičení (21.12.) Rovinné grafy, barvení grafů;
12. cvičení (4. 1.) Písemka (grafy: základní definice a vlastnosti, věta o skóre, matice sousednosti, Eulerovské grafy, stromy, rovinné grafy, barvení grafů)
13. cvičení (11.1.) Spernerovo lemma a Brouwerova věta o pevném bodě; Důkaz pro všechny dimenze od Jacoba Foxe

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