Publikacje
Filtry
wszystkich: 517
Katalog Publikacji
-
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
PublikacjaPrzedstawienie rozwiązań problemów kombinatorycznych w postacipermutacji daje podstawy do konstrukcji algorytmów lokalnychposzukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje prowadzącedo generowania sąsiedztwa rozwiązania to zamiana dwóch elementówlub przesunięcie elementu permutacji. W artykule wskazujemy metodępozwalającą na wykonanie takich operacji w czasie...
-
Certain family of analytical solutions of nonlinear von Neumann equations
PublikacjaIn this paper we present a slight generalization of certain type of Darboux transformation, that may be used sub-sequently in a convenient way. This method allows to obtain families of solutions of nonlinear von Neumann equations, that are used in particular in DNA modeling.
-
Robustness of quantum-randomness expansion protocols in the presence of noise
PublikacjaIn this paper we investigate properties of several randomness generation protocols in the device independent framework. Using Bell-type inequalities it is possible to certify that the numbers generated by an untrusted device are indeed random. We present a selection of certificates which guarantee two bits of randomness for each run of the experiment in the noiseless case and require the parties to share a maximally entangled state....
-
Equitable coloring of corona products of graphs
PublikacjaIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
-
Elementy kwantowego modelu obliczeń i algorytmiki kwantowej : łagodne wprowadzenie do informatyki kwantowej
PublikacjaJuż dziś wiadomo, że z chwilą udanej realizacji komputera kwantowego maszyna ta będzie pozwalała na znajdowanie rozwiązań problemów obliczeniowych leżących poza zasięgiem komputerów klasycznych. Opracowano szereg algorytmów kwantowych, z których największą sławą cieszy się procedura Shora, pozwalająca efektywnie dokonywać tzw. faktoryzacji, tj. rozkładu bardzo dużych liczb naturalnych na czynniki pierwsze. Na trudności obliczeniowej...
-
Evolving gene regulatory networks controlling foraging strategies of prey and predators in an artificial ecosystem
PublikacjaCo-evolution of predators and prey is an example of an evolutionary arms race, leading in nature to selective pressures in positive feedback. We introduce here an artificial life ecosystem in which such positive feedback can emerge. This ecosystem consists of a 2-dimensional liquid environment and animats controlled by evolving artificial gene regulatory networks encoded in linear genomes. The genes in the genome encode chemical...
-
Evolution of chemotaxis in single-cell artificial organisms
PublikacjaThe model of a liquid two-dimensional environment, which is based on physics of diffusion, allows us to simulate the diffusion of morphogenes. Artificial organisms move using a chemotaxis reacting to concentration difference. Organisms are controlled by a gene regulatory network coded in a linear genome and reproduce by division. We made a lot of experiments presenting organisms’ behaviour in various environment conditions. We...
-
Evolution of artificial single-cell organisms foraging for resources in a 3-dimensional environment
PublikacjaForaging for resources is a simple cognitive task that even one-celled biological organisms can ac- complish. We present an Artificial Life system in which artificial unicellular organisms (animats) forage for food in a 3-dimensional simulated liquid environment. The movement of animats is controlled by evolving artificial gene regulatory networks encoded in linear genomes. When an animat consumes enough food, it produces offspring...
-
Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
PublikacjaWe consider two versions of the rendezvous problem: exact RV, when the points representing agents have to coincide at some time, and e-RV, when these points have to get at distance less than e in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g. speed up or slow down the agent.
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublikacjaProblem rendezvous został dogłębnie zbadany, zarówno dla agendów anonimowych jak i poetykietowanych. zbadano też problem eksploracji grafu za pomocą agentów mobilnych.
-
Łagodne wprowadzenie do analizy algorytmów
PublikacjaKsiążka jest 11. wydaniem podręcznika akademickiego poświęconego podstawom algorytmiki. Składa się z trzech rozdziałów. Rozdział 1 daje podstawy formalne niezbędne przy analizie algorytmów pod kątem złożoności obliczeniowej. Rozdział 2 wprowadza w zagadnienia analizy algorytmów z różnych punktów widzenia.Rozdział 3 przedstawia podstawowe struktury danych.
-
Minimal double dominating sets in trees
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
An algorithm for listing all minimal double dominating sets of a tree
PublikacjaWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Bounds on the vertex-edge domination number of a tree
PublikacjaA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Zgred - Zgred Graph Editor
PublikacjaThe paper presents a graph editor that was developed as a supplementary tool for the Koala graph library. We discuss its requirements, design choices and main ideas behind the implementation. The later part of the paper is meant to be a brief user manual, as we go through the functionality provided by the editor
-
The Backbone Coloring Problem for Bipartite Backbones
PublikacjaLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
Generating fractal tiles using Voronoi diagrams
PublikacjaPraca opisuje szczególną klasę podziałów powierzchni n-wymiarowego torusa na komórki o fraktalnym brzegu. Zbiór komórek przejawia nietypowe własności samopodobieństwa, może zostać użyty do wypełnienia przestrzeni R^n w sposób periodyczny lub aperiodyczny ze zmienną gęstością podziałów. Zaproponowany został algorytm do generowania takich podziałów używając diagramów Woronoja. Opisana metoda może mieć zastosowania w grafice komputerowej.
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważ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.
-
Proceduralne modelowanie stworów w Suboceanic
PublikacjaSuboceanic to niewielki program wykonywalny zajmujący 50 kilobajtów. Został zaprezentowany na party demoscenowym Assembly 2005 w kategorii intro 64k. Efektem działania programu jest multimedialna animacja, w której zarówno obraz jak i dźwięk generowany jest w czasie rzeczywistym. Ta praca opisuje szczegółowo algorytmy opracowane podczas produkcji tego intra do generowania proceduralnych stworów i roślin. Opisana metoda polega na...
-
A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publikacja.
-
Greedy T-colorings of graphs
PublikacjaTreścią artykułu są pokolorowania kontrastowe wygenerowane przez algorytm zachłanny. Zbadane zostały ich własności, obejmujące liczbę kolororów, rozpiętość i rozpiętość krawędziową.
-
Scanning networks with cactus topology
PublikacjaThe family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
-
Packing Three-Vertex Paths in 2-Connected Cubic Graphs
PublikacjaW pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
-
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...
-
The complexity of list ranking of trees
PublikacjaUporzą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...
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować przy pomocy hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy jak przy pomocy modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania, oraz jak rozwiązać problemy dwukryterialne.
-
Inferring perfect phylogenies with restrictions on character state transitions
PublikacjaZnana z klasycznej literatury metoda rekonstrukcji drzewa filogenetycznego zbioru gatunków na podstawie ich cech analizowanych w modelu doskonałej filogenezy często okazuje się niewystarczająca ze względu na założenia tego modelu, zmuszające do pominięcia znanych biologom informacji. W pracy definiujemy rozszerzenie umożliwiając wprowadzenie dla każdej cechy grafu skierowanego dopuszczalnych przejść ewolucyjnych pomiędzy jej stanami....
-
W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo
Publikacjaw artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1, ..., jn, czas przetwarzania zadania i wynosi pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u,...
-
Metaheurystyki w szeregowaniu zadań uwarunkowanych czasowo
Publikacjaw artykule tym zbadano zastosowanie algorytmów metaheurystycznych w problemach szeregowania zadań uwarunkowanych czasowo. porównano wyniki algorytmu genetycznego, ewolucji różnicowej oraz symulowanego wyżarzania, z reprezentacjami rozwiązania: permutacyjną, opartą o priorytety reguł i kodowaniem przedziałowym, osiągnięte w rozwiązywaniu np-trudnego problemu 1 | pi = ai + bisi | sum wici. gdzie to możliwe, wyniki porównano z rozwiązaniami...
-
Some results on trading model in a consensus list coloring
PublikacjaKonsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...
-
A note on compact and compact circular edge-colorings of graphs
PublikacjaW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Metoda porównywania drzew filogenetycznych wykorzystująca najlżejsze doskonałe skojarzenie w grafach dwudzielnych
PublikacjaDrzewa filogenetyczne przedstawiają historyczne, ewolucyjne związki pokrewieństwa między różnymi gatunkami lub różnymi osobnikami w ramach jednego gatunku. Istnieje wiele metod rekonstruowania drzew filogenetycznych. Wykorzystywanie różnych metod na tym samym zbiorze danych zazwyczaj owocuje powstaniem różnych drzew. Pojawia się zatem pytanie: jak bardzo dwa dane drzewa różnią się od siebie. W niniejszej pracy prezentujemy nową...
-
Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych
PublikacjaUmieszczenie grafu w grafie jest odwzorowaniem pomiędzy parą grafów. Graf umieszczany reprezentuje sieć komunikujących się ze sobą zadań, natomiast graf docelowy dostępną architekturę wykonania tych zadań. Problem polega na takim odwzorowaniu wierzchołków i krawędzi, aby zminimalizować koszty wynikające z potrzeby użycia zastępczych ścieżek w grafie docelowym. W klasycznym modelu przyjmuje się, że oba grafy są proste i ich krawędzie...
-
Porównywanie topologii drzew i sieci filogenetycznych z wykorzystaniem metryki błędu
PublikacjaPodstawowymi modelami historii ewolucji organizmów są drzewa i sieci filogenetyczne. Ponieważ algorytmy konstrukcji filogenów zwracają różne wyniki dla tych samych danych wejściowych, powstaje problem oceny, który filogen najlepiej reprezentuje historię ewolucji dla zadanego zbioru gatunków. W pracy podano definicję metryki dla przestrzeni drzew o n liściach, zwanej metryką błędu. Dokonano przeglądu miar odległości na przestrzeni...
-
Algorytm budowy reprezentacji przedziałowej grafu jako heurystyka dla problemu mapowania DNA
PublikacjaW pracy dokonano analizy przydatności algorytmu Corneil'a budowy reprezentacji przedziałowej grafu jako heurystyki dla problemu tworzenia map fizycznych DNA. Prezentowana analiza dotyczy dwóch osobno rozpatrywanych przypadków, w których do danych wzorcowych wprowadzamy odpowiednio błędy negatywne (reprezentujące niedobór informacji) oraz błędy pozytywne (reprezentujące fałszywe informacje). Rozpatrywany algorytm zachowuje się znacznie...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublikacjaA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
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...
-
Równowaga strategiczna dla zbiorów defensywnych w drzewach
PublikacjaW pracy rozważany jest problem defensywnej równowagi strategicznej dla zbiorów defensywnych w drzewach (spójnych grafach acyklicznych), który polega na znalezieniu dwóch rozłącznych globalnych zbiorów defensywnych. Zagadnienie to znajduje zastosowanie w modelo- waniu problemów komunikacyjnych w sieciach. Dla danego grafu G podzbiór jego wierzchołków S jest zbiorem defensywnym, jeśli dla każdego wierzchołka v należącego do S spełniony...
-
Gdańska Międzynarodowa Szkoła Letnia na WETI
PublikacjaW dniach 5-12 września 2017 roku Katedra Algorytmów i Modelowania Systemów23, przy wydatnej pomocy,WETI, zorganizowała Międzynarodową Szkołę Letnią poświęconą algorytmom dla problemów optymalizacji dyskretnej.
-
Dynamic F-free Coloring of Graphs
PublikacjaA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
On-line Search in Two-Dimensional Environment
PublikacjaWe consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. As a way of modeling two-dimensional shapes, we restrict our attention to networks that are embedded into partial grids:...
-
ANALIZA MOŻLIWOŚCI WYKORZYSTANIA TRANSFORMACJI FALKOWEJ DO DETEKCJI NIEZAJĘTYCH PASM CZĘSTOTLIWOŚCI
PublikacjaCelem pracy była implementacja oraz wykonanie badań efektywności wybranej metody wykrywania niezajętych zasobów częstotliwości, opartej na wyznaczaniu entropii sygnału z wykorzystaniem analizy falkowej. W referacie przedstawiono podstawy teoretyczne rozważanych zagadnień, wyniki przeprowadzonych badań laboratoryjnych i ich analizę oraz wnioski.
-
Non-monotone graph searching models
PublikacjaGraph searching encompasses a variety of different models, many of which share a property that in optimal strategies fugitive can never access once searched regions. Monotonicity, as it is called, is vital in many established results in the field however its absence significantly impedes the analysis of a given problem. This survey attempts to gather non-monotone models, that are less researched in effort of summarizing the results...
-
Brief Announcement: Energy Constrained Depth First Search
PublikacjaDepth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due...
-
Metody oceny jakości łączy bezprzewodowych wykorzystywanych w systemie netBaltic
PublikacjaPrzedstawiono metodę oceny jakości łączy, opracowaną w ramach projektu netBaltic, która powstała w wyniku analizy danych zgromadzonych podczas wielu kampanii pomiarowych na wodach Morza Bałtyckiego oraz badań i testów prowadzonych w środowisku laboratoryjnym. Przedstawiono definicję parametru LQI (Link Quality Indicator) oraz sposób jego wyznaczania dla sieci komórkowych 3G i LTE oraz dla łączy bezprzewodowych WiFi. Zaprezentowano...
-
Oxygen sensitivity of hydrogenesis’ and methanogenesis’
PublikacjaIn the chapter, results of dark fermentation of sour cabbage in presence of oxygen with concentrations 2-9% are presented. The presence of oxygen in such concentration inhibits methanogesis (and methane production more than 2 times) and increases hydrogen production 6 times. It also shortens the fermentation process above 40%.
-
Restricted open shop scheduling
PublikacjaIn the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublikacjaW pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać...
-
The Snow Team Problem
PublikacjaWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b)...
-
Realizacja zadań w grafie przez grupę mobilnych jednostek
PublikacjaGrupa mobilnych jednostek, nazywanych także agentami, jest umiejscowiona w jednym lub wielu wierzchołkach grafu nazywanych bazami. Stamtąd poruszając się po z góry znanym (offline) lub nieznanym (online) grafie muszą wykonać powierzone im zadanie, takie jak przeszukanie grafu, spotkanie, dekontaminacja grafu czy wybór lidera. Celem jest znalezienie optymalnej, rozproszonej, deterministycznej strategii (sekwencji ruchów jednostek),...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublikacjaPraca 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.
-
Złożoność obliczeniowa problemu szeregowania zadań w cylindrycznym systemie przepływowym
PublikacjaW 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.
-
The complexity of equitable vertex coloring graphs
PublikacjaW 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.
-
Komputerowe wspomaganie przeprowadzania i oceniania testów
PublikacjaW artykule przedstawiono podstawowe funkcje sieciowego systemu komputerowego wspomagającego przeprowadzenie i ocenianie testów. Szczególną uwagę zwrócono na funkcję modułu obsługi nauczyciela.
-
Formalizm i metody szeregowania zadań dla potrzeb redukcji poboru mocy cyfrowych układów CMOS
PublikacjaW pracy przedstawiono związki pomiędzy modelami formalnymi stosowanymi w klasycznym szeregowaniu zadań a metodami wykorzystywanymi w syntezie wysokiego poziomu układów cyfrowych CMOS. Zagadnienia optymalizacyjne pojawiające się w obu tych problemach mogą być w pewnym sensie transformowalne. Pozwala to na przenoszenie wybranych metod rozwiązań z jednego problemu do drugiego.
-
Parallel tabu search for graph coloring problem
PublikacjaTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł edycji chromatogramu
PublikacjaModuł 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...
-
Identyfikacja terenu za pomocą autonomicznego robota
PublikacjaW pracy rozważane jest zagadnienie identyfikacji nieznanego terenuprzy pomocy autonomicznego robota o ograniczonym zasięguwidzialności. Przyjęty model matematyczny zakłada, że teren mapostać ograniczonej dwuwymiarowej mapy podzielonej na identycznekwadratowe obszary (pola) przylegające do siebie bokami. Zadaniemautonomicznego robota, którego zasięg widzialności ogranicza siedo pól przylegających do miejsca, w którym się znajduje,...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł dopasowań
PublikacjaBiologia 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...
-
Grafowy model macierzy ultrametrycznej i jego zastosowania w filogenezie i t-kolorowaniu
PublikacjaW pracy podano definicję macierzy ultrametrycznej i jej reprezentację grafową. Macierz ta jest wykorzystywana głównie w filogenezie, do budowy drzew ultrametrycznych. W pracy opisano jeden z algorytmów słuzący do konstrukcji takich drzew. Ponadto, omówiono inne możliwe zastosowania modelu grafowego macierzy, tym razem dla problemu przydziału częstotliwości dla nadajników. Zaproponowano również rozwiązanie tego problemu w szczególnym...
-
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...
-
On some ramsey and turan-type numbers for paths and cycles
PublikacjaUdowodniono, że R(P_3,C_k,C_k)= R(C_k,C_k)= 2k - 1, dla nieparzystych k. Udowodniono, że R(P_4,P_4,C_k) = k + 2 oraz R(P_3,P_5,C_k) = k + 1 dla k > 2.
-
Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych
PublikacjaHipergrafem 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. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...
-
Wyszukiwanie cykli w grafach przy użyciu cykli Hopfielda
PublikacjaPrzedstawiono przykłady zastosowania sieci neuronowej Hopfielda do rozwiązywania trudnych obliczeniowo problemów kombinatorycznych.
-
Zastosowanie algorytmów rojowych do kolorowania grafów
PublikacjaPrzedstawiamy 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.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublikacjaRozważ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.
-
Kolorowanie hipergrafów
PublikacjaHipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.
-
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.
-
Przechwytywanie obiektów poruszających się z ograniczoną prędkością
PublikacjaKrawędziowa liczba przeszukiwawcza grafu informuje nas ilu mobilnych agentów, przykładowo jednostek policji, jest niezbędnych do przechwycenia poruszającego się z dowolnie dużą prędkością uciekiniera w danym grafie. Podczas praktycznych zastosowań modelu w systemach bezpieczeństwa rzadko jednak spotyka się jednostki poruszające się z nieograniczoną prędkością. W pracy tej pokazujemy, że agenci mogą wykorzystać fakt ograniczonej...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
Witryna inrenetowa w funkcjonowaniu szkoły
PublikacjaW artykule przedstawiono problematykę funkcjonowania witryn internetowych w środowisku edukacyjnym. Przeanalizowano aspekty zarówno natury technologicznej jak i informacyjnej. Zaprezentowano technologie informatyczne i internetowe zorientowane na tworzenie witryn www. Przeanalizowano potrzeby funkcjonalne dla witryn szkolnych i edukacyjnych. Zwrócono uwagę na ich ukierunkowanie na grupy odbiorcze. Pokazano reprezentatywne przykłady...
-
Kształcenie umiejętności pracy w zespole wśród studentów informatyki
PublikacjaW pracy zaprezentowano przedmiot ''Projekt grupowy'' prowadzony na Wydziale ETI Politechniki Gdańskiej, którego celem jest przekazanie studentom wiedzy i wykształcenie umiejętności w zakresie: pracy zespołowej, prowadzenia rozmów z klientem zlecającym pracę projektowania i wytwarzania produktów z wykorzystaniem najnowszych technologii informacyjnych i telekomunikacyjnych oraz wytwarzania i utrzymania dokumentacji projektowej. W...
-
Kolorowanie końcówkowe multidrzew
PublikacjaW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Zwarte końcówkowe kolorowanie grafów
PublikacjaPraca dotyczy jednego z nowych modeli kolorowania grafów, tzw. zwartego końcówkowego kolorowania. Praca zawiera definicję modelu, informacje o jego zastosowaniach, dolne i górne oszacowania na liczbę kolorów oraz wartości dokładne zwartego końcówkowego indeksu dla wybranych klas grafów: ścieżek, cykil, gwiazd, kół, grafów pełnych i innych.
-
Modelowanie zagrożeń w sieciach komputerowych
PublikacjaW artykule przedstawiono problematykę zagrożeń w sieciach komputerowych. Dokonano przeglądu obszarów zastosowań Internetu ze szczególnym zwróceniem uwagi na zagadnienia bezpieczeństwa. Przedstawiono szereg strategii oraz rozwiązań o charakterze praktycznym w obszarach polityki bezpieczeństwa realizowanych przez różnego typu organizacje. Wyszczególniono zasady szeroko pojętej polityki bezpieczeństwa. Sklasyfikowano ataki oraz nielegalne...
-
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...
-
Application of an online judge & contester system in academic tuition
PublikacjaPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
Application of an online judge & contester system in academic tuition
PublikacjaPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
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...
-
Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania
PublikacjaW pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. danych jest n+1 zadań o czasach wykonywania postaci pi = a + bisi, gdzie si oznacza czas rozpoczęcia wykonywania i-tego zadania, a > 0, bi > 0, i = 0, 1, ..., n. wszystkie zadania są niepodzielne i dostępne w chwili t0 = 0. należy znaleźć harmonogram minimalizujący łączny czas zakończenia. w pracy przedstawiono algorytm, który, o...
-
Hiperheurystyki w kolorowaniu grafów
PublikacjaHiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla...
-
Zastosowania trójkątnych płytek w grafice komputerowej
PublikacjaPraca opisuje metody pokrywania trójkątnymi płytkami dowolnych powierzchni trójwymiarowych reprezentowanych przez siatki trójkątne. Omówione są znane metody konstruowania i układania trójkątnych płytek oraz ich optymalizacja algorytmami kolorowania grafów. Zaproponowana jest ulepszona hybrydowa metoda, umożliwiająca pokrycie dowolnej powierzchni wzorem, który wymaga kierunkowego uporządkowania.
-
Metody optymalizacji dyskretnej w analizie podobieństwa drzew filognetycznych
Publikacja -
Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
PublikacjaW artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.
-
Igrzyska Akademii ETI : Konkurs dla młodych talentów informatycznych, potencjalnych studentów WETI
PublikacjaSprawozdanie z pierwszych Igrzysk Akademii ETI, które odbyły się 21 stycznia 2012 r.
-
Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
PublikacjaArtykuł poświęcony jest szkieletowemu kolorowaniu grafów, które jest matematycznym modelem dla problemu minimalizacji szerokości pasma w sieciach radiowych. Badamy w nim zależność szkieletowej liczby chromatycznej od parametrów zagadnienia. Dowodzimy, że dla dużych wartości parametrów ta zależność jest liniowa.
-
Modele i metody kolorowania grafów. Część II
PublikacjaNiniejszy artykuł jest drugą 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 różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...
-
A Point Set Connection Problem for Autonomous Mobile Robots in a Grid
PublikacjaConsider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given...
-
METODA WYZNACZANIA ZŁOŻONOŚCI PODPRZESTRZENI STANÓW PLANSZOWYCH GIER LOGICZNYCH LOGICZNYCH
PublikacjaJedna z metod rozwiązywania gier jest analiza wsteczna. Jej skuteczność jest ograniczona wielkością przestrzeni stanów gry, która stanowi rozwiązywany problem. Pierwszego takiego oszacowania dokonał Claude E. Shannon odnośnie gry szachy w połowie minionego stulecia. Ważnym elementem jest podział takiej przestrzeni na mniejsze części, które mogą być rozwiązywane niezależnie lub z wykorzystaniem stosunkowo niewielkiej ilości informacji z...
-
An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.
-
On-line ranking of split graphs
PublikacjaA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
-
Cztery algorytmy które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublikacjaDrugi odcinek cyklu poświęcono problemowi programowania liniowego, który wywarł ogromny wpływ na życie milionów ludzi oraz badaniu liczb pierwszych, a więc problemowi ściśle związanemu z bezpieczeństwem naszych pieniędzy zdeponowanych w bankach.
-
Polynomial triset metric for unrooted phylogenetic trees
Publikacjathe following paper presents a polynomial triset metric for unrooted phylogenetic trees (based on weighted bipartite graphs and the method of determining a minimum edge cover) and its basic characteristics. also a list of further directions of research and examples of the wider use of this metric is presented.
-
Cztery algorytmy które wstrząsnęły światem. Część I: Wprowadzenie
PublikacjaArtykuł przeglądowy jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki. Wprowadzono w nim w arkana złożoności obliczeniowej i sztuki programowania komputerów.
-
Cztery algorytmy które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublikacjaW trzecim odcinku cyklu poruszono problem przyjaznego rysowania grafów oraz zaprezentowano algorytmy dla szybkiego mnożenia macierzy, a więc problemu, który pojawia się w każdej nauce inżynieryjnej. Rozważania ogólne zamknięto ilustracją postępu, jaki dokonał się w zakresie sprzętu liczącego i oprogramowania.
-
Million dollar algorithn?
PublikacjaArtykuł 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?
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublikacjaIn the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
-
Labyrynths generators, their properties and practical application in computer games
Publikacjathis paper presents three basic algorithms for generation of mazes, and many of their modifications and examples showing their practical application in creating random structures that resembles those from the real world. the paper highlights the difference in the labyrinths classes generated by listed algorithms and describes a specific and highly likely to occur shapes that occur in generated mazes. particular attention was paid...
-
Construction of phylogenetic trees with topological constraints
PublikacjaThis paper proposes a method of reconstruction of phylogenetic trees based on heuristic search with topological constraints. Using topological constraints it is possible to reduce the set of solutions as well as to enforce that the result is consistent with a given hypothesis about the evolution process within some group of species. Along with this work a number of algorithms used for phylogenetic analysis were implemented. Those...