Wyszukiwarka
Wyniki wyszukiwania dla: TEORIA GRAFÓW,PRZESZUKIWANIE GRAFÓW,ZŁOŻONOŚĆ OBLICZENIOWA
-
Duże rozgłoszeniowe pola Closa
PublikacjaW pracy pokazano nowe podejście do blokowalności dużych rozgłoszeniowych pól Closa. Przedstawione zostały także dowody na blokowalność pola C(n,r_1,n^2-1,n,r_2) oraz pola C(n,r_1,n^2,n,r_2), w których użyto ekstremalną teorię grafów i hipergrafów.
-
Zwarte kolorowanie krawędzi
PublikacjaPraca omawia model zwartego kolorowania grafów i jego zastosowania w szere-gowaniu zadań. Podano podstawowe właściwości kolorowania zwartego, a takżegrafów dających się w ten sposób kolorować. przedstawiono szereg rodzin gra-fów dwudzielnych posiadających zwarte pokolorowania. Zdefiniowano też pewnąmiarę ''niezwartości'' kolorowania krawędziowego zwaną stratnością.
-
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...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublikacjaW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Modelowanie informacją i pozyskiwanie wiedzy.
PublikacjaW rozdziale zaproponowano metody miękkiego modelowania dla wspomagania procesu pozyskania wiedzy. Skoncentrowano się na metodach opartych na teorii grafów skierowanych, drzew decyzyjnych i sieci neuronowych. Omówiono zastosowania metod na przykładach związanych z przepływem informacji w systemach autonomicznych. Wykazano przydatność modelowania miękkiego w procesach pozyskania wiedzy.
-
Projektowanie strategii frezowania złożonych kieszeni w komponentach mechanicznych
PublikacjaPrzedstawiono metody wyznaczania optymalnych sekwencji narzędziowych w projektowaniu strategii frezowania złożonych kieszeni przy wykorzystaniu określonego zestawu narzędziowego. W doborze sekwencji dopuszczalnych uwzględniano eliminację sekwencji nieefektywnych. Alternatywne sekwencje narzędziowe modelowano w postaci ważonych grafów acyklicznych dla generowanych wariantów ścieżek kolejnych narzędzi, dokonując ich oceny kosztowej.
-
Metoda chromatyczna i jej zastosowania techniczne
PublikacjaArtykuł ma charakter przeglądowy. Przedstawiono w nim najważniejsze modele koloryzowania grafów i ich zastosowania w wybranych problemach technicznych. Ponieważ jest to wiodąca tematyka badawcza Katedry Podstaw Informatyki Wydziału ETI Politechniki Gdańskiej, praca służy również upowszechnianiu dorobku naukowego pracowników Katedry oraz osób z nią współpracujących w opisywanej dziedzinie.
-
Geoinformatyka w komunikacji
Kursy OnlineSłuchacz poznaje podstawy Systemów Informacji Przestrzennej - GIS. Uczy się obsługi danych wektorowych w oprogramowaniu GIS. Przeprowadza kontrolę danych na podstawie relacji topologicznych. Student zapoznaje się z analizami sieciowymi, podstawami teorii grafów oraz sposobu działania algorytmów optymalnych ścieżek. Podczas kursu słuchacz nauczy się tworzenia numerycznych modeli terenu.
-
Energy optimisation in resilient self-stabilizing processes
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Distance paired domination numbers of graphs
PublikacjaW pracy przedstawione są pewne własności liczb k-dominowania parami w grafach. Wykazane jest, że problem decyzyjny liczby k-dominowania parami jest problemem NP-zupełnym nawet dla grafów dwudzielnych. Przedstawione są ograniczenia górne i dolne dla liczby k-dominowania parami w drzewach i scharakteryzowane drzewa, w których te ograniczenia są osiągnięte.
-
Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym.
PublikacjaW pracy rozważamy kombinatoryczny problem MERST polegający na szukaniu, dla danego grafu, drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Dla ogólnych grafów problem MERST jest NP-trudny. W pracy zaproponowano nową funkcję dobroci dla pewnego przybliżonego algorytmu rozwiązującego powyższy problem i przeprowadzono doświadczenia komputerowe w celu porównania nowej z wcześniej znaną funkcją dobroci.
-
Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych
PublikacjaPokazano, że pewien problem transportu produktów chemicznych może być sprowadzony do problemu szeregowania identycznych zadań kompatybilnych na wsadowych maszynach jednorodnych i rozwiązany metodami kolorowania grafów. Ponieważ problem ten jest NP-trudny, zbadano przypadki szczególne, które dają się rozwiązać w czasie kwadratowym. Rozważania ogólne są wsparte doświadczeniami komputerowymi zebranymi w trakcie implementacji wybranych...
-
Euler tour lock-in problem in the rotor-router model
PublikacjaW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Porównano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera dla różnych klas grafów, prowadząc rozważania w kontekście teorii gier. Przydział początkowych portów i wskaźników w modelu jest traktowany jako rozgrywka pomiędzy graczem...
-
Graph decomposition for improving memoryless periodic exploration
PublikacjaW ostatnich latach często badanym problem jest eksploracja anonimowych grafów z lokalnymi etykietami portów przy każdym wierzchołku. Niedawno pokazano [Czyzowicz et al., Proc. SIROCCO'09], że dla każdego grafu istnieje poetykietowanie prowadzące do eksploracji przez automat bezpamięciowy z okresem co najwyżej 13n/3. W niniejszej pracy poprawiamy to ograniczenie do 4n-2, stosując całkowicie nową technikę dekompozycji grafu.
-
Zastosowanie programów Mathematica i 20-sim do modelowania i analizy układów o parametrach rozłożonych
PublikacjaCelem pracy jest zaprezentowanie zastosowania pojęcia transmitancji układów o parametrach rozłożonych do konstruowania modalnych grafów wiązań dla układów zawierających jednowymiarowe podukłady o parametrach rozłożonych. Zaprezentowano sposób i efekty zastosowania programów Mathematica (do przygotowania parametrów modeli) i programu 20-Sim (do konstruowania modeli i do symulacji) w procesie modelowania i analizy układów zawierających...
-
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...
-
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...
-
Modele typu ''czarna skrzynka'' elektrycznych elementów napędu hybrydowego
PublikacjaOpisano opracowany przy zastosowaniu grafów wiązań (GW) i równań stanu (RS) model pojazdu hybrydowego. Uzasadniono potrzebę stworzenia uproszczonych modeli maszyn elektrycznych i akumulatora elektrochemicznego i przedstawiono koncepcję modelu w postaci "czarnej skrzynki", w którym uwzględniono jedynie związki między parametrami energetycznymi na wejściu i wyjściu elementu. Podano przykłady zastosowania tego podejścia do modelu...
-
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Packing [1,Delta]-factors in graphs of small degree
PublikacjaRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
Wyznaczanie sygnału sterowania silnikiem dla zadanych parametrów ruchu pojazdu.
PublikacjaW pracy zaprezentowano model układu napędowego pojazdu w formie grafów wiązań i równań stanu. Przedstawiono również model oporów ruchu pojazdu. Wyszczególniono parametry sterowania pojazdem oraz parametry określające ruch pojazdu. W pracy zawarto schemat wyznaczania parametru sterowania silnikiem, którego uzyskanie dla zadanych parametrów ruchu pojazdu jest niezbędnym elementem badań symulacyjnych i weryfikacyjnych opracowywanych...
-
Symulacja pracy mechanizmu prasującego pojazdu do usuwania odpadów z pojemników (PUOP)
PublikacjaW pracy przedstawiono analizę pracy wybranego typu mechanizmu prasującego PUOP oraz wpływ różnych konfiguracji elementów składowych tego urządzenia na energochłonność pracy w warunkach przyjętego cyklu obciążenia. W tym celu wykorzystano model mechanizmu prasującego PUOP w formie grafów wiązań oraz wyniki pomiarów ciśnienia roboczego w siłownikach hydraulicznych mechanizmu prasującego w trakcie jednego pełnego cyklu pracy przeprowadzonych...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublikacjaW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych - każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
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...
-
Kompleksowy model nowej generacji układu chłodzenia silnika spalinowego
PublikacjaPrzedstawiono tendencje w konstrukcji układów chłodzenia i dostępne komercyjne metody modelowania pracy układu chłodzenia. Przeprowadzono obliczenia symulacyjne temperatury cieczy komercyjnym programem komputerowym AmeSIM i porównano wyniki z pomiarami wykonanymi na hamowni podwoziowej. Opisano wybrane procesy wymiany ciepła występujące w układach chłodzenia. Przedstawiono ogólny model elementu cieplnego w postaci grafów wiązań...
-
program verification strategy and edge ranking of graphs
PublikacjaW artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
-
Sztuczne systemy immunologiczne w optymalizacji dyskretnej
PublikacjaSztuczne systemy immunologiczne to modele komputerowe oparte na niektórych właściwościach systemu odpornościowego kręgowców. Znajdują one szereg zastosowań m. in. w optymalizacji dyskretnej. Praca ta przedstawia informacje na temat trzech modeli obliczeniowych inspirowanych funkcjonowaniem układu immunologicznego, ich podstaw biologicznych i moŜliwych zastosowań. Artykuł zawiera opis algorytmu selekcji klonalnej w wersji optymalizacyjnej...
-
Model chłodnicy płytowej pracującej w układzie chłodzenia samochodowego silnika spalinowego
PublikacjaW artykule przedstawiono zastosowanie chłodnic płytowych w nowoczesnych układach chłodzenia silników spalinowych. uzasadniono potrzebę budowy modelu chłodnicy pozwalającego na przeprowadzenie badań symulacyjnych w nieustalonych warunkach pracy silnika samochodowego. Jako metodę modelowania przyjęto metodę grafów wiązań i równań stanu. Przyjęta metoda pozwala na powiązanie modelu chłodnicy z elementami systemu energetycznego silnik-pojazd,...
-
Szkoła letnia na WETI
WydarzeniaKatedra Algorytmów i Modelowania Systemów WETI organizuje szkołę letnią pt.: "Gdansk Summer School of Advanced Science on Algorithms for Discrete Optimization" dla osób zainteresowanych algorytmiką i teorią grafów.
-
Searching by Heterogeneous Agents
PublikacjaIn this work we introduce and study a pursuit-evasion game in which the search is performed by heterogeneous entities. We incorporate heterogeneity into the classical edge search problem by considering edge-labeled graphs. In such setting a searcher, once a search strategy initially decides on the label of the searcher, can be present on an edge only if the label of the searcher and the label of the edge are the same. We prove...
-
Model of speed-varing rotor for mechatronic systems analysis and design
PublikacjaW artykule przedstawiono sposób modelowania złożonych układów mechatronicznych w oparciu o metodę grafów wiązań. Celem zilustrowania metody posłużono się przykładem liczbowym, w którym rozważano wirnik obracający się ze zmienną prędkością kątową. Prezentowana metodyka doskonale nadaje się do modelowania układów o zróżnicowanej naturze fizycznej. Otrzymany model ma charakter obiektu o pewnej liczbie wejść i wyjść, który można w...
-
Detection of roles of actors in social networks using the properties of actors' neighborhood structure.
PublikacjaArtykuł opisuje metodę identyfikacji ról aktorów sieci społecznej. Metoda ta może być szczególnie przydatna w sieciach społecznych, o których posiadamy ograniczoną wiedzę, głównie zawężoną do lokalnych powiązań pomiędzy aktorami. Przedstawiona w artykule metoda korzysta z grafu relacji społecznych, algorytmu identyfikacji ról oraz zbioru grafów wzorców relacji. Rozwiązanie zostało przetestowane w społeczności użytkowników serwisu...
-
Model formalny dla problemu lokalizacji błędów w kodzie programu
PublikacjaIstnieje szereg sposobów badania poprawności programów komputerowych. W niniejszym referacie podejmujemy problem automatycznego testowania oprogramowania przy założeniu, iż dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu...
-
Wpływ odbiorników energii elektrycznej pojazduna parametry silnika spalinowego
PublikacjaW artykule przedstawiono model systemu energetycznego pojazdu napędzanego silnikiem spalinowym w postaci grafów wiązań (GW). W modelu tym uwzględniono szczególnie część elektryczną systemu składającą się z generatora, akumulatora elektrochemicznego i odbiorników energii elektrycznej. Podano zależności na podstawowe parametry systemu energetycznego w konwencji GW. W oparciu o przedstawioną w pracy [11] wielowymiarową charakterystykę...
-
Model procesu hamowania w pojeździe hybrydowym
PublikacjaW tradycyjnym procesie hamowania cała energia kinetyczna pojazdu jest rozpraszana do otoczenia w postaci energii cieplnej. W pojazdach hybrydowych istnieje możliwość odzyskania części tej energii przez przekazanie do akumulatorów i wykorzystania jej do napędu pojazdu. W pracy przedstawiono model energetyczny procesu hamowania pojazdu hybrydowego w układzie szeregowym, stosując metodę grafów wiązań (GW). Stosując konwencję GW podano...
-
Planning cellular machining systems for lean production.
PublikacjaRozważano zagadnienie projektowania struktur systemów obróbki o zdeterminowanych możliwościach technologicznych, odpowiadających wymaganiom oszczędnej produkcji. Przedstawiono model matematyczny wyznaczania struktur systemów grupowego wytwarzania, wykorzystujący zasady formalizmu relacji i grafów rozmytych. Zawarto wyniki badań symulacyjnych efektywności procesów wytwarzania określonego spektrum przedmiotowego, przebiegających...
-
Szkoła letnia na WETI – algorytmy i struktury danych
WydarzeniaKatedra Algorytmów i Modelowania Systemów WETI PG organizuje 3. edycję Międzynarodowej Szkoły Letniej na temat algorytmów i struktur danych dla problemów optymalizacji dyskretnej.
-
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...
-
Bilans energetyczny w pojeździe hybrydowym z napędem szeregowym.
PublikacjaPrzedstawiono model pojazdu hybrydowego z napędem szeregowym sformułowany przy użyciu grafów wiązań (GW) i równań stanu (RS). Podano składowe bilansu energetycznego hybrydowego układu napędowego i zdefiniowano najważniejsze sprawności, które mogą posłużyć do oceny ogólnej sprawności eksploatacji pojazdu. Krótko opisano pojazd hybrydowy zbudowany w Politechnice Gdańskiej w celu przeprowadzenia weryfikacji eksperymentalnej modelu...
-
Modelowanie układów napędowych pojazdów z silnikami spalinowymi
PublikacjaW analizie struktur układów napędowych pojazdów wykorzystano metodę Grafów Wiązań, która daje możliwość modelowania elementów o różnej naturze fizycznej. Jest to bardzo istotne przy analizie energetycznej systemów o złożonej i zróżnicowanej strukturze energetycznej, np. w przypadku pojazdów samochodowych z klasycznym lub hybrydowym układem napędowym. W pracy przedstawiono również przykłady popularnych programów komputerowych do...
-
Systemy aktywizacji, przetwarzania i wizualizacji danych AIS na potrzeby projektu netBaltic
PublikacjaSystem AIS (Automatic Identification System), zaprojektowany dla zapewnienia bezpieczeństwa żeglugi, służy do przekazywania w swoich komunikatach, wymienianych między jednostkami pływającymi, istotnych informacji geolokalizacyjnych. Znaczenie tych informacji wydaje się duże w kontekście planów budowy testowej instalacji, szerokopasmowej sieci teleinformatycznej netBaltic na morzu. W artykule przedstawiono wyniki dotyczące budowy...
-
Ocena przydatności systemu AIS w doborze tras rutingowych w sieciach bezprzewodowych o architekturze mesh na obszarze Bałtyku
PublikacjaCelem artykułu jest przybliżenie wyników jednego z kierunków prac prowadzonych w Katedrze Teleinformatyki Wydziału ETI Politechniki Gdańskiej w ramach projektu NetBaltic. Zaprezentowano w nim wstępne wyniki dotyczące systemu akwizycji danych oraz oceny przydatności systemu AIS do dynamicznego modelowania grafów powiązań między statkami, z uwzględnieniem zasięgów zapewnianych przez wybrane technologie sieciowe, a także określania...
-
Early detection of imminent threats in social relation graphs
PublikacjaWczesne wykrywanie zagrożeń i anomalii w sieciach społecznych jest dziś prawdziwym wyzwaniem. Ludzie w realnym świecie tworzą wiele złożonych relacji społecznych, które mogą być przedstawione za pomocą grafów, w których węzły reprezentują aktorów (pojedyncze osoby lub organizacje) a krawędzie wskazują na powiązania pomiędzy nimi. Analiza nieustannie zmieniających się relacji pomiędzy aktorami może wskazać konkretne nadciągające...
-
Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem...
-
Metaheurystyki dla problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat 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. Zagadnienie optymalizacyjne dla zadanego zbioru zgłoszeń polega na minimalizacji największej użytej wartości koloru ścieżki (tzw. liczby chromatycznej zbioru zgłoszeń). Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Porównano...
-
Synchronization helps robots to detect black holes in directed graphs
PublikacjaPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
Szkoła Letnia na WETI – algorytmy i struktury danych
WydarzeniaKatedra Algorytmów i Modelowania Systemów WETI PG organizuje 2. edycję Międzynarodowej Szkoły Letniej na temat algorytmów i struktur danych dla problemów optymalizacji dyskretnej.
-
Chapter 2: Modelling and analysis of rotor with magnetic bearing system
PublikacjaThe paper is concerned with rotor magnetic bearing system modelling. Such system is a relatively complex electromechanical system and can be considered as typical mechatronic one. The port-based modelling of physical systems has been used to obtain discrete-continuous model of considered system. Proposed approach enables to obtain reduced low-order lumped parameter representation of the system including gyroscopic interactions....