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 [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, anglič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

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

Poslední úprava: T_KSVI (04.05.2015)

angličtina

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

Poslední úprava: T_KSVI (23.05.2006)

Podmínky zakončení předmětu

čeština

Předmět je zakončen ústní zkouškou. Otázky, které jsou u zkoušky pokládány, čerpají z témat, uvedených v sylabu předmětu, a to v rozsahu, v němž jsou tato témata probírána na přednášce.

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

angličtina

The course is concluded with an oral exam. Questions posed in the exam explore the topics included in the syllabus to the extent that these topics are covered in lectures.

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

Literatura

čeština

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

M. Crochemore, T. Lecroq, W. Rytter, 
125 Problems in Text Algorithms, 
Cambridge University Press, 2021

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.

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

Sylabus

čeština

Úvod do stringologie

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

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

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

angličtina

Introduction to string algorithms

Data structures: suffix tree and its variants, suffix array, suffix automata

Exact and approximate pattern matching

String distance and the longest common subsequence

Regular expression matching

Applications in bioinformatics and data compression

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

Vstupní požadavky

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

Poslední úprava: T_KSVI (04.05.2015)