PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Kombinatorika - NMAG403
Anglický název: Combinatorics
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+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: prof. RNDr. Jan Kratochvíl, CSc.
Vyučující: prof. RNDr. Jan Kratochvíl, CSc.
doc. RNDr. Pavel Valtr, Dr.
Třída: M Mgr. MSTR
M Mgr. MSTR > Povinné
Kategorizace předmětu: Matematika > Algebra
Anotace -
Vytvořující funkce a kombinatorická enumerace. Extremální otázky v grafech a množinových systémech. Ramseyova teorie. Toky v sítích. Strukturálni otázky množinových systémů, transverzály a systémy různých reprezentantů. Pravidelné kombinatorické struktury (bloková schémata, Steinerovy systémy trojic, Latinské čtverce, konečné projektivní roviny). Vnořování grafů na plochy vyšších rodů.
Poslední úprava: T_KA (14.05.2013)
Podmínky zakončení předmětu -

Zápočet se uděluje za získání alespoň 50% bodů za domácí úkoly (zpravidla 4 serie úloh) + alespoň 50% docházky na cvičení, přičemž obojí lze vzájemně částečně nahradit (přesná podmínka je 2x+4y>=3, kde x je podíl docházky na cvičení a y podíl získaných bodů za domácí úkoly). Povaha kontroly studia neumožňuje opakování této kontroly.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (14.10.2023)
Literatura -

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2002

Diestel, R.: Graph Theory, Graduate Texts in Mathematics, Volume 173, Springer Verlag, Fourth Edition 2010

Hall, M. Jr.: Combinatorial Theory, Wiley, New York, 1986

Bollobás, B.: Modern Graph Thoery, Graduate Texts in Mathematics, Springer Verlag, 1998

Poslední úprava: T_KA (14.05.2013)
Požadavky ke zkoušce -

Zkouška je ústní, může mít kontaktní nebo distanční formu. Zkouší se látka podle sylabu v rozsahu předneseném na přednášce. Zkouší se porozumění pojmům a jejich souvislostem, věty včetně důkazů i schopnost aplikovat nabyté znalosti na jednoduché problémy předneseným tématům blízké. Udělení zápočtu je nutnou podmínkou účasti na zkoušce.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (23.09.2020)
Sylabus -

Základní strukturální a algoritmické otázky teorie gafů.

Toky v sítích a míra souvislosti grafu.

Extremální otázky v grafech a množinových systémech, systémy různých reprezentantů, Hallova věta.

Párování v grafech, Tutteova věta, Edmondsův algoritmus.

Rovinné grafy, důkaz Kuratowského věty.

Hamiltonovské kružnice v grafech.

Barevnost a vybíravost grafů, hranová barevnost (Vizingova věta), barevnost grafů vnořitelných na plochy vyšších rodů.

Pravidelné kombinatorické struktury, jejich existence.

Bloková schémata.

Steinerovy systémy trojic.

Symetrická schémata, věta Bruck-Ryser-Chowla.

Hadamardovy matice.

Navzájem ortogonální Latinské čtverce.

Konečné projektivní roviny.

Poslední úprava: Kratochvíl Jan, prof. RNDr., CSc. (02.10.2024)
 
Univerzita Karlova | Informační systém UK