Wyszukiwarka
Katedra Algorytmów i Modelowania Systemów
Publikacje
Filtry
wszystkich: 517
Katalog Publikacji
Rok 2012
-
Graph Decomposition for Memoryless Periodic Exploration
PublikacjaWe consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex...
-
Greedy algorithms for backbone graph coloring in KOALA library
Publikacja -
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.
-
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.
-
Katedra Algorytmów i Modelowania Systemów
PublikacjaPrzedstawiono podstawowe informacje nt. Katedry Algorytmów i Modelowania Systemów Wydziału Elektroniki, Telekomunikacji i Informatyki PG. W szczególności przedstawiono rys historyczny, działalność dydaktyczną, badania podstawowe, nagrody i wyróżnienia oraz ofertę dla przemysłu.
-
Kodowanie niedostarczonej do odbiorców informacji w systemach satelitarnych z wolnym kanałem zwrotnym
PublikacjaW poniższym artykule przedstawiono problem kodowania źródła satelitarnego opisany przez Birka i Kola. Przytoczono również nieoptymalne kodowanie dla postawionego problemu oraz miarę określającą możliwości takiego kodowania oraz kilka przykładów, w których wcześniej wspomniane kodowanie staje się optymalne.
-
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.
-
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...
-
Metody optymalizacji dyskretnej w analizie podobieństwa drzew filognetycznych
Publikacja -
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)...
Rok 2007
-
Graph models of clos networks
Publikacja...
-
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...
-
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...
-
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.
-
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...
-
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...
-
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...
Rok 2015
-
Graph security testing
PublikacjaSet S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...
-
Interval incidence graph coloring
PublikacjaIn this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the...
-
KOALA Graph Theory Internet Service
PublikacjaKOALA has been created with the idea of C++ library templates, implementing a broad set of procedures in the fields of algorithmic graph theory and network problems in discreate optimization. During the C2NIWA project, a library has been greatly ectended, the code refactored and enclosed with the internet service available in the public repository of thr project. Today it contains interconnected educational materials in the form...
-
Minimum order of graphs with given coloring parameters
PublikacjaA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
New potential functions for greedy independence and coloring
PublikacjaA potential function $f_G$ of a finite, simple and undirected graph $G=(V,E)$ is an arbitrary function $f_G : V(G) \rightarrow \mathbb{N}_0$ that assigns a nonnegative integer to every vertex of a graph $G$. In this paper we define the iterative process of computing the step potential function $q_G$ such that $q_G(v)\leq d_G(v)$ for all $v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type...
Rok 2021
-
Graphs hard-to-process for greedy algorithm MIN
PublikacjaWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.
-
Greencoin - educational information system for eco-inclusion and empowering urban adaptability.
PublikacjaSARS-CoV19 pandemic exposed a broad spectrum of challenges for modern cities, societies and the environment at large. The post-Covid transformation requires new social and ecological solutions, adjusted to modern challenges, but also equipped with technological advances that allow for digital inclusion and sustainable urban development to benefit the local economy and society. Many information systems are designed to enable...
-
Greencoin information system empowering urban adaptability and eco living choices.
PublikacjaThere are many gamification projects focused on mitigating climate changes which has been tested or implemented worldwide. However, the gap which remains is the limited number of solutions dedicated for central European countries where the urban polices in terms of climate vulnerability are bounded. On the other hand, cities, when implementing climate-oriented policies, are focused on urban resilience, while the opportunities...
-
Greencoin: prototype of a mobile application facilitating and evidencing pro-environmental behavior of citizens
PublikacjaAmong many global challenges, climate change is one of the biggest challenges of our times. While it is one of the most devastating problems humanity has ever faced, one question naturally arises: can individuals make a difference? We believe that everyone can contribute and make a difference to the community and lives of others. However, there is still a lack of effective strategies to promote and facilitate pro-environmental...
-
imPlatelet classifier: image‐converted RNA biomarker profiles enable blood‐based cancer diagnostics
PublikacjaLiquid biopsies offer a minimally invasive sample collection, outperforming traditional biopsies employed for cancer evaluation. The widely used material is blood, which is the source of tumor-educated platelets. Here, we developed the imPlatelet classifier, which converts RNA-sequenced platelet data into images in which each pixel corresponds to the expression level of a certain gene. Biological knowledge from the Kyoto Encyclopedia...
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublikacjaAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
Komputer w labiryncie
PublikacjaProgramiści piszą programy, które potrafią robić wiele różnych rzeczy: odtwarzać filmy, prognozować pogodę, pomagać w nauce języków obcych czy matematyki. Ale czy wiesz, że można zaprogramować komputer tak, aby tworzył labirynty? W dodatku takie, które zawierają tajne informacje!
-
Modelling of dark fermentation of glucose and sour cabbage
PublikacjaIn the article, modified Anaerobic Digestion Models 1 (ADM-1) was tested for modelling dark fermentation for hydrogen production. The model refitting was done with the Euler method. The new model was based on sets of differential equations. The model was checked for hydrogen production from sour cabbage in batch and semi-batch in 5 g VSS (volatile solid suspension)/L and at the semi-batch process from glucose at 5 and 10 g VSS/L....
Rok 2009
-
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ą.
-
Gwarantowanie bezpieczeństwa w systemie z połączeniami awaryjnymi
PublikacjaRozważamy zapewnianie bezpieczeństwa przed zewnętrznym intruzem w systemie o topologii drzewa, w którym wprowadzono dodatkowe połączenia awaryjne. Grupa mobilnych autonomicznych agentów musi przechwycić intruza, niezależnie od przyjętej przez niego strategii unikania. W literaturze problem ten jest modelowany jako przeszukiwanie grafów. W pracy zawężamy dotychczasowe oszacowanie na liczbę przeszukiwawczą kaktusów podkubicznych,...
-
Maximum vertex occupation time and inert fugitive: recontamination does help [online]
PublikacjaRozważamy problem przeszukania danego grafu prostego G w celu przechwycenia niewidocznego i leniwego uciekiniera. Parametrem optymalizacyjnym, który minimalizujemy jest maksymalny czas (liczba tur strategii przeszukiwania), podczas których wierzchołek może być strzeżony (okupowany przez strażnika). Strategia monotoniczna to taka, która nie dopuszcza sytuacji, w której uciekinier dociera do wierzchołka, który wcześniej został oczyszczony....
-
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublikacjaW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
Mixed graph edge coloring
PublikacjaW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
On efficient coloring of chordless graphs
PublikacjaArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
Rok 2011
-
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublikacjaA maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...
-
Hat problem on odd cycles
PublikacjaThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of a win. In this version every player can...
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublikacjaTwo identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result...
-
Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych
Publikacjaartykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. model matematyczny, który tutaj zastosowano to szeregowanie zadań uwarunkowanych czasowo. przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie
-
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...
-
Matching Split Distance for Unrooted Binary Phylogenetic Trees
PublikacjaRekonstrukcja drzew ewolucji jest jednym z głównych celów w bioinformatyce. Drzewa filogenetyczne reprezentuje historię ewolucji i związki pokrewieństwa między różnymi gatunkami. W pracy proponujemy nową ogólną metodę określania odległości między nieukorzenionymi drzewami filogenetycznymi, szczególnie użyteczną dla dużych zbiorów gatunków. Następnie podajemy szczegółowe własności jednej metryki określonej przy użyciu tej metody...
-
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?
-
Modeling and analysis of the effectiveness of the guard systemswith dynamic graphs
PublikacjaIn the following paper it will be presented a new model for analysis (in polynomial time) of the effectiveness of the guard systems. Therewill be presented its practical applications in problems such as searching for the weakest points of the system, planning guards' paths or cameras deployment, switching image from multiple cameras on several monitors, or interception of the intruder. This model is based on describing the guarded...
-
Ocena poprawności działania algorytmu proof-number search na strukturze digrafu acyklicznego
PublikacjaAlgorytm proof-number search jest znanym algorytmem służącym do rozwiązywania gier logicznych. Rozwiązanie gry jest jednoznaczne ze znalezieniem optymalnej strategii i pozwala przeprowadzić rozgrywkę w sposób pozwalający na osiągnięcie najlepszego możliwego wyniku. Jedną z największych wad tego algorytmu, naturalnie pracującego na strukturze drzewa, jest wielokrotne rozwijanie identycznych poddrzew gry co prowadzi do nadmiarowego...
Rok 2010
-
Hat problem on a graph
PublikacjaThe topic of our paper is the hat problem. In that problem, each of n people is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
Hat problem on the cycle C4
PublikacjaThe topic of our paper is the hat problem. In that problem, each of n people is randomly tted with a blue or red hat. Then everybody can try to guess simultanously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
Interval wavelength assignment in all-optical star networks
PublikacjaArtykuł omawia zwarte końcówkowe kolorowanie grafów, które jest matematycznym modelem dla problemu przydziału częstotliwości w sieciach optycznych. W artykule przedstawiono wielomianowe algorytmy wyznaczania zwartej końcówkowej liczby chromatycznej dla pełnych grafów k-dzielnych, drzew i podkubicznych grafów dwudzielnych.
-
Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
PublikacjaArtykuł podejmuje problem szeregowania zadań przy założeniu podziału czasu na sloty jednakowej długości, gdzie każde z zadań ma ustaloną długość oraz czas jego zakończenia, który jest relatywny do końca slotu. Problem znalezienia uszeregowania polega na dokonaniu przydziału zadań do poszczególnych slotów, przy czym w ogólności długość zadania może wymuszać sytuację, w której zadańie jest realizowane nie tylko w slocie, w którym...
-
Modele i metody kolorowania grafów. Część I
PublikacjaNiniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...
-
Modelowanie problemów strażniczych jako grafów dynamicznych - przykładowy sposób analizy skuteczności systemów strażniczych
PublikacjaW problemach strażniczych rozważamy przestrzeń (graf), w której znajduje się intruz i pewna liczba agentów przechwytujących, zaś celem większości algorytmów jest jak najszybsze przechwycenie intruza lub też uniknięcie przez niego detekcji.Zaprezentowany model pozwala na praktyczne rozważanie problemów z życia wziętych przez matematyczne przedstawienie różnorodnych agentów przechwytujących (kamery mobilne i stacjonarne, strażnicy...
-
New Proofs of Some Fibonacci Identities
PublikacjaLucas proved in 1876 several identities for Fibonacci numbers. We give elementary and short proofs of them.
-
On extremal sizes of locally k-tree graphs
PublikacjaA graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...
Rok 2006
-
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...
-
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,...
-
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.
-
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.
-
Neural network breast cancer relapse time prognosis
PublikacjaPrzedstawiono architekturę i wyniki testowania sztucznej sieci neuronowej w prognozowaniu czasu nawrotu choroby u kobiet chorych na raka piersi. Sieć neuronowa uczona była na danych zgromadzonych przez 20 lat. Dane opisują grupę 439 pacjentów za pomocą 40 parametrów. Spośród tych parametrów wybrano 6 najistotniejszych: liczbę przerzutowych węzłów chłonnych, wielkość guza, wiek, skalę według Blooma oraz stan receptorów estrogenowych...
Rok 2022
-
Hybrid no-signaling-quantum correlations
PublikacjaFundamental investigations in non-locality have shown that while the no-signaling principle alone is not sufficient to single out the set of quantum non-local correlations, local quantum mechanics and no-signaling together exactly reproduce the set of quantum correlations in the two-party Bell scenario. Here, we introduce and study an intermediate hybrid no-signaling quantum set of non-local correlations that we term HNSQ in the...
-
Infinite chromatic games
PublikacjaIn the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...
-
Non-Perfect Propagation of Information to a Noisy Environment with Self-Evolution
PublikacjaWe study the non-perfect propagation of information for evolving a low-dimensional environment that includes self-evolution as well as noisy initial states and analyse the interrelations between the degree of objectivization and environment parameters. In particular, we consider an analytical model of three interacting qubits and derive its objectivity parameters. The numerical analysis shows that the quality of the spectrum broadcast...
Rok 2003
-
III Konkurs Informatyczno-Techniczny
PublikacjaW 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
PublikacjaW 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.
PublikacjaW 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
PublikacjaW 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.
PublikacjaW 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
PublikacjaArtykuł 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
PublikacjaPraca 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.
Rok 2019
-
Improving Accuracy of Contactless Respiratory Rate Estimation by Enhancing Thermal Sequences with Deep Neural Networks
PublikacjaEstimation of vital signs using image processing techniques have already been proved to have a potential for supporting remote medical diagnostics and replacing traditional measurements that usually require special hardware and electrodes placed on a body. In this paper, we further extend studies on contactless Respiratory Rate (RR) estimation from extremely low resolution thermal imagery by enhancing acquired sequences using Deep...
Rok 2016
-
Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing
PublikacjaQuantum communication with systems of dimension larger than two provides advantages in information processing tasks. Examples include higher rates of key distribution and random number generation. The main disadvantage of using such multi-dimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a not-so-obvious problem: the relation between randomness certification and computational requirements...
-
Independence in uniform linear triangle-free hypergraphs
PublikacjaThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
Lossless Compression of Binary Trees with Correlated Vertex Names
PublikacjaCompression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering...
-
Network Graph Transformation Providing Fast Calculation of Paths for Resilient Routing
PublikacjaProtection of transmission against failures can be appropriately dealt with by alternative paths. However, common schemes (e.g., Bhandaris scheme) are characterized by a remarkable delay while determining the transmission paths. This in turn may have a serious impact on serving dynamic demands (characterized by relatively short duration time). As a remedy to this problem, we introduce an approach to pre-compute the sets of disjoint...
-
Non-isolating bondage in graphs
PublikacjaA dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')...
-
Normal-form preemption sequences for an open problem in scheduling theory
PublikacjaStructural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...
-
On bipartization of cubic graphs by removal of an independent set
PublikacjaWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
Rok 2008
-
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....
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublikacjaPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
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...
-
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ą...
Rok 2014
-
Interval incidence coloring of bipartite graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublikacjaWe consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...
-
Ł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.
Rok 2017
-
Interval incidence coloring of subcubic graphs
PublikacjaIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
Monitoring of the Process of System Information Broadcasting in Time
PublikacjaOne of the problems of quantum physics is how a measurement turns quantum, noncopyable data, towards copyable classical knowledge. We use the quantum state discrimination in a central system model to show how its evolution leads to the broadcasting of the information, and how orthogonalization and decoherence factors allow us to monitor the distance of the state in question to the one perfectly broadcasting information, in any...
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublikacjaIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublikacjaIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
Rok 2018
-
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...
-
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...
-
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...
Rok 2023
-
Longitudinal drug synergy assessment using convolutional neural network image-decoding of glioblastoma single-spheroid cultures
PublikacjaAbstract Background In recent years, drug combinations have become increasingly popular to improve therapeutic outcomes in various diseases, including difficult to cure cancers such as the brain cancer glioblastoma. Assessing the interaction between drugs over time is critical for predicting drug combination effectiveness and minimizing the risk of therapy resistance. However, as viability readouts of drug combination experiments...
-
Long-term mortality after transcatheter aortic valve implantation for aortic stenosis in immunosuppression-treated patients: a propensity-matched multicentre retrospective registry-based analysis
PublikacjaIntroduction Data regarding patients with a previous medical record of immunosuppression treatment who have undergone transcatheter aortic valve implantation (TAVI) are limited and extremely inconclusive. Available studies are mostly short term observations; thus there is a lack of evidence on efficacy and safety of TAVI in this specific group of patients. Aim To compare the in-hospital and long-term outcomes between patients...
Rok 2013
-
Minimal 2-dominating sets in Trees
PublikacjaWe provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2-dominating sets. We also show that thisbound is tight.
-
Non-isolating 2-bondage in graphs
PublikacjaA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....
-
On a matching distance between rooted phylogenetic trees
PublikacjaThe Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...
Rok 2020
-
Multi-agent graph searching and exploration algorithms
PublikacjaA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
Rok 2002
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublikacjaNiniejszy 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.
PublikacjaProblem 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...