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 2011 do 2014
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• 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

čeština

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

angličtina

Poslední úprava: T_KSVI (23.05.2006)

A survey of algorithms and data structures for efficient computation of patterns in strings with applications.

Literatura

čeština

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

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

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

čeština

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

Úvod do stringologie.

Sufixové datové struktury.

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: bioinformatika, komprese dat, porovnávání obrazu a zvuku.

angličtina

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

Introduction to string algorithms

Data structures: suffix tree and its variants, suffix array

Exact and approximate pattern matching

String distance and the longest common subsequence

Regular expression matching

Applications in bioinformatics and data compression

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.