Zkouška 18.6.2012 - Čepek

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
mykem
Matfyz(ák|ačka) level II
Příspěvky: 81
Registrován: 13. 2. 2011 18:52
Typ studia: Informatika Ph.D.

Zkouška 18.6.2012 - Čepek

Příspěvek od mykem »

Zdar,

dneska jsme na písemce třídili MFF-sortem :)

Dodejme akorát, že argument "musí to třídit, jelikož je to sort z MFF" prý v písemce (na rozdíl od případné prezentace v televizi) není dostačující. Snad se to v následujících letech změní!

Třetí úloha taky viz. minulej topic, jen dodám, že paměti bylo O(n), časová náročnost taky O(n). Optimálním řešením je postupný hashování bodů (kterých je n) do pole O(n). Pro každej bod se stačí podívat na jeho osm sousedů, jestli jsou (po zahashování) v tabulce. Pokud ne, bod se do tabulky přidá a jede se dál.

U ústního jsem nepochytil nic zvláštního - SSK (a důkaz), Floyd-Warshall, řešení kolizí v hashování...

Hodně štěstí :)
Odpovědět

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