Obsah
Cvičení z Diskrétní matematiky 2025/26
Na pravé straně této stránky vizte obsah. Pečlivě si vše pročtěte.
Při emailové komunikaci se mnou prosím vždy uveďte do předmětu text [DM].
Zadání úloh na cvičení bude zde na webu. Pro komunikaci kolem DÚ budu používat systém OWL. Pokud vám do něj nepřišel ode mě kód, napište mi email.
Úlohy na cvičení:
Požadavky na zápočet
Zápočet vám udělím, získáte-li celkově 100 bodů.
Váš aktuální počet bodů naleznete v OWL.
Body lze získávat následujícími způsoby:
- Řešení úkolů: po každém cvičení budou zadány domácí úkoly. Každý úkol má termín, typicky týden od zadání, později jej nelze odevzdat. Více o vypracovávání domácích úloh…
- Opravování úkolů: pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, máte možnost získat navíc až pětinásobek bodů tím, že se stanete korektorem pro tuto úlohu. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr. Více o korektorství…
Další informace
Vypracovávání domácích úloh
- Úkoly odevzdávejte pouze elektronicky přes OWL a to ideálně jako markdown s matematikou, nebo prostý text. Pokud chcete ilustrovat řešení obrázkem, můžete ho vložit jako přílohu. V minulosti jsem uznával i řešení psaná rukou, ale aktuálně je už nepřijímám. Zaprvé se domnívám, že je dobrá investice naučit se psát matiku na počítači, zadruhé jsou nyní dostupné dobré nástroje, které vám s tím pomůžou (ChatGPT obecně, dále také MathPix, MyScript Notes, pro dohledávání konkrétních LaTeXových symbolů Detexify).
- Pokud není řečeno jinak, vyřešením úlohy myslím, že dokážete dané tvrzení.
- Důkaz musí být korektní, přehledný a srozumitelný.
- V důkazu smíte používat bez důkazu tvrzení z přednášek.
- Pokud se začnete ve formulacích zamotávat, zaveďte si značení. Označte objekty nebo kvantity přesnými názvy nebo proměnnými a v textu používejte tyto proměnné, nikoliv ukazovací zájmena. (Je častá chyba, že autor důkazu mluví o té a tamté množině a cvičící je v okamžiku ztracen. Proč ne množina $A$ a množina $B$?). V prostém textu dolní index označujte pomocí podtržítka (tzn. $a_1$ je
a_1), horní pomocí stříšky ($a^2$ jea^2). - Za dobré (korektní, přehledné, srozumitelné) řešení příkladu dostanete plný počet bodů. Pokud něco chybí, ale důkaz obsahuje dobrou myšlenku, nebo pokud je důkaz správný, ale nepřehledný či nesrozumitelný, dostanete méně bodů. Pokud úlohu nevyřešíte nebo je důkaz zcela špatně (včetně myšlenky), dostanete 0 bodů.
- Se základy sazby matematiky pomocí systému LaTeX vám může pomoct wikikniha o LaTeXu. Nejjednoduší způsob, jak se do toho pustit, je přímo v OWLu (funkce preview) nebo v hackmd.io, kde můžete vidět živý náhled po straně se zdrojem (malá ukázka syntaxe (klikněte na „edit“, abyste viděli kód.)) Případně můžete používat nějaký webový LaTeXový editor (rozchodit LaTeX na vlastním počítači může být oříšek) – např. Overleaf.
- Při řešení úkolů doporučuji spolupráci, ALE:
- Vždy doporučuji, abyste příklad nejdřív zkusili vyřešit sami, více se toho naučíte.
- Přestože jste na úkolu s někým spolupracovali, musíte řešení vypracovat a zformulovat sami. Pokud ve mně vaše řešení vzbudí podezření, že příkladu vlastně nerozumíte, ale řešení jste opsali, a mé podezření se potvrdí, nedostanete žádné body a příště budu do vašich úkolů obzvlášť šťourat (abych si byl jistý, že jste je pochopili).
- Použití AI: Je nemalá šance, že zadané úlohy vyřeší současná AI správně. Je taky nemalá šance, že když mi takové řešení odevzdáte, tak na to nepřijdu, nebo budu mít podezření, ale nebudu vám to schopný dokázat. Stejně to nedělejte: nic se nenaučíte a na zkoušce se vám to vymstí. Pokud obracíte na AI proto, že se cítíte ztraceni a potřebujete pomoc, mnohem lepší je spolupracovat se spolužáky.
- Termíny: Řešení úlohy musíte odevzdat do termínu. Pak ale ještě probíhá naše interakce - třeba pokud je vaše řešení téměř správné, udělím částečné body a doptám se a když správně doplníte chybějící části, dostanete pak plné body. Tato interakce ale není nekonečná: po svém prvotním řešením můžete podat ještě dvě opravná, pak už je udělený počet bodů konečný. (Někdy nebudu zodpovězení své doplňující otázky brát jako nové řešení, ale nespoléhejte na to.)
Korektorství
Pokud jste při odevzdávání řešení domácího úkolu přesvědčeni, že jste úloze skutečně porozuměli a že vaše řešení je opravdu dobré, po odevzdání úlohy mi napište email s předmětem [DM/ADS1/KG1][korektor] název-úlohy (první část podle předmětu, vyberte samozřejmě jen jedno). Já vaše řešení zhodnotím přednostně a pokud bude v pořádku, za opravení řešení vašich kolegů navíc až pětinásobek bodů. Přesný počet bodů je dán vzorcem $r \cdot b/5$, kde $b$ je počet bodů za úlohu a $r$ je počet řešení, které opravíte, tedy např. pokud je úloha za 6 bodů a opravíte ji 10 kolegům, dostanete $10 \cdot 6/5 = 12$ bodů. Korektorem se můžete stát max. třikrát za semestr.
Technicky to bude fungovat tak, že korektorovi zpřístupním danou úlohu v OWL, kde on opravuje a uděluje body, ale já vše taky vidím a můžu případně korigovat :) Korektor si tedy řešení pečlivě přečte a zhodnotí ho. Je toto řešení korektní? Pokud ne, kde udělal autor chybu? Čemu nerozumí a jak mu můžu pomoci – jakou otázkou ho nakopnu správným směrem? Dále – je toto řešení přehledné a srozumitelné? Prospělo by řešení rozdělit do více/méně odstavců? Zavést nějaké značení? Atd. Na základě tohoto zhodnocení pak korektor navrhne bodové ohodnocení. Například:
Řešení je v zásadě správné, ale doporučil bych místo značení A, B, C, … používat indexované značení A_1, A_2, A_3, … Jinak byl důkaz poměrně přehledný.
2b
Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a přehodnotím body (ale to se často neděje).
Povinností korektora je opravit všechny přidělené úlohy do týdne od chvíle, kdy se v OWLu objeví.
Užitečné zdroje
- Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.
- Matoušek, Nešetřil: Kapitoly z diskrétní matematiky, Karolinum. Existuje několik různých vydání, která se liší číslováním kapitol; odkazy výše jsou podle staršího (černého). Také pozor na drobné chyby ve starších vydáních (viz errata). [K]
- Matoušek: Podrobný sylabus o pravděpodobnosti [P] (PDF)
- Mareš, Valla: Průvodce labyrintem algoritmů [L]
- Slajdy doc. Fialy, většinou obsahují konkrétní příklady, dobré pro získání intuice.
- Poznámky Toma Slámy z přednášek Martina Mareše