22. 6. 2015 Martin Mareš

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Uživatelský avatar
petrroll
Matfyz(ák|ačka) level I
Příspěvky: 12
Registrován: 23. 5. 2015 22:27
Typ studia: Informatika Bc.

22. 6. 2015 Martin Mareš

Příspěvek od petrroll »

1) Topologické uspořádání grafu (co to je, k čemu je to, jak se to hledá, ...)
2) AVL stromy (co to je, jak je to rychlý, popsat insert)
3) Máme posloupnost € Z (a1, a2, ... an) a číslo x € Z. Je třeba zjistit, jestli existují ai a aj (ne nutně různé), které dohromady dají x.
4) Máme graf a pro něj máme najít jak jej nakreslit co nejmenším počtem tahů (a ty tahy vypsat).

Bonus) Upravte B-stromy tak, aby byl vrchol vždy zaplněn alespoň z 2/3 a ne z 1/2.

---
Nápovědy (které sám MJ dal):
4a) Je jedno, jestli řešíte tah uzavřený nebo otevřený.
4b) Prvně uvažujte pro graf, na kterém existuje nakreslení jedním tahem; zbylé grafy jdou na tento případ snadno převést.
4c) (asi po hodině řešení): Při převádění z grafů, které nejdou nakreslit jedním tahem, zkuste hrany neodebírat ale přidávat.
Odpovědět

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