Cvičení z diskrétní matematiky pro matematiky (NMIN105)

Úterý od 17:20 a čtvrtek od 12:20

Muhehehe

Podmínky zápočtu

(viz info na stránce předmětu)

K získání zápočtu je třeba získat dostatek bodů z domácích úkolů a písemek. Domácí úkoly budou zadávány průběžně na každém cvičení (plus mínus drobné výjimky) a je potřeba získat 70 bodů z celkových 100 bodů. Písemky se budou psát v předem ohlášených termínech v průběhu semestru (každou písemku ohlásím alespoň cvičení předem, ale pokusím se dříve). Celkem se budou psát dvě písemky ze kterých je třeba získat 140 bodů z 200 možných. Dále se pro zájemce bude psát jedna opravná písemka.

Dále je možno získat bonusové body a to především za aktivitu na cvičeních a docházku (za nejvýše tři absence je možno získat deset bodů, za čtyři nebo pět absencí lze získat pět bodů). Docházka ale není povinná (pouze doporučená)

Odevzdávání domácích úkolů

Domácí úkoly mají termín do začátku následujícího cvičení. Odevzdávat je můžete jako pdf e-mailem (nezapomeňte do předmětu e-mailu uvést kód předmětu) nebo fyzicky mé osobě (typicky na začátku cvičení).

Pokud odevzdáváte úkoly elektronicky, posílejte je ve formátu pdf a čitelné. Speciálně, fotky nekvalitním fotoaparátem při mizerných světelných podmínkých a strašlivém škrabopisu vám hodím na hlavu!

Opravná písemka

Pokud jste nezískali dostatečný počet bodů z písemek, můžete na konci semestru napsat ještě jednu opravnou písemku. Ta může nahradit vaši nejhorší písemku (pokud si tím polepšíte). Přesněji, ze všech vámi psaných písemek, včetně opravné, se vezmou dvě nejlepší a z ty se budou počítat do limitu na zápočet. Termín opravné písemky dohodneme na konci semestru.

Úterní paralelka

Druhá písemka se bude psát 18.12.

1. cvičení: Úvodní info, rychlokurz dokazování -- důkaz z definice, množinové důkazy, protipříklad, spor, indukce, důkaz ekvivalence. Zadán 1.DÚ.

Příklady z 1. cvičení

2. cvičení: Dokazování s množinami a indukcí. Zadán 2.DÚ.

Příklady z 2. cvičení

3. cvičení: Relace a jejich vlastnosti - reflexivita, (anti)symetrie, tranzitivita. Zadán 3.DÚ.

Příklady ze 3. cvičení

4. cvičení: Ekvivalence - definice, třídy ekvivalence a jejich základní vlastnosti. Zadán 4.DÚ.

Příklady ze 4. cvičení

5. cvičení: Uspořádání - definice, znázorňování Hasseho diagramy, minimální vs. nejmenší prvek, řetězce a antiřetězce. Věta o dlouhém a široké, vztah mezi nejdelším řetězcem a pokrývání antiřetězci a naopak. Zadán 5.DÚ. (Do tištěné verze se vloudila nesmyslná definice množiny X_n, zde už je opravena.)

Příklady z 5. cvičení

6. cvičení: Nekonalo se, neboť jsme sportovali s panem děkanem.

7. cvičení: Psala se první písemka.

8. cvičení: Kombinatorika -- počet zobrazení, prostých zobrazení, bijekcí. Kombinační čísla jako počet podmnožin dané velikosti, binomická věta. Zadán 6.DÚ.

Příklady z 8. cvičení

9. cvičení: Hrátky s binomickými koeficienty -- dokazování identit a sčítání řad, trik s derivací binomické věty a násobením polynomů. Rychlý průlet základním počítáním kuliček a přihrádek. Zadán 7.DÚ (ježto cvičící rozumí víc kombinatorice než hudební teorii, bylo zadání upřesněno).

Příklady z 9. cvičení

10. cvičení: Multinomické koeficienty a princip inkluze a exkluze. Zadán 8.DÚ.

Příklady z 10. cvičení

11. cvičení: Úvod do grafů. Zadán 9.DÚ.

Příklady z 11. cvičení

12. cvičení: Psala se druhá písemka (na kombinatoriku a grafy). Písemka měla podobný formát, jako ta předchozí. Z grafů se předpokládá znalost následujících témat (v závorce odkaz na příslušnou kapitolu v Kapitolách z diskrétní matematiky, čtvrté oranžové vydání - ve starších vydání mohou být čísla kapitol jiná!):

13. cvičení: Nekonalo se, neboť byl Nový rok. Bonusový Vánoční DÚ 10. DÚ.

14. cvičení: Rovinné grafy a jejich barvení. Eulerovy formulky a některé jejich důsledky. Kuratowského věta. Věta o šesti, pěti a čtyřech barvách.

Příklady ze 14. cvičení

Body atp.

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.



Čtvrteční paralelka

Druhá písemka se bude psát 3.1.

1. cvičení: Úvodní info, rychlokurz dokazování -- důkaz z definice, množinové důkazy, protipříklad, spor, indukce, důkaz ekvivalence. Zadán 1.DÚ.

Příklady z 1. cvičení

2. cvičení: Dokazování s množinami a indukcí. Zadán 2.DÚ.

Příklady z 2. cvičení

3. cvičení: Relace a jejich vlastnosti - reflexivita, (anti)symetrie, tranzitivita. Zadán 3.DÚ.

Příklady ze 3. cvičení

4. cvičení: Ekvivalence - definice, třídy ekvivalence a jejich základní vlastnosti. Zadán 4.DÚ.

Příklady ze 4. cvičení

5. cvičení: Uspořádání - definice, znázorňování Hasseho diagramy, minimální vs. nejmenší prvek, řetězce a antiřetězce. Věta o dlouhém a široké, vztah mezi nejdelším řetězcem a pokrývání antiřetězci a naopak. Zadán 5.DÚ.

Příklady z 5. cvičení

6. cvičení: Zbytky uspořádání z minula. Kombinatorika -- počet zobrazení, prostých zobrazení, bijekcí. Kombinační čísla jako počet podmnožin dané velikosti, binomická věta. Zadán 6.DÚ.

Příklady z 6. cvičení

7. cvičení: Psala se první písemka.

8. cvičení: Hrátky s binomickými koeficienty -- dokazování identit a sčítání řad. Zadán 7.DÚ.

Příklady z 8. cvičení

9. cvičení: Základní kombinatorická kuchařka -- počítání kuliček a přihrádek, multinomické koeficienty a související multinomická věta. Zadán 8.DÚ.

Příklady z 9. cvičení

10. cvičení: Princip inkluze a exkluze. Zadán 9.DÚ.

Příklady z 10. cvičení

11. cvičení: Úvod do grafů. Zadán 10.DÚ.

Příklady z 11. cvičení

12. cvičení: Grafy podruhé, s trochou stromů a koster.

Příklady z 12. cvičení

Bonusový Vánoční DÚ 11. DÚ

13. cvičení: Psala se druhá písemka.

14. cvičení: Rovinné grafy a jejich barvení. Eulerovy formulky a některé jejich důsledky. Kuratowského věta. Věta o šesti, pěti a čtyřech barvách.

Příklady ze 14. cvičení

Body atp.

Pokud se zde nevidíte, pak je to nejspíše tím, že jste mi neposlali svou přezdívku.