od Vilda » 12. 6. 2018 12:58
Standardně 2 hodiny na tří příklady, které ale byly nejspíš nové (na foru jsem je ještě neviděl)
1. Uhádněte a substitucí dokažte theta složitost:
 = T(n/2) + 2T(n/3) + n^2)
2. Pro všechny řezy určíme lehkou hranu a tu přidáme do množiny
. Dokažte, že
je kostra.
3. Máme tabulku převodů měn (mezi každou měnou jen jeden záznam) a chceme zjistit, zdali existuje posloupnost výměn, která nám přinese zisk.
1.
)
. Triviálně dopočítáme konstanty.
2. Hrany musí pokrýt všechny vrcholy, jinak si bereme triviální řezy. Pak ukážeme, že to je strom, ideálně sporem (neexistují cykly a je to souvislé).
3. Z měn si uděláme vrcholy a pak hledáme
, kde začínáme a končíme ve stejném vrcholu. Pokud celou rovnici zlogaritmujeme, pak dostaneme
 < 0)
, což je ekvivalentní zápornému cyklu, na což hodíme Floyd Warshalla. Důležité je okomentovat, proč se změní nerovnost. Buď se tam nějak hraje ze znaménky, nebo základ logaritmu volíme jako nejmenší možnou hranu. Taková určitě je menší než 1, jinak by rozhodně chtěná posloupnost existovat nemohla.
Na ústní jsem šel ještě zatímco ostatní dopisovali. Spolužák, co byl na ústní přede mnou, myslím letěl. V jedničce jsem zapomněl být pečlivý a tam mi strhl 0.5 bodu. U trojky jsem omylem použil BF, ale to jsem zachránil popisem triku s nejmenším základem logaritmu. Celkově jsem měl 2.25 bodů (hranice je 1.5) a říkal, že můžu bojovat o jedničku. Dostal jsem průměrný počet pokusů v neúspěšném vyhledávání pro otevřené adresování, důkaz FW (protože jsem ho nepoužil tam, kde jsem měl) a nakonec hloubka RB stromu. Nevěděl jsem skoro nic, čehož si Čepek všiml. Když mě hodnotil, tak to komentoval slovy:
Z tohoto jste se vylhal, z tohoto taky, tak já vám dám za 2. Stresové to ale nebylo. Když něco nevíte, tak vám buď dá dobrý hint, nebo vám to vysvětlí. Když jsem mu řekl, že tu pravděpodobnost neznám, tak odvětil:
To je výhoda matfyzáka. Když nemá naučený důkaz, tak ho na zkoušce vymyslí. Správný důkaz jsem samozřejmě nevymyslel.
Rada: Nepodceňujte formalismy a na zkoušku přijďte s naučenými důkazy.
Standardně 2 hodiny na tří příklady, které ale byly nejspíš nové (na foru jsem je ještě neviděl)
1. Uhádněte a substitucí dokažte theta složitost: [latex]T(n) = T(n/2) + 2T(n/3) + n^2[/latex]
2. Pro všechny řezy určíme lehkou hranu a tu přidáme do množiny [latex]E[/latex]. Dokažte, že [latex]E[/latex] je kostra.
3. Máme tabulku převodů měn (mezi každou měnou jen jeden záznam) a chceme zjistit, zdali existuje posloupnost výměn, která nám přinese zisk.
1. [latex]\Theta(n^2)[/latex]. Triviálně dopočítáme konstanty.
2. Hrany musí pokrýt všechny vrcholy, jinak si bereme triviální řezy. Pak ukážeme, že to je strom, ideálně sporem (neexistují cykly a je to souvislé).
3. Z měn si uděláme vrcholy a pak hledáme [latex]w_1\cdot w_2 \cdot w_3 \dots w_n > 1[/latex], kde začínáme a končíme ve stejném vrcholu. Pokud celou rovnici zlogaritmujeme, pak dostaneme [latex]\sum \log(w_i) < 0[/latex], což je ekvivalentní zápornému cyklu, na což hodíme Floyd Warshalla. Důležité je okomentovat, proč se změní nerovnost. Buď se tam nějak hraje ze znaménky, nebo základ logaritmu volíme jako nejmenší možnou hranu. Taková určitě je menší než 1, jinak by rozhodně chtěná posloupnost existovat nemohla.
Na ústní jsem šel ještě zatímco ostatní dopisovali. Spolužák, co byl na ústní přede mnou, myslím letěl. V jedničce jsem zapomněl být pečlivý a tam mi strhl 0.5 bodu. U trojky jsem omylem použil BF, ale to jsem zachránil popisem triku s nejmenším základem logaritmu. Celkově jsem měl 2.25 bodů (hranice je 1.5) a říkal, že můžu bojovat o jedničku. Dostal jsem průměrný počet pokusů v neúspěšném vyhledávání pro otevřené adresování, důkaz FW (protože jsem ho nepoužil tam, kde jsem měl) a nakonec hloubka RB stromu. Nevěděl jsem skoro nic, čehož si Čepek všiml. Když mě hodnotil, tak to komentoval slovy: [i]Z tohoto jste se vylhal, z tohoto taky, tak já vám dám za 2.[/i] Stresové to ale nebylo. Když něco nevíte, tak vám buď dá dobrý hint, nebo vám to vysvětlí. Když jsem mu řekl, že tu pravděpodobnost neznám, tak odvětil: [i]To je výhoda matfyzáka. Když nemá naučený důkaz, tak ho na zkoušce vymyslí.[/i] Správný důkaz jsem samozřejmě nevymyslel.
Rada: Nepodceňujte formalismy a na zkoušku přijďte s naučenými důkazy.