Předměty

Váš prohlížeč nepodporuje JavaScript nebo je jeho podpora vypnutá. Některé funkce nemusejí být dostupné.

Diskrétní matematika - NMIN105

Anglický název:	Discrete Mathematics
Zajišťuje:	Katedra aplikované matematiky (32-KAM)
Fakulta:	Matematicko-fyzikální fakulta
Platnost:	od 2014 do 2015
Semestr:	zimní
E-Kredity:	5
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:	vyučován
Jazyk výuky:	čeština
Způsob výuky:	prezenční
Způsob výuky:	prezenční

Garant:	prof. RNDr. Jaroslav Nešetřil, DrSc. prof. RNDr. Martin Loebl, CSc. Mgr. Martin Mareš, Ph.D.
Třída:	M Bc. FM M Bc. FM > Povinné M Bc. FM > 1. ročník M Bc. MMIB M Bc. MMIB > Povinné M Bc. MMIB > 1. ročník M Bc. MMIT M Bc. MMIT > Povinné M Bc. OM M Bc. OM > Povinné M Bc. OM > 1. ročník
Kategorizace předmětu:	Informatika > Diskrétní matematika Matematika > Diskrétní matematika
Neslučitelnost :	NDMA005
Záměnnost :	NDMA005
Je záměnnost pro:	NDMA005

Anotace -

Poslední úprava: G_M (16.05.2012)

Základní přednáška z diskrétní matematiky pro všechny odborné obory bakalářského programu Matematika.

Literatura

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (02.02.2018)

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

Sylabus -

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (02.02.2018)

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.