Přejít k obsahu | Přejít k hlavnímu menu | Přejít k vyhledávání

Informace o projektu
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky

Informace

Projekt nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka projektu je na webu muni.cz.
Logo poskytovatele
Kód projektu
GA14-03501S
Období řešení
1/2014 - 12/2016
Investor / Programový rámec / typ projektu
Grantová agentura ČR
  • Standardní projekty
Fakulta / Pracoviště MU
Fakulta informatiky

Jeden z možných přístupů ke zdolání zdánlivě nepřekonatelné překážky NP-těžkosti algoritmických problémů nám podává teorie
parametrizované složitosti: Vstup těžkého problému je opatřen doplňkovým parametrem - libovolným číslem k, jehož jakákoliv počitatelná
funkce omezuje výpočetní složitost našeho problému. Snahou je volit parametr k tak, aby jeho hodnota byla na zajímavých vstupech nízká,
což následně umožňuje efektivní řešení problémů na takto charakterizovaných vstupech. V projektu budou hledány a studovány vhodné
strukturální a geometrické parametry pro třídy kombinatorických objektů (grafů) a nové poznatky budou využity v návrhu lepších
parametrizovaných algoritmů a obecných logikou popsaných tzv. algoritmických metavět. Mimo jiné bude pokračovat nedávno velmi úspěšné
nalézání dolních mezí parametrizované řešitelnosti problémů. Mezi novými směry výzkumu v navržené oblasti jsou především zmíněny
oblasti metavět pro kernelizaci (efektivní parametrické předzpracování) problémů a využití geometrických parametrů (vycházejících například
z reprezentace vstupního grafu).

Publikace

Počet publikací: 15

2018

2017

2016

2015

Předchozí 1 2 Další

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.