Wyszukiwarka
Filtry
wszystkich: 76
wybranych: 72
-
Katalog
Filtry wybranego katalogu
Wyniki wyszukiwania dla: złożoność obliczeniowa
-
Postępy algorytmiki i ich wpływ na rozwój informatyki w Polsce
PublikacjaPublikacja prezentuje najważniejsze polskie i światowe postępy algorytmiki i ich wpływ na rozwój informatyki w Polsce. w szczególności omówiono takie zagadnienia jak badanie pierwszości liczb, programowanie liniowe, płaskie rysowanie grafów i szybkie mnożenie macierzy.
-
Two-Rate Based Low-Complexity Variable Fractional-Delay FIR Filter Structures
PublikacjaThis paper considers two-rate based structures for variable fractional-delay (VFD) finite-length impulse response (FIR) filters. They are single-rate structures but derived through a two-rate approach. The basic structure considered hitherto utilizes a regular half-band (HB) linear-phase filter and the Farrow structure with linear-phase subfilters. Especially for wide-band specifications, this structure is computationally efficient...
-
The complexity of minimum-length path decompositions
PublikacjaWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
An efficient algorithm for finding ideal schedules
PublikacjaPodejmujemy problem szeregowania zadań jednostkowych z zadanymi czasamy przybycia i zależnościami kolejnościowymi. Uszeregowanie jest idealne jeśli jednocześnie minimalizuje maksymalny oraz średni czas zakończenia zadania. Podajemy przyklad pokazujący, że uszeregowania idealne nie istnieją dla relacji zależności zadań będącej drzewem, gdy dopuścimy możliwość wystąpienia przerwań. Z drugiej strony podajemy algorytm o złożoności...
-
Connected searching of weighted trees
PublikacjaW pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.
-
The complexity of zero-visibility cops and robber
PublikacjaWe consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...
-
Zero-visibility cops and robber and the pathwidth of a graph
PublikacjaWe examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...
-
The Complexity of Zero-Visibility Cops and Robber
PublikacjaIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
On minimum cost edge searching
PublikacjaWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Three-fast-searchable graphs
PublikacjaIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
Cztery algorytmy, które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublikacjaOdcinek ten poświęcony jest problemowi programowania liniowego oraz problemowi badania liczb pierwszych.
-
Cztery algorytmy które wstrząsnęły światem. Część I: Rys historyczny
PublikacjaOpracowanie jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki teoretycznej. Wprowadzono w w arkana złożoności obliczeniowej i sztuki programowania komputerów.
-
Clearing directed subgraphs by mobile agents
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 S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
Shared processor scheduling of multiprocessor jobs
PublikacjaWe study a problem of shared processor scheduling of multiprocessor weighted jobs. Each job can be executed on its private processor and simultaneously on possibly many processors shared by all jobs. This simultaneous execution reduces their completion times due to the processing time overlap. Each of the m shared processors may charge a different fee but otherwise the processors are identical. The goal is to maximize the total...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan wśród ludożerców
PublikacjaWprowadzono do zagadnień złożoności czasowej i pamięciowej
-
Building a Nest by an Automaton
PublikacjaA robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan w krainie czarów
PublikacjaWprowadzono w zagadnienia NP-zupełności na przykładzie problemu Suma Podzbioru
-
Finding small-width connected path decompositions in polynomial time
PublikacjaA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Cops, a fast robber and defensive domination on interval graphs
PublikacjaThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Cykliczny system otwarty z ograniczeniami obustronnych przestojów
PublikacjaW pracy badany jest system otwarty, który pracuje cyklicznie, tj. po ukończeniu jednego zestawu zadań przetwarzany jest kolejny zestaw identycznych zadań. Narzucone jest przy tym ograniczenie polegające na braku przestojów zarówno po stronie procesów jak i zadań. Wykazana jest NP-trudność problemu konstrukcji uszeregowania spełniającego te założenia jak i problemu minimalizacji długość i cyklu.
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublikacjaSzeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...
-
Parallel scheduling by graph ranking
PublikacjaNr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...