PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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.
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 -
Poslední úprava: doc. RNDr. Martin Balko, Ph.D. (11.09.2023)
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ý.
Podmínky zakončení předmětu
Poslední úprava: 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.

Literatura
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

Sylabus -
Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (07.09.2023)
  • kernelizace
  • omezené vyhledávací stromy
  • iterativní komprese
  • stromová šířka
  • W-hierarchie
  • hypotéza ETH (exponential-time hypothesis)
  • parametrizovaná aproximace

 
Univerzita Karlova | Informační systém UK