Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Grafy a kombinatorika

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-GAK Z,ZK 5 2P+2C česky
Garant předmětu:
Tomáš Valla
Přednášející:
Tomáš Valla
Cvičící:
Michal Opler, Tomáš Valla
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Předmět si klade za cíl seznámit studenta s nejdůležitějšími partiemi teorie grafů, kombinatorických principů a struktur, diskrétních modelů a algoritmů. Kromě pochopení teoretických principů bude kladen důraz i na aplikaci poznatků při řešení úloh a navrhování algoritmů. Mezi probraná témata patříí technika generujících funkců, vybrané partie z barevnosti grafů a hypergrafů, Ramseyovské věty, úvod do pravděpodobnostních technik a studium vlastností různých speciálních tříd grafů a kombinatorických struktur. Studenti budou seznámeni s příklady aplikací grafů, např. v kombinatorice na slovech, teorii jazyků a bioinformatice.

Požadavky:

Předpokládají se znalosti srovnatelné s obsahem předmětů Algoritmy a grafy I. a II. (BI-AG1 a BI-AG2).

Osnova přednášek:

Seznam témat přednášek

1. Generující funkce.

2. Barevnost grafů a perfektní grafy

3. Úvod do Ramseyovy teorie.

4. Párování v obecných grafech

5. Lineární algebra v kombinatorice: věta o počtu koster.

6. Úvod do pravděpodobnostní metody.

7. Extremální kombinatorika

8. Kuratowského věta a další otázky rovinnosti grafů.

9. Barvení grafů na obecných plochách

10. Listové barvení a vybíravost

11. Hranová barevnost

12. Teorie nestranných kombinatorických her.

Osnova cvičení:

1. Opakování pojmů z teorie grafů a kombinatoriky

2. Generující funkce.

3. Barevnost kombinatorických struktur.

4. Lineární algebra v kombinatorice: věta o počtu koster.

5. Úvod do Ramseyovy teorie.

6. Jazyky a grafy; Rauzyho graf.

7. Úvod do pravděpodobnostní metody.

8. Lovaszovo lokalní lemma a aplikace.

9. Extremalní teorie grafů.

10. Kuratowského věta a další otázky rovinnosti grafů.

11. Tutteova věta a Edmondsův algoritmus.

12. Perfektní grafy a chordalní grafy.

13. Teorie nestranných kombinatorických her.

14. Grafové algoritmy v kombinatorice na slovech a bioinformatice.

Cíle studia:
Studijní materiály:

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

2. Valla, T. - Matoušek, J. : Kombinatorika a grafy. ITI Series, 2005.

3. Bollobas, B. : Modern Graph Theory. Springer, 1998. ISBN 0-387-98488-7.

4. Graham, R. L. - Knuth, D. - Patashnik, O. : Concrete Mathematics. Addison-Wesley, 1994. ISBN 978-0-201-55802-9.

Poznámka:

Chybí metody akriteria hodnocení (CZ i EN), anglické překlady osnovy přednášek, osnovy cvičení, vstupních požadavků.Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-GAK/

Další informace:
https://courses.fit.cvut.cz/MI-GAK/
Rozvrh na zimní semestr 2023/2024:
Rozvrh není připraven
Rozvrh na letní semestr 2023/2024:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
místnost TH:A-942
Valla T.
11:00–12:30
(přednášková par. 1)
Thákurova 7 (budova FSv)
místnost TH:A-942
Opler M.
Valla T.

12:45–14:15
(přednášková par. 1
paralelka 101)

Thákurova 7 (budova FSv)
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 27. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6120006.html