Diskrétní matematika 2

Zkratka předmětu KMI/DMII
Název předmětu Diskrétní matematika 2
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/DMII
Název Diskrétní matematika 2
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk čeština
Nahrazovaný předmět
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 (dvě absence povoleny, více absencí se omlouvá individuálně pouze v závažných případech, za vypracování speciálních úkolů).
V průběhu semestru se píší dva testy z každého je možno získat 30 bodů. K zisku zápočtu je třeba dosáhnout z obou testů v součtu alespoň 30 bodů.
Předmět je zakončen zkouškovou písemkou za 40 bodů. K úspěšnému absolvování předmětu je nutno získat celkem 55 bodů z toho alespoň 20 ze závěrečné písemky.

Obsah

1 - Definice grafu, základní příklady a typy grafů, grafový isomorfizmus, representace grafu;
2 - Skóre grafu, princip sudosti, věta o skóre;
3 - Cestování v grafu, grafová metrika, hledání nejkratší cesty;
4 - Souvislost grafu;
5 - Jednotažky, eulerovské grafy;
6 - Stromy, definice, charakterizace stromů, kódování stromů;
7 - Kostry grafů, Kruskalův a Jarníkův algoritmus;
8 - Rovinné grafy, Eulerův vzorec, problém 4 barev;
9 - Vytvořující funkce a její použití v kombinatorice;
10 - Další příklady použití vytvořující funkce;
11 - Náhodná schémata a střední složitost algoritmů;
12 - Rekurentní vztahy
13 - Rezerva (případně téma na přání studentů)

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: RNDr. Filip Soudský, Ph.D.
  • Přednášející: RNDr. Filip Soudský, Ph.D.
  • Cvičící: 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