Algoritmy jsou ve světě technologií za vším. Přístrojům, které je mají ve své paměti, dávají návod, jak mají při řešení některých problémů postupovat. A právě jejich studiem se zabývá Petr Hliněný z fakulty informatiky. K tomu, aby člověk pochopil, čemu přesně se věnuje, by asi nejdřív bylo potřeba absolvovat aspoň některý z jeho předmětů zaměřený na základy matematiky pro informatiky. Přesto se o to ale v rozhovoru s tímto mezinárodně uznávaným odborníkem na teorii složitosti algoritmů pokusíme.
V českém prostředí není ještě pořád moc obvyklé, že by akademik ve své kariéře prošel několika různými pracovišti po celém světě...
Což není dobře...
Vy ale jste případ takového světoběžníka. Co vás k tomu vedlo?
Chtěl jsem se rozhlédnout po světě a trochu si pocestovat, než se někde usadím. V průběhu doktorského studia v Praze jsem dostal možnost udělat si doktorát v USA, zároveň jsem ho přitom dálkově dokončil i doma, ale zpátky se mi ještě nechtělo. Hodně jsem chtěl poznat Nový Zéland. Nejdřív se objevila příležitost v Kanadě na Fieldsově institutu v Torontu, ale jak jsem se o Zéland pořád zajímal, dozvěděli se tam o mě a domluvil jsem si práci na Victoria University.
S Masarykovou univerzitou jste v té době neměl nic společného. Co vás nakonec přitáhlo do Brna?
Chtěl jsem se vrátit do České republiky, ale nechtěl jsem do Prahy, to není město k žití pro mě. A pokud jsem chtěl na pracoviště na patřičné teoretické úrovni, už těch možností moc nebylo.
Co vám zahraniční zkušenost profesně dala?
Mám kontakty a přátele z oboru po celém světě. Umožňuje vám to udržet si přehled o trendech a máte s kým konzultovat. Bez toho na špici výzkumu nedosáhnete.
Vaší doménou je matematika. Čím se přesně zabýváte?
Je to asi dost složité na stručné vysvětlení. Věnuji se matematice ve spojení s teoretickou informatikou, což většinou obnáší to, že se zabývám problematikou různých algoritmů a tím, jak s jejich pomocí řešit nějaké podstatné a netriviální věci. Anebo se naopak snažím ukázat, proč některé věci algoritmicky řešit nejde.
Dá se taková práce přiblížit na něčem praktickém?
Většina věcí, které dělám, je velmi teoretického charakteru. Je to základní výzkum, ve kterém nám jde hlavně o posun poznání. S jedním studentem jsme se ale například věnovali problému hledání nejkratších cest v GPS navigacích a podařilo se nám nalézt dosud nezkoumaný směr a dosáhnout vylepšení.
Vylepšení po jaké stránce?
Zmenšili jsme paměťovou náročnost a zvýšili rychlost výpočtu. Všechny pokročilé vyhledávací algoritmy nějakým způsobem předpočítávají některá data, aby bylo vyhledávání rychlejší. Je ale potřeba to dělat úsporně, aby se tato data do zařízení vešla a přitom to uživateli pomohlo. Musíte tedy umět nějak rozumně určit, co se vůbec má předpočítat, aby to dávalo smysl. No a nám se díky trochu neobvyklému úhlu pohledu podařilo najít poměrně přirozený a přitom matematicky dobře definovatelný způsob, který skutečně pomáhá.
Zmiňoval jste, že dokazujete, že něco pomocí algoritmu řešit nejde. Co si přesně pod tím představit?
Existuje celá škála tak složitých problémů, že se sice dají řešit za pomoci algoritmů, ale trvá to strašně dlouho. S pomocí matematiky můžeme dokázat, že to nejspíše lépe nepůjde a že bude potřeba na řešení použít nějaké heuristické přístupy. Že třeba část podstaty problému obětujete, aby bylo možné se dobrat aspoň přibližného výsledku. Teorie tedy pomáhá identifikovat, kde se ještě máme snažit hledat přesné řešení problému a kde to nejspíše nikdy nepůjde.
V oboru jste dvacet let. Změnilo se toho za tu dobu hodně?
Obrovským způsobem. V oblasti složitosti algoritmů je dnes dominantní úplně nová teorie, vzniklá teprve v 90. letech. Je to takzvaná parametrizovaná složitost. Až koncem minulého století o ní vyšla první kniha, před tím v této teorii pracovalo jen pár lidí.
Co se touto teorií změnilo?
Od 70. let minulého století jsme se pohybovali v rámci klasické teorie složitosti. Tehdy se dokázalo, že jsou mnohé problémy, které nejspíše nikdy nedokážeme rozumně vyřešit, protože kdyby se to podařilo byť u jediného z nich, tak by se stejně rozumně dalo vyřešit téměř vše. Pak se ale ukázalo, že praktické instance některých z těchto problémů nejsou tak složité, jak teorie tvrdila, a začalo se zkoumat proč.
Můžete to na něčem ilustrovat?
Modelově se uvádí například měnová arbitráž. Účastníci (banky) si mezi sebou směňují jednotlivé měny a stanovují, v jakém kurzu chtějí co směnit do jakého množství. Otázka je, jestli se dá v tomto systému najít nějaké „kolečko“, na kterém je možné vydělat.
Klasická teorie složitosti říká, že tento problém je příliš těžký a že nemá smysl se ho pokoušet úplně vyřešit. Jenže ono se ukázalo, že ten problém je složitý jen v případě, že předpokládáte existenci velkého množství různých měn. Když budete ale pracovat v reálném prostředí, zjistíte, že těch měn je jen několik a že celý problém je vlastně algoritmicky jednoduchý. Cestou je tedy hledat parametry, které když jsou malé, stává se úloha najednou hezky řešitelnou.
Kromě bádání se hodně věnujete i učení. Vedete velké matematické předměty pro studenty prvních ročníků. Co vás baví víc: věda nebo učení?
Víc mě baví výzkum. Kdyby byli studenti chytřejší, bylo by to možná jinak, ale nechci si stěžovat. Je docela rozumné učit prváky teoretickou informatiku, dokud jsou ještě tvární a dá se jim něco dostat do hlavy.
Proč je pro informatika důležité osvojit si tento základ?
Aby programy, které pak bude psát, měly nějakou logickou formu, ve které se vyzná nejen on sám, ale i někdo další. Ale především proto, aby fungovaly správně a efektivně. Bez poznání matematické teorie, která je za fungováním algoritmů, jsou programy psány špatně nebo neefektivně. Počítají třeba příliš dlouho. Často vidíte u informatiků samouků nebo začátečníků, kolik dělají chyb v těchto oblastech. Bohužel ale málokdo na začátku chápe, že matematické základy potřebuje.
Je to tedy nezbytná součást vzdělání informatika.
Je otázka, kdo je informatik. Tak si dnes říká kde kdo, ale ten, kdo chce skutečně tvořit něco nového, psát třeba nějaký systém na zelené louce a vymýšlet, jak by se měl postavit, se bez formálních matematických poznatků neobejde. Anebo bude ztrácet čas tím, že bude vymýšlet věci, které už jsou dávno vymyšlené.
Máte ve svém bádání nějaký velký cíl? Existuje něco, na co byste chtěl přijít?
Vše se vyvíjí tak rychle, že říci vám nějaký velký cíl před deseti lety, nejspíš by se ukázalo, že to nebylo vůbec důležité a dneska bych se tomu smál, nebo by to už měl někdo dávno vyřešené. Kdybych ale měl vzít jeden problém, který je se mnou svázaný, i když není z globálního pohledu nijak důležitý, byla by to takzvaná Negamiho hypotéza rovinných pokrytí. To je věc, které jsem se začal věnovat už za doktorského studia a zase se k ní vrátil v posledních letech se dvěma studenty. Třebaže jsem tam dosáhl zajímavých výsledků, celý problém už 15 let v podstatě stojí na místě. Rozlousknout ho by bylo moc pěkné.
Co by z toho plynulo?
Prakticky nic. Ale byla by vyřešena nádherná matematická hádanka.
Vypadá to, že vás praktický dopad vašeho bádání příliš nezajímá.
Máte pravdu. Nezajímá. Říkám si, že už je pro jiné, aby vymysleli, co praktického se se získanými výsledky dá udělat. Takto se celá matematika vyvíjela vždycky. Vždy byla napřed před aplikacemi.
Máte dvě malé dcery. Mají také matematické spády?
Nechce se jim do toho. Zdá se jim to moc těžké.
Čím to podle vás je, že se mladí lidé často do matematiky nehrnou?
Nechce se jim přemýšlet. Přemýšlení bolí víc než učení nazpaměť.
Co k tomu přivedlo vás?
Právě ono přemýšlení a vyvozování věcí mě vždycky moc bavilo. Sám jsem se hlásil na různé matematické soutěže a olympiády a vydrželo mi to, i když v rodině nikdo neměl vyloženě tyto spády.
Vypínáte někdy mozek, abyste si odpočinul od práce?
Špičkovou vědou musí člověk žít pořád, to se nedá moc přerušovat. Je to podobné jako ve vrcholovém sportu. Zůstává to ve mně, ať se hnu kamkoliv.
Nepotřebujete se od toho někdy trochu odstřihnout?
Vypnout by bylo špatně. Když máte něčeho velkého dosáhnout, nesmíte to někam odsouvat, musí to být součástí vašeho života.
