Koutecký 11.6. 2020 - skupina B

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

Koutecký 11.6. 2020 - skupina B

Příspěvek od toby22 »

TEORIE:
1) Popsat hledání nejkratších cest (hlavně relaxace - invariant, lemmata) a rozebrat Dijkstru – složitost, kdy se vyplatí, kdy ne, jaký má problém se zápornými hranami,...
2) (a,b) stromy
PŘÍKLADY:
1)Stavíme dům a sestavíme si závislostní graf všech činností. O vrcholu tohoto grafu řekneme, že je kritický, pokud by zpomalení příslušné činnosti způsobilo pozdější dokončení celého domu. Při řízení stavby si proto na takové vrcholy musíme dávat pozor. Vymyslete, jak je všechny najít.
2)Pro neorientovaný ohodnocený graf G=(V,E,w) a množinu vrcholů S⊆V navrhněte algoritmus, který najde minimální kostru grafu G, u které jsou všechny vrcholy z množiny S listy nalezené kostry. Ostatní vrcholy mohou být také listy, tedy například pro S=∅ hledáme obvyklou minimální kostru.
Odpovědět

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