Předmět: Kombinatorické metody

» Seznam fakult » FM » KAP
Název předmětu Kombinatorické metody
Kód předmětu KAP/KME
Organizační forma výuky Přednáška + Cvičení
Úroveň předmětu Magisterský
Rok studia nespecifikován
Semestr Zimní
Počet ECTS kreditů 5
Vyučovací jazyk Čeština
Statut předmětu Povinný
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
Dostupnost předmětu Předmět je nabízen přijíždějícím studentům
Vyučující
  • Koucký Miroslav, doc. RNDr. CSc.
  • Jirsák Čeněk, Mgr.
Obsah předmětu
Přednášky: 1.-3. Rekurentní vztahy a jejich řešení. Homogenní lineární rekurentní vztahy a jejich řešení (charakteristická rovnice, násobné, komplexní kořeny). Nehomogenní lineární rekurentní vztahy a jejich řešení. Diferenční rovnice. 4.-7. Vytvořující funkce a jejich vybrané aplikace. Obyčejné, exponenciální vytvořující funkce, jejich vlastnosti. Řešení rekurentních vztahů a jejich soustav (včetně vybraných nelineárních) metodou vytvořujících funkcí. Catalanova čísla. Věžové polynomy. Rozklady. 8.-9. Pólyaova enumerační metoda. 10.-14. Úvod do teorie grafů. Souvislost. Eulerovské grafy, rovinné grafy. Algoritmy pro nalezení minimální kostry, nejkratší cesty. Toky v sítích, algoritmy pro nalezení maximálního toku v sítích. Cvičení: Procvičuje se látka vyložená na přednáškách. Důraz je kladen na schopnost aplikace teoretických poznatků při řešení aplikačně orientovaných úloh.

Studijní aktivity a metody výuky
Monologický výklad (přednáška, prezentace, vysvětlování)
  • Účast na výuce - 56 hodin za semestr
  • Příprava na zkoušku - 90 hodin za semestr
Výstupy z učení
Studenti se seznámí s vybranými kombinatorickými metodami (vytvořující funkce, rozklady, rekurentní vztahy, vybrané partie z teorie grafů).
Teoretické znalosti a schopnost jejich aplikace.
Předpoklady
Znalosti středoškolské matematiky

Hodnoticí metody a kritéria
Kombinovaná zkouška

Aktivní účast na cvičeních, zápočet, znalosti odpovídající sylabu.
Doporučená literatura
  • AIGNER, Martin. Combinatorial Theory. Berlin: Springer, 1997. ISBN 3-540-61787-6.
  • J. Matoušek, J. Nešetřil. Kapitoly z diskrétní matematiky. Karolinum, 2009. ISBN 80-246-0084-.
  • Rosen K. Discrete mathematics and its applications. McGraw-Hill, 1999.


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr
Fakulta: Fakulta mechatroniky, informatiky a mezioborových studií Studijní plán (Verze): Informační technologie (2013) Kategorie: Informatické obory 2 Doporučený ročník:2, Doporučený semestr: Zimní