Grafy a kombinatorika
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
NI-GAK | Z,ZK | 5 | 2P+2C | česky |
- Přednášející:
- Tomáš Valla
- Cvičící:
- Ondřej Suchý
- 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:
-
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 2020/2021:
- Rozvrh není připraven
- Rozvrh na letní semestr 2020/2021:
-
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 Čt Pá - Předmět je součástí následujících studijních plánů:
-
- Počítačová bezpečnost, verze 2020 (VO)
- Návrh a programování vestavných systémů, verze 2020 (VO)
- Počítačové systémy a sítě, verze 2020 (VO)
- Manažerská informatika, verze 2020 (VO)
- Softwarové inženýrství, verze 2020 (VO)
- Systémové programování, verze 2020 (VO)
- Webové inženýrství, verze 2020 (VO)
- Znalostní inženýrství, verze 2020 (VO)
- Specializace Teoretická informatika, verze 2020 (PS)
- Magisterský program Informatika, plán pro studenty bez specializace, verze 2020 (VO)