Na hranici těžkých problémů

Na hranici těžkých problémů

Matematika / rozhovor

Letos za svou práci získal jednu z výročních cen Nadačního fondu Bernarda Bolzana. V oceněném článku zkoumá dr. Alexandr Kazda využitelnost programovacího jazyka Datalog pro řešení určitého typu matematických otázek. „Rád balancuji na hranici oborů, u toho ještě nějakou dobu zůstanu,“ říká o svých plánech mladý matematik.

Proč se věnujete zrovna parametrům jazyka Datalog?

Zajímám se o to, jak těžké je řešit na počítači různé varianty problému splnitelnosti omezujících podmínek (constraint satisfaction problem, CSP). V tomto problému máme zadané nějaké proměnné a podmínky a cílem je najít hodnoty pro proměnné tak, aby podmínky byly splněny. Datalog umožňuje popsat způsob řešení CSP, kdy se snažím dívat na malé části problému a vyřazovat nevyhovující kombinace hodnot. Můj článek se věnoval fragmentu, podmnožině, tohoto jazyka známému jako symetrický Datalog.

K jakým účelům se tento jazyk využívá především?

Hlavní výhodou, ale současně i nevýhodou Datalogu je, že je omezený. Nejde v něm naprogramovat třeba Turingův stroj. Díky tomu se datalogový program chová „slušněji“ než obecný počítačový program. U nás používáme Datalog a jeho podmnožiny k popisu dobře řešitelných problémů, ale lze se s ním setkat i na skutečných počítačích v databázích. Sám Datalog je podmnožinou známějšího jazyka Prolog.

Laika udiví, že u programovacího jazyka nejsou předem známé jeho vlastnosti. Jak je to možné? Jde o častý případ?

Řekl bych, že je to časté. Umíme popsat, jak vypadá syntakticky správný datalogový program, ale to není totéž jako pochopit, co všechno Datalog dokáže nebo nedokáže. S češtinou je to ostatně podobné: také plus minus víme, jak vypadá česká věta, ale to neznamená, že umíme vytyčit hranice toho, co všechno se s naší mateřštinou dá podniknout.

Čím vaše práce může přispět do budoucna?

Je to teoretický výsledek, který nám říká, kde leží hranice těžkých problémů. Pro praktické výpočty to zatím příliš užitečné nebude, ale umožňuje nám to lépe pochopit, které problémy typu CSP jsou snadné a které ne.

Spíše to chápu tak, že primární jsou pro vás matematické principy, kterými testujete konkrétní problém. Zajímáte se jen o informatické záležitosti, nebo je tato práce spíše aplikací širšího zájmu na specifický problém?

Táhne mě to k problémům na rozhraní matematiky, konkrétně univerzální algebry a teoretické informatiky.

Co vás přivedlo k matematice a informatice? Čím jsou pro vás tyto disciplíny zajímavé?

Už jako malý jsem chtěl pochopit, jak věci fungují. Největší radost jsem měl, když se podařilo složité chování vysvětlit jednoduchými principy. Táhlo mě to k fyzice a matematice, ale mám rád i počítače. Nakonec vyhrála matematika. Na matematice mám rád, že popisuje svět, kde do sebe různé pravdy krásně zapadají. Na informatice pak to, že různé abstraktní algoritmy souvisejí s technikou, kterou skutečně používají miliony lidí.

Jakým směrem se dál chcete ubírat?

Baví mě se pohybovat na hranici mezi matematikou a informatikou, takže tam ještě nějakou dobu zůstanu. Existuje hodně různých úloh, o kterých nevíme, do jaké složitostní třídy patří. Rád bych pár z nich „ulovil“ a popsal.

Nadační fond Bernarda Bolzana funguje od roku 1999 při Matematicko-fyzikální fakultě UK. K  jeho úkolům patří mimo jiné nevýdělečná podpora vědecké a  pedagogické činnosti na Univerzitě Karlově v oborech fyziky, matematiky a  informatiky, rozšiřování úrovně experimentálních možností a  teoretických postupů nebo zprostředkování širšího mezinárodního uplatnění vědeckých výsledků dosažených v daných oborech na UK.


Mohlo by vás zajímat:

Stále mě okouzluje všestrannost matematiky
NF Bernarda Bolzana ocenil trojici mladých vědců

Další články k tématu

Tento článek jsme automaticky naimportovali z předchozího redakčního systému. Pokud se v něm něco pokazilo, dejte nám prosím vědět.