od unicorns » 16. 5. 2013 11:21
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í
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í