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.

• 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 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 důkaz 1=2 (en).
  • Další obvyklé chyby při indukci jsou dobře popsány v tomto textu (en).
  • 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é!
• 2. cvičení
• 3. cvičení
• 4. cvičení
• 5. cvičení
• 6. cvičení
• 8. cvičení
• 9. cvičení

• 1. série DÚ, termín 14:00 8. 10. 2014
• 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]
• 3. série DÚ, termín 14:00 23. 10. 2014
• 4. série DÚ, termín 14:00 29. 10. 2014
• 5. série DÚ, termín 14:00 5. 11. 2014
• 7. série DÚ, termín 14:00 27. 11. 2014
• 8. série DÚ, termín 14:00 5. 12. 2014
• 9. série DÚ, termín 11. 12. 2014
• 9¾. série DÚ, termín 17. 12. 2014

• Sbírka úloh z DM
• Návod ke Studnici vědomostí, která obsahuje mnohé jinak těžko sehnatelné materiály, mrk, mrk.

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…
• 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í…
• 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í :)

• Ú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 LaTeX. Asi jako nejlepší zdroj se mi osvědčila 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ř. WriteLaTeX nebo 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).

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ý.

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.

Tabulka