Wyniki wyszukiwania dla: ALGORYTMY ROZPROSZONE - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: ALGORYTMY ROZPROSZONE

Filtry

wszystkich: 33
wybranych: 28

wyczyść wszystkie filtry


Filtry wybranego katalogu

  • Kategoria

  • Rok

  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Wyniki wyszukiwania dla: ALGORYTMY ROZPROSZONE

  • Rozproszone kolorowanie grafów

    Publikacja

    - Rok 2006

    W pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.

  • Zachłanne algorytmy kolorowania grafów w modelu rozproszonym

    W artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.

  • Track-to-track fusion in tracking of multiple targets in clutter - a comparative study.

    Publikacja

    Przedstawiono i porównano algorytmy rozproszone wyznaczania trajektorii obiektów dynamicznych na podstawie danych z wielu źródeł. Rozważono przypadek, w którym dane dotyczące pozycji obiektów są zakłócone przez dodatkowe fałszywe wykrycia niezwiązane z obserwowanymi obiektami. Algorytmy rozproszone i centralne to dwie podstawowe klasy algorytmów służące do wyznaczania trajektorii obiektów dynamicznych na podstawie danych z wielu...

  • On the complexity of distributed graph coloring with local minimality constraints

    Publikacja

    - NETWORKS - Rok 2009

    Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Regulacyjne usługi systemowe w zakresie mocy czynnej. - P. Bićko.

    Publikacja

    - Rok 2011

    W pracy poddano krytycznej analizie aktualne zasady funkcjonowania rynku regulacyjnych usług systemowych w Krajowym Systemie Elektroenergetycznym. Badano powiązania procesów bilansowania mocy z bilansowaniem energii elektrycznej. W konsekwencji zidentyfikowano powiązania rynku usług regulacyjnych z Rynkiem Bilansującym. W pracy przedstawiono podstawowe uwarunkowania techniczne świadczenia omawianych regulacyjnych usług systemowych,...

  • Constructing a map of an anonymous graph: applications of universal sequences

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2010

    We study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2010

    Two mobile agents, modeled as points starting at differentlocations of an unknown terrain, have to meet. The terrain is a polygon with polygonal holes. We consider two versions of this rendezvous problem: exact RV, when the points representing the agents have to coincide at some time, and epsilon-RV, when these points have to get at distance less than epsilon in the terrain. In any terrain, each agent chooses its trajectory, but...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2010

    One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous...

    Pełny tekst do pobrania w portalu

  • Taking advantage of symmetries: gathering of asynchronous oblivious robots on a ring

    Publikacja

    - Rok 2008

    W pracy rozważano problem rendezvous (spotkania, zebrania) dla zbioru bezpamięciowych robotów umieszczonych na wierzchołkach cyklu nieskierowanego, niewyposażonych w urządzenia komunikacyjne. Przyjęto model systemu rozproszonego występujący w literaturze pod nazwą asynchronicznego systemu z cyklami Look-Compute-Move. Problem istnienia rozwiązania rozwiązano dla wszystkich konfiguracji poczatkowych składających się z więcej niż...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On the complexity of distributed greedy coloring

    Publikacja

    - Rok 2007

    W pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Grid Implementation of a Parallel Multiobjective Genetic Algorithm for Optimized Allocation of Chlorination Stations in Drinking Water Distribution Systems: Chojnice Case Study

    Solving multiobjective optimization problems requires suitable algorithms to find a satisfactory approximation of a globally optimal Pareto front. Furthermore, it is a computationally demanding task. In this paper, the grid implementation of a distributed multiobjective genetic algorithm is presented. The distributed version of the algorithm is based on the island algorithm with forgetting island elitism used instead of a genetic...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Bounds on the Cover Time of Parallel Rotor Walks

    Publikacja

    - Rok 2014

    The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Fast collaborative graph exploration

    Publikacja

    - INFORMATION AND COMPUTATION - Rok 2015

    We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

    Publikacja

    - Rok 2014

    We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • A Point Set Connection Problem for Autonomous Mobile Robots in a Grid

    Publikacja

    - COMPUTING AND INFORMATICS - Rok 2012

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Self-stabilizing algorithms for graph coloring with improved performance guarantees

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.

  • Bounds on the cover time of parallel rotor walks

    Publikacja

    - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - Rok 2016

    The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Leader election for anonymous asynchronous agents in arbitrary networks

    Publikacja

    - DISTRIBUTED COMPUTING - Rok 2014

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Universal Augmentation Schemes for Network Navigability

    Publikacja
    • P. Fraigniaud
    • C. Gavoille
    • A. Kosowski
    • E. Lebhar
    • Z. Lotker

    - THEORETICAL COMPUTER SCIENCE - Rok 2009

    Rozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu...

    Pełny tekst do pobrania w portalu

  • What Can Be Observed Locally? Round based models for quantum distributed computing

    Publikacja

    - Rok 2009

    W pracy rozważono zagadnienie lokalności w kontekście informacji kwantowej w obliczeniach rozproszonych. Rozważono dwa kwantowe rozszerzenia modelu LOCAL Liniala, otrzymane poprzez: (1) inicjalizację systemu w kwantowym stanie splątanym, (2) zastosowanie kwantowych kanałów komunikacyjnych. Dla obydwu typów rozszerzeń zaproponowano przykłady problemów, których złożoność rundowa ulega redukcji w porównaniu do oryginalnego modelu...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Multi-agent graph searching and exploration algorithms

    Publikacja

    - Rok 2020

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

    Pełny tekst do pobrania w portalu

  • On-line Search in Two-Dimensional Environment

    We 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. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...

    Pełny tekst do pobrania w portalu

  • Distributed largest-first algorithm for graph coloring.

    Publikacja

    - Rok 2004

    W artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.

  • An experimental study of distributed algorithms for graph coloring.

    W pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.

  • Energy optimisation in resilient self-stabilizing processes

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.

  • Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.

  • A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On greedy graph coloring in the distributed model

    Publikacja

    Artykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.