Poniżej możliwe tematy prac magisterskich wraz z krótkim omówieniem. Mogę też prowadzić prace pokrewne tematycznie. W przypadku zainteresowania proszę o kontakt (email lub osobiście).
W równaniach słów z jedną zmienną zainteresowani jesteśmy rozwiązaniem (w słowach nad ustalonym alfabetem Σ) równani postaci u = v, gdzie u oraz v są słowami nad alfabetem Σ ∪ {X}, gdzie X jest zmienną. Łatwo scharakteryzować rozwiązania tego równania, znanych jest też kilka algorytmów rozwiązywania takich równań. Pierwsze praca: czas działania n log n (1), odrobinę szybsza (2) i w pełni liniowa w ogólnym przypadku (3).
Praca polegałaby na zaimplementowaniu tych algorytmów oraz wykonaniu testów porównująych ich czasy działania. Zapewne wiązałoby sie to również z zaproponowaniem różnego rodzaju usprawnień tych algorytmów.
Dla ambitnych: algorytm liniowy działa w modelu RAM, nie wiadomo, czy jest możliwe poprawienie go tak, aby działał w prostszym modelu obliczeniowym.
Praca polegałaby na zaimplementowaniu kilku wybranych algorytmów i porównaniu ich czasów działania. Zapewne niezbędne będą różnego rodzaju optymalizacje podanych algorytmów.
Większość podanych algorytmów można rozszerzyć do wyszukiwania (skompresowanego) wzorca w (skompresowanym) tekście. Uwzględnienie tego wariantu w implementacji jest mile widziane, ale nie jest konieczne.
W równaniach słów zainteresowani jesteśmy rozwiązaniem (w słowach nad ustalonym alfabetem Σ) równania postaci u = v, gdzie u oraz v są słowami używającymi liter z Σ oraz zmiennych. Znany jest stosunkowo prosty algorytm rozwiazujący ten problem w pamięci wielomianowej.
Niestety, niewiele ze znanych algorytmów dla tego problemu zostało w pełni zaimplementowanych, mimo tego, że heurystyczne algorytmy są popularne i używane.
Praca polegałaby na implementacji tego algorytmu, w którymś z możliwych wariantów. Ze względu na to, żę problem jest dość znany, dobrze napisana i udokumentowana implementacja jest dobrą podstawą do publikacji konferencyjnej.