od Davpe » 14. 2. 2014 17:44
1) Strom s vrcholy stupně <=3. Nalézt hranu rozdělující strom na dva, že každý je <= (2n+1)/3 (úloha č. 10)
2) Zednický metr (úloha č. 11)
Oba příklady jsem měl správně.
Řešení jedničky:
DFS na graf (je to binární strom), počítám od zdola velikosti podstromů určené vrcholem v jako W(v).
Tedy W(list) = 1 a W(v) = W(levy syn vrcholu v) + 1 + W(pravy syn vrcholu v).
Najdu vrchol v, takový že W(levy syn vrcholu v) <= (n-1)/3 a W(pravý syn vrcholu v) <= (n-1)/3. Pak hrana (v, otec(v)) oddělí podstrom v velikosti <= (n-1)/3 + 1 + (n-1)/3 = (2n+1)/3
Ústní:
Příklad ÚPASu a znění těch tří lemmat. A prohlásil, že nic technického (tj. technické části důkazů) po mně nebude chtít.
Chtěl: Definici ÚPASu, zadání součtu podmnožiny a algoritmus ÚPAS pro něj. Dále ta tři lemmata. První dva dokazovat vyloženě nechtěl (moc technické), třetí už ano. Stačilo říct, že prvky seznamu tvoří geometrickou posloupnost s kvocientem 1/(1 - e/n) a že |L_i| <= log t o základu 1/(1 - e/n).
Protože jsem pokazil znění prvních dvou lemmat tak za 2.
Otázky:
První člověk co odevzdal dostal Kachlíkování a další, který neměl zednický metr dostal převod VP -> SP (tady pozor, že se to nedělá jako implikace, někdo se snažil to dělat tak, že začal: "Najdeme vrcholové pokrytí..." a Čepek na to vždycky naštvaně odpovídal že to je nemožné (čímž asi myslel najít ho polynomiálně rychle)).
1) Strom s vrcholy stupně <=3. Nalézt hranu rozdělující strom na dva, že každý je <= (2n+1)/3 (úloha č. 10)
2) Zednický metr (úloha č. 11)
Oba příklady jsem měl správně.
Řešení jedničky:
DFS na graf (je to binární strom), počítám od zdola velikosti podstromů určené vrcholem v jako W(v).
Tedy W(list) = 1 a W(v) = W(levy syn vrcholu v) + 1 + W(pravy syn vrcholu v).
Najdu vrchol v, takový že W(levy syn vrcholu v) <= (n-1)/3 a W(pravý syn vrcholu v) <= (n-1)/3. Pak hrana (v, otec(v)) oddělí podstrom v velikosti <= (n-1)/3 + 1 + (n-1)/3 = (2n+1)/3
Ústní:
Příklad ÚPASu a znění těch tří lemmat. A prohlásil, že nic technického (tj. technické části důkazů) po mně nebude chtít.
Chtěl: Definici ÚPASu, zadání součtu podmnožiny a algoritmus ÚPAS pro něj. Dále ta tři lemmata. První dva dokazovat vyloženě nechtěl (moc technické), třetí už ano. Stačilo říct, že prvky seznamu tvoří geometrickou posloupnost s kvocientem 1/(1 - e/n) a že |L_i| <= log t o základu 1/(1 - e/n).
Protože jsem pokazil znění prvních dvou lemmat tak za 2.
Otázky:
První člověk co odevzdal dostal Kachlíkování a další, který neměl zednický metr dostal převod VP -> SP (tady pozor, že se to nedělá jako implikace, někdo se snažil to dělat tak, že začal: "Najdeme vrcholové pokrytí..." a Čepek na to vždycky naštvaně odpovídal že to je nemožné (čímž asi myslel najít ho polynomiálně rychle)).