PředmětyPředměty(verze: 877)
Předmět, akademický rok 2020/2021
  
Diskrétní matematika - NDMI002
Anglický název: Discrete Mathematics
Zajišťuje: Katedra aplikované matematiky (32-KAM)
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
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://mj.ucw.cz/vyuka/dm/
Garant: doc. RNDr. Jiří Fiala, Ph.D.
doc. RNDr. Martin Tancer, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMA005
Z//Je záměnnost pro: NDMA005
Anotace -
Poslední úprava: T_KAM (06.05.2001)
Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (30.09.2020)

Zápočet bude udělen za zisk dostatečného počtu bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, popř. docházku. Přesné podmínky stanoví cvičící. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani náhradních domácích úkolů.

Zkouška v paralelce M. Mareše bude ústní s písemnou přípravou a bude pokrývat jak řešení příkladů, tak teorii. V paralelce M. Tancera se zkouška skládá z písemné části s řešením příkladů a ústní části z teorie. Podle epidemiologické situace může být písemná část nahrazena ústní, popřípadě může být zkouška u obou zkoušejících být vedena distančně online.

Literatura -
Poslední úprava: G_I (25.01.2007)

J. Matousek, J. Nesetril: Kapitoly z diskretni matematiky, nakladatelstvi Carolinum, Praha, 2000

Požadavky ke zkoušce -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)

Zkouška se skládá z písemné a ústní části. Ústní část proběhne formou diskuse řešení písemné části a případných doplňujících otázek.

Sylabus -
Poslední úprava: doc. RNDr. Martin Tancer, Ph.D. (19.10.2020)

Základní značení, motivační příklady, co je důkaz, důkaz indukcí.

Funkce, relace, ekvivalence. Permutace.

Základní kombinatorické počítání (počet podmnožin, k-prvkových podmnožin, všech zobrazení, prostých

zobrazení, permutací). Binomická věta. Odhady faktoriálu a binomických koecientů.

Princip inkluze a exkluze a jeho aplikace (šatnářka).

Pravděpodobnostní prostor (nejvýš spočetný, všechny podmnožiny jsou jevy). Nezávislé jevy, podmíněná

pravděpodnost. Náhodná veličina, distribuční funkce. Střední hodnota a její výpočet. (Základní diskrétní

pravděpodobnostní rozdělení).

Základní pojmy z grafů, cesta/tah/sled, izomorfismus apod.

Charakterizace eulerovských grafů (též orientovaný případ, silná a slabá souvislost).

Stromy (různé charekterizace, existence listu).

Rovinné grafy, Eulerova formule, maximální počet hran.

Barevnost grafu, charakterizace bipartitních grafů, d-degenerovaný graf má barevnost nejvýš d+1, 5-

barevnost rovinných grafů (přes Kempeho řetězce).

Částečné uspořádání, řetězce a antiřetězce, věta o dlouhém a širokém, Erdősovo-Szekeresovo lemma o

monotónní podposloupnosti.

Rozšiřující témata: hra HEX; věta o skóre.

 
Univerzita Karlova | Informační systém UK