Introduction to Parameterized Algorithms - NTIN103

• Anglický název: Introduction to Parameterized Algorithms
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020 do 2022
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• Virtuální mobilita / počet míst: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Další informace: https://sites.google.com/site/aefeldmann/teaching
• Garant: doc. Andreas Emil Feldmann, Dr.
• Třída: DS, teoretická informatika; DS, diskrétní modely a algoritmy; Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika, Optimalizace, Teoretická informatika
• Je neslučitelnost pro: NTIX103
• Je záměnnost pro: NTIX103

Anotace

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.04.2019)

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically sma

angličtina

Poslední úprava: T_KAM (18.04.2017)

Parameterized algorithmics analyzes the runtime in finer detail than classical complexity theory: instead of expressing the runtime as a function of the input size only, the dependence on a parameter of the input is taken into account. The aim is to isolate any fast growth of the runtime to a parameter, while the remaining growth of the time is kept low. Apart from giving a deeper theoretical understanding of the complexity of a problem, this can also lead to efficient (practical) algorithms if the parameter describes a property of the inputs, for which the parameter is typically small.

Literatura

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2019)

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6

angličtina

Poslední úprava: T_KAM (18.04.2017)

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, ISBN 978-3-319-21274-6

Sylabus

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (29.04.2019)

• kernelization

• bounded search trees

• iterative compression

• treewidth

• the W-hierarchy

• the exponential-time hypothesis

• kernelization lower bounds

• parameterized approximation

angličtina

Poslední úprava: doc. Andreas Emil Feldmann, Dr. (24.09.2020)

• kernelization

• bounded search trees

• iterative compression

• treewidth

• the W-hierarchy

• the exponential-time hypothesis

• parameterized approximation