A parallel dynamic programming algorithm for unranking set partitions

Type: Article

Number of downloads: 796

Download resource

PDF

Cite

BibTeX EndNote

Title: A parallel dynamic programming algorithm for unranking set partitions
Variant of the title: Równoległy algorytm programowania dynamicznego do konwersji liczb porządkowych w podziały zbioru
Author: Kokosiński, Zbigniew
Published in: Technical Transactions
Numbering: Y. 110, iss. 3-AC
Pages: 29-38
Release date: 2013
Place of publication: Kraków
Publisher: Wydawnictwo PK
Language: English
Keywords: 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
Abstract: 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).
PKT classification: 390000 Automatyka
Department: Faculty of Electrical and Computer Engineering
License: Licencja PK
Access rights: Zasób dostępny dla wszystkich