PředmětyPředměty(verze: 901)
Předmět, akademický rok 2021/2022
  
Diskrétní matematika - NMIN105
Anglický název: Discrete Mathematics
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: https://dl3.cuni.cz/user/index.php?id=98
Garant: prof. RNDr. Jaroslav Nešetřil, DrSc.
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.
Podmínky zakončení předmětu
Poslední úprava: RNDr. Martin Balko, Ph.D. (07.10.2019)

Zápočet je nutnou podmínkou účasti u zkoušky.

Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod. Maximální možný počet bodů, které lze získat, je zhruba 150.

Povaha kontroly studia předmětu vylučuje opakování této kontroly, tedy zápočtu.

Literatura -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (04.02.2018)

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

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

Požadavky ke zkoušce
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (30.09.2020)

Zkouška je ústní. Požadavky u ústní zkoušky odpovídají sylabu předmětu v rozsahu, který byl prezentován na přednášce. Zkouška může mít kontaktní nebo distanční formu.

Sylabus -
Poslední úprava: 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á, na, bijekce.

Vlastnosti relací (reflexivita, symetrie, ...).

Relace ekvivalence na množině, rozklad množiny, vzájemný vztah, příklady.

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.

Asymptotické odhady faktoriálu a kombinačních čísel.

Definice grafu, základní terminologie, izomorfismus grafů.

Stupeň vrcholu, princip sudosti, skóre grafu.

Cesty v grafu, souvislost, komponenty.

Metrika v grafu a pojmy z ní odvozené.

Stromy, jejich charakterizace a vlastnosti, počet stromů na dané množině.

Isomorfismus stromů, kódování stromů.

Kostra grafu, hledání minimální kostry.

Uspořádání, lineární uspořádání, největší/nejmenší, maximální/minimální prvek, řetězec/antiřetězec, supremum/infimum, příklady.

Existence minimálního prvku a věta o lineárním rozšíření pro konečné množiny.

Isomorfismus množin vzhledem k relacím.

Reprezentace částečného uspořádání pomoci inkluze.

Dobré uspořádání, princip indukce pro přirozená čísla.

Eulerovské tahy.

Eulerovské podgrafy a jejich popis pomocí vektorových prostorů (prostor cyklů a řezů).

Rovinné grafy.

Nakreslení grafu do roviny.

Eulerova formule a její důsledky.

Obarvení rovinného grafu pěti barvami.

Rozšiřující témata:

Ramseyova věta pro grafy, vícebarevná Ramseyova věta.

Dolní odhad Ramseyových čísel.

 
Univerzita Karlova | Informační systém UK