Vyhledávání



Kalendář akcí

Dnes < 2014 >  < srpen > 
Po Út St Čt So Ne
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

Akademický bulletin

abicko

Videa ze světa vědy

videoprezentace-blok-bgd.jpg

projekt BIOCEV

biocev-logo-color-horizontal.jpg

Více o projektu

 

projekt ALISI

ALISI

Český matematik získal prestižní evropský grant

Za výsledky dosažené v oblasti výpočetní složitosti byl oceněn Evropskou radou pro výzkum (ERC) prof. RNDr. Pavel Pudlák, DrSc., z Matematického ústavu AV ČR. Jako jediný z českých zástupců letos získal finanční podporu v rámci prestižní soutěže „ERC Advanced Grants“, vypsané pro zkušené výzkumné pracovníky. Uspěl s projektem „Feasibility, logic and randomness in computational complexity“ (Dosažitelnost, logika a náhodnost ve výpočetní složitosti) a po Eduardu Feireislovi (2012), Josefu Michlovi (2008), Detlefu Schröderovi (2008) a Tomáši Jungwirthovi (2011) je pátým držitelem pokročilého grantu v ČR.

Evropská rada pro výzkum z celkového počtu 2 400 přihlášených podpořila 284 projektů částkou 660 mil. eur. Grant přidělený prof. Pudlákovi je pětiletý a činí 1 259 596 eur (cca 32 milionů korun). Prof. Pavel Pudlák je tak v krátké době druhým českým matematikem oceněným prestižním grantem.
 
Výzkumná práce prof. Pavla Pudláka
Výpočetní složitost je disciplína, která má krátkou historii a teprve v poslední době začíná být uznávaná jako důležitý obor nejen v informatice, ale i v matematice. K tomu jistě přispěl fakt, že základní otázky v této oblasti (jako je např. známý problém „Pversus NP“) jsou matematické úlohy, které odolávají všem pokusům o vyřešení už několik desetiletí. Skupina vedená prof. Pudlákem se je snaží řešit pomocí metod matematické logiky. Jak se prof. Pudlák domnívá, je docela možné, že důvody proč neumíme na tyto otázky odpovědět, jsou fundamentálního charakteru, a proto je potřeba studovat logické aspekty těchto problémů. Z tohoto důvodu se spolu se svými spolupracovníky zaměřil na oblast na pomezí matematické logiky a teorie složitosti, která se nazývá důkazová složitost. Zatímco výpočetní složitost se zabývá otázkami, jak je obtížné něco vypočítat, důkazová složitost si klade otázky, jak je obtížné něco dokázat. Metody důkazové složitosti umožňují dokázat jak teoretické výsledky (např. obtížnost některých matematických problémů), tak i více praktické – například, že určitou výpočetní úlohu nelze řešit jistým typem algoritmů. Pražská skupina spolu se skupinou prof. Stephena Cooka v Torontu jsou dvě hlavní světová centra, která se touto tematikou zabývají.
 
Prof. Pavel Pudlák o „P versus NP“
Náš výzkum je motivován jedním důležitým problémem, který se nazývá problém „P versus NP“. Pro laiky se dá tento problém vysvětlit jako otázka, zda existuje jistý „zázračný algoritmus“. Pomocí tohoto algoritmu by se daly řešit mnohé praktické úlohy, pro které nemáme dostatečně dobré algoritmy. Například by se daly maximálně optimalizovat výrobní procesy, jízdní řády, investice a další úlohy. Algoritmus by byl samozřejmě velmi užitečný i pro řešení konkrétních úloh v matematice a fyzice. Na druhou stranu by takový algoritmus měl i velmi negativní důsledky: nebylo by možné bezpečně používat kódovaní tajných informací. Ten, kdo by tento zázračný algoritmus našel jako první, by ho mohl zneužít na to, aby se dostal do jakýchkoliv počítačů připojených na internet a přečetl si tajná
data.
 
Toto je pochopitelně poněkud zjednodušený popis matematického problému, ale za jistých okolností (pokud by konstanty skryté ve formulaci problému byly malé) by popsaná situace mohla nastat. Pro zajímavost se ještě zmiňme, že „P versus NP“ je jeden ze sedmi matematických problémů, na jejichž vyřešení Clayův institut vypsal odměnu 1 milion amerických dolarů.
 
Většina vědců, která se zabývá touto oblastí teoretické informatiky, se domnívá, že P se nerovná NP, a tedy že zázračný algoritmus neexistuje. Dosud ale nebyly vyvinuty metody, které by umožňovaly něco takového dokázat. Naše skupina se zaměřila na přístup založený na matematické logice. Snažíme se hledat souvislosti mezi problémy jak něco dostatečně rychle vypočítat a problémy jak něco dokázat krátkým důkazem. Jinými slovy, hledáme souvislosti mezi výpočetní složitostí a důkazovou složitostí. Ukazuje se, že tyto dva typy složitosti jsou jenom dva různé pohledy na obecný fenomén složitosti.
 
Kontakt:
Prof. RNDr. Pavel Pudlák, DrSc., Matematický ústav AV ČR, tel.: +420 222 090 721, e-mail: pudlak@math.cas.cz
 
 
Připravil: Odbor mediální komunikace Kanceláře AV ČR

 

1.10.2013