Doktoraty (WMiI)
Permanent URI for this collection
Browse
Browsing Doktoraty (WMiI) by Subject "algorithms"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów(2010-06-11T12:13:03Z) Kalkowski, Maciej; Karoński, Michał. PromotorCelem rozprawy jest przedstawienie nowych metod rozwiązywania problemów globalnej i lokalnej siły nieregularności grafów. Powyższe dwa zagadnienia są rozpatrzone zarówno dla grafów ważonych, jak i totalnie ważonych. Wszystkie przedstawione metody i dowody mają charakter algorytmów wyznaczających wartości funkcji ważących. Rozdział drugi składa się z dwóch części i dotyczy lokalnego rozróżniania wierzchołków. W pierwszej, zagadnienie omówione jest dla totalnego ważenia. Wprowadzone są dwa twierdzenia, dowodzące, że istnieją lokalnie nieregularne 5-totalne-ważenie oraz 3-totalne-ważenie. W drugiej części rozdziału rozważony jest problem rozróżniania wierzchołków dla ważenia krawędzi nawiązujący do hipotezy 1-2-3. Wprowadzone są trzy nowe metody rozwiązania problemu, które wykazują, że możliwe są konstrukcje lokalnie nieregularnych 10-ważenia, 6-ważenia i 5-ważenia grafu. Rozdział trzeci dotyczy globalnego rozróżniania wierzchołków i również składa się z dwóch części. W pierwszej, zagadnienie rozpatrzone jest dla ważenia krawędzi grafu. Opisana jest metoda konstrukcji globalnie nieregularnego 6 ⌈n/δ⌉ -ważenia grafu. W drugiej części rozdziału omówione jest globalne rozróżnianie wierzchołków dla totalnego ważenia grafów. Wykazana jest konstrukcja globalnie nieregularnego (3⌈n/δ ⌉+1)-totalnego-ważenia. W ostatnim rozdziale przedstawione są pokrewne problemy rozróżniania wierzchołków.Item Rozproszone algorytmy aproksymacyjne w analizie własności grafowych(2010-06-14T09:53:39Z) Wawrzyniak, Wojciech; Karoński, Michał. PromotorPrzez ostatnie kilkanaście lat zauważyć można znaczący wzrost zainteresowania algorytmami rozproszonymi. Powodem jest zastosowanie ich w wielu praktycznych zagadnieniach informatyki. Celem rozprawy doktorskiej jest przedstawienie i omówienie deterministycznych rozproszonych algorytmów aproksymacyjnych rozwiązujących podstawowe problemy grafowe, takie jak konstrukcja: minimalnego zbioru dominującego, największego zbioru niezależnego, minimalnego pokrycia wierzchołkowego, największego skojarzenia oraz pakowania grafów. Modelem obliczeń przeze mnie rozważanym jest tzw. model Local. W Rozdziale 2 opisany jest algorytm rozwiązujący problem pakowania grafu G=(V,E) w planarnym grafie H. Zwracane rozwiązanie jest dowolnie dobrą aproksymacją problemu, a złożoność czasowa algorytmu wynosi O(logk|V|). Z praktycznego punktu widzenia zastosowanie znajdują również algorytmy działające w znacząco krótszym czasie, jednak o dużo gorszym współczynniku aproksymacji. Podejście to przedstawiono w Rozdziale 3, gdzie opisane zostały algorytmy działające w czasie O(1). Konstruują one (2 + ε)-aproksymację minimalnego pokrycia wierzchołkowego, w grafach o ograniczonym stopniu, o ograniczonej lesistości. W Rozdziale 4 opisane zostały algorytmy działające w czasie O(log*n). Zwracają one przybliżone rozwiązanie problemów: minimalnego zbioru dominującego, największego skojarzenia oraz największego ważonego zbioru niezależnego w grafach planarnych. Współczynnik aproksymacji wynosi (1 ± ε). Ponadto z twierdzenia udowodnionego w ostatnim Rozdziale 5 wynika, że algorytmy te są optymalne.Item Wydajne algorytmy parsowania dla języków o szyku swobodnym(2014-05-30) Skórzewski, Paweł; Jassem, Krzysztof. PromotorNiniejsza rozprawa stawia sobie za cel zbadanie pewnego problemu teoretycznego z zakresu gramatyk probabilistycznych oraz optymalizację związanego z nim problemu implementacyjnego. Część teoretyczna poświęcona jest zagadnieniom formalnego opisu języków o szyku swobodnym i algorytmom ich analizy składniowej. Rozważam w niej sposoby wykorzystywania gramatyk probabilistycznych do opisu języków swobodnego szyku. Definiuję autorski formalizm probabilistycznych gramatyk binarnych generujących drzewa (PTgBG), który stanowi probabilistyczne rozszerzenie formalizmu TgBG (gramatyk binarnych generujących drzewa). Prezentuję również parser wykorzystujący ten formalizm. Z drugiej strony celem niniejszej pracy jest zbadanie, w jaki sposób implementacja algorytmu parsowania wpływa na jego wydajność. W szczególności, przedstawiam proces adaptacji parsera do systemu przetwarzania języka naturalnego. Analizuję napotkane trudności i ewaluuję wydajność na poszczególnych etapach optymalizacji. Przedstawiam też wnioski płynące z tego procesu.