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 do 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.
• Vyučující: 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

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).

Poslední úprava: T_KAM (15.05.2003)

angličtina

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

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

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

čeština

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

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

angličtina

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

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

Literatura

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ě.

Poslední úprava: FIALA (15.03.2006)

Metody výuky

čeština

Klasická frontální výuka.

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

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

angličtina

Classic frontal teaching.

English preferred in even years, Czech in odd.

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

Sylabus

čeština

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ů.

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

angličtina

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.

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