====== Cvičení z diskrétní matematiky 2014/15 ====== 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 ''[DM1415]''. **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 ''[DM1415][!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:dm1415:01-cv_koutecky.pdf|1. cvičení}}. Též jsem zmiňoval: * 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 [[https://kam.mff.cuni.cz/~mikina/materialy/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:dm1415:02-cv_koutecky.pdf|2. cvičení}} * {{: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:dm1415:01-du_koutecky.pdf|1. série DÚ}}, termín 14:00 8. 10. 2014 * {{: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ě 60 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 odevzdáte opravdu jasné a přehledné řešení domácího úkolu, z něhož uvidím, že jste mu skutečně porozuměli, nabídnu vám 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ísemka:** v průběhu semestru (na konci listopadu nebo v prosinci) budeme psát jednu písemku, která bude obsahovat úkoly za 50b. Ú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ů. * **Aktivita na cvičení:** za aktivitu na cvičení (např. vyřešení příkladu na tabuli atd.) můžete dostat 1-2b (podle náročnosti úlohy). I pokud vyřešíte více úloh, jeden člověk může získat za jedno cvičení max. 2b -- chci, abyste se u tabule střídali a nedělali všechno vždy ti stejní :) ===== 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 mi pošlete hezké řešení domácí úlohy, nabídnu vám možnost opravovat řešení vašich spolužáků. Pokud nabídku přijmete a splníte následující, dostanete pětinásobek bodové hodnoty příkladu. Korektorem se můžete stát nejvýše třikrát za semestr. 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ý. 2bTyto 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 ===== ===== Body za úkoly ===== [[https://docs.google.com/spreadsheet/ccc?key=0Aoow9Tms8HyddG50MHo5UkhuR2ZEZ1EteGw4bEY4REE&usp=sharing|Tabulka]] {{url>https://docs.google.com/spreadsheet/pub?key=0Aoow9Tms8HyddG50MHo5UkhuR2ZEZ1EteGw4bEY4REE&single=true&gid=0&output=html&widget=true}}