Discrete Mathematics 2

Zkratka předmětu KMI/YDMII
Název předmětu Discrete Mathematics 2
Akademický rok 2018/2019
Pracoviště / Zkratka KMI/YDMII
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 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í
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.
  • Cvičící: RNDr. Filip Soudský, Ph.D.
Literatura
  • Diestel, R. Graph Theory. electronic edition [online]. [cit. 1. 9. 2008]. New York: Springer-Verlag, 2000.
  • Rosen, K. H. Discrete Mathematics and Its Applications. New York: McGraw-Hill, 1988.
  • Matoušek, J., Nešetřil, J. Invitation to Discrete Mathematics. Oxford. ISBN 0-19-850207-9.
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