Textové algoritmy
Kód | Zakončení | Kredity | Rozsah |
---|---|---|---|
36TAL | Z,ZK | 4 | 2+2s |
- Předmět nesmí být zapsán současně s:
- Textové informační systémy (36TIS)
- Předmět je náhradou za:
- Textové algoritmy (X36TAL)
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- katedra počítačů
- 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.
- Požadavky:
- Osnova přednášek:
-
1. Textové systémy, základní pojmy, klasifikace vyhledávacích problémů.
2. Sousměrné vyhledávání, modely vyhledávacích algoritmů.
3. Nedeterministické vyhledávací automaty.
4. Simulace nedeterministických vyhledávacích automatů, bitový paralelismus, dynamické programování.
5. Prefixové a suffixové automaty.
6. Faktorové automaty, faktor oracle, sufix oracle.
7. Hranice a periody v textu.
8. Repetice v textu, přesné a přibližné.
9. Simulace nedeterministických vyhledávacích automatů, fail funkce, MP a KMP algoritmy.
10. Simulace nedeterministických vyhledávacích algoritmů, fail funkce, AC algoritmus.
11. Protisměrné vyhledávání jednoho vzorku, BM algoritmus.
12. Protisměrné vyhledávání množiny vzorků, CW algoritmus.
13. Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání ve vícerozměrném textu).
14. Aktuální výsledky v oblasti vyhledávání v textu (např. vyhledávání v komprimovaném textu).
- Osnova cvičení:
-
1. Konečné automaty, základní operace s konečnými automaty.
2. Formulace základních vyhledávacích problémů pro přesné a přibližné vyhledávání.
3. Nedeterministické konečné automaty jako modely pro vyhledávání v textu.
4. Deterministické vyhledávací automaty a jejich složitost.
5. Simulace vyhledávacích automatů, bitový paralelismus, dynamické programování.
6. Konstrukce prefixových a sufixových automatů.
7. Konstrukce faktorových automatů, faktor a sufix oracle automatů.
8. Hledání hranic a period v textu.
9. Hledání přesných a přibližných repetic v textu.
10. Simulace vyhledávacích automatů, MP a KMP algoritmy.
11. Simulace vyhledávacích algoritmů, AC algoritmus.
12. Protisměrné vyhledávání, BM algoritmus.
13. Protisměrné vyhledávání, CW algoritmus.
14. Zápočet.
- Cíle studia:
- Studijní materiály:
-
1. Melichar, B., Holub, J., Polcar, T.: Text searching algorithms. Volume I and II, Učební text pro přednášky.
2. Melichar, B. a kol.: Text searching algorithms. Seminars. Sbírka příkladů pro cvičení.
- Poznámka:
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů: