Co bylo
Algorytmy tekstowe 2018/19
Co bylo na wykladzie:
Wyklad 1
Nieformalna dyskusja tego co bedzie na wykladach.
Lemat o okresowosci - dowod poprzez algorytm Euklidesa.
Slowa pierwotne.
Szczegolne klasy slow: slowa Fibonacciego.
Tablica prefikso-sufiksow
Zastosowanie do zadania ''Szablon''
Wyklad 2
Tablica PREF prefikso-prefiksow
Zastosowanie tej tablicy do zadania ''Szablon''
Algorytmy MP i KMP
Wersja on-line algorytmu KMP, delay=O(log m)
Tablica silnych prefikso-sufiksow
Wersja algorytmu MP wykonujaca co najwyzej 3/2 n porownan
Wyklad 3
Algorytm BM (algorytm Boyera-Moore'a)
Dowod liniowego czasu algorytmu BM
Wyklad 4
Algorytm Max-Suffix Matching: czas O(n), pamiec O(1)
Wyklad 5
Algorytm ''TwoWay String Matching''
Lokalne okresy
Twierdzenie o faktoryzacji krytycznej
Wyklad 6
Slowa de Bruijna: algorytmy prefer-zero, prefer-opposite
Slowa Lyndona - generacja leksykograficzna
Algorytm FM generacji ciagow de Bruijna
Wyklad 7
Dowod poprawnosci algorytmu FM
Konstrukcja slow gestych.
Wyklad 8
Konstrukcja slow super-gestych
Prosty algorytm Sawady generacji slow de Bruijna
korzystajacy ze slow cyklicznie minimalnych
Wyklad 9
Najkrotsze superslowa dla zbioru skroconych permutacji
Cykle Eulera w grafach Jacksona
Wlasnosci slow Thue-Morse'a
Konstrukcje dlugich slow bezkwadratowych
Wyklad 10
Slownik podslow bazowych (DBF).
Zastosowanie do testowania kwadratow w slowach.
Wyklad 11
Drzewa sufiksowe. Zastosowania.
Wstep do algorytmu McCreighta.
Wyklad 12
Algorytmy McCreighta i Ukkonena
Wyklad 13
Tablice sufiksowe.
Tablica sufiksowa dla slow Fibonacciego.
Przyklady tablic sufiksowych dla slow Thue Morse'a
Liczenie tablicy lcp
Tablice sufiksowe --> drzewa podslow
Wyklad 14
Zastosowanie drzew sufiksowych do konstrukcji nadslowa (superstringu)
Zastosowanie drzew sufiksowych do kompresji Lempel-Ziva
Zastosowanie faktoryzacji LZ do liniowego szukania kwadratow w slowach