Tematem wykładu będą aktualne zagadnienia i nowe rozwiązania z dziedziny
przetwarzania i przeszukiwania danych tekstowych. W dziedzinie tej można
znależć zarówno trudne i bardzo zaawansowane rozwiązania, jak i prostsze
koncepcyjnie, ale nadal bardzo pomysłowe i efektywne (także efektowne)
konstrukcje algorytmiczne. Wśród poruszanych tematów znajdą się:
* Analiza i zastosowania algorytmów wyszukiwania wzorca, w tym wyszukiwanie w tekście skompresowanym, filtrowanie, wyszukiwanie przybliżonych wystąpień wzorca.
* Problemy podobieństwa tekstów (wspólne podciągi, nadciągi, odległość edycyjna, dopasowanie).
* Struktury danych dla tekstów: drzewa i tablice sufiksowe oraz pliki odwrócone itp.
* Bazy danych tekstowych: struktury danych, problemy kompresji i wyszukiwania.
Polecana do przedmiotu literatura:
1. M.Crochemore, W.Rytter, "Jewels of Stringology"
2. ed. A.Apostolico, Z.Galil "Pattern Matching Algorithms"
3. M.Crochemore, Ch.Handcart, T.Lecroq "Algorithms on Strings
Wymagane przygotowanie do przedmiotu to znajomość tematyki z zakresu
algorytmów i struktury danych.
w semestrze zimowym 2015/16 konsultacje mam w terminach: wt. 11-12, cz. 11-12; w razie potrzeby można umówić się też na inny termin przez e-mail (generalnie preferuję wtorki i czwartki)
