====== Cvičení z diskrétní matematiky 2015/16 ====== Na pravé straně této stránky vizte obsah. Silně doporučuji pečlivě vše pročíst. Při emailové komunikaci se mnou prosím **vždy** uveďte do předmětu text ''[DM1516]''. **Pozor:** pokud mi chcete psát cokoliv //nesouvisejícího// s domácími úlohami (organizační dotaz, žádost o konzultaci, poznámka ke cvičení, ...), napište mi zvláštní email a do předmětu uveďte ''[DM1516][!DU]''. Pokud to neuděláte, mail může na delší dobu zapadnout mezi domácí úkoly. Díky. ===== Co se dělalo na cvičení ===== * {{:teaching:dm1516:01-cv_koutecky.pdf|1. cvičení}}. Též doporučuji se podívat na: * Proč není dobré při důkazu indukcí "soustružit"? (Tzn. napsat si rovnost, kterou chceme dokázat, a nějakým způsobem ji upravit na rovnost, kterou již známe.) Doporučuji přečíst kapitolku o matematické indukci v textu [[ftp://math.feld.cvut.cz/pub/velebil/y01dma/dma-sbirka.pdf|Diskrétní matematika - sbírka řešených příkladů]] z FEL ČVUT. Jako hloupá demonstrace podvodů, které lze dělat při "ekvivalentních" úpravách rovností se podívejte na [[https://www.math.toronto.edu/mathnet/falseProofs/first1eq2.html|důkaz 1=2 (en)]]. * Další obvyklé chyby při indukci jsou dobře popsány v tomto [[https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f08/Site/Materials/Handouts/induction-problems.pdf|textu (en)]]. * [[https://en.wikipedia.org/wiki/Therac-25|Therac-25 (en)]] byl ozařovací přístroj vyráběný v 80. letech v Kanadě; při nejméně 6 nehodách v letech 1985-87 zemřeli pacienti, kterým přístroj dal více než tisícinásobné dávky ozáření -- kvůli softwarové chybě. Poučení? Dělejte matematiku pořádně, nebo budou umírat lidé! * {{:teaching:dm1516:02-cv.pdf|2. cvičení}} * {{:teaching:dm1516:03-cv.pdf|3. cvičení}} * {{:teaching:dm1516:04-cv.pdf|4. cvičení}} * {{:teaching:dm1516:05-cv.pdf|5. cvičení}} * {{:teaching:dm1516:06-cv.pdf|6. cvičení}} * [[http://kam.mff.cuni.cz/~koblich/teaching/dm2015/ulohy/cviceni07.pdf|7. cvičení]] (vedl Pavel Dvořák) /* * {{:teaching:dm1415:03-cv_koutecky.pdf|3. cvičení}} * {{:teaching:dm1415:04-cv_koutecky.pdf|4. cvičení}} * {{:teaching:dm1415:05-cv_koutecky.pdf|5. cvičení}} * {{:teaching:dm1415:06-cv_koutecky.pdf|6. cvičení}} * {{:teaching:dm1415:08-cv_koutecky.pdf|8. cvičení}} * {{:teaching:dm1415:09-cv_koutecky_2014.pdf|9. cvičení}} */ ===== Domácí úkoly ===== * {{:teaching:dm1516:01-du_koutecky.pdf|1. série DÚ}}, termín 15:40 13. 10. 2015 * {{:teaching:dm1516:02-du.pdf|2. série DÚ}}, termín 15:40 20. 10. 2015 * {{:teaching:dm1516:03-du.pdf|3. série DÚ}}, termín 15:40 27. 10. 2015 * {{:teaching:dm1516:04-du.pdf|4. série DÚ}}, termín 15:40 3. 11. 2015 * {{:teaching:dm1516:05-du.pdf|5. série DÚ}}, termín 23:59 12. 11. 2015 (**posunutý termín**) * {{:teaching:dm1516:06-du.pdf|6. série DÚ}}, termín 23:59 18. 11. 2015 (**posunutý termín**) * {{:teaching:dm1516:mega-du.pdf|7. (mega) série DÚ}}, termín 15:40 22. 12. 2015 * {{:teaching:dm1516:13-du.pdf|8. série}}, termín: kdykoliv. /* * {{:teaching:dm1415:02-du_koutecky.pdf|2. série DÚ}}, termín 14:00 15. 10. 2014 * Bonusový úkol -- **džbány pořádně**. Mějme $k$ (alespoň $2$) džbánů s vodou. V každém je celočíselné množství litrů vody a celkově je ve džbánech $2^n$ ($n \geq 2$) litrů vody. Libovolný džbán $A$ můžeme vzít a přelít z něj do jiného džbánu $B$ nejvýše tolik vody, kolik už džbán $B$ obsahuje, přičemž $B$ (před přelitím) obsahuje stejně nebo méně vody jako $A$. **[2 body]** * {{:teaching:dm1415:03-du_koutecky.pdf|3. série DÚ}}, termín 14:00 23. 10. 2014 * {{:teaching:dm1415:04-du_koutecky.pdf|4. série DÚ}}, termín 14:00 29. 10. 2014 * {{:teaching:dm1415:05-du_koutecky.pdf|5. série DÚ}}, termín 14:00 5. 11. 2014 * {{:teaching:dm1415:07-du_koutecky.pdf|7. série DÚ}}, termín 14:00 27. 11. 2014 * {{:teaching:dm1415:08-du_koutecky.pdf|8. série DÚ}}, termín 14:00 5. 12. 2014 * {{:teaching:dm1415:09-du_koutecky_2014.pdf|9. série DÚ}}, termín 11. 12. 2014 * {{:teaching:dm1415:09-du_koutecky_bonus.pdf|9¾. série DÚ}}, termín 17. 12. 2014 */ ===== Užitečné zdroje ===== * [[http://kam.mff.cuni.cz/~sbirka/show_category.php?c=11|Sbírka úloh z DM]] * [[http://wiki.matfyz.cz/index.php?title=Studnice_v%C4%9Bdomost%C3%AD|Návod ke Studnici vědomostí]], která obsahuje mnohé jinak těžko sehnatelné materiály, //mrk, mrk//. ===== Požadavky na zápočet ===== Zápočet vám udělím, získáte-li celkově 70 bodů. Váš aktuální počet bodů bude uveden v tabulce na konci této stránky. **Pozor:** z důvodu ochrany osobních údajů nemůžu bez vašeho svolení v tabulce uvádět vaše jméno; proto mi v každém řešení domácí úlohy uveďte i svou přezdívku, pod kterou chcete být v tabulce uvedeni. Pokud přezdívku neuvedete, beru to jako implicitní souhlas k uvedení vašeho skutečného jména. 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 za ~5 bodů. (Za typický příklad lze získat 2b, je-li příklad lehký či podúloha většího příkladu, je za 1b. Pokročilé příklady jsou naopak za 3b či víc.) Tyto úkoly budou mít termín (typicky do příštího cvičení), později za ně nezískáte žádné body. Více o [[#vypracovávání domácích úloh|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 pětinásobek bodů** tím, že se stanete //korektorem// pro tuto úlohu. (Např. když se stanete korektorem pro úlohu za 2b, dostanete navíc 10b.) Korektorem se můžete stát max. třikrát za semestr. Více o [[#korektorství|korektorství]]... * **Písemky:** v průběhu semestru budeme psát dvě písemky, každou s úlohami za 25b. Úkoly budou podobné obtížnosti jako ty ze cvičení či DÚ, jen je na ně méně času a tedy jsou za více bodů. ===== Další informace ===== ==== Vypracovávání domácích úloh ===== * Úkoly odevzdávejte pouze elektronicky (mailem) a pouze buď jako prostý text přímo v těle emailu, nebo jako přílohu ve formátu ''pdf'' (vizte níže o systému LaTeX). Řešení některých úloh je nejvhodnější ilustrovat obrázkem, proto přijímám i přílohy ve formátech ''jpg''/''png''. Žádné jiné formáty nepřijímám. * 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ý**. * 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$ je ''a^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 přibližně poloviční počet bodů. Pokud úlohu nevyřešíte nebo je důkaz zcela špatně (včetně myšlenky), dostanete 0 bodů. * **Silně** doporučuji naučit se používat sázecí systém [[http://www.latex-project.org/|LaTeX]]. Asi jako nejlepší zdroj se mi osvědčila [[https://en.wikibooks.org/wiki/LaTeX|wikikniha o LaTeXu]]. Dále doporučuji používat nějaký webový LaTeXový editor (rozchodit LaTeX na vlastním počítači může být oříšek) -- např. [[https://www.writelatex.com|WriteLaTeX]] nebo [[https://www.sharelatex.com|ShareLaTeX]] (oba umožňují sdílení souborů s dalšími uživateli). * Při řešení úkolů //můžete// spolupracovat, **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, 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). ==== 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šlete ho v emailu s předmětem začínajícím ''[DM1516][korektor]''. Já vaše řešení zhodnotím a pokud bude opravdu v pořádku, za opravení řešení vašich kolegů dostanete pětinásobek bodové hodnoty příkladu. Korektorem se můžete stát nejvýše třikrát za semestr. Naopak pokud si vyloženě nepřejete, aby někdo z vašich kolegů vaše řešení (jakožto korektor) četl, tzn. přejete si, abych vaše řešení opravoval osobně, pošlete email s předmětem začínající ''[DM1516][!korektor]''. Podotýkám ale, že se tak můžete připravit o často kvalitnější zpětnou vazbu, než vám dávám já. Technicky to bude fungovat tak, že když mi od někoho přijde řešení dané DÚ, přepošlu ho příslušnému korektorovi. Korektor si ř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
Tyto poznámky pak korektor pošle autoru úlohy a v kopii též mě. Já zhodnotím řešení úlohy a korekturu, případně se k oběma vyjádřím a pokud budu s hodnocením souhlasit, zapíšu do tabulky získané body. Povinností korektora je opravit **všechny** zaslané úlohy do **týdne od termínu úlohy**. ===== Body za úkoly ===== [[https://docs.google.com/spreadsheets/d/1-mBx-pFtMkHf9l90uYqVZwWF9PXwDyng8toST3XOR3A/edit?usp=sharing|Tabulka]] {{url>https://docs.google.com/spreadsheets/d/1-mBx-pFtMkHf9l90uYqVZwWF9PXwDyng8toST3XOR3A/pubhtml?gid=0&single=true}}