Textové Algoritmy

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Textové Algoritmy
Kód předmětu: NNTIN087
Přednáší: Tomáš Dvořák

ZK ZS 07/08

Zkouška je ústní, většinou tak pro 6 lidí. Den předem oznámil zkoušející přesnou hodinu, kdy má který student přijít. Na zkoušku určitě stačí jen to, co je ve slidech, není třeba shánět jinde. Detailnější věci ze slidů nejsou úplně potřeba (ač se můžou hodit). Poptáváno je asi vše co lze na slidech nalézt (snad až na nějaké dlouhé konstrukce).


Otázky (pro jednoho člověka)

  • 1) Nalézt dvojice podslov slova x v suffixovém stromě. (viz. slide číslo7)
  • 2) Kódovat slovo pomocí suffixového pole (viz. slide číslo 24) (slovo bylo stejné)
  • 3) Konstrukce DAWG / CDAWG na slovo cocoa (jak se konstruují, jaká je prostorová složitost, porovnání se suffix stromem)
  • 4) Problém nejdelší společnépodposloupnosti - najít nějaký rozumný algoritmus ... Wagner - Fischer (viz. slide číslo 14,15)
  • 5) Problém palindromu (viz. slide číslo 13)

Po napsání řešení následuje kontrola a diskuze nad řešením. Obvykle se zkoušející vyptává např. na čas, náročnost a další upřesnění. Chce, aby to člověk chápal, ale není třeba do detailů. Dost se toho dá vymyslet až tam (pokud to člověk chápe :-)

hodnocení

Pomyslným žebříčkem je 100 bodů (tedy 20 za každou otázku), do 90 na jedničku, 80 na dvojku, 60 na trojku (myslím, že to tak říkal) Nakonec podle tohoto žebříčku zkoušející spočítá body (spíše strhne ze 100), ne ale nijak přísně => vytvoří známku. Pokud je známka dost nerozhodná (pár bodů pod hranicí), nabídne zkoušející další otázku, kterou je možno skore vylepšit.

Hodnocení předmětu

Předmět patří mezi ty jednodušší, člověk si ale rozšíří obzor o další algoritmy a struktury, které se mohou hodit. Zkouška je příjemná, nestresující. Zkoušející se spíše z člověka snaží dostat odpověď, než že by se v zadání šťoural.

Odkazy