Koutecký 11.6. 2020 - skupina A

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

Koutecký 11.6. 2020 - skupina A

Příspěvek od patin »

Nazdar, tohle jsou příklady ze zkoušky od kouteckýho. Říkal, že musíte zvládnout minimálně jeden příklad ze "cvičení". Byly totiž dva příklady na algoritmy z průvodce a dva příklady ze "cvičení" - tzn. vymyslet algoritmus:

1) Kruskalův algoritmus - tzn. dokázat řezový lemma, vysvětlit jak funguje a ukázat Union-find (s důkazem hloubky keříků)
2) Karacubův algoritmus - můžete to dělat přes kuchařkovou větu - v tom případě ji musíte dokázat. Já odvodil přímo složitost bez ní (pomocí toho rekurzivního stromu), což je taky ok.

Příklady ze "cvičení"
1) Na začátku máme jednu korunu a máme matici směn K, kde K_{i, j} znamená, kolik dostaneme měny j za jednu jednotku měny i. Máte zjistit, jestli jde udělat posloupnost měn taková, že z jedný koruny dokážeme udělat víc korun (tzn. dokážeme neomezeně vydělávat).
2) Máte množinu přirozených čísel (tzn. neuspořádaný pole, kde se prvky neopakujou) a číslo x. Chcete zjistit, jestli existujou dva prvky v množině takový, že jejich součet je x.

V jedničce vezmete Bellman-Forda a upravíte ho. Vlastně jakoby maximalizujete výdělek, tzn. při relaxaci se snažíte zvyšovat ohodnocení (ne snižovat). No a platí, že pokud neexistuje v grafu zápornej cyklus, pak se po n iteracích B-F zastaví, (pro nás kladnej cyklus, protože maximalizujeme). Ale není těžký rozmyslet, že platí i opačná implikace, že pokud se B-F zastaví, neexistuje kladnej cyklus. Takže pustíte B-F n-krát a když se nezastaví, máte kladnej cyklus a dokážete neomezeně vydělávat. Napsal jsem to dost zjednodušeně, ale pointa je snad jasná.

Ve dvojice projedete jednou pole a vytvoříte si hešovací tabulku, kam prvky uložíte. No a pak projedete pole ještě jednou a pro každej prvek si spočtete, jakej by musel bejt ten druhej prvek, aby v součtu se rovnaly x (tzn. hledate prvek a = x - P). No a to se v konstantním čase kouknete do tý hešovací tabulky, jestli ten prvek v množině existuje, a máte to v O(n).

Hele u Kouteckýho si fakt čtěte Průvodce. Jeho hodiny jsou takový, že on jenom čte Průvodce, takže co jinýho byste asi měli umět, žejo. Zkouška probíhá tak, že tam přijdete, zadá příklady, vy pracujete, když máte, dáte mu to, on to přečte, pak vám řekne, hele, tohle je blbě, oprav to, tak se to snažíte opravit, když to dáte, máte třeba lepší známku, když ne, tak horší a tak. Přijde mi, že se ta zkouška dá v pohodě udělat, že je mírnej, sám to říká. Na dobrou známku ale doporučuju ty věci umět.

Přeju hodně štěstí, borci
Odpovědět

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