Algorytmy tekstowe

• Krotki opis przedmiotu.

• Co bylo dotychczas na wykladzie: rok 2019/20

• Co bylo na wykladzie, rok 2018/19

• Wstepna lista zagadnien na egzamin.

• Algorytmy tekstowe w odcinkach, pdf

• 2 robocze rozdzialy

Ksiazka "Text algorithms", dostepna za darmo tutaj
• Nowsza ksiazka "Jewels of stringology"

• Wybrane algorytmy tekstowe z Olimpiad Inf.

• Zbior zadan (niedokonczony) w pdf
• Algorytm konstrukcji gestych slow binarnych,
  z pracy: On the maximum number of distinct factors in a binary string,
  Graphs and Combinatorics 9 (1993), 197-200.

• Alternatywny draft algorytmu konstrukcji gestych slow binarnych,
  

• Zadania z egzaminu pisemnego 30. 01. 2010

• Pytania z egzaminu styczen 2011.

• Pytania z egzaminu styczen 2012.

• Zadania z egzaminu luty 2017.

• Zadania z egzaminu luty 2018.

• Zadania z egzaminu luty 2019.

• Graf podslow z egaminu styczen 2011.

• Cztery twierdzenia.

• Dowod twierdzenia Fredricksona-Maiorany o ciagach de Bruijna

• Prosty algorytm na maksymalny sufiks

• Program Piotra Wisniewskiego na maksymalny sufiks

• Program Piotra Wisniewskiego na rownowaznosc cykliczna

• Przyklad grafu de Bruijna rzedu 3

• Algorytm Prefer-Opposite generowania ciagu de Bruijna pdf
• Dowod poprawnosci algorytmu PreferOpposite

• Algorytm Prefer-Opposite generowania ciagu de Bruijna pdf

• Dowod twierdzenia o rownowaznosci kwadratowej tekstow.

• Zbior zaimplementowanych niektorych algorytmow tekstowych

• Skrypt J. Karhumakiego "Kombinatoryka tekstow" (dostepny za darmo)

• Skrypt J. Berstela " Combinatorics on Words: Christoffel Words and Repetition in Words " (dostepny za darmo)

• Algorytm GREEDY dla najkrotszego superstringu w czasie liniowym (wersja Tomasza Kociumaki) w ps

• Oszacowanie liczby maksymalnych powtorzen (run'ow) w ps

• Grafy podslow dla slow Fibonacciego w pdf

• Grafy podslow dla slow Sturma w pdf

• Grafy podslow dla slow Thue-Morse'a w pdf

• Zastosowania run'ow: lokalne okresy, liczenie squar'ow w ps

• Szybkie testowanie rownowaznosci kwadratowej slow w ps

• Proste algorytmy n log n dla squar'ow i rn'ow w ps

• (Praca mgr J. Radoszewskiego) Ciagi de Bruijna w pdf
• Generacja slow z duza iloscia podslow (Praca mgr Damiana Repke) w pdf
• Kompresja BWT szczegolnych slow (Praca mgr B. Romanskiego) w pdf

• Automaty Boyer-Moore'a (Praca mgr ) W. Tyczynskiego) w pdf