| Identifikační kód |
GA14-03501S |
| Důvěrnost údajů |
S - Není předmětem státního či obchodního tajemství a data lze v souladu s právními předpisy poskytnout do veřejně přístupných
informačních systémů včetně mezinárodních |
| Název projektu v původním jazyce |
Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky |
| Název projektu anglicky |
Parameterized algorithms and kernelization in the context of discrete mathematics and logic |
| Poskytovatel |
GA0 - Grantová agentura České republiky (GA ČR) |
| Program |
GA - Standardní projekty (1993 - 2050) |
| Kategorie VaV |
ZV - Základní výzkum |
| Hlavní obor - skupina |
I - Informatika |
| Hlavní obor |
IN - Informatika |
| Vedlejší obor |
- |
| Další vedlejší obor |
- |
| Zahájení řešení |
01.01.2014 |
| Ukončení řešení |
31.12.2016 |
| Datum posledního uvolnění účelové podpory |
05.04.2016 |
| Číslo smlouvy |
14-03501S |
| Poslední stav řešení |
U - Ukončený (rok ukončení projektu < rok sběru dat, v roce sběru dat již není financován ze SR) |
| Finance projektu | 2014 | 2015 | 2016 | celkem |
|---|
| Výše podpory z národních zdrojů | 1 487 000,001487 | 1 487 000,001487 | 1 484 000,001484 | 4 458 000,004458 | | Výše podpory z veřej. zahraničních zdrojů *** | 0,000 | 0,000 | 0,000 | 0,000 | | Celkové uznané náklady | 1 487 000,001487 | 1 487 000,001487 | 1 484 000,001484 | 4 458 000,004458 | | Typ | čerpané | čerpané | čerpané | |
** Finance v tisících Kč jsou automaticky zaokrouhleny z částky v jednotkách Kč s přesností na 2 desetinná místa
*** Výše podpory z veřejných zahraničních zdrojů je sledována od období sběru 2020 |
|
Zobrazit skutečně čerpané finance projektu z národních zdrojů »
| Skutečně čerpané finance projektu z národních zdrojů | 2014 | 2015 | 2016 | celkem |
|---|
| Finance | 1 487 000,001487 | 1 487 000,001487 | 1 484 000,001484 | 4 458 000,004458 |
|
| Druh soutěže |
VS - Veřejná soutěž |
| Veřejná soutěž ve výzkumu, vývoji a inovacích |
SGA0201400001 - Veřejná soutěž (GA0/GA) |
| Cíle řešení v původním jazyce |
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). |
| Cíle řešení v anglickém jazyce |
A possible approach to overcome the notorious intractability of NP-hard problems is provided by the theory of Parameterized Complexity: an auxiliary "parameter" - an arbitrary number k - is assigned to each input, such that a computable function of k upper-bounds the computational complexity of the problem. The general goal here is to choose a parameter k which attains low values on interesting inputs, thus leading to efficient algorithms on inputs characterized by such k. The project will search for suitable structural and geometric parameters for classes of combinatorial objects (graphs) and use the new findings to obtain more efficient parameterized algorithms, as well as, so-called algorithmic metatheorems based on logic description. In particular, it will continue the recent very successful research of parameterized complexity lower bounds. Metatheorems for kernelization (parameterized preprocessing) of problems, and search for usable geometric parameters (e.g., coming from an input representation of the graph) are specifically mentioned among the new research tasks. |
| Klíčová slova v anglickém jazyce |
parameterized complexity;kernelization;algorithmic metatheorems;complexity lower bounds;MSO logic;graphs |
| Kontrolní číslo stavu projektu v letech |
2014: 183549414
2015: 187105071
2016: 190554708 ( v1.0 )
2017: 190675410 ( v1.0 ) |
| Datum dodání posledního záznamu o projektu |
28.06.2017 |
| Systémové označení dodávky dat |
CEP17-GA0-GA-U/03:1 |