FI:MA026 Advanced Combinatorics - Informace o předmětu
MA026 Advanced Combinatorics
Fakulta informatikyjaro 2024
- Rozsah
- 2/1/0. 3 kr. (plus ukončení). Ukončení: zk.
- Vyučující
- Igor Balla, PhD (přednášející)
prof. RNDr. Petr Hliněný, Ph.D. (přednášející) - Garance
- prof. RNDr. Petr Hliněný, Ph.D.
Katedra teorie programování – Fakulta informatiky
Dodavatelské pracoviště: Katedra teorie programování – Fakulta informatiky - Rozvrh
- St 8:00–9:50 B411
- Rozvrh seminárních/paralelních skupin:
- Předpoklady
- MA010 Graph Theory
The subject *strictly requires* solid theoretical background in combinatorics, at least on the level of MA010 or equivalent courses. - Omezení zápisu do předmětu
- Předmět je nabízen i studentům mimo mateřské obory.
Předmět si smí zapsat nejvýše 25 stud.
Momentální stav registrace a zápisu: zapsáno: 10/25, pouze zareg.: 0/25, pouze zareg. s předností (mateřské obory): 0/25 - Mateřské obory/plány
- předmět má 37 mateřských oborů, zobrazit
- Cíle předmětu
- The goal is to introduce students into selected advanced areas of combinatorics, also refering to combinatorial algorithms and computational complexity of the studied problems.
- Výstupy z učení
- After finishing the course, the students will understand selected advanced principles of combinatorics and graph theory; will be able to conduct research work in areas of combinatorics.
- Osnova
- Advanced structural graph theory: graph minors and well-quasi-ordering, width parameters, matching in general graphs, list coloring, intersection graphs
- Topological graph theory: planarity testing and SPQR trees, MAXCUT algorithm in planar graphs, graphs on surfaces of higher genus, crossing numbers
- Probabilistic method: review of tools - linearity of expectation and concentration bounds, lower bounds on Ramsey number, crossing number, and list chromatic number, Lovász Local Lemma
- Regularity method: regularity decompositions, removal lemma, property testing algorithms
- Extremal Combinatorics: Hales-Jewett Theorem, Van der Waerden Theorem, Gallai-Witt Theorem
- Literatura
- doporučená literatura
- DIESTEL, Reinhard. Graph theory. 4th ed. Heidelberg: Springer, 2010, xviii, 436. ISBN 9783642142789. info
- Výukové metody
- Weekly lectures, bi-weekly tutorials, individual homework projects
- Metody hodnocení
- individual homework project 30%, oral exam 70%
- Vyučovací jazyk
- Angličtina
- Informace učitele
- This subject will be taught at least once in two years.
- Další komentáře
- Studijní materiály
Předmět je vyučován každoročně.
- Statistika zápisu (jaro 2024, nejnovější)
- Permalink: https://is.muni.cz/predmet/fi/jaro2024/MA026