Diskrétní matematika II

Zkratka předmětu KMI/KDMII
Název předmětu Diskrétní matematika II
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/KDMII
Název Diskrétní matematika II
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 8 HOD/SEM
Vyučovací jazyk čeština
Nahrazovaný předmět KMI/DMII
Vyloučené předměty KMI/DMIIA, KMI/KDIIA, KMI/YDMII
Podmiňující KMI/DMI, KMI/DMIA, KMI/KDMI, KMI/KDMIA, KMI/YDMI
Způsob zakončení Zkouška
Forma zakončení Kombinovaná
Zápočet před zkouškou Ano
Vyučovaný semestr Zimní
Cíle předmětu (anotace)

Kurz je pokračováním DMI. Jeho první část je zaměřena na základy teorie grafů, včetně vybraných grafových algoritmů. Dále je podána teorie vytvořujících funkcí s aplikacemi na slovní příklady (Pólyova věta) a také technika řešení lineárních rekurentních vztahů.

Požadavky na studenta

Aktivní účast na seminářích (100 %).
Splnění každého ze dvou zápočtových testů na minimálně 55%.
Písemná práce ke zkoušce minimálně 55%.

Obsah

1 - Definice grafu;
2 - Grafové operace;
3 - Cestování v grafu;
4 - Grafové homomorfismy;
5 - Stromy;
6 - Kódování stromů;
7 - Kostry grafů;
8 - Hladový algoritmus;
9 - Problém nejkratší cesty;
10 - Vytvořující funkce;
11 - Pólyova věta;
12 - Rekurentní vztahy;
13 - Slovní úlohy.

Předpoklady - další informace k podmíněnosti studia předmětu

Diskrétní matematika I (DMI, DMIA).

Získané způsobilosti

Student chápe fundamentální pojmy teorie grafů. Předvádí základní grafové operace a určuje některé typické parametry grafu. Ovládá kódování stromů Prüferovým kódem, hladový, Dijkstrův a Floydův algoritmus a na různých slovních úlohách demonstruje užití vytvořujících funkcí a rekurentních vztahů.

Garanti a vyučující
  • Garanti: Mgr. Tomáš Roskovec, Ph.D.
  • Přednášející: Mgr. Tomáš Roskovec, Ph.D., RNDr. Filip Soudský, Ph.D.
Literatura
  • Nýdl, V. Diskrétní matematika v příkladech, díl 2. České Budějovice: PF JU, 2007.
  • http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
  • Rosen, K. H. Discrete Mathematics and Its Applications. New York: McGraw-Hill, 2006. ISBN 0073229725 / 9780.
  • Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky. Praha: Karolinum, 2007. ISBN 978-80-246-1411-3.
Vyučovací metody

Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming)

Hodnotící metody

Ústní zkouška, Písemná zkouška, Test

Stáhnout jako PDF