Search
Department of Algorithms and Systems Modelling
Publications
Filters
total: 517
Catalog Publications
Year 2002
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów
PublicationArtykuł poświęcony jest zachłannym algorytmom przybliżonym dla problemu szeregowania zadań w systemach równoległych z zadaniami dedykowanymi.
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublicationW pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.
-
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.
-
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.
-
Cyrkularny indeks chromatyczny grafów kubicznych
PublicationW pracy omówiono własności cyrkularnego indeksu chromatycznego grafów kubicznych. Po zdefiniowaniu tego rodzaju kolorowania zbadano, które ze znanych wyników dla klasycznego kolorowania krawędzi grafów kubicznych można przenieść na rozważany model kolorowania. Dodatkowo podano nietrywialne oszacowanie na cyrkularny indeks chromatyczny dla nieskończonej rodziny grafów kubicznych klasy 2.
-
Dedicated scheduling of tasks to minimize mean flow time
PublicationThis paper investigates the complexity of scheduling biprocessor tasks on dedicated processors to minimize mean flow time. Since the general problem is strongly NP-hard, we assume some restrictions on task lengths and the structure of associated scheduling graphs. Of particular interest are acyclic graphs. In this way we identify a borderline between NP-hard and polynomially solvable special cases.
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublicationNiniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.
-
Ograniczone (p1, p2,...,pk) kolorowanie wierzchołków grafów.
PublicationProblem ograniczonego (p1,...,pk) kolorowania grafów polega na poszukiwaniu odpowiedzi na pytanie, czy istnieje takie pokolorowanie wierzchołków grafu , że krotności użycia poszczególnych barw są równe ustalonym progom p1,...,pk. W ogólnym przypadku problem ten, jako uogólnienie klasycznego kolorowania grafów pozostaje NP-zupełnym. W pracy przedstawiamy wyniki dotyczące ograniczonego kolorowania split grafów, kografów oraz...
-
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.
-
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...
-
Rozproszone kolorowanie grafów
PublicationW pracy zaprezentowano nowy rozproszony algorytm kolorowania grafów. Przeprowadzone eksperymenty pokazują, że daje on lepsze wyniki niż znany wcześniej algorytm trywialny.
-
T-SL, T-SLF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości
PublicationNiniejszy artykuł poświęcony został algorytmom T-SL, T-SLF i T-DSATUR - nowym heurystykom dla problemu przydziału częstotliwości. Zawiera opis algorytmów, omówienie ich teoretycznych własności oraz wyniki testów komputerowych, którym zostały poddane.
-
Uporządkowane kolorowanie wierzchołków grafów
PublicationW pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie...
-
Uszeregowania zadań wieloprocesorowych w ogólnych systemach równoległych.
PublicationPlanowanie procesorów produkcyjnych czy sterowanie systemami komputerowymi wymaga skonstruowania adekwatnych modeli teoretycznych w celu uzyskania zadowalającego poziomu efektywności stosowanych rozwiązań oraz przeprowadzenia w miarę jak najpełniejszej klasyfikacji problemów ''łatwych'' oraz ''trudnych''obliczeniowo. W pracy rozważane są problemy deterministycznego szeregowania zadań wieloprocesorowych w środowisku maszyn...
-
Zintegrowane środowiska projektowania aplikacji internetowych.
PublicationZintegrowane środowiska, umożliwiające analizę, projektowanie i implementację aplikacji, stanowią wymarzone narzędzie pracy każdego inżyniera oprogramowania. Opisano próby dostarczenia takiego środowiska w postaci Borland Delphi 5.0 oraz w postaci Rational XDE - środowiska projektowania w UML przeznaczonego do integracji z istniejącymi środowiskami implementacji, takimi jak Microsoft Visual Studio.NET i IBM Web Sphere...
Year 2003
-
A polynomial algorithm for finding T-span of generalized cacti.
PublicationW pracy opisano wielomianowy algorytm wyznaczający optymalne T-pokolorowania dla uogólnionych kaktusów.
-
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.
-
Antypodalna radiowa liczba chromatyczna grafu.
PublicationOpisane zostały podstawowe zasady i właściwości antypodalnego kolorowania grafów. Zebrano publikowane w literaturze przedmiotu twierdzenia i uzupełniono wnioskami wynikającymi z własnych badań.
-
Automatyzacja sprawdzania poprawności wnioskowania podczas rozwiązywania zadań obliczeniowych.
PublicationW artykule omówiono założenia projektowe i architekturę edukacyjnego systemu informatycznego nadzorującego proces wnioskowania użytkownika podczas rozwiązywania zadań obliczeniowych. Opisywany jest system z bazą wiedzy, w których wiedza o zadaniach z elementarnej matematyki, fizyki lub chemii jest reprezentowana w postaci modeli obliczeniowych, stanowiących szczególny przypadek sieci semantycznych. Scharakteryzowano prototypowy...
-
III Konkurs Informatyczno-Techniczny
PublicationW artykule przedstawiono cele oraz przebieg III Konkursu Informatyczno-Technicznego "InfoTech" dla młodzieży szkół średnich. Zaprezentowano przykładowe pytania i zadania ilustrujące tematykę, zakres wiedzy i poziom konkursu. Autorzy kończą artykuł uwagami i sugestiami skierowanymi do organizatorów następnej edycji konkursu.
-
Komputerowy system sieciowy wspomagający ocenianie uczniów
PublicationW referacie przedstawiono funkcje użytkowe sieciowego systemu komputerowego umożliwiające utworzenie przez nauczycieli testów wyboru z dowolnej dziedziny, przeprowadzenie lekcji polegającej na rozwiązywaniu testów, automatyczne ocenianie rozwiązań, sporządzanie statystyk oraz powiadamianie uczniów o wynikach testów.
-
Kształcenie nauczycieli informatyki w zakresie opracowywania komputerowych multimedialnych środków dydaktycznych.
PublicationW artykule przedstawiono studia podyplomowe ''Internet i multimedia'', których słuchaczami są nauczyciele informatyki szkół średnich i gimnazjów. Opisano program kształcenia tych studiów, wyróżniając w nim dwa zasadnicze nurty:zapoznanie słuchaczy ze współczesnymi trendami rozwoju technologii informacyjnej oraz nauczenie słuchaczy opracowywania komputerowych pomocy dydaktycznych wykorzystujących zasoby multimedialne...
-
Kształcenie w firmie symulacyjnej
PublicationW artykule opisano zadania i funkcje firmy symulacyjnej jako nowego modelu kształcenia zawodowego. Przebieg edukacji w firmie symulacyjnej przedstawiono na przykładzie Przedsiębiorstwa Symulacyjnego CKU-Modex w Sopocie. W zakończeniu artykułu opisano i uzasadniono zalety takiego sposobu kształcenia.
-
Metaheurystyczne metody optymalizacji dyskretnej w problemie układania rozkładów zajęć dla szkół wyższych.
PublicationW pracy rozważany jest problem układania rozkładów zajęć dla szkoły wyższej. Do rozwiązania tego zagadnienia wykorzystane zostały następujące metody lokalnego i globalnego przeszukiwania przestrzeni możliwych rozwiązań: symulowane wyżarzenie, przeszukiwanie tabu oraz algorytmy genetyczne.
-
Metoda chromatyczna i jej zastosowania techniczne
PublicationArtykuł 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.
-
O pewnym zastosowaniu uporządkowanego kolorowania grafów
PublicationPraca opisuje związki pomiędzy problemami uporządkowanego kolorowania wierzchołków grafów oraz szukania drzewa eliminacji o minimalnej wysokości dla danego grafu. Stąd wynika przydatność tytułowego problemu przy równoległej faktoryzacji macierzy metodą Cholsky´ego.
-
Porównanie metod algorytmicznych i eksperymentalnych oceny systemów rekomendacji.
PublicationNa przykładzie systemu rekomendacji badań endoskopowych (ERS) przedstawiono problematykę oceny jakości systemów rekomendacji. Zaproponowane zostały dwa podejścia oceny jakości: algorytmiczne wynikające ze zdefiniowanych miar i sposobu ich pomiaru za pomocą algorytmów testowych oraz eksperymentalne opierające się na ocenie rzeczywistej pracy systemu. Przedstawiono szereg miar służących do pomiarów algorytmicznych. Pokazano...
-
Prezentacje multimedialne z wykorzystaniem środowiska Flash
PublicationW referacie przedstawiono istotne cechy środowiska programowego pakietu Macromedia-Flash umożliwiającego tworzenie multimedialnych aplikacji edukacyjnych.
-
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.
-
Sieciowy system komputerowy wspomagający testowanie wiedzy uczniów
PublicationW referacie przedstawiono organizację sieciowego systemu komputerowego wspomagającego tworzenie i przeprowadzanie testów. Omówiono przypadki użycia systemu z punktu widzenia administratora sieci, nauczyciela i ucznia, a także przypadki wspólne dla wszystkich użytkowników systemu. Podano opis interfejsu dla poszczególnych grup użytkowników.
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublicationNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublicationRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
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.
-
Uszeregowania zadań wieloprocesorowych minimalizuje średni czas przepływu
PublicationW artykule rozważane są problemy efektywnego wyznaczania uszeregowań wieloprocesorowych dla zadań jednostkowych na dedykowanych procesorach równoległych, które minimalizują średni czas przepływu.
-
Warianty algorytmu Tabu Search w zastosowaniu harmonogramów zajęć szkolnych
PublicationW niniejszej pracy przedstawiono warianty adaptacji przeszukiwania tabu wrazz wynikami eksperymentów obliczeniowych do układania szkolnych harmonogramówzajęć. W modelu teoretycznym uwzględniono ograniczenia krytyczne jak np.konflikty czasowe uczestników zajęć (nauczyciele i uczniowie) oraz brakprzerw w zajęciach (eliminacja okienek) wybranych uczestników, jak równieżniekrytyczne składniki funkcji celu jak np. równomierne...
-
Wprowadzenie do algorytmów kwantowych. Problemy współczesnej nauki. Teoria i zastosowanie.
PublicationCelem tej pracy jest prezentacja kwantowego modelu obliczeń. Szczególny nacisk położono na zagadnienia matematyczne i informatyczne. Zadbano o wyjaśnienie podstaw teoretycznych, podanie pełnych dowodów poprawności algorytmów kwantowych oraz szacowanie złożoności obliczeniowej.
-
Współbieżność w obiektowych językach programowania.
PublicationPraca przedstawia koncepcje współbieżności i ich implementacje w językach programowania. Analizuje się efektywność rozwiązań i zwraca uwagę na problemy dotąd nierozwiązane.
Year 2005
-
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.
Year 2006
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
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 znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
An approximation algorithm for maximum P3-packing in subcubic graphs
PublicationW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
An efficient algorithm for mobile guarded guards in simple grids
PublicationW pracy rozważono problem strzeżenia ortogonalnych krat dwuwymiarowych przez mobilne straże strzeżone. Podano algorytmy wielomianowe m.in. dla przypadku krat prostych i dla przypadku krat bez przeszkód w kierunku poziomym (pionowym).
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł dopasowań
PublicationBiologia molekularna jest obecnie bardzo dynamicznie rozwijającą się dziedziną nauki. Wzrost mocy obliczeniowej komputerów pozwala na coraz szybszą i dokładniejszą analizę wielocząsteczkowych biologicznych polimerów. Poniższy artykuł przedstawia jeden z modułów programu AlignGator - modułowego systemu przeznaczonego do analizy DNA. Omawiany moduł pozwala na tworzenie, oraz edycję wielodopasowań. W początkowej części artykułu opisane...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł edycji chromatogramu
PublicationModuł edycji chromatogramu jest częścią większej aplikacji, służącej do wspomagania przetwarzania danych pochodzących z sekwencjonowania DNA. Aplikacja skonstruowana jest z odrębnych, samodzielnych programów, które współpracują dwiema drogami - poprzez popularne formaty plików, co umożliwia wprowadzenie do modułów danych opracowanych częściowo w aplikacjach zewnętrznych, oraz poprzez przesyłanie danych pomiędzy modułami, co usprawnia...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublicationPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublicationRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
Efficient parallel query processing by graph ranking
PublicationW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
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.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublicationRozważ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.
-
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.