Vybrané kapitoly z výpočetní složitosti I

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

ZS 2018/2019

NTIN085 - 2/1 Z, Zk

Čas konání: Pá 10:40 (první přednáška je 5. 10. 2018)
Místo konání: S4, Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován tzv. zjemnělé složitosti (fine-grained complexity). Zjemnělá složitost je oblast, která vznikla a pozoruhodně se rozvinula během posledních deseti let. Snaží se odpovědět na otázku, proč nejlepší známé algoritmy například pro hledání nejdelší společné podposloupnosti mají kvadratickou časovou složitost a pro jiné problémy mají všechny známé algoritmy zase složitost kubickou. Dává to do souvislosti s exponenciálními algoritmy pro řešení splnitelnosti (SAT).

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z výpočetní složitosti, pravděpodobnosti a diskrétní matematiky. Přednášku je možné si zapsat opakovaně.

Předběžný plán přednášky

Literatura:

Domácí úkoly

TBA