Čepek 12. 6. 2018

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Vilda
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 15. 1. 2018 15:02
Typ studia: Informatika Bc.

Čepek 12. 6. 2018

Příspěvek od Vilda »

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) = 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 E. Dokažte, že 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. \Theta(n^2). 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 w_1\cdot w_2 \cdot w_3 \dots w_n > 1, kde začínáme a končíme ve stejném vrcholu. Pokud celou rovnici zlogaritmujeme, pak dostaneme \sum \log(w_i) < 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.
Vilda
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 15. 1. 2018 15:02
Typ studia: Informatika Bc.

Re: Čepek 12. 6. 2018

Příspěvek od Vilda »

Už nevím, kde jsem to ukradl (někde zde na fóru), ale tyto zápisky jsou úžasné. Doporučuji se z nich učit. Jsou už pár let staré, ale jsou velmi čitelné a výklad je z nich srozumitelný.
Přílohy
ads1_zapisky_cepek.zip
(3.92 MiB) Staženo 267 x
Blaward

Re: Čepek 12. 6. 2018

Příspěvek od Blaward »

Ja som mal na ústnej najprv dôkaz očakávaného počtu skúšaných pozícií pri neúspešnom vyhľadávaní v haš-tabuľke otv.adr. (1/1-\alpha). K tomu spomenul niečo v zmysle, že to mu ešte nikto dnes nepovedal, takže asi tomu padlo za obeť viacero nešťastníkov.
Ako doplňujúcu som dostal DAG.
Iné čo si pamätám, boli SSK + Floyd-Warshall, Kruskal + dvojité hašovanie.

PS: K 3-ke ak sa nemýlim:
\prod_{i=1}^n w_i > 1
log(\prod_{i=1}^n w_i) > 0
\sum_{i=1}^n log(w_i) > 0
\sum_{i=1}^n -log(w_i) < 0
Takže všetky hrany na -log(w).
Odpovědět

Zpět na „TIN060 Algoritmy a datové struktury I“