Wyszukiwarka
Filtry
wszystkich: 76
wybranych: 72
-
Katalog
Filtry wybranego katalogu
Wyniki wyszukiwania dla: ZŁOŻONOŚĆ OBLICZENIOWA
-
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
PublikacjaW pracy rozważano złożoność obliczeniową problemu szeregowania w cylindrycznym systemie przepływowym. Skonstruowano algorytm wielomianowy dla problemu dwumaszynowego oraz wykazano, iż zagadnienie staje się NP-trudne przy szeregowaniu na trzech procesorach, bądź na dwóch, przy dodatkowym wymuszeniu braku obustronnych przestojów.
-
The complexity of list ranking of trees
PublikacjaUporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
T-coloring of graphs.
PublikacjaNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
Kolorowanie grafów obciążonych i jego zastosowanie w problemie przydziału częstotliwości
PublikacjaReferat omawia jeden z modeli dla problemu przydziału częstotliwości, oparty o kolorowanie grafów obciążonych. Podana została złożoność obliczeniowa modelu i wielomianowy algorytm 4-kolorowania grafów w tym modelu.
-
Cykliczny system otwarty i cyrkularne kolorowanie grafów.
PublikacjaW pracy rozważany jest cykliczny system otwarty - modyfikacja otwartego systemu procesów dedykowanych polegająca na założeniu, że praca jest wykonywana w ruchu ciągłym, czyli kolejne cykle pracy wykonywane są bezpośrednio po sobie. Rozważana jest złożoność obliczeniowa problemów związanych z układaniem harmonogramu w systemach tego typu.
-
Fast Distance Vector Field Extraction for Facial Feature Detection
PublikacjaPraca dotyczy metody lokalizowania cech twarzy z wykorzystaniem wektorowych pól odległości (DVF), zaproponowanej przez Asteriadisa. Zawiera skrótowy opis tej koncepcji oraz prezentuje ulepszenia wprowadzone przez autorów do oryginalnego rozwiązania. Główną zaletą wprowadzonych zmian jest znacznie zredukowana złożoność obliczeniowa algorytmu, jak również zwiększona precyzja wektorowego pola odległości wyznaczanego w wyniku jego...
-
Determining the optimal course alteration maneouvre in a multi-target encounter situation for a given ship domain model
PublikacjaW artykulee przedstawiono nową deterministyczną metodę wyznaczania niezbędnego manewru kursem dla sytuacji spotkania z wieloma obiektami obcymi i dla dowolnej zadanej domeny. Jej prostota i niska złożoność obliczeniowa czynią ją dobrą alternatywą dla obecnie stosowanych metod. Główny algorytm został przedstawiony wprost, tak aby mógł być bezpośrednio zastosowany w pokładowych systemach antykolizyjnych lub w systemach VTS.
-
Metoda szybkiego wyznaczania par węzłowo rozłącznych tras dla ochrony transmisji unicast
PublikacjaW celu ochrony transmisji przed awarią węzłów/łączy wykorzystuje się alternatywne trasy transmisji. Jednakże, złożoność obliczeniowa dostępnych algorytmów doboru tras rozłącznych często istotnie wstrzymuje producentów sprzętu od implementacji tychże rozwiązań. W pracy prezentujemy nowe podejście wyznaczania par rozłącznych tras bazujące na transformacji grafu sieci w meta strukturę. Wyniki badań odnośnie czasu wyznaczania tras...
-
Direct spectrum detection based on Bayesian approach
PublikacjaThe paper investigates the Bayesian framework's performance for a direct detection of spectrum parameters from the compressive measurements. The reconstruction signal stage is eliminated in by the Bayesian Compressive Sensing algorithm, which causes that the computational complexity and processing time are extremely reduced. The computational efficiency of the presented procedure is significantly...
-
Analiza tolerancji filtrów Gm-C czasu ciągłego.
PublikacjaW pracy przedstawiono efektywną metodę analizy tolerancji dla dowolnych filtrów Gm-C. Korzystając z ogólnego modelu filtrów tej klasy oraz jego opisu macierzowego wyprowadzono formuły pozwalające na wyznaczanie zniekształceń charakterystyk częstotliwościowych filtrów spowodowanych rozrzutem rzeczywistych wartości elementów filtru względem wartości nominalnych. Złożoność obliczeniowa związana z ewaluacją tych formuł jest...
-
Numerical Algorithms of Planning Safe Ship Trajectories for ARPA Systems
PublikacjaGłównym celem pracy było zaprojektowanie metody znajdowania bezpiecznych trajektorii statków, która byłaby prosta w implementacji, szybka (niska złożoność obliczeniowa)i deterministyczna, elastyczna (umożliwiałaby zastosowanie dowolnej domeny). Aby zrealizować cel należało zbadać bieżący stan wiedzy w dziedzinie,zaprojektować nową metodę, zaimplementować metodę (wraz ze wszystkimi niezbędnymi algorytmami) w środowisku programistycznym...
-
Wielkogabarytowe hydrodynamiczne łożyska wzdłużne
PublikacjaW monografii przedstawiono problemy konstrukcyjne i badawcze hydrodynamicznych łożysk wzdłużnych o dużych średnicach. Łożyska takie stanowią istotne i niezwykle odpowiedzialne podzespoły hydrogeneratorów elektrowni wodnych. Z uwagi na rozmiary (średnice przekraczają niekiedy 5 metrów) i złożoność zjawisk łożyska te wymagają specjalnej postaci konstrukcyjnej, a ich dokładna analiza obliczeniowa przysparza wiele problemów. Dodatkowo...
-
Estymacja współrzędnych kątowych w radarze trójwspółrzędnym z elektronicznym skanowaniem wiązki i obracaną anteną planarną
PublikacjaW rozprawie zawarto historię radiolokacji oraz sposób obróbki sygnałów i danych radarowych przed etapem estymacji. Przedstawiono oraz przetestowano klasyczne metody estymacji współrzędnych wraz ze wskazaniem ich słabych oraz mocnych stron. Zaproponowano uodpornione warianty estymatorów największej wiarygodności, które pozwolił poprawić jakość oszacowania przy estymacji elewacji w warunkach propagacji wielodrogowej, redukując jednocześnie...
-
Metoda analizy związanych z czasem wymagań dotyczących bezpieczeństwa systemów komputerowych
PublikacjaBezpieczeństwo jest pożądaną cecha systemów przemysłowych, transportowych i innych typów. A ponieważ do sterowania tymi systemami powszechnie stosuje się systemy komputerowe, jest ono również ważną cechą oprogramowania. Analiza bezpieczeństwa oprogramowania jest jednak, ze względu na jego niematerialność, trudniejsza od typowej analizy. Ponadto, ze względu na skomplikowane reguły sterujące oraz naturę kontrolowanych systemów, bezpieczeństwo...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Paired domination and doubly domination in graphs
PublikacjaW rozprawie poruszane są zagadnienia związane z dominowaniem parami w grafach oraz domiowaniem totalno - powściągniętym w grafach. Ponadto omawiane są zagadnienia związane ze złożonością obliczeniową różnych problemów dominowania w grafach.
-
Cost minimization in wireless networks with a bounded and unbounded number of interfaces
PublikacjaPraca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne. Rozważono zarówno wariant, w którym liczba interfejsów komunikacyjnych jest parametrem stałym (narzuconym...
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...