Algorytmy tekstowe

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
    • powtórzenia
    • kompresja LZ
  • Algorytmy aproksymacyjnego dopasowywania tekstu
    • odległość edycyjna
    • teksty z symbolem uniwersalnym (don't care)
  • Równoważność kwadratowa tekstów

Literatura

Materiały elektroniczne