Analytická kombinatorika - NDMI087

• Anglický název: Analytic combinatorics
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina, čeština
• Způsob výuky: prezenční
• Garant: doc. RNDr. Vít Jelínek, Ph.D.
• Vyučující: doc. RNDr. Vít Jelínek, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

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: Töpfer Pavel, doc. RNDr., CSc. (02.05.2019)

angličtina

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.

Poslední úprava: IUUK (16.05.2012)

Podmínky zakončení předmětu

čeština

Ústní zkouška s možností písemné přípravy.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)

angličtina

Oral exam with time for written prepapration.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (10.06.2019)

Literatura

čeština

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)

Požadavky ke zkoušce

čeština

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: Jelínek Vít, doc. RNDr., Ph.D. (25.02.2019)

angličtina

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.

Poslední úprava: Jelínek Vít, doc. RNDr., Ph.D. (25.02.2019)

Sylabus

čeština

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)

angličtina

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.

Poslední úprava: IUUK (16.05.2012)