Opis
Projektowanie i analiza algorytmów związanych z tekstami i ciągami. Zasadniczym problemem jest zrozumienie struktury wielu skomplikowanych algorytmów oraz różnego typu technik algorytmicznych i struktur danych związanych z tekstami (drzewa sufiksowe, tablice sufiksowe, grafy podsłów). Klasyczne problemy algorytmiczne związane są z szukaniem (lub wykrywaniem) wzorca, regularnością i kompresją tekstów. Charakter przedmiotu jest przede wszystkim algorytmiczny, ale zawiera też skromny fragment kombinatoryki tekstów.
Autorzy
- Wojciech Rytter — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
- Bartosz Szreder — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki
Wymagania wstępne
- Wstęp do programowania
- Matematyka dyskretna
- Algorytmy i struktury danych
Zawartość
- Wprowadzenie do podstawowych własności tekstów
- prosta kombinatoryka okresowości
- przykłady ciekawych ciągów
- Algorytmy wyszukiwania dokładnych wystąpień wzorca
- algorytmy Morrisa-Pratta i Knutha-Morrisa-Pratta
- algorytmy z małą pamięcią
- Struktury danych reprezentujące zbiów wszystkich podsłów
- Drzewa sufiksowe
- Tablice sufiksowe
- Grafy podsłów
- Regularności w tekstach
- Algorytmy aproksymacyjnego dopasowywania tekstu
- odległość edycyjna
- teksty z symbolem uniwersalnym (don't care)
- Równoważność kwadratowa tekstów
Literatura
Materiały elektroniczne