Diskrétní matematika - cvičení

Zde se průběžně budou objevovat nějaké informace ke cvičením. Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.

Speciální (náhradní) písemka

Počítejte s náhradní písemkou v pátek 19. 1. od 13:00 v učebně S4. Body získané za domácí úkoly, docházku a aktivitu se Vám budou plně započítávat do náhradní písemky. Body za předchozí písemky se budou započítávat částečně. Na písemku budete mít dostatek času (cca 3 hodiny).

Výsledky druhé písemky

V průběžném bodování níže už najdete výsledky 2. písemky. Kdo má 70 bodů, má nárok na zápočet. Kdo ještě nemá 70 bodů, bude je moci získat na náhradní písemce, viz výše. Zároveň máte možnost získat ještě nějaké body za čtvrtý DÚ níže, pokud si před náhradní písemkou chcete polepšit (nebo se ji zcela vyhnout).

DÚ 4

Vytvořme náhodný graf G následujícím způsobem: Zvolíme tři množiny A={1}, B={2,3} a C={4,5,6}. Množina vrcholů G je sjednocení množin A, B a C. Hrany G vedou pouze mezi různými dvojicemi množin (tj. například z A do C, ale nikoliv z C do C). Každou takovou hranu do grafu umístíme s pravděpodobností 1/3 nezávisle na ostatních hranách. Určete střední hodnotu (a) počtu hran v G (b) počtu trojúhelníků v G (c) počtu indukovaných podgrafů H grafu G izomorfních cestě délky 2 (cestě se třemi vrcholy) (d) počtu všech podgrafů H grafu G izomorfních cestě délky 2 (cestě se třemi vrcholy).

Za zcela vyřešený DÚ nabízím 10 bodů. Termín DÚ je 28. 1. Prodloužení termínu je možné pouze po předchozí vzájemné domluvě před tímto datem.

Druhá písemka

Druhá písemka byla 5. 1. na 60 bodů.

Průběžné bodování

Průběžné bodování najdete zde. Aby Vaše jména nebyla snadno dohledatelná internetovými vyhledávači, uvádím výsledky ve tvaru křestní jméno, iniciála z příjmení. (Kdyby v bodování něco nesedělo, tak se ozvěte.)

DÚ 3

Nabízím další domácí úkol, do 15. 12. (před cvičeními!). Není povinný, ale nabízím za jeho správné vyřešení 5 bodů. Kdo mi odevzdá úkol do 8. 12. (opět před cvičeními), tak se mu ho budu snažit rychle překontrolovat, a kdybych narazil na nějaký problém, tak ještě nabídnu opravu bez jakékoliv bodové ztráty.

Pro známou hru člověče nezlob se, určete o kolik políček se průměrně posune figurka při jednom tahu, pokud:

a) Hráč hází pouze jednou.

b) Hodí-li hráč 6, hází znovu, ovšem v jednom tahu však hází nejvýše třikrát. Postupuje o součet hodnot, které naházel.

c) Hodí-li hráč 6, hází znovu a to tak dlouho, dokud mu padají 6. Postupuje o součet hodnot, které naházel.

Výsledky první písemky

První písemka byla 10. 11. Bylo možné získat 40 bodů, bodování za jednotlivé příklady bylo 8-12-10-10. Výsledky najdete v bodování výše. Kdo měl alespoň 20 bodů je na dobré cestě (ale neusnout na vavřínech), kdo měl méně, doporučuji přidat.

DÚ 2

DÚ 2 byl neveřejný (tím, že je trochu nestandardní, tak to je kvůli opakovanému použití, navíc může fungovat jenom u těch, kteří byli na cvičení).

DÚ 1

Zde nabízím první domácí úkol, do 24. 11. (před cvičeními!). Není povinný, ale nabízím za jeho správné vyřešení 3 body. Kdo mi odevzdá úkol před první písemkou 10. 11., tak se mu ho budu snažit rychle překontrolovat, a kdybych narazil na nějaký problém, tak ještě nabídnu opravu bez jakékoliv bodové ztráty.

Určete počet slov z písmen A, G, H, I, K, L, M, N takových, že po vyškrtání některých písmen nemůžeme dostat žádné ze slov LIGA, LINKA, KNIHA či KAMIL.

Podmínky k zápočtu

Podmínkou k získání zápočtu je získat 70 bodů. Budou dvě písemky (na 100 možných bodů). Dále je možné získat nějaké body navíc za docházku (5 bodů), aktivitu během cvičení (není omezeno, čekejte tak kolem 8-10 bodů pro aktivnější), příležitostné domácí úkoly. V případě neúspěchu při řešení písemek bude náhradní možnost za obě písemky (speciální písemka), ale až během zkouškového. Nicméně doporučuji se připravit už napoprvé, dříve budete moci ke zkoušce a nebudete se muset trápit se získáváním zápočtu během zkouškového.

Příklady z cvičení

Zde se budou objevovat příklady z cvičení ve formátu .pdf. Jsou vytvořeny pomocí aplikace sbírka příkladů . V této sbírce naleznete i řešení některých příkladů. (Z části jsou čerpány z knihy od J. Matouška a J. Nešetřila Kapitoly z diskrétní matematiky).

6. 10.: zadání 1. série (verze pro tisk). [Matematická indukce a relace.]

13. 10.: Pokračovali jsme v příkladech z prvního cvičení.

20. 10.: zadání 2. série (verze pro tisk). [Funkce a částečná uspořádání.]

27. 10.: zadání 3. série (verze pro tisk). [Kombinatorické počítání.]

3. 11.: zadání 4. série, verze pro tisk. [Princip inkluze a exkluze.] (Základní verzi jsem omylem smazal, tak se podívejte na verzi pro tisk.)

10. 11.: Byla písemka, 60 minut. Zbytek jsme věnovali ještě PIE.

24. 11.: zadání 5. série (verze pro tisk). [Pravděpodobnost.]

1. 12.: zadání 6. série (verze pro tisk). [Grafy - úvod.]

8. 12.: zadání 7. série (verze pro tisk). [Grafy - stupně vrcholů, eulerovské grafy, matice sousednosti.]

15. 12.: zadání 8. série (verze pro tisk). [Grafy - souvislost, stromy, kostry.]

22. 12.: zadání 9. série (verze pro tisk). [Rovinné grafy, barevnost.]