[Zk] 12.2.2009
Napsal: 12. 2. 2009 20:43
Zadaní písemné části standardní
1)Ukázat, že lze nalézt pomocí DFS zadané topologické uspořádání
2)Ukázat, že v binárním stromu existuje hrana po jejímž oddělení zbydou dvě komponenty každá s max (2n+1/3) vrcholy
3)Zednický metr
Ústní je trochu loterie. Já dostal odvodit složitost u UPAS pro SM. Základem bylo napsat algoritmus -zde jsem proškrtával z druhé strany než je ve skritpech, což čepkovi v podstatě nevadilo /asi to možná i funguje/ a říci, že v nejhorším případě je ten proškrtaný seznam geometrická posloupnost - v okamžiku, kdy si todle pamatujete je ten zbytek důkazu relativně snadný a dá se odvodit metodou "doplňování obrázku" ... Dva další kolegové dostali neexistenci UPAS pro TSP a aproximační algo pro TSP s trojúhelníkovou nerovností. Poslední dostal #P. Jenom snad poznamenám, že čepek stačil vyzkoušet tři lidi zatímco vedle zkoušející kučera studenty zkoušel o poznání důkladněji.
1)Ukázat, že lze nalézt pomocí DFS zadané topologické uspořádání
2)Ukázat, že v binárním stromu existuje hrana po jejímž oddělení zbydou dvě komponenty každá s max (2n+1/3) vrcholy
3)Zednický metr
Ústní je trochu loterie. Já dostal odvodit složitost u UPAS pro SM. Základem bylo napsat algoritmus -zde jsem proškrtával z druhé strany než je ve skritpech, což čepkovi v podstatě nevadilo /asi to možná i funguje/ a říci, že v nejhorším případě je ten proškrtaný seznam geometrická posloupnost - v okamžiku, kdy si todle pamatujete je ten zbytek důkazu relativně snadný a dá se odvodit metodou "doplňování obrázku" ... Dva další kolegové dostali neexistenci UPAS pro TSP a aproximační algo pro TSP s trojúhelníkovou nerovností. Poslední dostal #P. Jenom snad poznamenám, že čepek stačil vyzkoušet tři lidi zatímco vedle zkoušející kučera studenty zkoušel o poznání důkladněji.