Cvičení z Diskrétní matematiky
V zimním semestru 2021/2022 vedu cvičení z předmětu Diskrétní matematika [NDMI002] k přednáškám Martina Mareše každou středu od 15:40 v učebně N6.
Máte-li nějaký dotaz, či chcete-li si domluvit konzultaci, napište mi prosím email na adresu jiribenes+dm@kam.mff.cuni.cz.
Podmínky zápočtu
Na cvičení půjde získat body z domácích úkolů a písemek. Celkem bude možné získat alespoň 150 bodů, přičemž k zápočtu je potřeba alespoň 100 bodů.
Domácí úkoly
Na konci každého cvičení budou zadány domácí úkoly, celkem za alespoň 80 bodů (ale ne o moc víc). Každý úkol lze řešit dva týdny od cvičení, na kterém byl úkol zadán (není-li řečeno jinak).
Domácí úkoly můžete řešit společně s ostatními účastníky cvičení (dokonce to doporučuji), ale řešení musíte zformulovat a sepsat každý zvlášť.
Nezapomeňte pečlivě zdůvodnit všechny kroky, je to důležitější než správný výsledek. Věty a tvrzení z přednášek či cvičení můžete použít bez důkazu, jen vždy uveďte, co používáte! Více tipů jak řešit a sepisovat úkoly má Kate Konczycki zde.
Řešení domácích úkolů mi posílejte emailem na adresu jiribenes+dm@kam.mff.cuni.cz. Preferuji řešení ve formátu PDF, či jako text v těle emailu. Pokud budete posílat ručně psané poznámky, zajistěte prosím, aby byly v dostatečné kvalitě (použijte například aplikaci Notebloc, či aplikaci Tiny Scanner, obojí je pro Android i pro iOS) a aby byly v jednom PDF souboru.
K prvnímu úkolu mi napište i přezdívku (zapsatelnou Unicodem), abych mohl na stránce zveřejnit počet získaných bodů.
Vzorové řešení úkolu v LaTeXu najdete zde zazipované. Upravit jej můžete například na stránce Overleaf (vyžaduje bezplatnou registraci) – stačí zvolit vpravo nahoře New Project, poté Upload Project a vybrat zazipované vzorové řešení.
Písemky
V průběhu semestru se budou psát dvě písemky, dohromady za právě 70 bodů. Písemky budou ohlášeny alespoň týden předem, ale plánuji jednu v polovině semestru, druhou na konci.
Písemka bude probíhat během doby cvičení, každá bude na zhruba 70 minut. Kdybyste někdo nemohli dojít na cvičení, na kterém se píše písemka, napište mi a domluvíme se.
Bonusové body
Za aktivitu a bonusové úkoly půjdou získat bonusové body, které se přičítají k bodům z úkolů a písemek.
Co se dělalo na cvičení
- 1. cvičení (29. 9.) – Matematické hrátky, důkazy, úvod do indukce; zadán DÚ 1
- 2. cvičení (6. 10.) – Matematická indukce a její silná varianta, falešné důkazy; zadán DÚ 2
- 3. cvičení (13. 10.) – Množiny, kartézský součin, relace a jejich vlastnosti; zadán DÚ 3
- 4. cvičení (20. 10.) – Ekvivalence, částečná uspořádání, řetězce a antiřetězce; zadán DÚ 4
- 5. cvičení (27. 10.) – Kombinatorické počítání; zadán DÚ 5
- 6. cvičení (3. 11.) – Princip holubníku, princip inkluze a exkluze; zadán DÚ 6
- 7. cvičení (10. 11.) – První písemka, potom lehký úvod do teorie grafů; zadán DÚ 7
- Dne 17. 11. cvičení odpadá (Den boje za svobodu a demokracii), nebyl zadán úkol
- 8. cvičení (24. 11.) – Grafy, podgrafy, doplňky grafů; zadán DÚ 8
- 9. cvičení (1. 12.) – Cesty, tahy, eulerovské grafy; zadán DÚ 9
- 10. cvičení (8. 12.) – Souvislost, stromy, kostry; zadán DÚ 10
- 11. cvičení (15. 12.) – Druhá písemka, potom kreslení grafů; zadán DÚ 11 + bonusové úkoly
- 12. cvičení (22. 12.) – Rovinné grafy, barvení grafů; nebyl zadán úkol
- 13. cvičení (5. 1.) – Podmíněná pravděpodobnost, střední hodnota; byl zadán DÚ 12
Tabulka s body
Pokud nejste v tabulce, nemám vaši přezdívku.| Přezdívka | Bonus | Domácí úkoly | Písemky | Celkem | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ∑ | 1 | 2 | ∑ | |||
| Pál Erdős | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 7 | 6 | 8 | 14 | 6 | 82 | 35 | 35 | 70 | 152 | |
| Dvou-třetiňák | 4 | 4 | 4.75 | 4 | 4.75 | 2 | 4 | 4.75 | 4 | 5.5 | 9.5 | 4 | 55.25 | 23.5 | 23.5 | 47 | 102.25 | |
| Vilda | 15.5 | 6 | 6 | 6.75 | 6 | 7 | 3 | 6 | 7 | 6 | 8 | 61.75 | 35 | 35 | 70 | 147.25 | ||
| KCKy | 9 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 7 | 6 | 8 | 14 | 76 | 31 | 35 | 66 | 151 | |
| Σ | 2.75 | 6 | 6 | 7 | 5.5 | 7 | 1.5 | 6 | 7 | 6 | 52 | 29.5 | 24.5 | 54 | 108.75 | |||
| Vláďa | 15.5 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 7 | 6 | 8 | 62 | 31.5 | 35 | 66.5 | 144 | ||
| Pepa | 9.25 | 6 | 6 | 7 | 6 | 7 | 3 | 5.5 | 7 | 4.25 | 8 | 59.75 | 25.5 | 27 | 52.5 | 121.5 | ||
| Nalim | 10 | 6 | 6 | 4 | 5 | 5.5 | 7 | 6 | 39.5 | 29.5 | 35 | 64.5 | 114 | |||||
| Dann | 6.25 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 7 | 6 | 8 | 62 | 31 | 30 | 61 | 129.25 | ||
| baugi | 7.5 | 5.75 | 6 | 5.25 | 3.5 | 4.75 | 3 | 4.5 | 7 | 6 | 4.5 | 50.25 | 21 | 24 | 45 | 102.75 | ||
| carpincho | 3 | 6 | 6 | 5 | 5.25 | 4.75 | 3 | 5.25 | 7 | 3.5 | 8 | 53.75 | 15 | 28.5 | 43.5 | 100.25 | ||
| entropy warrior | 8 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 7 | 5 | 7 | 60 | 26.5 | 21 | 47.5 | 115.5 | ||
| Timurbtr23 | 3 | 6 | 6 | 5 | 2.5 | 3 | 3 | 2.25 | 2 | 1.5 | 1.5 | 2.5 | 35.25 | 19 | 19.5 | 38.5 | 76.75 | |
| Ryšavec | 8 | 6 | 6 | 5 | 6 | 6.5 | 1.25 | 5.25 | 7 | 6 | 49 | 24.5 | 35 | 59.5 | 116.5 | |||
| WildGreen | 6 | 5 | 6 | 7 | 0.5 | 18.5 | 24.5 | |||||||||||
| Vendy | 7.5 | 6 | 6 | 7 | 5.75 | 7 | 3 | 5.75 | 7 | 6 | 8 | 61.5 | 32 | 21 | 53 | 122 | ||
| Aloha | 4.5 | 6 | 5.25 | 3.5 | 3 | 2 | 3 | 7 | 3.5 | 37.75 | 18.5 | 15 | 33.5 | 71.25 | ||||
| Hello12 | 11 | 6 | 6 | 7 | 6 | 7 | 2.75 | 6 | 7 | 6 | 8 | 61.75 | 29.5 | 24.5 | 54 | 126.75 | ||
| Bombomchik | 4.75 | 5.5 | 2 | 6.25 | 5.5 | 5 | 3 | 5.75 | 6 | 4.5 | 6.5 | 50 | 25 | 33 | 58 | 112.75 | ||
| bdím | 1.25 | 6 | 6 | 6 | 5.75 | 7 | 3 | 6 | 7 | 6 | 6.5 | 59.25 | 24.5 | 18.5 | 43 | 103.5 | ||
| Hornet | 0.25 | 5.5 | 6 | 6.25 | 2.5 | 4.5 | 3 | 5 | 7 | 4.5 | 8 | 9.5 | 61.75 | 28 | 16 | 44 | 106 | |
| mago | 2.75 | 2.75 | 2.75 | |||||||||||||||
| bouncik | 1.25 | 2 | 2 | 3 | 5 | 5 | 7 | 6 | 8 | 12.5 | 6 | 56.5 | 25.5 | 21 | 46.5 | 104.25 | ||
Užitečné odkazy
- Loňská verze cvičení
- Předmět pro zvídavé studenty 1. ročníku: IPS
- Předmět na procvičení základních matematických dovedností: Matematické dovednosti
- Vyhledávač operátorů pro LaTeX
- Podrobný sylabus k pravděpodobnosti
- Tahák ke kombinatorice
- Sbírka řešených úloh
- Online encyklopedie celočíselných posloupností