| |
Textové algoritmy (36TAL)
předmět denního studia, v tomto semestru se nevyučuje
Rozsah (přednášky + cvičení): 2+2
Zakončení: Zápočet, zkouška
Anotace:
| |
Text je nejjednodušší a přirozená reprezentace informací v různých oblastech. Text je lineární posloupnost symbolů z nějaké abecedy. Manipulace s textem se používá v mnoha aplikačních oblastech: zpracování textu v přirozených a formálních jazycích, studium posloupností v molekulární biologii, analýza hudby atd. Hlavními problémy, kterými se zabývá tento předmět, je vyhledávání vzorků a opakujících se částí textu. V obou případech se jedná jak o přesné vyhledávání, tak o přibližné vyhledávání. Těmto problémům je věnována hlavní pozornost v přednáškách i cvičeních. Hlavním formálním systémem, který je pro popis algoritmů použit, jsou konečné automaty. Ty se ukázaly jako vynikající nástroj nejen pro pochopení, ale i pro řešení mnoha problémů zpracování textu.
|
Osnova:
| |
- Textové systémy, základní pojmy, klasifikace vyhledávacích problémů.
- Sousměrné vyhledávání, modely vyhledávacích algoritmů.
- Nedeterministické vyhledávací automaty.
- Simulace nedeterministických vyhledávacích automatů, bitový paralelismus, dynamické programování.
- Prefixové a suffixové automaty.
- Faktorové automaty, faktor oracle, sufix oracle.
- Hranice a periody v textu.
- Repetice v textu, přesné a přibližné.
- Simulace nedeterministických vyhledávacích automatů, fail funkce, MP a KMP algoritmy.
- Simulace nedeterministických vyhledávacích algoritmů, fail funkce, AC algoritmus.
- Protisměrné vyhledávání jednoho vzorku, BM algoritmus.
- Protisměrné vyhledávání množiny vzorků, CW algoritmus.
- Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání ve vícerozměrném textu).
- Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání v komprimovaném textu).
|
Osnova cvičení:
| |
- Konečné automaty, základní operace s konečnými automaty.
- Formulace základních vyhledávacích problémů pro přesné a přibližné vyhledávání.
- Nedeterministické konečné automaty jako modely pro vyhledávání v textu.
- Deterministické vyhledávací automaty a jejich složitost.
- Simulace vyhledávacích automatů, bitový paralelismus, dynamické programování.
- Konstrukce prefixových a sufixových automatů.
- Konstrukce faktorových automatů, faktor a sufix oracle automatů.
- Hledání hranic a period v textu.
- Hledání přesných a přibližných repetic v textu.
- Simulace vyhledávacích automatů, MP a KMP algoritmy.
- Simulace vyhledávacích algoritmů, AC algoritmus.
- Protisměrné vyhledávání, BM algoritmus.
- Protisměrné vyhledávání, CW algoritmus.
- Zápočet.
|
Literatura:
| |
- Melichar, B., Holub, J., Polcar, T.: Text searching algorithms. Volume I and II, Učební text pro přednášky.
- Melichar, B. a kol.: Text searching algorithms. Seminars. Sbírka příkladů pro cvičení.
|
|
 
|
