NTIN087 Textové algoritmy

Co se jinam nevejde

NTIN087 Textové algoritmy

Příspěvekod Ger » 29. 1. 2013 23:15

Zatím tu chybí nějaké info o zkoušce z TA, takže...

Večer před zkouškou najednou napsal e-mail, kdy má kdo přijít, takže ten čas v SIS neberte až tak vážně (bere to zřejmě buď podle abecedy, nebo podle data přihlášení, to nedokáži podle svého času rozhodnout 0:-) + Když přijdete k učebně, tak se dozvíte, že to nebude v ní, ale u něj ve 405 (proč to nenapsal rovnou do e-mailu netuším).
takže zkouší po jednom, po příchodu mi dal papír se čtyřmi otázkami:
1) Prostorová složitost suffixového stromu a suffixové trie.
2) Nalezení všech dvojic i, j takových že existuje k>=0 t.ž. [i..i+k]=[j..j+k].
3) Nalezení nejdelší společné podposloupnosti.
4) Sestrojit automat pro regulární výraz ((ab)|(c)*)* nad abecedou {a,b,c}.
Po nějakém čase přijde a zkoumá, co už máte, takže nic neobvyklého.

Jinak je zkouška pohodová, nevadilo, že jsem si nejdříve špatně přečetl (3) a místo LCS jsem hledal maximální NRE... Není potřeba psát moc formálně, stačí když to umíte okecat. ;-)
Ger
 

Re: NTIN087 Textové algoritmy

Příspěvekod Návštěvník » 16. 1. 2014 12:56

Zkouška z 16.1.2014:

1) Popište efektivní algoritmus na sestavení sufixového pole. Odvoďte jeho časovou složitost. (slide 23-42)
2) Popište algoritmus na vytváření NFA z regulárního výrazu. Popište jeho časovou a prostorovou složitost. (slide 8-18)
3) Určování vzdálenosti mezi slovy pomocí dynamického programování. Rekurentní vztah a časová + prostorová složitost. (slide 10-13)

První příklad je v podstatě nutná podmínka složení zkoušky.
Návštěvník
 

Re: NTIN087 Textové algoritmy

Příspěvekod Davpe » 3. 9. 2014 17: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[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í 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.
Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
 
Příspěvky: 98
Registrován: 22. 9. 2010 15:07
Typ studia: Informatika Bc.
Login do SIS: pegrimed

Re: NTIN087 Textové algoritmy

Příspěvekod Kaelthar » 1. 10. 2014 14:48

Zkouška 18.9. 2014

1) Sufixové pole
a) Detailně algoritmus konstrukce
b) důkaz časové složitosti

2) Rekurentní vztah u algoritmu pro vzdálenost dvou slov

3) Popsat algoritmus pro stavbu NFA pro regulární výrazy

- zkouška není těžká, ale pan Dvořák se na všechno detailně ptá, co a jak funguje a proč, u druhé otázky nestačí pouze napsat vztah ale nutné je říci proč tak funguje. Jak už bylo řečeno, pokud nevíte tak neradí a čeká, popřípadě odejde a vrátí se až po chvíli. Takže když něco nevíte a myslíte že to dohromady nedáte, rovnou to řekněte a možná se zeptá na něco jiného. Jinak pokud napíšete zkoušku na 2, bude vás dlouho přemlouvat aby vám mohl dát další otázku a zlepšit hodnocení.
Kaelthar
Matfyz(ák|ačka) level I
 
Příspěvky: 10
Registrován: 29. 1. 2013 22:55
Typ studia: Informatika Mgr.

Re: NTIN087 Textové algoritmy

Příspěvekod katebrich » 26. 1. 2017 17:17

Zkouška 26. 1. 2016

1) Srovnat prostorovou složitost sufixového trie, sufixového stromu, DAWG a CDAWG a vysvětlit, proč to tak je
2) Aho-Corasick, napsat definici Fail funkce, popsat, k čemu slouží, napsat algoritmus pro efektivní konstrukci a jak dlouho bude trvat
3) Algoritmus pro určení vzdálenosti dvou slov (dynamické programování)

Nechal nám dost času na přípravu, a taky čas na rozmyšlenou, když jsem něco nevěděla hned. Jak už tady všichni psali, hodně se ptá na detaily, chce vědět, proč co funguje, je potřeba tomu docela rozumět.
Na druhou stranu mi připadalo, že moc netrvá na formalismech a když jsem mu třeba u 2) napsala pseudokód na konstrukci těch zpětných hran, tak mě pochválil, že to mám hodně precizně :D (a to jsem si myslela, že jsem to odflákla :D). U 3) si přečetl, co jsem napsala, řekl, že všechno dobře, a pak se ptal ještě na spoustu věcí - jak z té tabulky poznáme, které operace použít, jestli poznáme délku nejdelší podposloupnosti, zajímalo ho i vylepšení toho algoritmu (jak se berou jenom určité diagonály).
Nakonec jsem ale dostala jedničku, takže možná se takhle moc ptal proto, že se chtěl přesvědčit, jestli tomu fakt rozumím :)
katebrich
 


Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron