Search
Search results for: ZŁOŻONOŚĆ
-
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
PublicationW 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 equitable vertex coloring graphs
PublicationW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
-
The complexity of list ranking of trees
PublicationUporzą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
PublicationW 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.
-
Złożoność obliczeniowa
e-Learning Courses -
Joanna Raczek dr inż.
PeopleEmployment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...
-
Jerzy Konorski dr hab. inż.
PeopleJerzy Konorski received his M. Sc. degree in telecommunications from Gdansk University of Technology, Poland, and his Ph. D. degree in computer science from the Polish Academy of Sciences, Warsaw, Poland. In 2007, he defended his D. Sc. thesis at the Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology. He has authored over 150 papers, led scientific projects funded by the European Union,...
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
RNS reverse converter based on the new chinese remainder theorem.
PublicationPrzeanalizowano złożoność układu cyfrowego opartego na nowej odmianie chińskiego twierdzenia o resztach.
-
Complexity of weak acceptonic conditions in tree automata
PublicationRozważano złożoność problemu pustości dla automatów na drzewach ze słabymi warunkami akceptowalności. Rozważano także translacje pomiędzy słabymi i silnymi warunkami akceptowalności.
-
Wpływ stabilizatorów systemowych na kołysania elektromechaniczne
PublicationPrzedstawiono kilka wybranych zagadnień z dziedziny stabilizatorów systemowych. Obecna praca powinna zwrócić uwagę na złożoność problemu stabilizacji oscylacji eklektromechanicznych w systemie elektroenergetycznym.
-
T-coloring of graphs.
PublicationNiniejszy 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.
-
Kontrastowe kolorowanie grafów
PublicationNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana zostałajego definicja i podstawowe własności, zastosowania oraz złożoność oblicze-niowa problemów rozważanych w ramach tej dziedziny.
-
Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie.
PublicationReferat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Zaprezentowano wybrane twierdzenia, oparte w dużej mierze na wynikach badań własnych. Omówiono złożoność obliczeniową problemu routingu chromatycznego i kolorowania ścieżek zarówno...
-
Weakly cooperative guards in grids
PublicationW pracy autorzy zajmują się rozmieszczaniem strażników mobilnych w kratach ortogonalnych, podali wzór na minimalną liczbę strażników w kracie oraz przeanalizowali złożoność obliczeniową problemu.
-
Obliczanie prawdopodobieństwa spójności grafów losowych
PublicationZaproponowano metodę wykorzystania systemu Comcute do przeliczania prawdopodobieństwa grafów losowych. Obliczenia te mają zbyt dużą złożoność, aby dla dużych grafów przeprowadzać je na pojedynczym komputerze.
-
Adjustable fractional-delay filters utilizing the Farrow structure and multirate techniques. [Przestrajalne filtry o opóźnieniu ułamkowym wykorzystujące strukturę Farrowa i techniki wieloszybkościowe]
PublicationDo efektywnej realizacji ułamkowo opóźniających, przestrajalnych filtrów FIR (o skończonej odpowiedzi impulsowej) można wykorzystywać strukturę Farrowa. Jednakże, niezależnie od efektywności w porównaniu z innymi strukturami, jej złożoność implementacyjna szybko rośnie ze wzrostem szerokości pasma filtru. Celem zredukowania złożoności numerycznej, zaproponowano podejście wieloszybkościowe. W tym podejściu sygnał wejściowy jest...
-
Circular colorings of graphs.
PublicationRozdział poświęcony jest cyrkularnemu modelowi kolorowania krawędzi. Rozważana jest zarówno wersja wierzchołkowa i krawędziowa. Szczególny nacisk położono na złożoność obliczeniową i zastosowania dla omawianych modeli kolorowania.
-
A new method for searching optimal path on a raster plane including cost of direction changes
PublicationArtykuł przedstawia nowy algorytm znajdowania optymalnych tras na siatkach rastrowych. Szczegółowo opisano zastosowane struktury danych, dzięki który algorytm ma liniową złoŻoność obliczeniową. Zamieszczono również propozycje możliwych zastosowań.
-
Fast recursive basis function estimators for identification of time-varying processes
PublicationW pracy wprowadzono nową kategorię filtrów adaptacyjnych opartych na metodzie funkcji bazowych i wykorzystujących koncepcję postfiltracji. Proponowane algorytmy pozwalają połączyć niską złożoność obliczeniową i dobre właściwości śledzące.
-
Metody modelowania charakterystyk magnesowania przełączalnych silników reluktancyjnych i ich porównanie
PublicationW pracy przedstawiono metody stosowane do modelowania charakterystyk magnesowania przełączalnych silników reluktancyjnych oraz dokonano ich porównania biorąc pod uwagę dokładność modelowania charakterystyk oraz złożoność obliczeniową poszczególnych metod.
-
Metody modelowania charakterystyk magnesowania przełączalnych silników reluktancyjnych i ich porównanie
PublicationW pracy przedstawiono metody stosowane do modelowania charakterystyk magnesowania przełączalnych silników reluktancyjnych oraz dokonano ich porównania biorąc pod uwagę dokładność modelowania charakterystyk oraz złożoność obliczeniową poszczególnych metod.
-
Kolorowanie grafów obciążonych i jego zastosowanie w problemie przydziału częstotliwości
PublicationReferat 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.
-
Czy definiowanie sakralności architektury cerkwi Zachodniej Ukrainy lat 90-tych służy poznaniu rzeczy? Sama rzecz bowiem wymyka się.
PublicationArtykuł przedstawia złożoność problemów procesu powstawania nowych cerkiew na Ukrainie Zachodniej w kontekście analogicznych zmian w Polsce w latach osiemdziesiątych. Porusza problemy z pogranicza kultury, tradycji, kanonu, sztuki i estetyki.
-
Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów
PublicationW artykule autorzy proponują algorytm przybliżony dla cylkularnego kolorowania krawędzi grafu. Przedstawione są oszacowania na złożoność obliczeniową tego algorytmu, a także wyniki testów na grafach o małej liczbie wierzchołków jak i na grafach losowych.
-
Religijność Czesława Miłosza (książka)
PublicationMówić o twórczości Czesława Miłosza bez uwzględnienia obecnych w niej idei i wierzeń religijnych jest jak oglądać czubek góry lodowej. Może piękny, lecz nie dający pojęcia o napieraniu głębi. Próbą ogarnięcia teologicznego wymiaru dzieła noblisty jest książka Religijność Czesława Miłosza. Na jej stronach twórczość ta jawi się w pełni odniesień poety do natury i darwinizmu zapładniającego manichejską wizję dziejów oraz...
-
The circular chromatic index of some class 2 graphs
PublicationW 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.
-
Ocena protokołu 6rd
PublicationW pracy przedstawiono nową propozycję dostępu do Internetu IPv6 - tunelowanie 6rd, zorientowaną na operatorów telekomunikacyjnych i dostawców usług internetowych. Oceniono złożoność protokołu i porównano z poprzednimi rozwiązaniami tunelowania, w szczególności 6to4. Przedyskutowano możliwości i zagrożenia szybkiego wdrażania tunelowania 6rd.
-
Self-adjusting sub-sample delay estimator based on fractional delaying Hilbert transform filter
PublicationZaprezentowano nowe rozwiązanie samo-nastrajalnego estymatora opóźnienia sygnału sinusoidalnego, działającego w czasie dyskretnym. Zastosowano filtr Hilberta o skończonej odpowiedzi ipulsowej (FIR od ang. finite impulse response) zagregowany z filtrem ułamkowo-opóźniającym. Zilustrowano performancję estymatora, również w obecności szumu. Przeanalizowano jego złożoność numeryczną.
-
Przedsiębiorczość technologiczna – wysokie technologie, badania i rozwój.
PublicationDotychczas nie powstała jedna definicja przedsiębiorczości technologicznej (PT) z uwagi na złożoność zjawiska. Najogólniej, PT łączy zagadnienia związane z przedsiębiorczością oraz zarządzaniem technologią i innowacjami, jak również nauki społeczne z naukami technicznymi. Rozdział kompleksowo wyjaśnia pojęcie PT oraz przedsywia analizę historyczną pojęcia
-
Cykliczny system otwarty i cyrkularne kolorowanie grafów.
PublicationW 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.
-
Wielkogabarytowe hydrodynamiczne łożyska wzdłużne
PublicationW 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...
-
Organizacja jako myślenie obrazami.
PublicationAutorka na tle zmian transformacyjnych przedstawiła szerokie spojrzenie na organizacje. Począwszy od Maksa Webera poprzez inne definicje ukazuje złożoność i zmienność określenia definicji organizacji. W tym kontekście prezentuje wiele nowych koncepcji organizacji, określając je jako obrazy, metafory Myślenie obrazami to wychodzenie z mechanicznego postrzegania organizacji,to prezentowanie kierunku holistycznego.
-
Wody opadowe, aspekty prawne, ekonomiczne i techniczne
PublicationW oparciu o ustalenia specjalistycznej konferencji przedstawiono podstawowe problemy związane z rozsądnym zagospodarowaniem wód opadowych. Braki jednoznacznych regulacji prawnych w tym określenia odpowiedzialności, niemożlliwość dostataecznie wiarygodnej oceny ilościowej oraz szczególna złożoność ssytemów narzucają konieczność poszukiwanie akceptowalnych rozwiązań. Problem dynamiczności rozwoju zjawisk meteorologicznych, szczególna...
-
Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
PublicationW artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.
-
Przetwarzanie zapytań w rozproszonej bazie wiedzyopartej na logice opisowej
PublicationRozdział prezentuje podstawy algorytmu Spider przetwarzania zapytań asercjonalnych (typu ABox) w rozproszonej bazie wiedzy opartej na logice opisowej. Algorytm Spider może być stosowany w celu integracji wiedzy z różnych źródeł. W rozdziale pokrótce przedstawiono zasadę kartograficznej reprezentacji wiedzy, sposób odwzorowywania terminologii różnych źródeł oraz oszacowano złożoność obliczeniową przedstawianego algorytmu.
-
Ontologia PIPSDrugs: praktyczne zastosowanie metody SIM
PublicationMetoda SIM zmniejsza złożoność ontologii oraz upraszcza proces modelowania, jednak może też wywołać niekorzystne zjawiska, np. konieczność uproszczenia modelu lub utrudnienie wnioskowania. Na pytanie, jak duży jest zasięg szkodliwych zjawisk, może odpowiedzieć tylko praktyczne zastosowanie. Ontologia POPSDrugs jest pierwszą praktyczną realizacją opisu wiedzy na podstawie reguły metody SIM.
-
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Publicationartykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. model matematyczny, który tutaj zastosowano to szeregowanie zadań uwarunkowanych czasowo. przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie
-
Klasyfikacja metod modelowania procesów biznesowych
PublicationW rozdziale podjęto próbę klasyfikacji metod modelowania procesów biznesowych uwzględniając złożoność metody, cel modelowania oraz zakres modelowanych aspektów organizacji. Zawarto także opis popularnych diagramów używanych w metodologiach modelowania procesów bitznesowych. Wyjaśniono przy tym podstawowe pojęcia związane z modelowaniem procesów biznesowych w kontekście inżynierii oprogramowania oraz zarzadzania procesami biznesowymi.
-
Podzielne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych w celu minimalizacji sumy czasów zakończenia
PublicationW pracy rozważamy deterministyczne szeregowanie zadań dwuprocesorowych na maszynach dedykowanych, które minimalizuje sumę czasów zakończenia, przy czym dopuszcza się możliwość przerwania wykonywania zadania i ponownego wznowienia obsługi z pomijalnie małym kosztem. Wiadomo, że tak postawione zagadnienie jest problemem silnie NP-trudnym. W pracy badamy złożoność obliczeniową problemu, ograniczając liczbę maszyn.
-
Fast Distance Vector Field Extraction for Facial Feature Detection
PublicationPraca 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...
-
A new method of ship routing on raster grids, with turn penalties and collision avoidance
PublicationArtykuł przedstawia nowy algorytm znajdowania optymalnych tras na siatkach rastrowych. Szczegółowo opisano zastosowane struktury danych, dzięki którym algorytm ma liniową złożoność obliczeniową. Na podstawie algorytmu opracowano metodę wyznaczania tras dla statków, uwzględniającą kwestie unikania kolizji z innymi statkami i przeszkodami nawigacyjnymi.Przedstawiono dwa warianty metody, dedykowane odpowiednio systemom pokładowym...
-
Complex multiplier based on the polynomial residue number system
PublicationPrzedstawiono próbę zaprojektowania mnożnika zespolonego 4x4 opartego na algorytmie Skavantzosa i Stouraitisa. W algorytmie stosuje siękodowanie liczb n-bitowych jako wielomianów stopnia 7 w pierścieniu wielomianów modulo (x^8-1) z n/4-bitowymi współczynnikami. Mnożenie zespolone jest wykonywane jako 8-punktowy splot cykliczny. Podanoopóżnienie i złożoność sprzętową jak również porównanie ze standardowym.rozwiązaniem.
-
Duży obiekt szklarniowy jako potencjalny odbiorca dla układu kogeneracyjnego - studium przypadku
PublicationPrzedstawiono wyniki analizy opłacalności zastosowania układu skojarzonego do zasilania w ciepło i energię elektryczną dużego obiektu szklarniowego. Analizowano wykorzystanie silników lub turbin gazowych wykorzystujących jako paliwo gaz ziemny. We wnioskach stwierdzono, że prezentowany przykład jest wynikiem analizy wskaźnikowej. Ze względu na złożoność uwarunkowań lokalnych, analizy opłacalności dla rzeczywistych przypadków powinny...
-
Efektywny algorytm modelowania kanału radiokomunikacyjnego
PublicationW referacie omówiono efektywny algorytm modelowania kanału radiokomunikacyjnego z zanikami i propagacją wielodrogową. Zaproponowano szybką metodę ważonego próbkowania prążkowej odpowiedzi impulsowej kanału radiokomunikacyjnego. Przedstawiono algorytm generacji sekwencji współczynników rayleighowskich o pożądanym rozkładzie gęstości mocy z wykorzystaniem transformacji FFT. Na podstawie porównania ze stosowanym dotychczas modelem...
-
Determining the optimal course alteration maneouvre in a multi-target encounter situation for a given ship domain model
PublicationW 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.
-
Techniki wielokryterialnego podejmowania decyzji jako narzędzia wspierające etap przygotowania próbek do analizy
PublicationDylematami decyzyjnymi chemików-analityków są wybór odpowiednich technik przygotowania próbek do analizy, procedur analitycznych, warunków ich prowadzenia oraz dobór odczynników chemicznych. Elementy szczególnie istotne w aspekcie metrologicznym. Jednakże rozwiązanie optymalne powinno także uwzględniać kwestie ekonomiczne i środowiskowe, ostatnie reprezentowane przez koncepcję zielonej chemii (wytyczne do projektowania bardziej...
-
Interpolator wykorzystujący filtr z maskowaniem charakterystyki częstotliwościowej
PublicationInterpolator o dużej krotności wymaga stosowania dolnoprzepustowych filtrów cyfrowych o bardzo wąskim paśmie przejściowym. Przekłada się to na dużą złożoność obliczeniową i problemy z projektowaniem filtrów interpolacyjnych. W pracy zaproponowano użycie metody FRM rozbijającej filtr o wąskim paśmie przejściowym na grupę filtrów o obniżonych wymaganiach, co zmniejsza liczbę niezerowych współczynników. W rezultacie użycie tego rozwiązania...
-
Sondowanie statyczne : Metody i zastosowanie w geoinżynierii.
PublicationKsiążka stanowi pierwsze polskie kompendium nt. sondowań statycznych metodą CPTU. Przedstawiono w niej problematykę sondowania w dwóch częściach: numerycznej i praktycznej. W części pierwszej autor zwraca uwagę na złożoność obliczeniową omawianych zagadnień, porusza kwestie zaawansowanej mechaniki obliczeniowej. Druga część zawiera wiele praktycznych wskazówek jak korzystać z metody CPTU i jak interpretować jej wyniki w celu określenia...
-
Szacowanie złożoności czasowej projektu informatycznego
PublicationArtykuł analizuje czasową złożoność projektu informatycznego jako kwalifikowaną prognozę z uwzględnieniem doświadczeń modeli COCOMO. Na wstępie, dyskusji poddano zaproponowaną funkcję prognostyczną. Z kolei wskazano na szereg, także pozatechnicznych, czynników, mających wpływ na powodzenie projektu. Wreszcie pokazano formuły opisujące trójwymiarową integrację systemową w obszarze: osobowym, softwarowym i hardwarowym. W podsumowaniu...