Akce ČVUT

PIS 18. přednáška - doc. Michal Koucký - Dolní odhady a fyzikální realita

28.01.2016   16:00

ANOTACE:

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. 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ě.
Formát semináře připravil přípravný výbor ve složení 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), 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.

Místo konání

Karlovo nám. 13, budova E, místnost 107 (Zengerova posluchárna)

Pořadatel

Přípravný výbor PIS

Kontaktní osoba

Přípravný výbor PIS, info@praguecomputerscience.cz, 224 35 7667

Podrobnější informace

http://www.praguecomputerscience.cz/

Příloha

Stáhnout