Diskrétní matematika - NDMA005
Anglický název: Discrete Mathematics
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2022
Semestr: zimní
E-Kredity: 4
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: zrušen
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: prof. RNDr. Jaroslav Nešetřil, DrSc.
doc. Mgr. Robert Šámal, Ph.D.
Kategorizace předmětu: Informatika > Diskrétní matematika
Matematika > Diskrétní matematika
Záměnnost : NDMI002, NMIN105
Je neslučitelnost pro: NDMI002, NDMA006, NDMI030, NMIN105
Je záměnnost pro: NDMI030, NMIN105
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Základní přednáška oboru matematika.
Poslední úprava: ()
Literatura

P.Štěpánek, B.Balcar: Teorie množin, Academia Praha 1986

J.Matoušek, J.Nešetřil: Kapitoly z diskrétní matematiky, MATFYZPRESS 1996

J.Nešetřil: Kombinatorika I, grafy, SPN Praha 1983

Poslední úprava: Šámal Robert, doc. Mgr., Ph.D. (16.05.2012)
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.

Poslední úprava: T_KTI (10.04.2001)