Předmět Diskrétní matematika (NMIN105)
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 NMIN105 - 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
Pojem množiny (Cantor), jazyk teorie množin, formule. Popis množiny výčtem nebo jako množiny prvků "dané vlastnosti". Základní operace s množinami (vč. potence a sumy) a jejich vlastnosti. Kartézský součin, (binární) relace, skládání relací. Funkce, funkce prostá a na. Vlastnosti relací (reflexivita, symetrie,...). Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady. Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální,... prvek, příklady. Izomorfizmus množin vzhledem k relacím. Dobré uspořádání. Dobré uspořádání přirozených čísel podle velikosti, princip indukce pro přirozená čísla. Kombinatorické počítání. Počet zobrazení (prostých zobrazení) n-prvkové do m-prvkové množiny, počet podmnožin n-prvkové množiny. Variace, permutace, kombinace. Kombinační čísla, binomická věta. Princip inkluze a exkluze. Definice grafu, základní terminologie, izomorfizmus grafů. Stupeň uzlu, skóre grafu. Cesty v grafu, souvislost, komponenty, hledání nejkratší cesty. Metrika v grafu a pojmy z ní odvozené. Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině, kostra grafu, hledání minimální kostry. Izomorfizmus stromů, kódování stromů. Rovinné grafy, Eulerova formule a její důsledky. Obarvení rovinného grafu pěti barvami.
Literatura
J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, MATFYZPRESS 1996 J.Nešetřil: Kombinatorika I, grafy, SPN Praha 1983 P.Štěpánek, B.Balcar: Teorie množin, Academia Praha 1986
Garant
prof. RNDr. Jaroslav Nešetřil, DrSc.prof. RNDr. Martin Loebl, CSc.Mgr. Martin Mareš, Ph.D.