Úvod do aproximačních a pravděpodobnostních algoritmů - 2017

Každý neuvedený předmět
Honza__

Úvod do aproximačních a pravděpodobnostních algoritmů - 2017

Příspěvek od Honza__ »

NDMI084 - Úvod do aproximačních a pravděpodobnostních algoritmů
Datum: 17.01.2017
Zkoušející: Kolman, Sgall

Zkouška byla ústní s písemnou přípravou.
Každý dostal 2 otázky na teorii - jednu na pravděpodobnostní, a jednu na aproximační algoritmy.
Mě se ptal na pravděpodobnostní algoritmus pro nalezení minimálního řezu a na aproximační algoritmy pro set cover využívající lineárního programování.
Jelikož si nebyl jistý známkou, dostal jsem ještě doplňující otázku na něco dalšího. (už nevím přesně na co, ale byl to taky nějaký algoritmus a nebylo to těžké)

Měl jsem ty algoritmy popsat, dokázat proč fungují a jak jsou dobré atd.

U minimálního řezu se ptal, jestli existuje polynomiální algoritmus (Existuje. Pro každou dvojici vrcholů spustím algoritmus pro maximální tok), a proč používáme tenhle pravděpodobnostní alg., když máme polynomiální algoritmus. (Protože tenhle pravděpodobnostní algoritmus je rychlý a dá se hodně snadno implementovat)
Odpovědět

Zpět na „Ostatní“