od JiriD » 12. 1. 2011 16:43
Jenom co se týče zkoušky,
písemná část není nejjednodušší, pokud to chce člověk vymyslet na místě.
U 2SATu jsem napsal sice správný algoritmus, ale bez důkazu polynomiality - půl bodu.
MMNM jsem věděl - 1 bod.
U ústní jsem dostal ÚPAS pro Součet Podmnožiny. Stačilo napsat co je to AS, PAS, ÚPAS, relativní chyba - definice, zadání úlohy, napsat algoritmus a asi pět lemmat - pouze znění, pomocí kterých dokážeme korektnost algoritmu. Říkal, že důkazy nemusím, že se kdyžtak zeptá, kdyby ho to zajímalo. K důkazu stačilo potom jenom říct: to je technická analýza, tohle indukcí, tole rozborem případů atd. Asi viděl, že to umím a nechal mě s 1 jít.
Jinak co jsem slyšel z dalších zadání, tak padlo obvyklé: #P a NP a Test 2-souvislosti grafu + označení artikulací (upravené DFS)
Hodně štěstí u zkoušky.
Jenom co se týče zkoušky,
písemná část není nejjednodušší, pokud to chce člověk vymyslet na místě.
U 2SATu jsem napsal sice správný algoritmus, ale bez důkazu polynomiality - půl bodu.
MMNM jsem věděl - 1 bod.
U ústní jsem dostal ÚPAS pro Součet Podmnožiny. Stačilo napsat co je to AS, PAS, ÚPAS, relativní chyba - definice, zadání úlohy, napsat algoritmus a asi pět lemmat - pouze znění, pomocí kterých dokážeme korektnost algoritmu. Říkal, že důkazy nemusím, že se kdyžtak zeptá, kdyby ho to zajímalo. K důkazu stačilo potom jenom říct: to je technická analýza, tohle indukcí, tole rozborem případů atd. Asi viděl, že to umím a nechal mě s 1 jít.
Jinak co jsem slyšel z dalších zadání, tak padlo obvyklé: #P a NP a Test 2-souvislosti grafu + označení artikulací (upravené DFS)
Hodně štěstí u zkoušky.