Year 2003

• Sieciowy system komputerowy wspomagający testowanie wiedzy uczniów

  Publication

  • M. Chabiera
  • O. Choreń
  • J. Mucek

  - Year 2003

  W 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.

  Publication

  • K. Giaro

  - Year 2003

  Niniejsza 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

  Publication

  • H. Furmańczyk
  • M. Kubale

  - Automatyka / Automatics - Year 2003

  Rozważ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.

  Publication

  • K. Giaro
  • R. Janczewski
  • M. Małafiejski

  - DISCRETE APPLIED MATHEMATICS - Year 2003

  W pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.

  Full text available to download

• Uszeregowania zadań wieloprocesorowych minimalizuje średni czas przepływu

  Publication

  • R. Janczewski
  • Ł. Kuszner
  • M. Małafiejski
  • A. Nadolski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Year 2003

  W 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

  Publication

  • K. Piwakowski
  • D. Szyfelbein

  - Automatyka / Automatics - Year 2003

  W 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.

  Publication

  • K. Giaro
  • M. M. Kamiński

  - Year 2003

  Celem 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.

  Publication

  • W. Porębski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Year 2003

  Praca 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 2002

• A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs

  Publication

  • K. Giaro
  • R. Janczewski
  • M. Kubale
  • M. Małafiejski

  - LECTURE NOTES IN COMPUTER SCIENCE - Year 2002

  We 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

  Publication

  • R. Janczewski
  • M. Małafiejski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  Artykuł 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.

  Publication

  • M. Kubale
  • A. Kosowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W 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

  Publication

  • J. Neumann
  • A. Szepietowski
  • I. Walukiewicz

  - INFORMATION PROCESSING LETTERS - Year 2002

  Rozważ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.

  Publication

  • A. Nadolski

  - Year 2002

  W 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

  Publication

  • A. Nadolski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W 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

  Publication

  • K. Giaro
  • M. Kubale
  • M. Małafiejski
  • K. Piwakowski

  - LECTURE NOTES IN COMPUTER SCIENCE - Year 2002

  This 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

  Publication

  • K. Giaro
  • R. Janczewski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  Niniejszy 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.

  Publication

  • H. Furmańczyk
  • K. Giaro

  - Year 2002

  Problem 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

  Publication

  • M. Małafiejski
  • Ł. Kuszner
  • M. Kubale

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W 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

  Publication

  • K. Giaro
  • M. Kubale

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  Rozważ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

  Publication

  • Ł. Kuszner

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W 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

  Publication

  • R. Janczewski
  • M. Małafiejski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  Niniejszy 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

  Publication

  • M. Kubale
  • D. Dereniowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W 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.

  Publication

  • M. Małafiejski

  - Year 2002

  Planowanie 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.

  Publication

  • J. Kuchta

  - Year 2002

  Zintegrowane ś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...