15.5.2013 Mareš

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
unicorns

15.5.2013 Mareš

Příspěvek od unicorns »

1) (a-b)-tree: definice, insert/delete, časové složitosti operací
2) popsat a dokázat libovolný algoritmus na hledání min. kostry
3) slovní žebřík - je dán slovník N slov délky nejvýše L, nalezněte nejdelší posloupnost slov, které se jedno z druhého tvoří odebráním jednoho libolného písmene, např Glass -> Glas -> Gas -> as (pokud by tato slova dávala smysl)
4) Knihovna - v knihovně je N knih, z nichž K je setřízeno špatně - dotřiďte knihovnu
*) V daném stromě zrušte co nejméně hran tak, aby vznikla alespoň jedna komponenta souvislosti obsahující právě K vrcholů

Řešení:
1) 2) triviálně popsat
3) vytvořit graf, jehož vrcholy jsou slova a hrana z vrcholu A do vrcholu B vede právě tehdy, lze-li slovo B odebráním jednoho písmene přetvořit na slovo A, potom stačí dokázat, že graf je DAG a řešení je najít v něm nejdelší cestu - celkem O(N.L^2)
4) procházíme posl. knih zleva doprava, a kdykoli je nějaká kniha zařazena špatně, vyndáme ji (+ navíc ještě tu která byla před ní), vyndaných knih je 2K, ty setřídíme a mergneme z původní posl. Celkem O(N + KlogK)
*) by mě upřímně zajímala :)

zkouška úplně v klidu, dostatek času, mírné hodnocení
Odpovědět

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