Discrete Mathematics II

Zkratka předmětu KMI/KDIIA
Název předmětu Discrete Mathematics II
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/KDIIA
Název Diskrétní matematika II (anglicky)
Akreditováno/Kredity Ano/6
Rozsah hodin Přednáška 8 HOD/SEM
Vyučovací jazyk angličtina
Nahrazovaný předmět KMI/DMIIA
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;
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ů. Studenti plní všechny povinnosti v anglickém jazyce.

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
  • 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