Wykład 1. Liniowe algorytmy tekstowe

 Zagadnienia poruszone na wykładzie:

  • Prefikso-sufiksy i algorytm KMP w wersji z prostym dowodem i prostą implementacją.
  • Związki między prefikso-sufiksami, okresami a pierwiastkami słowa. Pierwiastek pierwotny słowa, jego wyznaczanie i właściwości.
  • Wyznaczanie najkrótszego szablonu słowa (słowa, którym można w całości pokryć dane słowo) w czasie O(n*log(n)).
  • Algorytm Manachera wyznaczania promieni palindromów parzystych.
  • Funkcja PREF -- jej wyznaczanie oraz szkic metody jej zastosowania do rozwiązania zadania "Prawie równoważne słowa".
  • Algorytmy tekstowe w zadaniach geometrycznych (badanie możliwości przekształcenia jednego zbioru punktów na drugi za pomocą algorytmu na równoważność cykliczną napisów, wyznaczanie osi symetrii wielokąta za pomocą algorytmu Manachera). Tego nie zdążyłem omówić na wykładzie, ale jest zawarte w notatkach.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 25.02.2008, 16:20-17:45.

Dostępne materiały: Nagrania, Notatki.