Search
Search results for: GRAFY TRUDNE ALGORYTMICZNIE
-
Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.
PublicationPraca zawiera charakterystykę suboptymalnych algorytmów antypodalnego kolorowania grafów, stanowiących adaptację algorytmów sekwencyjnych S, SL, LF stosowanych przy klasycznym kolorowaniu grafów. Dla tych algorytmów wskazano grafy dość trudne i trudne do pokolorowania (HC i SHC). Porównano ich funkcję dobroci i rozpiętości uzyskiwanych pokolorowań dla grafów o różnej gęstości krawędziowej.
-
Grafy w Imperium Rzymskim
PublicationTeoria grafów znalazła zastosowanie w sieciach telekomunikacyjnych, transporcie, bioinformatyce, zarządzaniu i w wielu innych dziedzinach. Ale co ma ona wspólnego z Imperium Rzymskim?
-
Modalne grafy wiązań - podejście wykorzystujące metodę transmitancji układu o parametrach rozłożonych
PublicationCelem pracy jest zastosowanie metody transmitancji układu o parametrach rozłożonych do konstruowania modalnych grafów wiązań. Grafy takie wykorzystuje się w modelowaniu układów zawierających jednowymiarowe podukłady o parametrach rozłożonych. W wyniku zaproponowanego podejścia uzyskuje się dalsze zwiększenie dokładności otrzymywanych modeli.
-
Grafy i systemy. Urzeczywistnienie abstrakcji
Publication -
Graphs with convex domination number close to their order
PublicationW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Zachowanie poprzez sieciowanie w przedsiębiorczości społecznej w odpowiedzi na trudne otoczenie instytucjonalne – przypadek 5 spółdzielni socjalnych
PublicationCelem niniejszego artykułu jest zobrazowanie procesów, jakimi są zachowania przedsiębiorców, zachodzących w przedsiębiorczości społecznej w odpowiedzi na trudne otoczenie instytucjonalne. Opisano zachowania przedsiębiorcze przedstawicieli pięciu spółdzielni socjalnych na podstawie pogłębionych wywiadów i obserwacji . Za pomocą metody ciągłego porównywania wyodrębniono 3 główne kategorie zachowań badanych przedsiębiorców, które...
-
Spam classification methods besed on users e-mail communication graphs
PublicationW artykule poddano analizie grafy zbudowane w oparciu o logi serwerów pocztowych. Węzły grafów reprezentują nadawców i odbiorców wiadomości e-mail natomiast krawędzie przedstawiają procesy wymiany wiadomości e-mail. Analiza grafów pozwala na znalezienie korelacji pomiędzy topologią grafów a relacjami pomiędzy użytkownikami serwisu pocztowego. W oparciu o te relacje zaproponowano algorytm klasyfikujący wymieniane wiadomości e-mail...
-
Easy and hard instances of arc ranking in directed graphs
PublicationArtykuł 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...
-
Trudne kompromisy: Prace konserwatorskie przy płytach nagrobnych w prezbiterium i transepcie kościoła św. Jana w latach 1996-2000
PublicationInterdyscyplinarna publikacja dotycząca gdańskiego kościoła jako obiektu sepulkralnej, zawierająca m.in. artykuły z dziedzin: historii, historii sztuki, konserwacji zabytków, archeologii, historii kultury materialnej,. historii literatury.
-
Weakly connected domination critical graphs
PublicationPraca dotyczy niektórych klas grafów krytycznych ze względu na liczbę dominowania słabo spójnego.
-
Zdolni z Pomorza 2019/20 - Kropki i kreski, czyli grafy i ich zastosowania
e-Learning CoursesCel kursu: Celem kursu jest wprowadzanie uczniów w świat grafów i zapoznanie ich z praktycznymi zastosowaniami teorii grafów. Opis kursu: Dawno temu Leonard Euler, jadąc do Petersburga, zatrzymał się po drodze w Królewcu. Tam zainteresował go problem, nad którym, jak wieść niesie, głowili się mieszkańcy tego miasta: czy da się przespacerować po Królewcu tak, aby każdy z jego siedmiu mostów przejść dokładnie raz? Euler podszedł...
-
Trudne sytuacje w pracy nauczyciela akademickiego
EventsTematyka szkolenia: sytuacje konfliktowe, sposoby dochodzenia do porozumienia oraz metody rozwiązywania problemów.
-
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.
-
Strong weakly connected domination subdivisible graphs
PublicationArtykuł dotyczy wpływu podziału krawędzi na liczbę dominowania słabo spójnego. Charakteryzujemy grafy dla których podział dowolnej krawędzi zmienia liczbę dominowania słabo spójnego oraz grafy dla których podział dowolnych dwóch krawędzi powoduje zmianę liczby dominowania słabo spójnego.
-
Agnieszka Kurkowska dr inż. arch.
PeopleAgnieszka Kurkowska, adiunkt na Wydziale Architektury Politechniki Gdańskiej od 2020 roku. W roku 2010 uzyskanie tytułu doktora na Politechnice Gdańskiej, której jest absolwentką. Od 2000 roku członek POIA RP. W latach 2013-2020 praca na Wydziale Architektury i Wzornictwa Politechniki Koszalińskiej, w tym pełnienie funkcję kierownika Zakładu Architektury Wnętrz. Laureatka nagród Rektora Politechniki Koszalińskiej za pracę naukową...
-
Lower bound on the distance k-domination number of a tree
PublicationW artykule przedstawiono dolne ograniczenie na liczbę k-dominowania w drzewach oraz scharakteryzowano wszystkie grafy ekstremalne.
-
Music Archive Metadata Processing Based on Flow Graphs.
PublicationW referacie zaproponowano metodykę wyszukiwania informacji muzycznej w bazach internetowych w oparciu o meta opis. Skonstruowany algorytm wykorzystuje grafy przepływowe Pawlaka.
-
Graphs with equal domination and 2-distance domination numbers
PublicationW publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.
-
Million dollar algorithn?
PublicationArtykuł w sposób popularnonaukowy porusza następujące problemy:- 2300 lat algorytmiki- 7 problemów milenijnych- rodzaje problemów pod kątem złożoności obliczeniowej- planowanie optymalne- banki i grafy- czy P=NP?
-
Hybrydowy model linii hydraulicznej.
PublicationZaprezentowano metodę modelowania linii hydraulicznej wykorzystując dwa sposoby budowy przybliżonych modeli dyskretnych dla układów ciągłych: dyskretyzację przestrzenną orac dekompozycję modalną. Do budowy takich modeli zastosowano modalne grafy wiązań.
-
Modelowanie układów dyskretno-ciągłych z ruchomym obciążeniem.
PublicationZaprezentowano modele niskiego rzędu dla wybranych jednowymiarowych układów ciągłych z ruchomym obciążeniem w postaci przemieszczających się podukładów o parametrach skupionych.Do budowy takich modeli zastosowano zmodyfikowane modalne grafy wiązań.
-
On efficient coloring of chordless graphs
PublicationArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
Przybliżone hybrydowe modele wybranych układów o parametrach rozłożonych
PublicationZaprezentowano metodę budowy modeli w postaci grafów wiązań dla układów za-wierających jednowymiarowe podukłady o parametrach rozłożonych. Wykorzystanodwa znane sposoby budowy przybliżonych modeli o parametrach skupionych dla układów o parametrach rozłożonych: dyskretyzację przestrzenną oraz analizę modalną (modalne grafy wiązań).
-
Sum coloring of bipartite graphs with bounded degree.
PublicationArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Fault tolerant guarding of grids
PublicationW pracy rozważano problem strzeżenia krat dwuwymiarowych przez dwa niezależne zespoły straży. Wykazano, że zagadnienie minimalizacyjne jest NP-trudne i zaproponowano dla niego wielomianowy algorytm 6/5-przybliżony.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublicationW 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.
-
Energy optimisation in resilient self-stabilizing processes
PublicationW 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.
-
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
PublicationW 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.
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublicationRozważ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.
-
Application of discrete wavelet transform in the analysis of nonlinear chemical system
PublicationW pracy omówiono zastosowanie dyskretnej transformacji falkowej do analizy oscylacji chemicznych. Szczegółowej analizie falkowej poddano rejestry potencjałowe reakcji Biełousowa-Żabotyńskiego. Pozwoliło to zlokalizować trudne do zidentyfikowania przejścia pomiędzy kolejnymi etapami tej złożonej reakcji.
-
Programy do kosztorysowania [Rozdział 11.8]
PublicationWażnym elementem w procesie projektowania węzłów drogowych jest ocena kosztów inwestycji. Jest to zajęcie trudne i czasochłonne, jednakże pojawienie się odpowiedniego oprogramowania znacznie przyspieszyło ten proces. Obecnie technika komputerowa niemal całkowicie wyparła tradycyjne sposoby sporządzania kosztorysów.
-
Comparison of volume-and surface-detention-time distributions
PublicationCzas zatrzymania ścieków w reaktorze jest bardzo ważnym parametrem projektowym. Jego wyznaczenie jest trudne i kłopotliwe. Z tego względu zbadano możliwość zastąpienia wartości tego parametru, wyznaczonej tylko dla swobodnej powierzchni ścieków. W wyniku stwierdzono dopuszczalność takiej zamiany.
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublicationSzeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...
-
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.
-
Applications of computational intelligence techqniues to acoustics
PublicationCelem artykułu jest przegląd wybranych zastosowań metod inteligentnych w akustyce, a w szczególności w szeroko rozumianej inżynierii dźwięku. Przedstawione badania i eksperymenty były prowadzone w oparciu o sztuczne sieci neuronowe, metodę zbiorów przybliżonych, logiką rozmytą, grafy przepływowe Pawlaka oraz algorytmy genetyczne. Rozwiązywane problemy dotyczyły klasyfikacji dźwięków muzycznych, rozpoznawania fraz muzycznych, przetwarzania...
-
Metoda grafów wiązań w zastosowaniu do opracowania szczególnego obwodu elektrycznego
PublicationGrafy wiązań wykorzystano do odwzorowania krwiobiegu nerki. Zaproponowany model, uwzględnia również odcinek tętnicy głównejoraz, w uproszczeniu, dystrybucję krwi do pozostałych segmentów krwiobiegu. Opisanie zjawisk przepływu krwi w naczyniach krwionośnych za pomocą grafów wiązań pozwala w łatwy sposób przejść do modelu w postaci obwodu elektrycznego. Sprowadzenie problemu dystrybucji krwi do modelu elektrycznego umożliwia zastosowanie...
-
Anonymous agreed order multicast: performance and free riding
PublicationPrzedstawiono protokół rozgłaszania wiadomości dla sieci lokalnych z usługą 1C, zapewniający całkowite uporządkowanie wiadomości przy zachowaniu anonimowości stacji. Wykorzystywane są raporty zawierające grafy częściowego uporządkowania wiadomości, otrzymywane na podstawie kolejności odbioru i wnioskowania o bezpośrednim następstwie par wiadomości. Wskazano, że kolektywna odpowiedzialność za utrzymanie stałego rytmu raportów sprzyja...
-
Programowanie dynamiczne w rozwiązywaniu problemów szeregowania zadań w systemach o acyklicznej strukturze
PublicationRozważono rozrzedzone systemy niepodzielnych zadań dwuprocesorowych o jednostkowych długościach operacji oraz systemy maszyn dedykowanych (open shop,flow shop, mixed shop) o operacjach zero-jedynkowych. Przedstawiono rodzinę wielomianowych algorytmów opartych na programowaniu dynamicznym, pozwalających na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 3. Alicja i Bogdan remontują mieszkanie.
PublicationPoniższe zagadki nawiązują z jednej strony do problemu kafelkowania płaszczyzny, który jest nierozstrzygalny, z drugiej do problemu rozkroju wstęgi, który jest NP-trudny. Jednakże przypadki szczególne, które tu rozważamy, nie są tak trudne i mogą być rozwiązane za pomocą algorytmów działających w czasie wielomianowym.
-
Determination of the bearing capacity of pile foundations based on CPT test results
PublicationAnalityczne określanie pełnej krzywej obciążenie - osiadanie na podstawie parametrów geotechnicznych wciąż stanowi bardzo trudne zadanie naukowe i inżynierskie. W pracy przedstawiono metodę bezpośredniego wykorzystania oporów na stożku sondy statycznej do określania pełnej krzywej osiadania dla pali Vibro-Fundex. W sumie jako materiał weryfikacyjny wykorzystano 94 próbne obciążenia statyczne pali.
-
Sumacyjne kolorowanie grafów
PublicationW tym rozdziale, oprócz szczegółowego zaprezentowania koncepcji sumy chroma-tycznej, jej własności oraz wyników z nią związanych, dokonano analizy zło-żoności problemu sumacyjnego kolorowania dla wybranych klas grafów, w szcze-gólności rozróżniono klasy grafów, dla których problem sumacyjnego kolorowa-nia można rozwiązać w czasie wielomianowym oraz przypadki NP-trudne.
-
100 years of the technical university education in Gdańsk 1904-2004.
PublicationNa tle warunków polityczno-społecznych książka przedstawia szczegółowo narodziny i działalność niemieckiej politechniki w Gdańsku w latach 1904-1945 oraz trudne początki Politechniki Gdańskiej po jej uruchomieniu w roku 1945. Angielskojęzyczna wersja książki pozwala na jej upowszechnienie za granicą, gdzie sprawy te nie są znane lub też są naświetlane dość jednostronnie.
-
Sieć SSWN w oczyszczalni ścieków
PublicationModelowanie złożonych, dynamicznych, nieliniowych systemów z wieloma skalami czasu, do jakich należą biologiczne oczyszczalnie ścieków, jest wcišż poważnym wyzwaniem. Problemy związane z pomiarem sporej części stanu obiektu oraz duże koszty urządzeń pomiarowych utrudniają a wręcz uniemożliwiają korzystanie z modeli fizykalnych rozważanych systemów. Jest to szczególnie trudne, gdy potrzebujemy modelu do celów sterowania.
-
100 years of the technical university education in Gdańsk 1904-2004.
PublicationNa tle warunków polityczno-społecznych książka przedstawia szczegółowo narodziny i działalność niemieckiej politechniki w Gdańsku w latach 1904-1945 oraz trudne początki Politechniki Gdańskiej po jej uruchomieniu w roku 1945. Angielskojęzyczna wersja książki pozwala na jej upowszechnienie za granicą, gdzie sprawy te nie są znane lub też są naświetlane dość jednostronnie.
-
Rational determination of dynamic characteristics of fluid-flow Reactors
PublicationPodstawowa charakterystykę reaktorów stanowi krzywa rozkładu czasu zatrzymania. Jej dokładne wyznaczenie jest trudne i kosztowne. W pracy zaproponowano wykorzystanie metody aproksymacyjnej, polegającej na zastąpieniu rzeczywistej funkcji przez jej przebieg uproszczony. Zaproponowano aproksymację rozkładem trójkątnym. Na konkretnym przykładzie pokazano, że metoda ta daje lepsze wyniki niż powszechnie stosowany model przepływu tłokowego.
-
Pakt Stabilności i Wzrostu - strażnik porządku Unii Gospodarczej i Walutowej?
PublicationBlisko 10 lat funkcjonowania Unii Gospodarczej i Walutowej skłania do refleksji nad funkcjonowaniem ważnego dla strefy euro mechanizmu, jakim jest Pakt Stabilności i Wzrostu. Choć pełni on trudne do przecenienia dyscyplinujące funkcje, wywołuje wiele kontrowersji w aspekcie trudności w praktycznym jego zastosowaniu. W opracowaniu Autor wskazuje na te ułomności i podejmuje próbę odpowiedzi na pytanie zawarte w tytule.
-
Wyznaczanie parametrów elektrycznych trakcyjnego układu zasilania dla złożonych warunków ruchu przy wykorzystaniu programu pspice
PublicationRozwój systemów zelektryfikowanego transportu, modernizacje linii kolejowych, rozbudowa sieci komunikacji miejskiej, zakupy nowoczesnego taboru, sprawiają, że konieczne staje się w tych przypadkach dostosowanie i unowocześnienie trakcyjnych systemów zasilania. Wyznaczenie parametrów elektrycznych tych układów metodami analitycznymi, zwłaszcza dla złożonej sytuacji ruchowej, jest trudne. W artykule przedstawiono efektywną metodę...
-
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...
-
Modele i metody kolorowania grafów. Część I
PublicationNiniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...