Introduction to Parameterized Algorithms - NTIN103

• Anglický název: Introduction to Parameterized Algorithms
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2023
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/2, Z+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: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: Mgr. Martin Koutecký, Ph.D.; doc. RNDr. Jiří Fiala, Ph.D.
• Vyučující: doc. RNDr. Jiří Fiala, Ph.D.; Mgr. Martin Koutecký, Ph.D.; Mgr. Tung Anh Vu
• 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

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

Poslední úprava: Balko Martin, doc. RNDr., Ph.D. (11.09.2023)

angličtina

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.

Poslední úprava: T_KAM (18.04.2017)

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

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.

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

Literatura

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

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

Sylabus

čeština

• kernelizace

• omezené vyhledávací stromy

• iterativní komprese

• stromová šířka

• W-hierarchie

• hypotéza ETH (exponential-time hypothesis)

• parametrizovaná aproximace

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

angličtina

• kernelization

• bounded search trees

• iterative compression

• treewidth

• the W-hierarchy

• the exponential-time hypothesis

• parameterized approximation

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