2-INF-147 Vyhľadávanie v texte, LS 2012/2013

Táto stránka sa týka ukončeného semestra. Navyše tento predmet už nebude vyučovaný. Pre potreby štátnicového bloku B a D ho nahrádza pnvý predmet Vybrané partie z dátových štruktúr.

Poznámky z prednášok

Poznámky spísané študentami (stav 20.5.2013, priebežne opravované):

• Pdf
• LaTeXové súbory

Za písanie nových poznámok ako aj opravovanie a vylepšovanie starých je možné získať body za aktivitu. Nové alebo zmenené poznámky odovzdajte v pdf + Latexové zdrojáky. Obrázky odovzdajte v eps a v zdrojovom tvare podľa toho, akým softvérom ste ich vyrábali. Ako vzor použite už existujúce poznámky.

Pracovať na jednej časti poznámok môžu postupne aj viacerí študenti, ale každý ďalší musí začať z predchádzajúcej zlepšenej verzie. Na zabránenie konfliktov pri väčších zmenách je možné si určitú časť poznámok na týždeň rezervovať e-mailom u vyučujúcej. Niektoré poznámky majú na konci časť TO DO, popisujúcu žiadané zmeny.

Pri existujúcich poznámkach môžete získať 1% za aktivitu za nájdenie a opravenie vecnej chyby (nie preklepu a pod., ale chyby v matematike alebo v kóde). Stačí napísať e-mail s popisom chyby, netreba posielať súbory. Limit je 2% na osobu a jednu prednášku. Každá oprava sa ráta iba prvému, kto ju pošle.

Sylaby k skúške v školskom roku 2012/13

Na skúške sa môže vyskytnúť ľubovoľné odprednášané učivo, s výnimkou detailov sekvenovacej technológie SOLiD a operácie select na prednáške z MIT. Väčšina z prednášaných algoritmov je aspoň v stručne popísaná v poznámkach, s nasledujúcimi výnimkami:

• Ukkonenov algoritmus na konštrukciu sufixového stromu je v poznámkach, ale tento rok sme ho nebrali, netreba ho teda vedieť
• Brali sme jednoduchý algoritmus na vyhľadávanie približných výskytov vzorky, ktorý pracuje v priemernom prípade v čase O(nk) (preskakuje niektoré časti tabuľky dyn. prog.).
• Nebrali sme zarovnania s dlhými inzerciami a deléciami, ani detaily programu BLAST z poznámok.
• Pri viacnásobných zarovnaniach sme brali iba sum-of-pairs ceny.
• Pri najkratšom spoločnom nadslove sme robili dôkaz aproximačného faktoru 3 pre maximalizáciu ušetrených znakov.
• Pri hľadaní motívov sme robili iba presné výskyty reťazca, consensus pattern problem a closest string problem.
• Z úsporných dátových štruktúr sme robili operáciu rank na bitových vektoroch, jej použitie na úspornú implementáciu binárneho stromu, počet binárnych stromov, wavelet tree a FM index