Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (02.05.2019)
Přednáška představí základní metody řešení kombinatorických problémů pomocí
vytvořujících funkcí, s důrazem na metody využívající poznatky z komplexní
analýzy. Žádné předchozí znalosti z komplexní analýzy nejsou k absolvování
přednášky nutné, očekávají se pouze základní znalosti o vytvořujících funkcích
na úrovni předmětů NDMI011 Kombinatorika a grafy 1 nebo NDMA001 Teorie grafů a algoritmy pro matematiky 1.
Poslední úprava: IUUK (16.05.2012)
The course will focus on solving combinatorial problems by application of
generating functions, with emphasis on methods based on complex analysis. No
previous knowledge of complex analysis is necessary, but basic knowledge of
generating functions is expected.
Podmínky zakončení předmětu -
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Ústní zkouška s možností písemné přípravy.
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (10.06.2019)
Oral exam with time for written prepapration.
Literatura -
Poslední úprava: IUUK (16.05.2012)
Herbert S. Wilf: Generatingfunctionology. Academic Press, 1993. ISBN 0-12-751956-4
Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009. ISBN 978-0-521-89806-5
Poslední úprava: IUUK (16.05.2012)
Herbert S. Wilf: Generatingfunctionology. Academic Press, 1993. ISBN 0-12-751956-4
Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics. Cambridge University Press, 2009. ISBN 978-0-521-89806-5
Požadavky ke zkoušce -
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (25.02.2019)
Zkouška má ústní formu s možností písemné přípravy. Je požadována znalost látky v rozsahu předneseném na přednášce, včetně schopnosti aplikovat tuto látku na řešení konkrétních kombinatorických příkladů.
Poslední úprava: doc. RNDr. Vít Jelínek, Ph.D. (25.02.2019)
The exam is oral, with the possibility of a written preparation. The exam covers the material presented at the lectures, including the ability to apply the theory presented at the lectures to solve specific combinatorial exercises.
Sylabus -
Poslední úprava: IUUK (16.05.2012)
Formální mocninné řady. Lagrangeova inverzní formule. Obyčejné a exponenciální
vytvořující funkce, kombinatorický význam základních operací s nimi. Přehled
základních vlastností komplexních analytických funkcí, racionální a meromorfní
funkce, reziduová věta. Využití komplexní analýzy při počítání kombinatorických
objektů. Vytvořující funkce více proměnných a jejich užití pro studium
vlastností náhodných kombinatorických objektů.
Poslední úprava: IUUK (16.05.2012)
Formal power series. Lagrange inversion formula. Ordinary and exponential
generating functions, and the combinatorial interpretation of their basic
operations. Overview of basic theory of complex analytic functions. Rational
and meromorphic functions, the residue theorem. Applications of complex
analysis to the enumeration of combinatorial objects. Multivariate generating
functions, and their application to the study of random combinatorial objects.
