ERC CZ Consolidator Grant na výzkum složitosti

Grantovou soutěž ERC CZ pořádá ministerstvo školství pro české uchazeče o prestižní evropské granty ERC, jejichž projekty byly mezinárodní panelem výborně hodnoceny, avšak v důsledku nedostatku finančních prostředků nebyly podpořeny. Výzkum docenta Zdeňka Dvořáka patří mezi osm projektů, které v páté veřejné soutěži uspěly.

Projekt s názvem „Algoritmy a složitost v rámci a nad omezenou expanzí“ je plánován na dva roky a docent Dvořák na něm společně s tříčlenným týmem začne pracovat letos v červnu.

„Náš výzkum spadá do oblasti teorie grafů, což je pro laiky trochu matoucí pojmenování. Pojmem graf myslíme to, co si běžný člověk představí pod pojmem síť - ať už síť počítačová, síť neuronů v našem mozku, vztahy mezi uživateli na sociálních sítích či silniční síť. Pro tyto sítě nás zajímají různé otázky, zejména algoritmického charakteru. Na příkladu silniční sítě se můžeme ptát, jak efektivně zjistit, kolik poboček a jak umístěných potřebujeme, abychom ke každému z našich zákazníků byli schopni dojet do 30 minut. V případě velkých sítí však na podobné otázky bez dalších předpokladů neumíme odpovědět a možná to ani nejde,“ přibližuje doc. Dvořák výzkumný problém.

V projektu se bude zabývat výzkumem složitosti těchto sítí, resp. grafů s využitím tzv. teorie omezené expanze. „Její základní ideou je omezení složitosti struktury grafů v závislosti na tom, do jaké vzdálenosti od každého z jejich vrcholů ji uvažujeme.“

Mezi jednotlivými třídami grafů s omezenou expanzí existují dle docenta Dvořáka kvalitativní rozdíly. Cílem jeho výzkumu proto bude vytvořit detailní hierarchické teorie v rámci omezené expanze a nalézt obecné algoritmické techniky, které budou použitelné na různých stupních této hierarchie.

„Náš výzkum je čistě teoretický. Problémy, které uvažujeme, jsou do velké míry idealizované. Snažíme se nicméně vyvinout obecné techniky, ze kterých se dá v případných aplikacích vycházet,“ říká doc. Dvořák a dodává, že díky získanému grantu může do svého výzkumu intenzivněji zapojit také studenty či postdoktorandy a rozšířit spolupráci se zahraničními pracovišti jako například s kanadskou McGill University nebo s National Institute of Informatics v Japonsku.

Více o projektu doc. Zdeňka Dvořáka na webu Matfyz.cz.

–OFSKP, OPMK–