Cvičení z Diskrétní matematiky

Na této stránce se nachází informace pro studenty Diskrétní matematiky (2017/2018), páteční cvičení od 12:20 k přednáškám Martina Tancera.

Co se dělalo na cvičení:

1. hodina: co je důkaz, příklady na procvičení matematické indukce.
Příklady ze cvičení.

Domácí příprava na 1b: Dokažte matematickou indukcí:\[\sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}, 4/(6n^2+2n).\]
2. hodina: Příklady ze cvičení. Doprocvičení matematické indukce. Procvičení relací, kartézský součin, různý zápis relací, vlastnosti relací (reflexivita, symetrie, tranzitivita, ekvivalence).
Domácí příprava na 1b: Napiště příklad relace (na vámi zvolené množině), která je a) symetrická, b) reflexivní, c) tranzitivní, d) ekvivalence.
Příští hodinu by se mohla psát malá písemka.

3. hodina: Příklady ze cvičení. Ekvivalence a třídy rozkladu, částečné uspořádání.
Domácí příprava na 1b (druhá část příkladu 3 ze cvičení): Je následující relace (porovnání v alespoň jedné souřadnici) na množině dvojic přirozených čísel uspořádáním? Pokud ano, je lineárním uspořádáním? \[\le_U: (a,b)\le_U(x,y) \Leftrightarrow a\le x \vee b\le y\].
4. hodina: Příklady ze cvičení.
Domácí příprava na 1b: Příklad 5 ze cvičení (o prostém a "na" zobrazení na množině).
5. hodina [zástup]: Kombinatorické počítání (kolika způsoby vybereme ze třídy tým, různá slova z POPOCATEPETL...), binomická věta a její aplikace, kombinační čísla. Vybrané příklady z příkladů Martina Tancera.
Domácí příprava na 1b: Kolik existuje různých přirozených desetimístných čísel? Kolika způsoby mohu z 50 studentů vybrat 5 místopředsedů a jednoho předsedu? Kolika způsoby se může do fronty seřadit 15 lidí? (Výsledek úloh nevyčíslujte, stačí zápis pomocí kombinačních čísel, faktoriálů apod.)
6. hodina: Příklady ze cvičení. Počítání dvěma způsoby, princip inkluze a exkluze.
Domácí příprava na 1b: Kolik čísel zbyde z čísel 1 až n po vyškrtání násobků 2, 3, 5, 7? Určete obecně a dále vyčíslete pro n=999.
17. listopadu - státní svátek

7. hodina: Příklady ze cvičení. Pravděpodobnost
Domácí příprava na 1b: Zpráva je přenášena jako 8 bitové slovo (8 znaků 0/1), chyba při přenosu nastane s pravděpodobností 0,01 %. Pokud nastane pouze jedna chyba ve slově, algoritmus ji umí napravit. Jaká je pravděpodobnost, že algoritmus chybu neopraví (tedy nastalo 2 a víc chyb)?
8. hodina: Příklady ze cvičení. Náhodná veličina, indikátory. Seznámení s grafy.
Domácí příprava na 1b: Jaký nejmenší, resp. největší, součet prvků může mít matice sousednosti souvislého grafu (tj. kolik minimálně/maximálně 1 obsahuje matice sousednosti souvislého grafu)?
9. hodina: Příklady ze cvičení. Grafy, věta o počtu sledů, skóre grafu, izomorfismus grafů.
Domácí příprava na 1b: Existuje bipartitní graf na alespoň 5 vrcholech, jehož doplněk je také bipartitní? (def. doplňku: viz příklad ze cvičení)
10. hodina: Příklady ze cvičení. Eulerovské grafy, orientovaný eulerovský tah, stromy.
Domácí příprava na 1b: Proč musí být ve větě o eulerovském tahu v grafu podmínka souvislosti? Tj. nalezněte takový graf, který splňuje všechny ostatní podmínky věty a nemá eulerovský tah.
11. hodina: Příklady ze cvičení. Kostry grafu, rovinne grafy a Euleruv vzorec.
Domácí příprava na 1b: Určitě se těšíte, až na Štědrý večer uvidíte prasátko. Co byste ale byli za matfyzáky, kdyby vás nenapadlo spočítat počet jeho koster? Určitě to zvládnete spočíst dřív než vám uteče. Kolik různých koster má tedy graf prasátka?

12. hodina (5. ledna): Velká písemka: Pokud se z nějakého důvodu nebudete moci zúčastnit, dejte vědět co nejdříve.

13. hodina [zástup]: Příklady ze cvičení.
Domácí příprava na 1b (lze odevzdávat do konce zkouškového): Jaká je barevnost grafu prasátka?

Požadavky na zápočet:

V průběhu semestru budou vypsány domácí úkoly za 40 bodů, velká písemka za 20 bodů a malé písemky dohromady za 20 bodů. Dále bude možné získávat bonusové body za aktivitu, několika způsoby:

aktivita na cvičení,
vyřešením jednoduchých příkladů, které budu vždy zadávat po cvičení (odevzáte je na dalším cvičení),
hezkým vyřešením nebo sepsáním úloh aj.

Z takto získaných bonusových bodů se do celkového počtu bodů započítává maximálně 12 bodů.

Zápočet lze získat za splnění všech následujících podmínek:

Alespoň 12 bodů z velké písemky nebo alespoň 12 bodů ze všech malých písemek.
Alespoň 50 bodů celkem (tj. domácí úkoly, malé písemky, velká písemka, aktivita).

Pokud vypadá, že nesplníte limity, něco vám uteklo, nepovedlo se... Ozvěte se včas, třeba se bude dát něco vymyslet. "Problémy jdou řešit, když se o nich ví."

Písemky:

Velká písemka se bude psát na cvičení někdy ke konci semestru, bude předem ohlášena. Časově zabere celé cvičení a bude obsahovat látku od začátku roku.

Malé písemky budou vždy na začátku hodiny tak na 10 min. Často vám nebudu předem oznamovat, kdy přesně budou.Typicky budou obsahovat látku z posledních cvičení, nějaký jednodušší příklad, či základní definice.

Domácí úkoly:

V průběhu semestru zde přibydou dva domácí úkoly, na jejichž vyřešení budete mít vždy alespoň dva týdny. Úkoly nejlépe odevzdávejte na cvičení, příp. posílejte mailem v rozumném formátu (pokud mi pošlete pěkně ofocený text psaný ručně, který jste z nějakého důvodu nemohli donést na cvičení, nemám s tím problém).

Při vymýšlení řešení domácích úkolů spolu klidně spolupracujte, každý však musí sepsat řešení sám. Dejte si záležet se sepsáním domácích úkolů a všechny kroky řešení pečlivě zdůvodněte, důležitější je zpravidla postup než výsledek (cokoli z přednášek a cvičení můžete naopak brát jako známé, jen je třeba uvést, co používáte).

DÚ 1, termín odevzdání 24. 11. 2017.

DÚ 2, termín odevzdání 22. 12. 2017.

každé

______________________________________________________________________________

Výsledky

Pokud nechcete mít zveřejněny iniciály na webu, napiště mi/odevzdejte s nějakým úkolem/písemkou vaši přezdívku. Pokud nechcete být uvedeni vůbec, dejte mi vědět.

Dosavadní Výsledky v google dokumentu.

Při jakékoli nesrovnalosti/reklamaci mi dejte vědět.

Ostatní

Na procvičování se vám může hodit sbírka úloh nebo knížka Kapitoly z diskrétní matematiky od J. Matouška a J. Nešetřila.

A pár rad na závěr... Nebojte se ptát, když vám není něco jasné. Klidně choďte na konzultace. Nenachávejte vše na poslední chvíli.