Studenti Matfyzu se s docentem Zdeňkem Dvořákem setkávají na přednáškách předmětu Teorie grafových minorů a při praktiku řešení programátorských úloh. Někteří z nich se brzy budu moci zapojit také do jeho nového výzkumného projektu. Devětatřicetiletý teoretický informatik se v minulých dnech stal příjemcem dvouletého prestižního grantu ERC CZ Consolidator Grant za více než sedm milionů korun.
ERC CZ je program určený na podporu uchazečů o prestižní evropské granty ERC. České projekty, které dosáhly v soutěži ERC výborného hodnocení, ale nebyly z důvodu nedostatku finančních prostředků přijaty, financuje v rámci programu ERC CZ ministerstvo školství. Pro letošní rok takto podpořilo pouze osm projektů. Mezi nimi také výzkum docenta Dvořáka s názvem „Algoritmy a složitost v rámci a nad omezenou expanzí“.
Laik si pod tímto názvem jen těžko něco představí. Můžete mi váš výzkum nějak přiblížit?
Projekt je z oblasti teorie grafů, což je pro laiky trochu matoucí pojmenování. Pojmem graf myslíme to, co si normální č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.
Tento a mnoho dalších problémů ale pro velké sítě bez dalších předpokladů neumíme efektivně řešit a dost možná to ani nejde. Pojem omezené expanze formalizuje jisté omezení složitosti sítě, které nám umožňuje vyvinout efektivnější algoritmy pro tyto otázky.
Silniční síť mi trochu pomáhá problém pochopit, ale pořád tomu úplně nerozumím...
Výzkum se dosud tradičně, od sedmdesátých let minulého století, zaměřoval na striktně omezené třídy grafů, například na rovinné grafy. Ty odpovídají předpokladu, že v silniční síti se na křížení dvou cest vždy dá přejet z jedné na druhou, který samozřejmě není úplně realistický. Novější přístupy proto uvažují robustnější omezení aplikovatelná na obecnější třídy grafů, a koncept omezené expanze je jedním z nejvýznamnějších z nich. 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.
Můžete mi zkusit vysvětlit tento model?
Uznávám, že to není snadné uchopit, a přesnou definicí bych asi nikomu nepomohl. Pro vysvětlení mého projektu stačí představa, že omezená expanze je vlastnost, kterou mají mnohé pro nás zajímavé sítě. Tato vlastnost je poměrně jednoduchá, ale v posledním desetiletí bylo nalezeno mnoho obecných algoritmických postupů aplikovatelných na všechny sítě, které ji splňují. To je velká výhoda, ale svým způsobem i slabina: jestliže je nějaký problém obtížný na libovolné třídě grafů s omezenou expanzí, tento přístup pro něj nemůže uspět ani na žádné jiné třídě.
Co je tedy základní myšlenkou vašeho projektu?
Základní myšlenkou mého projektu je, že tento monolitický pohled není jediný možný, a že i v rámci tříd grafů s omezenou expanzí existují kvalitativní rozdíly. Cílem výzkumu je vybudování detailní teorie této hierarchie v rámci tříd s omezenou expanzí.
Těšíme se na výsledky. Čím se budete zabývat nejdříve?
V současnosti se plánuji zaměřit na důležitý bod ve zmíněné hierarchii, takzvané třídy grafů s polynomiální expanzí. Pro tyto třídy lze například výše zmiňovaný problém s pobočkami efektivně řešit alespoň v přibližné verzi, přestože tomu tak obecně není pro všechny třídy grafů s omezenou expanzí. Chtěl bych ukázat, že grafy s polynomiální expanzí lze reprezentovat geometricky, což by umožnilo pro ně použít nástroje z výpočetní geometrie.
Jaké jsou aplikace vašeho výzkumu?
Projekt je teoretický, nezabýváme se řešením konkrétních problému z praxe. Problémy, které uvažujeme, jsou do velké míry idealizované, a po pravdě řečeno, subjektivní krása či nápaditost dosažených výsledků je pro nás často důležitější než jejich reálná použitelnost. Snažíme se nicméně vyvinout obecné techniky, ze kterých se dá v případných aplikacích vycházet.
Co pro vás osobně udělení grantu znamená? Co to znamená pro studenty?
Díky podpoře grantu mohu do svého výzkumu intenzivněji zapojit postdoktorského výzkumníka a několik studentů. Umožní mi také udržet a případně rozšířit spolupráci s odborníky ze zahraničních pracovišť, například s McGill University v Kanadě a National Institute of Informatics v Japonsku.
doc. Mgr. Zdeněk Dvořák, Ph.D.
Někdejší žák matematika prof. Jaroslava Nešetřila působí od roku 2013 na Informatickém ústavu UK. Dlouhodobě se zabývá strukturální teorií grafů, algoritmy a jejich komplexitou. V minulosti absolvoval postdoktorandské pobyty na Simon Fraser University ve Vancouveru a na Georgia Institute of Technology v Atlantě. Na svém kontě má více než stovku odborných publikací. Za výzkumnou činnost byl v minulosti již několikrát oceněn, ještě během doktorského studia získal Cenu Neuron pro mladé matematiky, v roce 2015 obdržel Evropskou cenu v kombinatorice.
Mohlo by vás také zajímat:
Jak
ochladit molekulu
Kouzlo
hledání přibližné hodnoty
O
statistice a plovoucím tělese