2014
2015
2016
2017

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

Michal Koucký

Dolní odhady a fyzikální realita

Algoritmy určují meze (přesněji horní odhady) na množství výpočetních prostředků jako je čas a prostor, které je k vyřešení různých algoritmických problémů dostačující. Dolní odhady na druhou stranu určují meze na množství prostředků, které je k vyřešení takových problémů nutné.

28. ledna 2016

16:00

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

Anotace přednášky

Algoritmy určují meze (přesněji horní odhady) na množství výpočetních prostředků jako je čas a prostor, které je k vyřešení různých algoritmických problémů dostačující. Dolní odhady na druhou stranu určují meze na množství prostředků, které je k vyřešení takových problémů nutné. Společně nám tak dovolují určit, jaký algoritmus může být optimální pro daný problém.

V této přednášce podám přehled o dosavadním pokroku na poli dokazování dolních odhadů, a ukážu, jak dolní odhady souvisí se základními otázkami kladenými ve fyzice. Na příkladu katalytických výpočtů pak demonstruji překážky, které nám brání v dokázání silných dolních odhadů. Katalytické výpočty představují nový způsob využití zaplněné paměti pro provedení užitečných výpočtů.

Přednášející

doc. Mgr. Michal Koucký, Ph.D.

Michal Koucký se zabývá teoretickou informatikou, zejména výpočetní složitostí, datovými strukturami a kombinatorikou. Mezi jeho známé práce patří studium náhodných procházek, včetně zavedení nového druhu procházek, tzv. exploration sequences, a různé dolní odhady. Je řešitelem ERC Consolidator grantu na téma Lower bounds for combinatorial algorithms and dynamic problems. Titul Ph.D. získal na Rutgers University ve Spojených státech. Poté pracoval v Matematickém ústavu AV ČR a na univerzitách v Austinu, Montrealu, Amsterdamu, Torontu a Aarhusu. Od roku 2013 pracuje v Informatickém ústavu Univerzity Karlovy.

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