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
• Guarantor: Mgr. Martin Koutecký, Ph.D.; doc. RNDr. Jiří Fiala, Ph.D.
• Teacher(s): doc. RNDr. Jiří Fiala, Ph.D.; Mgr. Martin Koutecký, Ph.D.; Mgr. Tung Anh Vu
• 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

English

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.

Last update: T_KAM (18.04.2017)

Czech

Parametrizovaná výpočetní složitost analyzuje dobu běhu algoritmů podrobněji než klasická teorie složitosti: namísto vyjádření doby běhu pouze jako funkce velikosti vstupu se bere v úvahu závislost na vhodném dalším parametru vstupu. Cílem je, aby případný rychlý (exponenciální) růst doby běhu závisel jen na parametru, zatímco závislost na velikosti vstupu je nízká (polynomiální). Kromě hlubšího teoretického pochopení složitosti problému to může vést i k efektivním a praktickým algoritmům, je-li zvolený parametr pro obvyklé vstupy malý.

Last update: Balko Martin, doc. RNDr., Ph.D. (11.09.2023)

Course completion requirements

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.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (07.09.2023)

Literature

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

Last update: Kynčl Jan, doc. Mgr., Ph.D. (30.04.2019)

Syllabus

English

• kernelization

• bounded search trees

• iterative compression

• treewidth

• the W-hierarchy

• the exponential-time hypothesis

• parameterized approximation

Last update: Feldmann Andreas Emil, doc., Dr. (24.09.2020)

Czech

• kernelizace

• omezené vyhledávací stromy

• iterativní komprese

• stromová šířka

• W-hierarchie

• hypotéza ETH (exponential-time hypothesis)

• parametrizovaná aproximace

Last update: Fiala Jiří, doc. RNDr., Ph.D. (07.09.2023)