NDMI018 Aproximační a online algoritmy

Skripta a záznamy

• Aktuální ročník

• Záznamy z COVIDu

• Poznámky kouril.dev

• Fotky studentských poznámek

Otázky od zkoušky

Je třeba vědět co napsat a pak umět o problému přemýšlet, protože vždycky se ptá. Nejde o kompletní výčet, spíše pro představu, jak moc do hloubky se jde. V "nebo" případech se může lehce zeptat i na druhou podčást.

• Steiner tree

• PTAS - Scheduling nebo Bin packing

• Randomizované stránování, $2H_n$-kompetitivní algoritmus

• Konstrukce tree metriky

• Lower bound pro k-server - k-kompetitivnost

• PCP theorem, jak z něj plyne neexistence PTAS pro MAX-SAT

• k-server: lower bound pro obecnou metriku nebo upper bound pro tree metriku