SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
Introduction to Parameterized Algorithms - NTIN103
Title: Introduction to Parameterized Algorithms
Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
Faculty: Faculty of Mathematics and Physics
Actual: from 2023
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: Mgr. Martin Koutecký, Ph.D.
doc. RNDr. Jiří Fiala, Ph.D.
Class: DS, teoretická informatika
DS, diskrétní modely a algoritmy
Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Discrete Mathematics, Optimalization, Theoretical Computer Science
Is incompatible with: NTIX103
Is interchangeable with: NTIX103
Annotation -
Last update: 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.
Course completion requirements - Czech
Last update: doc. RNDr. Jiří Fiala, Ph.D. (07.09.2023)

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

Zápočet je podmínkou pro konání zkoušky.

Literature - Czech
Last update: 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

Syllabus -
Last update: doc. Andreas Emil Feldmann, Dr. (24.09.2020)
  • kernelization
  • bounded search trees
  • iterative compression
  • treewidth
  • the W-hierarchy
  • the exponential-time hypothesis
  • parameterized approximation

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html