FI:MA026 Advanced Combinatorics - Informace o předmětu

MA026 Advanced Combinatorics

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:

MA026/01: každé sudé pondělí 10:00–11:50 B204, P. Hliněný

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

• Analýza a zpracování obrazu (program FI, N-VIZ)
• Bioinformatika a systémová biologie (program FI, N-UIZD)
• Computer Games Development (program FI, N-VIZ_A)
• Computer Graphics and Visualisation (program FI, N-VIZ_A)
• Computer Networks and Communications (program FI, N-PSKB_A)
• Computing Technology and Methodology (program FI, D-INF_A)
• Cybersecurity Management (program FI, N-RSSS_A)
• Digitální lingvistika (program FI, N-DL)
• Diskrétní algoritmy a modely (program FI, N-TEI)
• Formální analýza počítačových systémů (program FI, N-TEI)
• Fundamentals of Computer Science (program FI, D-INF_A)
• Fundamenty informatiky (program FI, D-INF)
• Grafický design (program FI, N-VIZ)
• Graphic Design (program FI, N-VIZ_A)
• Hardware Systems (program FI, N-PSKB_A)
• Hardwarové systémy (program FI, N-PSKB)
• Image Processing and Analysis (program FI, N-VIZ_A)
• Informační bezpečnost (program FI, N-PSKB)
• Informatika (angl.) (program FI, D-IN4)
• Informatika (program FI, D-IN4)
• Information Security (program FI, N-PSKB_A)
• Kvantové a jiné neklasické výpočetní modely (program FI, N-TEI)
• Počítačová grafika a vizualizace (program FI, N-VIZ)
• Počítačové sítě a komunikace (program FI, N-PSKB)
• Počítačové systémy a technologie (angl.) (program FI, D-IN4)
• Počítačové systémy a technologie (program FI, D-IN4)
• Řízení kyberbezpečnosti (program FI, N-RSSS)
• Řízení vývoje služeb (program FI, N-RSSS)
• Řízení vývoje softwarových systémů (program FI, N-RSSS)
• Services Development Management (program FI, N-RSSS_A)
• Software Systems Development Management (program FI, N-RSSS_A)
• Software Systems (program FI, N-PSKB_A)
• Softwarové systémy (program FI, N-PSKB)
• Technologie a metodologie počítačových systémů (program FI, D-INF)
• Vývoj počítačových her (program FI, N-VIZ)
• Zpracování a analýza rozsáhlých dat (program FI, N-UIZD)
• Zpracování přirozeného jazyka (program FI, N-UIZD)

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

neurčeno
• ALON, Noga a Joel H. SPENCER. The probabilistic method. 3rd ed. Hoboken, N.J.: Wiley, 2008, xv, 352. ISBN 9780470170205. info
• MOHAR, Bojan a Carsten THOMASSEN. Graphs on surfaces. Baltimore: The Johns Hopkins University Press, 2001, xi, 291. ISBN 0801866898. 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