PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
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 2019 do 2019
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
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: 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
Anotace -
Poslední úprava: 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
Literatura -
Poslední úprava: 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

Sylabus -
Poslední úprava: 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

 
Univerzita Karlova | Informační systém UK