Diskrétní matematika - cvičení
Zde se průběžně budou objevovat nějaké informace ke cvičením.
Najdete tu příklady k cvičením (z velké části jsou čerpány z knihy od J.
Matouška a J. Nešetřila Kapitoly z diskrétní matematiky).
Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou
stránku. Tato stránka k cvičením se týká pouze skupin st 15:40 M3 a
st 17:20 M3.
Opravná písemka
Opravná písemka za 1. a 2. písemku se bude konat ve čtvrtek 19. 1. od 9:00 v
učebně S9.
Výsledky po 2. písemce
2. písemka je už opravena a výsledky najdete zde skupina 15:40 a skupina 17:20. Zároveň tam už máte finální body za
docházku a aktivitu. Kdo se bude chtít na písemku podívat, ať mne kontaktuje
emailem a domluvíme se. Rád písemku ukážu: dokonce to velmi doporučuji, ať víte, v čem jste
dělali největší chyby. A také, rozhodl jsem se snížit počet potřebných bodů na
zápočet z 70 bodů na 65. Kdo tedy získal alespoň 65 bodů, měl by už mít zápočet
v SISu. Zkontrolujte si! Kdo na zápočet zatím těsně nedosáhl, může zkusit
vyřešit některé z následujících jednoduchých DÚ. S těmi, co nedosáhli výrazněji se domluvíme
na opravné písemce. (Ale body za DÚ si také můžete vypomoci.)
DÚ 3a: Určete počet permutací s právě jedním pevným bodem. Můžete používat
šatn. číslo ve výsledku. (2 body)
DÚ 3b: Nalezněte všechny stromy, jejichž doplňkem je nesouvislý graf. (3
body)
DÚ 3c: Graf G získáme tak, že z úplného grafu s 2n vrcholy odbereme
perfektní párování, to znamená n hran z nichž žádné dvě nejsou sousední.
Pro parametr t menší roven n určete počet podgrafů grafu G izomorfních s úplným
grafem s t vrcholy. (3 body)
Druhá písemka
Druhá písemka bude ve středu 11. 1.
Dobrovolný DÚ 2
Byl zadán dobrovolný domácí úkol 2. Mezi variantami a) a
b) si vyberte jenom jednu. Bodování je 3 body za a), 4 body za b), 3 body za c) (maximálně tedy
můžete získat 7 bodů). Termín odevzdání úkolu je 4. 1. 2017. Kdo mi však řešení
úkolu odevzdá nebo pošle mailem do 21. 12. 2016, tomu napíšu nějaké připomínky,
poud řešení nebude v pořádku (a bude mít možnost řešení ještě opravit bez
ztráty bodů).
Dobrovolný DÚ 1
Za následující dobrovolný domácí úkol můžete získat 4 body (do středy 23. 11.):
Nechť G=(V,E) je graf a A je jeho matice sousednosti. Dokažte, že součet prvků
na hlavní diagonále druhé mocniny matice A je roven 2|E|.
První písemka
První písemka byla ve středu 9. listopadu za 42 možných bodů. Zde můžete najít výsledky skupiny 15:40 a skupiny 17:20. Zároveň tu
máte body za aktivitu k 9. 11.
Podmínky k zápočtu
Základní podmínkou k získání zápočtu je úspěšné absolvování dvou písemek. Z
písemek je potřeba získat 70% (70 bodů ze 100 možných). 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 (ale doporučuji se
připravit už napoprvé, dříve budete moci ke zkoušce).
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ů.
5. 10.: zadání 1. série (verze pro tisk). [Matematická indukce a
relace.]
12. 10.: zadání 2. série (verze pro tisk). [Funkce a částečná uspořádání.]
19. 10.: zadání 3. série (verze pro tisk). [Základní kombinatorické počítání.]
26. 10.: zadání 4. série (verze pro tisk). [Princip inkluze a exkluze.]
2. 11.: dodělávali jsme příklady ze 4. série.
9. 11.: byla písemka. Posledních 20 minut: zadání 5. série (verze pro tisk). [Základní pojmy teorie grafů.]
16.11.: zadání 6. série (verze pro tisk). [Podgrafy, matice sousednosti, stupně a
skóre.]
23.11.: zadání 7. série (verze pro tisk). [Eulerovské grafy a stromy.]
30.11.: dodělávali jsme příklady ze 7. série.
7.12.: zadání 8. série (verze pro tisk). [Kostry, rovinné grafy.]
14.12.: zadání 9. série (verze pro tisk). [Ještě rovinné grafy a barvení grafů.]
4.1.: zadání 10. série (verze pro tisk). [Prostor cyklů.]