Hubička 5.6.2019

Dnes bylo následující:

1. Definujte AVL stromy, insert nebo delete + důkaz složitosti (10 bodů)

2. Bellman-Ford - časová složitost, jak pracuje, ... (5 bodů)

3. Slovní žebřík: Je dán slovník. Sestrojte co nejdelší slovní žebřík, což je posloupnost slov ze slovníku taková, že (i+1)-ní slovo získáme z i-tého smazáním jednoho písmene. V češtině například zuzavírání, uzavírání, zavírání, zvírání, zírání, zrání, zrní. (5 bodů)

4. Máme čtverečkovou mapu se zdmi mezi čtverečky (jako obvykle). Přechod na volný sousední čtvereček stojí 1, prokopání zdi stojí K (celé číslo). Najděte nejkratší cestu mezi danými vrcholy, z do v. (5 bodů)

5. bonusová úloha, zadání si nepamatuji :-)...

Na zkoušce byla velmi příjemná atmosféra, je na ni v podstatě neomezeně času.

Zadani
1.) AVL stromy (definice, insert/delete,důkaz času
2) Bellman-ford (popis a čas)
3) Najít nejdelší posloupnosti slov, že i+1-té slovo vzniklo z i-tého odebráním libovolného písmena
4) Máme čtverečkovanou mapu (šachovnice) a některé pole mají zeď a trvá K tu zeď probourat, jinak pohyb stojí 1. nalezněte nejkratší cestu mezi A a B
5) máme množinu a hledáme dvojici, která mezi sebou nemá čísla a je co nejdál od sebe (lineární složitost)
Reseni
1-2) viz průvodce 3) dynamika: od nejmenších slov děláme toto: Odendáme písmeno a zkusíme jestli je to slovo a pokud ano tak se koukneme do tabulky kolik má podslov. toto děláme pro každé slovo a každé písmeno. časová složitost je tedy O(ndd) kde n je počet slov a d délka nejdelšího z nich.
4) zkoušel jsem jednoduše dijkstra, který výjde O(n*logn) kde n je celkový pčoet polí (počet hran z každého vrcholu je max 4), ale vadil mu ten log n. 5) nedělal jsem
Poznamky
Pan Hubička je dobrák. Probíhá to několika kolečkami odpovědí - můžete po jednotlivých cvičeních mu to ukazovat. Koukněte se na časové složitosti. Příklady dává jednoduché až na to, že je potřeba sesekat časovou složitost