9. 6. 2017 Hric

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Návštěvník

9. 6. 2017 Hric

Příspěvek od Návštěvník »

1. Topologické uspořádní (definice, algoritmus, vlastnosti)
2. Dopředná a zpětná eliminace LUP rozkladu (složitost, využití... - váhu "matematickým" chybám moc nepřikládal, stačilo mu vypsat, k čemu se LUP používá a o LUP se rozepsat, zhruba vědět, co to je)
3. a) Napsat "kuchařku" Master Theoremu
b) Aplikace s parametrem, T(n) = a*T(n/3) + O(n^2), v závislosti na parametru rozdělit na tři případy z kuchařky... a < 9, a = 9, a > 9
4. Pro graf G=(V,E)G=(V,E) určete, zda je možné ho pokrýt grafy K1,2K1,2 (vidlička, cesta délky 2). Navrhněte algoritmus, které toto pokrytí nalezne, pokud existuje a jinak vypíše nějakou chybu.

Na ústní zkoušce bylo dvanáct lidí od jedné do šesté. Zkouška vypadá tak, že je vám zadáno jedno z témat, které se ve slidech vyskytují.
Dostanete tak patnáct minut na přípravu, stejný čas se vám věnuje, pokud nejsou nějaké nejasnosti.

Příklady témat na ústní, co byly:
Bellman-Ford, Dijkstra (složitost, haldy, algoritmus, vstup), otevřené adresování (analýza, popsat způsoby, příklad), Floyd-Warshallův algoritmus, Kruskal (důkaz z řezy), Jarníkův alg., Counting Sort
Když nevíte téma, dostanete jiné a máte i tak možnost získat jedničku, pokud máte dost bodů z písemky. Zkoušející fajn. Témata se v jednom termínu neopakovala, každý dostal jiné.
Odpovědět

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