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ć ładny 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.

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.

Implementacja algorytmu dla równań słów

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 &Sigma 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 napisan i udokumentowana implementacja jest dobrą podstawą do publikacji konferencyjnej.