Grafové minory a stromové rozklady - NDMI059

• Anglický název: Graph Minors and Tree Decompositions
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, 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
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. RNDr. Jiří Fiala, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: T_KAM (15.05.2003)

Kurz zaměřený na teorii grafových minorů a zvláště na aplikace souvisejícího pojmu stromového zdvihu pro návrh algoritmů. Vhodné pro studenty mat. a inf. od 3.r. i pro doktorandy (M a I).

angličtina

Poslední úprava: FIALA/MFF.CUNI.CZ (08.10.2008)

Special course for advanced undergraduate and graduate students devoted to graph minor theory in its relationship to treewidth.

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (12.10.2017)

Osvojení látky v rozsahu syllabu a schopnost je aplikovat na úlohy z oboru.

angličtina

Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (07.10.2019)

To learn the subject as described in the syllabus and be able to solve appropriate problems.

Literatura

Poslední úprava: FIALA (15.03.2006)

Diestel, R.: Graph Theory, graduate texts in mathematics, vol. 173., Springer Verlag, May 1997.

Kloks, T. Treewidth: Computations and approximations, no. 842 in Lecture Notes in Computer Science, Springer Verlag, 1994.

Časopisecká literatura podle specifikace přednášejícího. K dipozici budou též poznámky přednášejícího v angličtině.

Metody výuky

čeština

Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (10.10.2022)

Klasická frontální výuka.

V lichých letech preferovaně česky, v sudých anglicky.

angličtina

Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (10.10.2022)

Classic frontal teaching.

English preferred in even years, Czech in odd.

Sylabus

čeština

Poslední úprava: FIALA/MFF.CUNI.CZ (08.04.2010)

Na kurzu bude probrán úvod do teorie grafových minorů a dobrých kvaziuspořádání, m.j. bude dokázána Kruskalova věta o dobrém kvaziuspořádání na třídě konečných stromů. Těžiště kurzu je založeno na pojmu stromového zdvihu a na jeho vztahu k teorii grafových minorů.

angličtina

Poslední úprava: FIALA/MFF.CUNI.CZ (08.04.2010)

The course will be devoted to the introduction to graph minor theory, for example we prove the Kruskal theorem on the existence of well quasiordering on finite trees. The main part of the course will be devoted to the notion of treewidth and on its relationship to graph minor theory.