Hubicka 2019

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
spidoosho
Matfyz(ák|ačka) level I
Příspěvky: 20
Registrován: 27. 5. 2019 19:36
Typ studia: Informatika Bc.

Hubicka 2019

Příspěvek od spidoosho »

Zadani
1) co největší popis a,b-stromů.
2) DFS, jak tam fungují cykly, pojmenování hran
3) setřiď posloupnost N čísel, kde různých čísel je K, kde K je mnohem menší, jak N (lineárně)
4) vypiš nejdelší cestu (o nejvíce hranách) z těch nejlevnější cest mezi A a B v grafu
5) najdi nejdelší souvislou podposloupnost čísel, ve které se čísla neopakují.

Reseni
(1) viz Průvodce
(2) viz Průvodce
(3) zmenšení na posloupnost K čísel (v lineárním čase -> je potřeba zvolit chytře Datovou strukturu (více možností)), normální sort - třeba marge -> O(klogk + n)-> O(n)
(4)Upravená Dijkstra
(5) Rozděluj a panuj

Poznamky
Bohatě stačí shlédnout natočené přednášky Mareše z roku 2015 a párkrát si projít od něj vyfocené tabule. Nic víc v testu nebude. Průvodce je prej taky dobrej.
Odpovědět

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