Start
Badania
Studenci
Konkursy
Galeria
Gry/projekty
Linki
Kontakt
Historia
|
Poniżej kilka tematów, które moim zdaniem mogą nadawać się na pracę magisterską.
Uwaga: niektóre cytowane prace nie są jeszcze opublikowane -- proszę skontaktować się ze mną, by uzyskać dostęp do wstępnych wersji. Liczenie słów w języku regularnymNiech Σ=(a1,a2,...,ak) będzie ustalonym alfabetem. W pracy [1] pokazaliśmy niezależnie z Anthonym Widjaja To, że następujący problem jest w P:DANE: automat niedeterministyczny A; liczby n1,n2,...,nk zapisane binarnie WYNIK: Czy język L(A) zawiera słowo mające dokładnie ni wystąpień litery ai? Narzuca się naturalne pytanie, ile jest takich słów? Warto tutaj zauważyć, że słów tych może być bardzo dużo (liczba o zapisie binarnym długości wykładniczej względem ni), także nie możemy spodziewać się algorytmu dającego dokładny wynik w wielomianowym czasie. Można rozważać liczenie do pewnego progu, modulo p, obliczenie przybliżone, albo algorytm wielomianowy w zależności od długości wyniku. Uwagi: Oryginalny problem był otwarty przez długi czas, także problem liczenia również może być trudny. Literatura: [1] Complexity of Problems for Parikh Images of Automata. Eryk Kopczyński, Anthony Widjaja To. LICS '2010, pages 80--89, 2010 25th Annual IEEE Symposium on Logic in Computer Science. PDF [2] Complexity of Problems for Commutative Grammars. Eryk Kopczyński, 2010. Preprint at arXiv:1003.4105v1. [3] Complexity of Problems of Commutative Grammars. Eryk Kopczyński. Submitted to a journal. In progress. Spektra a własności grafoweNiech φ będzie formułą logiki pierwszego rzędu. Spektrum φ, oznaczanym spec(φ), nazywamy zbiór takich liczb naturalnych n, że φ ma model, którego uniwersum ma moc n. Chcemy scharakteryzować podzbiory zbioru liczb naturalnych będące spektrami jakiejś formuły. Klasyczne wyniki (Fagin '74, Jones & Selman '74) wiążą spektra z teorią złożoności: podzbiór A⊂N jest spektrum wtedy i tylko wtedy, gdy zbiór A (rozumiany jako zbiór zapisów binarnych liczb) jest w klasie złożoności NE (równoważnie w NP, jeśli liczby zapisujemy unarnie).Ostatnio gorącym tematem badań są własności logiczne grafów o prostej strukturze, takich jak na przykład grafy planarne. Interesujące zatem jest badanie problemu spektrum w kontekście takich grafów. W pracy [1] z Anujem Dawarem pokazaliśmy odpowiednią teoriozłożonościową charakteryzację spektrum, jeśli rozważamy tylko modele będące grafami planarnymi (zbiory zapisów binarnych rozpoznawane przez maszyny działające w czasie trochę mniejszym niż O(N) (gdzie N to zadana liczba, nie długość jej zapisu) są tak zdefiniowanymi spektrami planarnymi; spektra planarne są rozpoznawane w czasie trochę większym niż O(N)). Proponuję zbadać jeden z następujących problemów: 1) W pracy [1] pokazaliśmy, że jeśli maszyna rozpoznająca zbiór A działa na zapisie binarnym liczby N w pamięci logarytmicznej (czyli proporcjonalnej do długości zapisu liczby) i w czasie N1-ε, to istnieje formuła, której spektrum jest równe A i wszystkie modele φ są grafami planarnymi. W tym wyniku rzuca się w oczy mała ilość dostępnej pamięci. Czy da się tak symulować maszynę formułą, by ilość dostępnej pamięci była większa? 2) Grafy planarne to klasa grafów z zabronionymi minorami K3,3 i K5. Co z innymi klasami grafów zamkniętymi na minory? Uwagi: Nie jestem specjalistą od minorów, także magistrant zainteresowany problemem (2) będzie musiał zapoznać się z tematem samodzielnie. Problemy mogą być trudne, ale cała dziedzina jest dość szeroka, także powinno dać się w niej znaleĽć coś odpowiedniego (z surveyu [2] kilka problemów udało nam się rozwiązać). Literatura: [1] Bounded degree and planar spectra. Anuj Dawar, Eryk Kopczyński. In progress. [2] Fifty years of the spectrum problem: survey and new results. A. Durand, N.D. Jones, J.A. Makowsky, M. More. PDF [3] Spectra of formulae with restrictions. Eryk Kopczyński. A talk from the DMV-PTM meeting. PDF |
Start
Research
Students
Contests
Gallery
Games & projects
Links
Contact
History