Cvičení z diskrétky

V zimním semestru 2009/2010 cvičím diskrétní matematiku pro matematiky. Cvičení se koná každé úterý od 9:50 v K9.

Zápočet si můžete vysloužit za napsání zápočtových písemek (jedna v půli semestru, druhá na konci) a alespoň 2/3 docházku.

Co jsme dělali

29. 9. Matematická indukce na mnoho způsobů. Součty druhých mocnin, hra s plusky a minusky, vzorec na Fibonacciho čísla, hra s lámáním čokolády.
6. 10. Procházka temnem (totiž teorií množin). Jak vypadají formule, jak axiomy a jak se z nich dokazují jednoduché větičky (třeba existence průniku, sjednocení a kartézského součinu). Zkoumali jsme Zermelo-Fraenkelovu teorii množin, pro srovnání se zkuste podívat na Gödelovu-Bernaysovu (té stačí konečně mnoho axiomů).
13. 10. Relace a různé jejich vlastnosti (reflexivita, (anti)symetrie, transitivita).
20. 10. Počítání objektů: podmnožiny, sudé podmnožiny, relace a funkce s různými vlastnostmi. Jak se k tomu hodí binomická věta.

Úkoly:

  • Spočtěte Σk C(n,k)*2k, kde C(n,k) je kombinační číslo "n nad k".
  • Kolik existuje ekvivalencí na 4-prvkové množině?
27. 10. Princip inkluze a exkluze: algebraický důkaz pomocí charakteristických funkcí, šatnářka a spol., počet funkcí na a jeho souvislost s počtem ekvivalencí.

Úkoly:

  • Dokažte, že počet ekvivalencí na n-prvkové množině je roven 1/e*Σk≥0 kn/k!. (Jde to úpravou vzorce, který jsme odvodili na cvičení.)
  • Spočtěte, kolik je pořadí písmen A až P, která neobsahují jako vybranou podposloupnost slova PONK, DOBA, COP.
  • ... a když zakážeme i OPICE?
3. 11. Odhady rychlosti růstu funkcí: faktoriály a kombinační čísla.

Úkoly:

  • Dokažte, že e(n/e)n ≤ n! ≤ en(n/e)n.
  • Dokažte, že součin všech prvočísel p takových, že n < p ≤ 2n, je menší nebo roven 22n.
10. 11. Zápočtová písemka.
Rozšířené příklady:
  • 1*) Jak by to bylo, kdybychom syčivost a ocasnost porovnávali neostře?
  • 2*) Jak to dopadne na množině {1,...,n}?
24. 11. Zoo častečných a lineárních uspořádání. Minimální, maximální, největší a nejmenší prvky; suprema a infima; řetězce a antiřetězce. Uspořádání N, Z, Q, R, P(X) s inkuzí pro konečnou X, N\{0} s dělitelností, N\{0,1} s dělitelností.

Úkoly:

  • Dokažte, že v částečném uspořádání n-prvkové množiny neexistuje antiřetězec větší než C(n,n/2).
  • Dokažte, že má-li každá (i prázdná) podmnožina uspořádané množiny X supremum, pak má i každá podmnožina množiny X infimum.
1. 12. Ještě jednou uspořádání (nekonečně mnoho minimálních i maximálních prvků, nebo právě jeden minimální, který není nejmenší?). Věta o Dlouhém a Širokém. Věta o monotónních podposloupnostech a její dva důkazy (Dlouhým a Širokým nebo Principem holubníku). Zoo spočetných množin, nespočetnost reálných čísel (důkaz à la Cantorovo diskontinuum) a existence transcendentních čísel.

Úkol:

  • Jak sestrojit pro každé N posloupnost délky N2, která neobsahuje monotónní podposloupnost délky větší než N?
8. 12. Zoo nespočetných množin. Cantorova věta o mohutnosti potence. Grafy: pro která n, k existuje k-regulární graf na n vrcholech?

Úkoly:

  • Jakou mohutnost má Cantorovo diskontinuum?
  • Jakou mohutnost má množina všech reálných funkcí?
  • (*) ... spojitých reálných funkcí?
15. 12. Grafy: může existovat takový, jehož všechny stupně jsou různé? Až na jeden různé? Jak vypadají grafy neobsahující P1, P2, P3 nebo liché kružnice? Vyvážená orientace grafu se sudými stupni. Lichý uzavřený sled implikuje lichou kružnici.

Úkoly:

  • (*) Jak vypadají grafy, které neobsahují jako podgraf P4 (cestu se 4 hranami)?
  • Dokažte, že každý graf lze zorientovat tak, aby se v každém vrcholu lišil vstupní a výstupní stupeň nejvýše o 1.
  • Charakterizujte grafy, které se dají nakreslit k tahy.
  • (*) Dokažte, že má-li graf m hran, pak obsahuje bipartitní podgraf s alespoň m/2 hranami.
5. 1. Zápočtová písemka.
12. 1. Grafy: Každý netriviální strom má alespoň 2 listy. Strom s vrcholem stupně k má alespoň k listů. Graf, jehož všechny vrcholy mají stupeň alespoň k, obsahuje cestu délky k a kružnici délky alespoň k+1. Graf je souvislý, právě když má kostru. Mosty jsou právě ty hrany, které leží ve všech kostrách.

Úkoly:

  • Dokažte, že každý graf s m hranami má bipartitní podgraf s alespoň m/2 hranami.
  • Dokažte, že 2k-regulární graf nemůže obsahovat most.

Zápočtové písemky

Z110. 11.1. zápočtová písemka
(kvůli problému s ostrými uspořádáními jsem nakonec první příklad počítal jen za 2 body [maximum je tedy 15 bodů + až 4 za rozšířené příklady] a snížil hranici úspěšnosti na 8 bodů)
X124. 11.1. písemka včetně dodatečného příkladu
O19. 12.1. opravná písemka (v 15:20 před S322) a dodatečné příklady
Z25. 1.2. zápočtová písemka
O213. 1.2. opravná písemka (v 15:20 před S322)
X22. opravná písemka včetně dodatečných příkladů

Stránku spravuje Martin Mareš