Stringologie

Garant předmětu:

Jan Holub

Přednášející:

Jan Holub

Cvičící:

Jan Holub

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Algoritmy na zpracování a vyhledávání v textu.

Prezentované postupy jsou zalozeny na principu konecnych automatu.

Postupy na zpracování komprimovaného textu a paralelních algoritmu.

Požadavky:

Osnova přednášek:

1. Obecné principy zpracování a vyhledávání v textu.

2. Pouzití konecnych automatu jako základních modelu textovych algoritmu.

3. Pouzití konecnych automatu jako indexovacích nástroju.

4. Vyhledávání pravidelností v textu (repetice, periody, hranice, .).

5. Metody zalozené na simulaci konecnych automatu.

6. Vyhledávání v komprimovaném textu.

7. Paralelní metody ve stringologii.

8. Hledání nejdelsích spolecnych faktoru a podposloupností v mnozine retezu.

9. Pokrytí retezu, vytvorení superretezce

10. Pouzití textovych algoritmu pro slozitejsí datové struktury (stromy, matice, .)

Osnova cvičení:

Cíle studia:

Studijní materiály:

1. Crochemore, M., Rytter, W.: Jewels of stringology. World Scientific Publishing, 2003.

2. Melichar, B., Holub, J. Polcar, T.: Text searching algorithms. http://www.stringology.org/athens/, 2005

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Informatika (doktorská) (povinně volitelný předmět)
• Informatika (povinně volitelný předmět)