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é.
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ů.
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.
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ě.
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.
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)
© 2013-2022, Prague Computer Science Seminar 
Toto dílo podléhá licenciCreative Commons Attribution 4.0 International License.
