od Davpe » 3. 9. 2014 18:19
3.9.2014
1) Sufixový strom: efektivní konstrukce
2) Bitový paralelismus: vybrat si problém a vyřešit ho pomocí bitových operací + pseudokód
3) Konečná množina vzorků - časová složitost
ad 1) Ukkonen + 4 triky.
V algoritmu pro i-tou iteraci jsem měl napsáno že se řídím podle toho, zda návěští hrany je x, což není pravda, protože návěští hran mohou být víceznaková, tak se zeptal na definici sufixového stromu a nakonec ze mě dostal že se řídím podle prvního znaku návěští.
Chtěl po mně vysvětlení každého triku, proč triky a pozorování k nim potřebná platí. Nemohl jsem přijít na to proč funguje "pokud x[j..i] je list pak i x[j-1..i] je list". Docela jsme se na tom zasekli než mi ukázal že listy v implicitním SS reprezentují unikátní přípony (tedy přípony tam nejsou 2x) a z toho už to jde vidět.
Chtěl po mně ještě sufixové hrany, tak jsem napsal co to je a jak se to používá. Ptal se co se stane když tam sufixová hrana není (vytvořím ji), jak se vytváří, co je to fastscan, co je to slowscan a jak se liší, jak dlouho trvají a jak dlouho trvá celý Ukkonen,
ad 2) Vybral jsem si přesné vyhledávání vzoru, Chtěl to ještě vysvětlit, proč tam jsou ty bitové operace tak jak jsou, co je s^i, jak dlouho to trvá a pak dodal že je to vhodné jen pro malé délky vzorků.
ad 3) Vybral jsem si Aho-Corasicka a napsal k tomu složitost konstrukce trie a hledání pomocí ní a zmínil jsem nejlepší dolní odhad .
Výsledek, za dva hned nebo se na něco zeptá. Chtěl jsem vzít dvojku, ale začal mi to rozmlouvat že chce vědět podrobnější časovou analýzu buď u 1) nebo 3). Věděl jsem obojí - u 1) mu šlo o důkaz m = O(n) kde stačilo říct že sufixová funkce jde pořád hlouběji a počet vrcholů na cestě je <= n a u 3) chtěl vědět že tam je fail funkce, co to je a k času jsem řekl že to je stejný argument jako u hranic a zmínil jsem jak se upočítá, že #iterací je < n.
Zkouška příjemná, zvlášť absence důkazů (až na pár triviálních) :D Na druhou stranu se Dvořák hodně!! ptá: na spoustu detailů, proč co platí, chce všechno vysvětlit a nepřehlídne žádnou chybu. Narozdíl od některých zkoušejících nenapovídá. Pokud budete přemýšlet, tak bude svorně mlčet s vámi dokud něco neřeknete. Pokud to nevymyslíte, neprozradí vám správnou odpověď, ale přeskočí otázku a nechá vám ji na později. Přišlo mi dobré (pokud jsem nevěděl odpověď hned) mu narovinu říct, že chcete otázku přeskočit a promyslet si ji.
3.9.2014
1) Sufixový strom: efektivní konstrukce
2) Bitový paralelismus: vybrat si problém a vyřešit ho pomocí bitových operací + pseudokód
3) Konečná množina vzorků - časová složitost
ad 1) Ukkonen + 4 triky.
V algoritmu pro i-tou iteraci jsem měl napsáno že se řídím podle toho, zda návěští hrany je x[i], což není pravda, protože návěští hran mohou být víceznaková, tak se zeptal na definici sufixového stromu a nakonec ze mě dostal že se řídím podle prvního znaku návěští.
Chtěl po mně vysvětlení každého triku, proč triky a pozorování k nim potřebná platí. Nemohl jsem přijít na to proč funguje "pokud x[j..i] je list pak i x[j-1..i] je list". Docela jsme se na tom zasekli než mi ukázal že listy v implicitním SS reprezentují [b]unikátní[/b] přípony (tedy přípony tam nejsou 2x) a z toho už to jde vidět.
Chtěl po mně ještě sufixové hrany, tak jsem napsal co to je a jak se to používá. Ptal se co se stane když tam sufixová hrana není (vytvořím ji), jak se vytváří, co je to fastscan, co je to slowscan a jak se liší, jak dlouho trvají a jak dlouho trvá celý Ukkonen,
ad 2) Vybral jsem si přesné vyhledávání vzoru, Chtěl to ještě vysvětlit, proč tam jsou ty bitové operace tak jak jsou, co je s^i, jak dlouho to trvá a pak dodal že je to vhodné jen pro malé délky vzorků.
ad 3) Vybral jsem si Aho-Corasicka a napsal k tomu složitost konstrukce trie a hledání pomocí ní a zmínil jsem nejlepší dolní odhad .
Výsledek, za dva hned nebo se na něco zeptá. Chtěl jsem vzít dvojku, ale začal mi to rozmlouvat že chce vědět podrobnější časovou analýzu buď u 1) nebo 3). Věděl jsem obojí - u 1) mu šlo o důkaz m = O(n) kde stačilo říct že sufixová funkce jde pořád hlouběji a počet vrcholů na cestě je <= n a u 3) chtěl vědět že tam je fail funkce, co to je a k času jsem řekl že to je stejný argument jako u hranic a zmínil jsem jak se upočítá, že #iterací je < n.
Zkouška příjemná, zvlášť absence důkazů (až na pár triviálních) :D Na druhou stranu se Dvořák hodně!! ptá: na spoustu detailů, proč co platí, chce všechno vysvětlit a nepřehlídne žádnou chybu. Narozdíl od některých zkoušejících nenapovídá. Pokud budete přemýšlet, tak bude svorně mlčet s vámi dokud něco neřeknete. Pokud to nevymyslíte, neprozradí vám správnou odpověď, ale přeskočí otázku a nechá vám ji na později. Přišlo mi dobré (pokud jsem nevěděl odpověď hned) mu narovinu říct, že chcete otázku přeskočit a promyslet si ji.