Stringologie

Přednášející:

Bořivoj Melichar (gar.)

Cvičící:

Bořivoj Melichar (gar.)

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:

Ukázat metody konstrukce algoritmu pro resení úloh zpracování retezcu. Základním teoretickym základem je teorie konecnych automatu. Cely predmet je koncipován tak, ze jsou prezentovány postupy tvorby algoritmu na trídy problému, kterych jsou v jednotlivych prípadech stovky.

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 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Informatika (VO)