Tematem wykładu będą algorytmy i struktury danych służące do przetwarzania i
przeszukiwania danych tekstowych. W programie znajdą się zarówno klasyczne
rozwiązania opracowane już w latach osiemdziesiątych, jak i takie, które są
znane dopiero od kilku lat. Wiele z nich będzie, mimo prostoty koncepcyjnej,
bardzo pomysłowych. Część wykładu poświęcimy na przedstawienie ogólnych
struktur danych, które mogą znaleźć zastosowanie także w problemach
niezwiązanych z tekstami.
**Program:**
1. Analiza i zastosowania algorytmów wyszukiwania wzorca: dokładnego, z niezgodnościami, z błędami.
2. Problemy podobieństwa tekstów (wspólne podciągi, nadciągi, odległość edycyjna, dopasowanie).
3. Struktury danych dla tekstów: drzewa i tablice sufiksowe.
4. Zwięzłe struktury danych i ich zastosowanie w strukturach danych dla tekstów.
5. Problemy kompresji i wyszukiwania wzorca w skompresowanych tekstach.
6. Conditional lower bounds dla problemów na tekstach.
**Wymagania:** zalecane zaliczone Algorytmy i struktury danych lub doświadczenie zdobyte w startach w olimpiadzie informatycznej (i podobnych imprezach).
