Na programu bude přednáška Michala Kouckého: 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é. 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ů.
Bližší informace najdete na webové stránce PIS.
Žádné komentáře:
Okomentovat