2014
2015
2016
2017
2018
2019
2020
2022
2023
2024

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 obvykle schází jednou za měsíc ve čtvrtek v 16:15 a to buď v budově FEL ČVUT nebo v budově MFF UK.

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), Jaroslav Hlinka (ÚI AV ČR), Michal Chytil, Pavel Kordík (FIT ČVUT), Michal Koucký (MFF UK), 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

Pražský informatický seminář je z důvodů prevence šíření nákazy novým koronavirem do odvolání pozastaven.