Prace magisterskie

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).

Dla ambitnych

Część tematów ma również wariant "dla ambitnych". Wykonanie tej części oznacza, iż uzyskane wyniki są publikowalne (na konferencji, w czasopiśmie) oraz mogę stanowić łądny wstęp do doktoratu.

Tematy

Implementacje algorytmów rozwiązujących równania słów z jedną zmienną

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. Z drugiej strony, nie wiadomo wciąż, jak wiele rozwiązań może mieć takie równanie: wciąż nie wiadomo, czy może ono mieć liczbę rozwiązań większą niż 2 (ale skończoną).

Implementacje algorytmów sprawdzających równość dwóch skompresowanych tekstów

Kompresja gramatykowa jest ciekawę z teoretycznego punktu widzenia formą kompresji. Niestety, skompresowana postać nie jest jednoznaczna, istnieją jednak liczne wielomianowe algorytmy sprawdzajace równość takich (lub podobnych) reprezentacji (1, 2, 3, 4, 5).

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.

Implementacje algorytmów aproksymacyjnych dla kompresji gramatykowej

W kompresji gramatykowej dane (rozumiane jako pojedyncze słowo) przdstawiane są jako gramatyka bezkontekstowa generująca język składający się z tego jednego słowa. W ogólności problem wyznaczenia rozmiaru najmniejszej takiej gramatyki jest NP-trudny, znane są jednak liczne algorytmy aproksymacyjne oraz heurystyczne dla tego problemu.

Praca polegałaby na zaimplementowaniu znanych algorytmów aproksymacyjnych (1, 2 3, 4), porównaniu ich czasu działania oraz rozmiaru generowanych gramatyk.