A parallel dynamic programming algorithm for unranking set partitions

Typ: Artykuł

Liczba pobrań: 804

Pobierz zasób

PDF

Cytuj

BibTeX EndNote

Tytuł: A parallel dynamic programming algorithm for unranking set partitions
Wariant tytułu: Równoległy algorytm programowania dynamicznego do konwersji liczb porządkowych w podziały zbioru
Autor: Kokosiński, Zbigniew
Opublikowane w: Technical Transactions
Numeracja: Y. 110, iss. 3-AC
Strony: 29-38
Data wydania: 2013
Miejsce wydania: Kraków
Wydawca: Wydawnictwo PK
Język: angielski
Słowa kluczowe: set partition, unranking algorithm, associative algorithm, parallel dynamic programming

podział zbioru, algorytm konwersji liczby porządkowej w obiekt, algorytm asocjacyjny, równoległe programowanie dynamiczne
Abstrakt: In this paper, an O(n) parallel algorithm is presented for unranking set partitions in Hutchinson’s representation. A simple sequential algorithm is derived on the basis of a dynamic programming paradigm. In the parallel algorithm, processing is performed in a dedicated parallel architecture combining certain systolic and associative features. The algorithm consists of two phases. In the first phase, a coefficient table is created by systolic computations. Then, n subsequent elements of a partition codeword are computed, in O(1) time each, through associative search operations.

W artykule przedstawiono równoległy algorytm o złożoności O(n) dla wyznaczania podziału zbioru {1, ..., n} w reprezentacji Hutchinsona na podstawie jego liczby porządkowej. Prosty algorytm sekwencyjny opiera się na paradygmacie programowania dynamicznego. Algorytm równoległy łączy w sobie cechy programowania systolicznego i asocjacyjnego. Algorytm składa się z dwóch kroków. W pierwszej kolejności, za pomocą obliczeń systolicznych, wyznaczana jest tablica współczynników, zwanych liczbami Williamsona. Następnie, przez asocjacyjne wyznaczanie maksimum zbioru liczb, obliczanych jest n kolejnych elementów reprezentujących podział, każdy w czasie O(1).
Klasyfikacja PKT: 390000 Automatyka
Wydział: Wydział Inżynierii Elektrycznej i Komputerowej
Licencja: Licencja PK
Prawa dostępu: Zasób dostępny dla wszystkich