Cvičení z Diskrétní matematiky

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

Co se dělalo na cvičení:

  • 1. hodina: Příklady na procvičení indukce: sčítání, dělitelnost, Fibonacciho čísla, dláždění mřížky.

    Domácí příprava na +: Dokažte matematickou indukcí:\[\sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}{6}, 4/(6n^2+2n), \sum_{i=1}^n{F_i}=F_{n+2}-1\].

  • 2. hodina: Příklady ze cvičení. Procvičení relací, kartézský součin, různý zápis relací,vlastnosti relací (reflexivita, symetrie, tranzitivita, ekvivalence).

    Domácí příprava na +: Napiště příklad relace, která je a) symetrická, b) reflexivní, c) tranzitivní.

  • 3. hodina: Příklady ze cvičení.

    Domácí příprava na +: Nakreslete Hasseho diagram pro uspořádání dělitelnost přirozených čísel na množině přirozených čísel od 1 do 16. Určete nejmenší, největší, minimální a maximální prvek. Pokuste se určit supremum a infimum podmnožiny {3, 4, 5}.

  • 4. hodina: Kombinatorické počítání (kolik existuje binárních matic rozměru nm, kolika způsoby vybereme ze třídy tým, různá slova z POPOCATEPETL...), binomická věta a její aplikace, kombinační čísla.

    Domácí příprava na +: 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.)

  • 5. hodina: Počítání dvěma způsoby, princip inkluze a exkluze.

  • 6. hodina: Příklady ze cvičení. Seznámení s grafy. Speciální třídy grafů: úplný, bipartitní graf, cesta, kružnice, strom. Podgrafy, matice sousednosti a incidence, izomorfismus grafů.

    Domácí příprava na +: Nalezněte všechny grafy, které jako podgraf neobsahují cestu délky 3.

    Domácí příprava na +: 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í. Reakce k písemkám a domácím úkolům, jak správně psát definice. Skóre grafu, věta o počtu sledů v grafu, izomorfismus grafů, matice sousednosti.

    Domácí příprava na +: Nalezněte dva grafy na alespoň sedmi vrcholech, z nichž jeden je strom a druhý strom není, se stejným skórem grafu.

  • 8. hodina: Příklady ze cvičení. Eulerovské grafy, stromy.

    Domácí příprava na +: 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.

  • 9. hodina: Příklady ze cvičení. Stromy, kostra grafu.

    Domácí příprava na +: Kolik různých koster má graf prasátka?

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

  • 11. hodina: Příklady ze cvičení. Rovinné grafy.

    Domácí příprava na +: Najděte takový rovinný graf, jehož duál je také rovinným grafem.

  • 12. hodina: Příklady ze cvičení. Rovinné grafy - pokračování, barvení grafů.

    Domácí příprava na +: Jaká je barevnost grafu prasátka?

  • 13. hodina: Prostor cyklů, jakou velikost má množina všech kružnic bipartitního/úplnéh grafu, stromu..., aplikace věty o prostoru kružnic - určování dimenze, nalezení báze vzhledem k nalezené kostře, vyjadřování jiné kružnice pomocí bazických vektorů.

    • Domácí příprava na +: Určete dimenzi prostoru cyklů mřížky m x n.

Požadavky na zápočet:

K tomu, abyste dostali zápočet, budete muset splnit několik podmínek. V průběhu semestru vás čeká

  • 1 velká písemka za 30 bodů,
  • 5 malých písemek po 5 bodech,
  • 5 sérií domácích úkolů po 10 bodech.
Dále budu vyžadovat aktivitu, za kterou budete dostávat +(pluska). Pluska můžete získat 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ápočet lze získat za splnění všech následujících podmínek:

  • Zisk alespoň 13 +
  • Alespoň 60 % bodů z velké písemky nebo alespoň 60 % bodů ze všech malých písemek.
  • Alespoň 55 % všech bodů (tj. série domácích úkolů, malé písemky, velká písemka).

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í." Doplnění: místo původních 6 malých písemek a 6 dú bude jen 5 malých písemek a 5 dú, k tomu bude bonusová malá písemka i domácí úkol, ale snažte se splnit podmínky i bez toho.

Domácí úkoly:

Zde budou postupně přibývat domácí úkoly, na jejich vyřešení budete mít vždy alespoň týden. Ú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. 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í 27. 10. 2016.
  • DÚ 2, termín odevzdání 10. 11. 2016.
  • DÚ 3, termín odevzdání 24. 11. 2016.
  • DÚ 4, termín odevzdání 15. 12. 2016.
  • DÚ 5, termín odevzdání 12. 1. 2017.
______________________________________________________________________________
  • Bonusový DÚ (není povinný), termín odevzdání týden před tím, než budete chtít zápočet.
Pokud potřebujete získat více plusek: odevzdejte bezchybně vyřešené úlohy z průběhu roku nebo vyřešte náhradní úlohy na pluska.

Výsledky

Pokud nechcete mít zveřejněny iniciály na webu používejte k podpisům ještě navíc přezdívku.

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.