Publications
Filters
total: 517
Catalog Publications
Year 2002
-
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...
-
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...
-
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...
-
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.
-
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.
-
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...
-
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.
-
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...
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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...
Year 2003
-
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.
-
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.
-
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...
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Prezentacje multimedialne z wykorzystaniem środowiska Flash
PublicationW referacie przedstawiono istotne cechy środowiska programowego pakietu Macromedia-Flash umożliwiającego tworzenie multimedialnych aplikacji edukacyjnych.
-
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...
-
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.
-
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.
-
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.
-
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.
-
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...
-
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.
-
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.
-
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...
-
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ń.
-
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.
-
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.
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
-
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.
-
Zastosowanie algorytmów rojowych do kolorowania grafów
PublicationPrzedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.
-
Zachłanne algorytmy kolorowania grafów w modelu rozproszonym
PublicationW artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.
-
Wyszukiwarka internetowa z bazą wiedzy
PublicationW artykule scharakteryzowano program wspomagający klienta w wyborze najbardziej go satysfakcjonującej wycieczki ze zbioru ofert biura turystycznego. Zakładamy, że agencja podróży oferuje szeroki i bardzo różnorodny zakres usług a klienci nie mają jasno sprecyzowanej wizji wycieczek.
-
Wyszukiwanie cykli w grafach przy użyciu cykli Hopfielda
PublicationPrzedstawiono przykłady zastosowania sieci neuronowej Hopfielda do rozwiązywania trudnych obliczeniowo problemów kombinatorycznych.
-
Wpływ technologii informacyjnych na rozwój mediów dydaktycznych
PublicationW artykule scharakteryzowano wpływ technologii informacyjnych i telekomunikacyjnych na rozwój pomocy dydaktycznych stosujących środki multimedialne i zasoby sieci Internet. Opisano komputerowe programy wspomagające nauczanie i uczenie się, których współautorami są słuchacze studiów podyplomowych z zakresu technologii informacyjnych.
-
Sztuczne systemy immunologiczne w optymalizacji dyskretnej
PublicationSztuczne 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...
-
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.
-
Self-stabilizing algorithm for edge-coloring of graphs
PublicationReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
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.
-
Rozproszone kolorowanie grafów
PublicationW pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.