Diskrétní matematika, zimní semestr 2009/2010 (P. Kolman)



Minulé přednášky

30. 9. 2009 Úvodní přednáška. Množiny a operace na nich. Součty, součiny. Matematická indukce.

7. 10. Kartézský součin množin. Relace (definice, příklady, reprezentace, zvláštní vlastnosti [reflexivní, symetrická, antisymetrická, tranzitivní], skládání). Funkce jako zvláštní relace (definice, příklady, zlváštní vlastnosti [prostá ap.], skládání). Počet všech funkcí z množiny X do množiny Y, počet všech podmnožin množiny. Rozmyslet si: jaký je počet všech podmnožin liché velikosti, pro danou množinu X?

14. 10. Výuka zrušena (imatrikulace)

21. 10. Počet lichých podmnožin, počet prostých zobrazení X do Y, prosté zobrazení jako uspořadaná k-tice, permutace. Kombinační čísla a počet podmnožin dané velikosti, binomická věta (důkaz za úkol). Lehký úvod do pravděpodobnosti.

28. 10. Státní svátek

4. 11. Diskrétní pravděpodobnostní prostor, Bertrandův paradox (hra s barevnými kartami). Podmíněná pravděpodobnost, věta o úplné pravděpodobnosti, Bayesova věta. Nezávislé jevy.

11. 11. Soucin diskrétních pravděpodobnostních prostoru. Nahodna velicina, stredni hodnota nahodne veliciny, median, linearita stredni hodnoty, indikator jevu.

18. 11. Nezavisle nahodne veliciny, Markovova nerovnost, rozptyl, soucet rozptylu nezavislych NV, Cebysevova nerovnost, priklady.

25. 11. Distribuční funkce NV, důležitá pravděpodobnostní rozdělení. Grafy. Pojem grafu, reprezentace grafu obrázkem, důležité grafy (úplný, cesta, kružnice, úplný bipartitní), bipartitní grafy, stupeň vrcholu, skore grafu. Izomorfismus grafů, odhad počtu neizomorfních grafů na n vrcholech. Podgraf, indukovaný podgraf, cesta v grafu.

2. 12. Eulerovské grafy (přednášel Jan Volec).

9. 12. Stromy. Lemma o koncovém vrcholu, věta o postupné výstavbě stromů. Počet koster úplného grafu.

16. 12. Rovinné grafy. Oblouk, nakreslení grafu a rovinné nakreslení. Topologická kružnice, komponenty obloukové souvislosti, Jordanova věta. Stěny, Eurelův vztah. Maximální počet hran rovinného grafu. K_5, K_{3,3}.

6. 1. 2010 Platónská tělesa a rovinné grafy. Kuratowského věta (bez důkazu). Barvení map a grafů. Věta o pěti barvách.

13. 1. 2010 Uspořádané množiny. Částečně uspořádaná množina. Úplné (lineární) uspořádání. "Zúplňování" ČUM. Minimální prvek. Nejmenší prvek. Věta o dlouhém a širokém. Erdosovo-Szekeresovo lemma.


Čas a místo konání: Streda 12:20, poslucharna S3 na Male Strane. Paralelni prednasky maji na starosti J. Matousek a O. Pangrac.

Literatura: J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky. Treti, rozsirene a opravene vydani: Karolinum.
Sylabus pro pravděpodobnost (připravil J. Matoušek).

Cvičení: Cviceni vedou a zapocty udili Josef Cibulka, Helena Nyklova a Jan Volec. Pro procviceni doporucuji Sbirku prikladu.

Zkoušky: Ustni, s casem na pripravu. Terminy budou vypsany v SISu.

Konzultacni hodiny: Upresnim po doladeni rozvrhu. Zatim dle dohody.

Informace pro studenty dalkoveho studia

29. září 2009