PředmětyPředměty(verze: 835)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Diskrétní matematika - NMIN105
Anglický název: Discrete Mathematics
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018
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
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
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. 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
Anotace -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (02.02.2018)

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: Mgr. Jan Kynčl, Ph.D. (02.02.2018)

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.

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. (02.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: Mgr. Jan Kynčl, Ph.D. (02.02.2018)

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.

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