Discrete Mathematics 2

Zkratka předmětu KMI/DMIIA
Název předmětu Discrete Mathematics 2
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/DMIIA
Název Discrete Mathematics 2
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 2 HOD/TYD Cvičení 2 HOD/TYD
Vyučovací jazyk angličtina
Nahrazovaný předmět
Vyloučené předměty KMI/DMII, KMI/KDMII
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íLetní
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ů. Kurz se vyučuje v anglickém jazyce.

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, 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ů. Studenti plní všechny povinnosti v anglickém jazyce.

Garanti a vyučující
  • Garanti: RNDr. Filip Soudský, Ph.D.
  • Přednášející: RNDr. Filip Soudský, Ph.D.
Literatura
  • Rosen, K. H. Discrete Mathematics and Its Applications. New York: McGraw-Hill, 1988.
  • Nýdl, V. Diskrétní matematika v příkladech, díl 2. České Budějovice: PF JU, 2007.
  • Diestel, R. Graph Theory. electronic edition [online]. [cit. 1. 9. 2008]. New York: Springer-Verlag, 2000.
  • 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

Kombinovaná zkouška, Test

Stáhnout jako PDF