08. 10. 2010
Nieformalna dyskusja tego co bedzie na wykladach.
Lemat o okresowosci - dowod poprzez algorytm Euklidesa.
Silny lemat o okresowosci: dowod syntaktyczny i grafowy.
Slowa pierwotne.
Szczegolne klasy slow: slowa Fibonacciego.
Zwiazek z gra Wythoffa.
Gestosc slow w nieskonczonym slowie
Fib. wynosi .
Dowod tego ze slowo nieskonczone o mniejszej gestosci
g(k) jest okresowe od pewnego miejsca.
Algorytm sprawdzania rownowaznosci kwadratowej slow.
15. 10. 2010
Algorytm dla zadania Slowa - metoda odkodowywania.
Tablica P prefikso-sufiksow (psufiksow): obliczanie, wlasnosci.
Zastosowanie psufiksow w zadaniu Szablon.
Zastosowanie tablicy psufiksow w zadaniach Palindromy, Okresy
Zastosowanie do obliczania pierwiastka slowa.
22. 10. 2010
Maksymalny sufiks - modyfikacja liczenia tablicy psufiksow.
Algorytm MP (Morrisa-Pratta) i KMP (Knutha-Morrisa-Pratta)
Wersja on-line KMP z opoznieniem logarytmicznym.
Wersja real-time (z opoznieniem stalym)
Oszczedna wersja (3/2 n porownan symboli).
29. 10. 2010
Algorytm BM (algorytm Boyera-Moore'a)
Dowod liniowego czasu algorytmu BM
Algorytm Max-Suffix Matching: czas O(n), pamiec O(1)
5. 11. 2010
Algorytm TwoWay String Matching
Lokalne okresy
Twierdzenie o faktoryzacji krytycznej
Slowa Lyndona - generacja leksykograficzna
Algorytm FM generacji ciagow de Bruijna
12. 11. 2010
Dowód twierdzenia o faktoryzacji
Ciągi de Bruijna - naiwny algorytm generacji
ciągu lexmin, związek z cyklami Eulera w grafie de Bruijna
związek z drzewami rpzinającymi
liczenie wzoru na liczbę binarnych ciągów liniowych de Bruijna
za pomocą wyznacznika: pierwiastek kwadratowy z
19. 11. 2010
Dowod poprawnosci algorytmu Fredricksona-Maiorany ciagow de Bruijna
26. 11. 2010
Slownik podslow bazowych.
Algorytm konstrukcji drzew sufiksowych w czasie O(n log n) korzystajac
ze slownika podslow bazowych
tablice sufiksowe i tablica lcp
obliczanie tablicy lcp w czasie liniowym
liniowy algorytm konstrukcji drzewa sufiksowego za
pomoca tablicy sufiksowej i lcp
algorytm liniowy Karkaina-Sandersa (KS) liczenia tablicy sufisksowej
liczenie najkrotszego slabego szablonu (seed) korzystajac z drzew suf.
technika podzialowa (partitioning technique)
liczenie slabego szablonu: technika podzialowa c.d.
Algorytm Ukkonena dla drzew sufiksowych.
Wlanosci grafow podslow (dawg): liczba wezlow i krawdedzi.
Algorytm liniowy on-line liczenia grafu podslow.
Algorytm on-line na grafy podslow c.d.
Skompresowane grafy podslow (cdawg)
Struktura grafow podslow dla slow STurma
Wlasnosci slow Thue-Morse'a.
Grafy podslow dla slow Thue-Morse'a.
Faktoryzacja Lempel-Ziva (LZ-factorization)
Obliczanie faktoryzacji w czasie liniowym
Algorytmy na testowanie czy slowo jest square-free
maksymalne powtorzenia (runs)
liczenie lokalnych okresow za pomoca maksymalnych powt.
liczenie liczby squarow za pomoca maks. powt.