PředmětyPředměty(verze: 804)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Textové algoritmy - NTIN087
Anglický název: String Algorithms
Zajišťuje: Katedra softwaru a výuky informatiky (32-KSVI)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://ksvi.mff.cuni.cz/~dvorak/vyuka/NTIN087/
Garant: doc. RNDr. Tomáš Dvořák, CSc.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: T_KSVI (04.05.2015)

Přednáška podává přehled algoritmů a datových struktur pro efektivní vyhledávání vzorků a opakujících se částí textu s aplikacemi. • Úvod do stringologie • Datové struktury: sufixový strom a jeho varianty, sufixové pole • Přesné a přibližné vyhledávání vzorků v textu • Určování vzdálenosti slov a problém nejdelší společné podposloupnosti • Vyhledávání podle regulárních výrazů • Aplikace v bioinformatice a kompresi dat
Literatura -
Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (03.10.2015)

M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2014.

G. Navarro, M. Raffinot, Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences, Cambridge University Press, 2007.

W. Smyth, Computing Patterns in Strings, Addison Wesley, 2003.

D. Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.

Sylabus -
Poslední úprava: doc. RNDr. Tomáš Dvořák, CSc. (01.05.2015)

Úvod do stringologie

Datové struktury: sufixový strom a jeho varianty, sufixové pole

Přesné a přibližné vyhledávání vzorků v textu

Určování vzdálenosti slov a problém nejdelší společné podposloupnosti

Vyhledávání podle regulárních výrazů

Aplikace v bioinformatice a kompresi dat

Vstupní požadavky
Poslední úprava: T_KSVI (04.05.2015)

Knowledge at the level of the subjects Algorithms and Data Structures I and II, Automata and Grammars.

 
Univerzita Karlova | Informační systém UK