2014
2015
2016
2017

První setkání Pražského informatického semináře

Pavel Pudlák

Complexity and Infinity

Vůdčím principem při axiomatizaci teorie množin bylo zachovat co nejvíce vlastností konečných množin také pro nekonečné množiny. Dnes, kdy nám chybí metody k řešení problémů v teorii složitosti, děláme v jistém smyslu ...

23. ledna 2014

16:00

Posluchárna K9, FEL ČVUT
Karlovo nám. 13, Praha 2
Zobrazit na mapě

Anotace přednášky

Vůdčím principem při axiomatizaci teorie množin bylo zachovat co nejvíce vlastností konečných množin také pro nekonečné množiny. Dnes, kdy nám chybí metody k řešení problémů v teorii složitosti, děláme v jistém smyslu opak: vytváříme domněnky o konečných strukturách na základě podobných nekonečných struktur. Například naše víra, že P ≠ NP se hlavně opírá o skutečnost, že rekurzivně spočetné množiny nejsou rekurzivní.

Ukážu několik příkladů takových domněnek v teorii složitosti a zmíním se o výsledcích, jež je možné chápat jako evidenci podporující platnost oněch domněnek. Tyto příklady pocházejí z důkazové složitosti – oblasti, která studuje složitost z hlediska logiky – ale mohou být formulovány v čistě výpočetních termínech. Jedna z těchto domněnek je, že neexistuje úplný problém pro jistou třídu vyhledávacích problémů.

Přednášející

Prof. RNDr. Pavel Pudlák, DrSc.

Prof. RNDr. Pavel Pudlák, DrSc., patří ke špičkovým vědeckým osobnostem v oblasti matematické logiky a teoretické informatiky. Jeho výzkum je motivovaný fundamentálními otázkami jako je tzv. P=NP problém. Věnuje se zejména důkazové složitosti a souvisejícím oblastem výpočetní složitosti, kombinatoriky a algebry. Pracuje v Matematickém ústavu Akademie věd ČR, kde dlouhodobě organizuje semináře z logiky a složitosti, z jejichž okruhu vzešla řada dalších matematiků a informatiků. Působil i na řadě zahraničních univerzit a ústavů, včetně Institute for Advanced Study v Princetonu. Je zván na řadu přednášek na významných univerzitách a konferencích, včetně prestižního International Congress of Mathematicians.

Jako prvnímu z české informatické komunity mu byl udělen Advanced Grant ERC, který začíná 1. 1. 2014 a bude věnován teoretickým aspektům výpočtové složitosti.

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI

Seminář se schází vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.

Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT)

Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Podporovatelé

Kontakt