Předmět Diskrétní matematika (NDMI002)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NDMI002 - Diskrétní matematika, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
Základní značení, motivační příklady, co je důkaz, důkaz indukcí. Funkce, relace, ekvivalence. Permutace. Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých zobrazení, permutací). Binomická věta. Princip inkluze a exkluze a jeho aplikace (šatnářka). Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy). Nezávislé jevy, podmíněná pravděpodnost. Náhodná veličina, distribuční funkce. Střední hodnota a její výpočet. (Základní diskrétní pravděpodobnostní rozdělení). Základní pojmy z grafù, cesta/tah/sled, izomorsmus apod. Charakterizace eulerovských grafù (též orientovaný případ, silná a slabá souvislost). Stromy (různé charekterizace, existence listu). Rovinné grafy, Eulerova formule, maximální počet hran. Barevnost grafu, charakterizace bipartitních grafù, d-degenerovaný graf má barevnost nejvýš d+1, 5-barevnost rovinných grafù (přes Kempeho řetězce). Částečné uspořádání, řetězce a antiřetězce, věta o dlouhém a širokém, Erdösovo-Szekeresovo lemma o monotónní podposloupnosti.Rozšiřující témata: hra HEX; věta o skóre.
Literatura
J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000
Garant
doc. RNDr. Jiří Fiala, Ph.D.Mgr. Jan Kynčl, Ph.D.Hans Raj Tiwary, M.Sc., Ph.D.