Cvičení z Diskrétní matematiky
V zimním semestru 2020/2021 vedu cvičení z předmětu Diskrétní matematika [NDMI002] k přednáškám Martina Mareše a Martina Tancera každý čtvrtek od 14:00.
Na cvičení budeme používat Zoom, odkaz jste dostali emailem na adresu, kterou máte nastavenou v SISu. Pokud odkaz nemáte, napište mi email!
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.
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 60 minut + dalších 10 minut na zaslání řešení. Kdybyste někdo nemohli dojít na cvičení, na kterém se píše písemka, napište mi a domluvíme se. To samé, kdyby vám spadl internet, nebo něco podobného.
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í (1. 10.) – Matematické hrátky, důkazy, úvod do indukce; zadán DÚ 1
- 2. cvičení (8. 10.) – Matematická indukce a její silná varianta, falešné důkazy; zadán DÚ 2
- 3. cvičení (15. 10.) – Relace a jejich vlastnosti, ekvivalence a jejich třídy; zadán DÚ 3
- 4. cvičení (22. 10.) – Částečná a lineární uspořádání, řetězce a antiřetězce; zadán DÚ 4
- 5. cvičení (29. 10.) – Kombinatorické počítání; zadán DÚ 5
- 6. cvičení (5. 11.) – Princip holubníku, princip inkluze a exkluze, odhady; zadán DÚ 6
- 7. cvičení (12. 11.) – První písemka, potom úvod do teorie grafů; zadán DÚ 7
- 8. cvičení (19. 11.) – Grafy, podgrafy, skóre grafu; zadán DÚ 8
- 9. cvičení (26. 11.) – Cesty, tahy, eulerovské grafy, orientované grafy; zadán DÚ 9
- 10. cvičení (3. 12.) – Souvislost, extremální grafy, stromy, kostry; zadán DÚ 10
- 11. cvičení (10. 12.) – Rovinné grafy, barvení grafů; zadán DÚ 11 + Bonusové úkoly
- 12. cvičení (17. 12.) – Druhá písemka, poté krátké povídání o barvení grafů; nebyl zadán DÚ
- 13. cvičení (7. 1.) – Podmíněná pravděpodobnost, střední hodnota; 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 | 6 | 6 | 8 | 14 | 6 | 81 | 35 | 35 | 70 | 151 | |
| Dvou-třetiňák | 4 | 4 | 4.75 | 4 | 4.75 | 2 | 4 | 4 | 4 | 5.5 | 9.5 | 4 | 54.5 | 23.5 | 23.5 | 47 | 101.5 | |
| Matezzzz | 26.5 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 6 | 6 | 53 | 34.75 | 34 | 68.75 | 148.25 | |||
| Mysak0CZ | 14.25 | 6 | 6 | 7 | 3 | 7 | 2.5 | 6 | 6 | 6 | 49.5 | 28 | 29 | 57 | 120.75 | |||
| mynameisjeff | 21.5 | 4.5 | 6 | 5.5 | 4.25 | 5 | 1 | 6 | 5 | 4 | 9.75 | 5.5 | 56.5 | 13.5 | 11 | 24.5 | 102.5 | |
| tryhard69 | 5 | 6 | 6 | 7 | 6 | 7 | 3 | 2.5 | 6 | 6 | 8 | 57.5 | 29 | 27 | 56 | 118.5 | ||
| qwerty | 6 | 6 | 2.5 | 7 | 5.5 | 7 | 2.5 | 4.75 | 5.75 | 6 | 1.25 | 48.25 | 25.25 | 20.5 | 45.75 | 100 | ||
| vladav | 24.5 | 6 | 6 | 7 | 6 | 6.75 | 2.75 | 6 | 6 | 6 | 8 | 60.5 | 31 | 30 | 61 | 146 | ||
| Major Tom | 5.75 | 6 | 6 | 7 | 6 | 7 | 3 | 6 | 6 | 6 | 8 | 61 | 31 | 31.5 | 62.5 | 129.25 | ||
| oisho | 8.75 | 6 | 6 | 7 | 5.75 | 6.75 | 2.75 | 5.25 | 6 | 5.75 | 8 | 9 | 68.25 | 19.75 | 14 | 33.75 | 110.75 | |
| Kappa | 16 | 6 | 6 | 6 | 6 | 7 | 3 | 5.75 | 5.75 | 6 | 8 | 59.5 | 21 | 32.5 | 53.5 | 129 | ||
| unknown | 5.75 | 6 | 5 | 4.75 | 6.5 | 2.5 | 5.25 | 5.25 | 6 | 6.75 | 9.5 | 63.25 | 24.75 | 18 | 42.75 | 106 | ||
| Mona | 6 | 6 | 6 | 7 | 3 | 6.75 | 3 | 5 | 6 | 6 | 48.75 | 27.75 | 17.5 | 45.25 | 100 | |||
| ﷽ | 6 | 6 | 7 | 6 | 6.5 | 3 | 5.75 | 6 | 6 | 8 | 60.25 | 34.25 | 26 | 60.25 | 120.5 | |||
| Tue | 4 | 2 | 3.75 | 2 | 3.75 | 2.5 | 18 | 25 | 25 | 43 | ||||||||
| Kukimo | 2.25 | 6 | 6 | 5.5 | 4.75 | 5.5 | 2.5 | 4.25 | 6 | 6 | 7.5 | 6.5 | 60.5 | 19 | 23.5 | 42.5 | 105.25 | |
| 4b756261 | 6 | 6 | 6 | 7 | 5.75 | 6.75 | 2.5 | 5 | 6 | 6 | 6.5 | 57.5 | 15 | 23 | 38 | 101.5 | ||
| Discombobulator | 20 | 3 | 6 | 3 | 0.75 | 5.25 | 2.75 | 2.5 | 6 | 4.5 | 6 | 4 | 43.75 | 21 | 18.5 | 39.5 | 103.25 | |
| David Duong | 18 | 4 | 6 | 4 | 5.25 | 4.5 | 2.75 | 4.75 | 4.25 | 3 | 4.25 | 7.5 | 6 | 56.25 | 19 | 9.5 | 28.5 | 102.75 |
| Drakosha | 5 | 4.5 | 4 | 5 | 3.25 | 6.25 | 1.25 | 24.25 | 17.5 | 17.5 | 46.75 | |||||||
| Jára | 2 | 3.5 | 3 | 8.5 | 8.5 | |||||||||||||
| »ÐØN« | 2 | 4 | 6 | 4 | 2.5 | 7 | 2.5 | 2.75 | 6 | 3.5 | 3.5 | 7 | 5.75 | 54.5 | 24 | 21.5 | 45.5 | 102 |
| Belafon | 9.5 | 3.5 | 6 | 6 | 4.5 | 7 | 2.5 | 5.25 | 6 | 6 | 5 | 51.75 | 24.25 | 23 | 47.25 | 108.5 | ||
| MVB | 27 | 4.5 | 2 | 3 | 2.75 | 5 | 4 | 5.75 | 5.25 | 5.5 | 11.5 | 49.25 | 15 | 14.5 | 29.5 | 105.75 | ||
| Kepler | 5.75 | 6 | 7 | 1.75 | 7 | 1 | 5 | 6 | 6 | 8 | 53.5 | 25 | 22 | 47 | 100.5 | |||
Užitečné odkazy
- 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
- Jak nastavit Zoom Virtual Background, abyste vypadali cool při cvičení ;)
- 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í