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.



Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
Úvod
Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
| Pravidlá
Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
|
Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
| Prezentácia
Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
| Poznámky
Notice: Undefined variable: title in /var/www/vyuka/vvt/shared.php on line 68
| Moodle

Poznámky z prednášok

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

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:

                                         
Notice: Undefined offset: 0 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 0 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 1 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 1 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 0 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 0 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 1 in /var/www/vyuka/vvt/poznamky.php on line 224

Notice: Undefined offset: 1 in /var/www/vyuka/vvt/poznamky.php on line 224
Týždeň 11.-17.2.2013
Streda Úvod, motivácia, hľadanie podľa kľúčových slov, invertovaný index, prienik utriedených polí a doubling search
  Prezentácia:PDF, 33 Kb ]
Štvrtok Lexikografické stromy, invertovaný index, triviálny algoritmus na hľadanie vzorky v texte a jeho priemerný prípad
  Prezentácia:PDF, 43 Kb ]
Týždeň 18.-24.2.2013
Streda Konečné automaty, Morris-Pratt
  Prezentácia:PDF, 61 Kb ]
Štvrtok Knuth-Morris-Pratt a jeho analýza
  Prezentácia:PDF, 66 Kb ]
Týždeň 25.2.-3.3.2013
Streda Hľadanie viacerých vzoriek (Aho-Corasick), 2D problém (Baker-Bird), Boyer-Moore
  Prezentácia:PDF, 48 Kb ]
Štvrtok Boyer-Moore, Rabin-Karp, Shift-AND, BNDM, dolný odhad na počet porovnaní
  Prezentácia:PDF, 80 Kb ]
Týždeň 4.-10.3.2013
Streda Vyhľadávanie v komprimovaných súboroch
  Prezentácia:PDF, 59 Kb ]
Štvrtok Vyhľadávanie regulárnych výrazov, vzorky so žolíkmi
  Prezentácia:PDF, 36 Kb ]
Týždeň 11.-17.3.2013
Streda FFT, sufixové stromy
  Prezentácia:PDF, 45 Kb ]
Štvrtok Aplikácie sufixových stromov a lca
  Prezentácia:PDF, 43 Kb ]
Týždeň 18.-24.3.2013
Streda Najnižší spoločný predok, RMQ
  Prezentácia:PDF, 43 Kb ]
Štvrtok Použitie RMQ, sufixové polia a hľadanie vzorky v nich
  Prezentácia:PDF, 51 Kb ]
Týždeň 25.-30.3.2013
Streda Lineárna konštrukcia sufixových polí, výpočet LCP, lineárna konštrukcia sufixových stromov
  Prezentácia:PDF, 33 Kb ]
Štvrtok Veľká noc
Týždeň 1.-7.4.2013
Streda Burrows-Wheelerova transformácia, použitie na kompresiu, úsporné dátové štruktúry
  Prezentácia:PDF, 27 Kb ]
Štvrtok Úsporné dátové štruktúry: rank a select, wavelet tree, FM index
  Prezentácia:PDF, 21 Kb ]
Týždeň 8.-14.4.2013
Streda Úsporné dátové štruktúry: kompresia, binárny (lexikografický) strom
  Prezentácia:PDF, 46 Kb ]
Štvrtok Výpočet editačnej vzdialenosti, najdlhšia spoločná podpostupnosť
  Prezentácia:PDF, 62 Kb ]
Týždeň 15.-21.4.2013
Streda Editačná vzdialenosť v lineárnej pamäti, zrýchlenie výpočtu editačnej vzdialenosti (technika 4 Rusov), zrýchlenie pri malej vzdialenosti
  Prezentácia:PDF, 56 Kb ]
Štvrtok Prednáška zrušená
Týždeň 22.-28.4.2013
Streda Približné výskyty vzorky, lokálne podobnosti, bioinformatika
  Prezentácia:PDF, 97 Kb ]
Štvrtok Zostavovanie DNA sekvencií, najkratšie spoločné nadslovo
  Prezentácia:PDF, 321 Kb ]
Týždeň 29.4.-5.5.2013
Streda Sviatok
Štvrtok Viacnásobné zarovnanie, opakujúce sa sekvenčné motívy
  Prezentácia:PDF, 102 Kb ]
Týždeň 6.-12.5.2013
Streda Sviatok
Štvrtok Prezentácie
Týždeň 13.-19.5.2013
Streda Prezentácie
Štvrtok Prezentácie