Čepek - 14.6. 2010

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
ostan
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 28. 1. 2010 14:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Čepek - 14.6. 2010

Příspěvek od ostan »

V písemné části byly tyto tři úkoly:

1) Libovolný binární vyhledávací strom na n vrcholech lze upravit pomocí O(n) rotací na spojový seznam. (Myšleno takové rotace, jaké se používají k vyvažování Č-Č nebo AVL stromů.) Tvrzení jsme měli dokázat nebo vyvrátit.
2) Úloha na téma hashování, konkrétně na otevřené adresování. Byl tam kousek kódu (insert nebo search) a z něho jsme měli poznat, o jaký typ zkoušení jde.. Měli jsme ukázat jestli je to lineární nebo kvadratické zkoušení tím, že najdeme konstanty c,d pro h(x,i)=(h´(x) + c i + d i^2) mod m. A taky dokázat, že v případě plné hashovací tabluky insert opravdu vyzkouší všechna pole aniž by na nějaké sáhnul dvakrát (byl tam předpoklad, že velikost tabulky m = 2^k a vycházelo c=1/2, d=1/2.
3) Máme orientovaný graf s ohodnocenými hranami a výchozí bod s. Hrany jsou silnice a ohodnocení udává, jaké nejvyšší auto může po cestě ještě projet (představujte si např. výšku mostu přes silnici). Navrhněte algoritmus, který pro každý vrchol grafu spočte, jaké nejvyšší auto se tam může dostat po nějaké cestě z výchozího bodu s.

Takže tolik k písemce, odpoledne je pak ústní část a na ní jsou lidi zváni podle času odevzdání písemky. Zkoušejí pánové Ondřej Čepek a Petr Kučera. Já jsem dostal hledání SSK v grafu, měl jsem to bez chyby a z písemky dva body ze tří, takže celkově za jedna :)
Odpovědět

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