Textual Information Systems

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

Předmět Textové informační systémy se zabývá zpracováním řetězců a posloupností a kompresí dat. Zpracování řetězců a posloupností, zvané též stringologie, je používáno v různých oblastech informatiky kontrolou pravopisu a získáváním dat počínaje a složitějšími úlohami jako zpracování řetězců DNA konče. V rámci předmětu je prezentováno mnoho algoritmů stringologie. V závěru jsou pak představeny některé základní algoritmy komprese dat.

Požadavky:

Osnova přednášek:

1. Vyhledávání v textu, základní pojmy, klasifikace vyhledávacích problémů.

2. Sousměrné vyhledávání, konečné automaty pro sousměrné vyhledávání.

3. Prefixové, sufixové a faktorové automaty.

4. Hranice, repetice a periody, základní pojmy, klasifikace vyhledávacích problémů.

5. Konečné automaty pro výpočet hranic a repetic.

6. Konečné automaty pro výpočet repetic a period.

7. Simulace vyhledávacích nedeterministických konečných automatů pomocí fail funkce.

8. Simulace pomocí vyhledávacích konečných automatů pomocí dynamického programování a bitového paralelismu.

9. Protisměrné vyhledávání jednoho vzorku.

10. Protisměrné vyhledávání množiny vzorků.

11. Statistické metody komprese dat.

12. Slovníkové metody komprese dat.

13. Kontextové metody komprese dat.

Osnova cvičení:

1. Konečné automaty a operace s nimi.

2. Acyklické konečné automaty pro konečné jazyky.

3. Vyhledávací nedeterministické konečné automaty pro sousměrné vyhledávání.

4. Deterministické vyhledávací automaty pro sousměrné vyhledávání.

5. Prefixové, suffixové a faktorové automaty.

6. Vyhledávání hranic a repetic.

7. Vyhledávání repetic a period.

8. Simulace vyhledávacích nedeterministických konečných automatů pomocí fail funkce.

9. Simulace pomocí vyhledávacích konečných automatů pomocí dynamického programování a bitového paralelismu.

10. Protisměrné vyhledávání jednoho vzorku.

11. Protisměrné vyhledávání množiny vzorků.

12. Statistické metody komprese dat.

13. Slovníkové metody komprese dat.

14. Kontextové metody komprese dat.

Cíle studia:

Studijní materiály:

Melichar, B.: Textové informační systémy. Praha, Vydavatelství ČVUT 1997.

Poznámka:

Předmět má stejnou náplň jako předmět 36TIS.

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ů: