Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Równoległy algorytm programowania dynamicznego do konwersji liczb porządkowych w podziały zbioru
Języki publikacji
Abstrakty
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).
Czasopismo
Rocznik
Tom
Strony
29--38
Opis fizyczny
Bibliogr. 29 poz., wz., rys.
Twórcy
autor
- Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology
Bibliografia
- [1] Akl S.G., Parallel computation: models and methods, Prentice Hall, 1997, 475-509.
- [2] Akl S.G., Stojmenovič I., Generating combinatorial objects on a linear array of processors, [in:] Zomaya A.Y. (editor): Parallel Computing: Paradigms and Applications, Int. Thompson Comp. Press, 1996, 639-670.
- [3] Butler J.T., Sasao T., Hardware index to set partition converter, Proc. ARC’2013, Lecture Notes in Computer Science, Vol. 7806, 2013, 72-83.
- [4] Djokič B. et al., A fast iterative algorithm for generating set partitions, The Computer Journal, Vol. 32, 1989, 281-282.
- [5] Djokič B. et al., Parallel algorithms for generating subset and set partitions, Proc SIGAL Int. Symposium on Algorithms, Tokyo 1990.
- [6] Er M.C., A fast algorithm for generating set partitions, The Computer Journal, Vol. 31, 1988, 283-284.
- [7] Hankin R.K.S., West L.J., Set partitions, J. of Statistical Software, Vol. 23, Code Snippet 2 (December 2007), available at: http://www.jstatsoft.org/
- [8] Hutchinson G., Partitioning algorithms for finite sets, Comm. ACM, Vol. 6, 1963, 613-614.
- [9] Kapralski A., New methods for the generation of permutations, combinations and other combinatorial objects in parallel, Journal of Parallel and Distributed Computing, Vol. 17, 1993, 315-326.
- [10] Kapralski A., Modelling arbitrary sets of combinatorial objects and their sequential and parallel generation, monograph, Studia Informatica, Vol. 21, No. 2 (40), 2000.
- [11] Kaye R., A Gray code for set partitions, Information Processing Letters, Vol. 5, 1976, 171-173.
- [12] Knuth D.E., The art of computer programming. Fundamental algorithms, Addison-Wesley, 3rd edition, 1997.
- [13] Knuth D.E., The art of computer programming, Pre-fascicle 3B. Generating all partitions, Addison-Wesley, 2004.
- [14] Kokosiński Z., On generation of permutations through decomposition of symmetric groups into cosets, BIT, Vol. 30, 1990, 583-591.
- [15] Kokosiński Z., Circuits generating combinatorial objects for sequential and parallel computer systems, Monografia 160, Politechnika Krakowska, Kraków 1993.
- [16] Kokosiński Z., Mask and pattern generation for associative supercom-puting, Proc. 12th Int. Conf. Applied Informatics AI’94, Annecy 1994, 324-326.
- [17] Kokosiński Z., Algorithms for unranking combinations and their applica-tion, Proc. 7th Int. Conf. Parallel and Distributed Computing and Systems PDCS’95, Washington D.C., USA, 1995, 216-224.
- [18] Kokosiński Z., Unranking combinations in parallel, Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications PDPTA’96, Sunnyvale, CA, USA, Vol. I, 1996, 79-82.
- [19] Kokosiński Z., On parallel generation of set partitions in associative processor architectures, Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications PDPTA’99, Las Vegas, USA, Vol. III, 1999, 1257-1262.
- [20] Kokosiński Z., A parallel dynamic programming algorithm for unranking t-ary trees, Proc. PPAM’2003, Lecture Notes in Computer Science, Vol. 3019, 2004, 255-260.
- [21] Kokosiński Z., A new algorithm for generation of exactly m-block set partitions in associative model, Proc. PPAM’2005, Lecture Notes in Computer Science, Vol. 3911, 2006, 67-74.
- [22] Kokosiński Z., Parallel enumeration of t-ary trees in ASC SIMD model, Int. J. Computer Science and Network Security, Vol. 11, No. 12, 2011, 38-49.
- [23] Mirsky L., Transversal theory, Academic Press, 1971.
- [24] Semba I., An efficient algorithm for generating all partitions of the set {1, 2, ..., n}, Journal of Information Processing, Vol. 7, 1984, 41-42.
- [25] Stojmenovič I., An optimal algorithm for generating equivalence relations on a linear array of processors, BIT, Vol. 30, 1990, 424-436.
- [26] Stojmenovič I., On random and adaptive parallel generation of combinato-rial objects, Int. Journal of Computer Mathematics, Vol. 42, 1992, 125-135.
- [27] Tomic R.V., Quantized indexing: background information, Technical Report TR05-0625, 1st Works Corporation, June 25, 2005, 39.
- [28] Üçoluk G., A method for chromosome handling of r-permutations of n-element set in genetic algorithms, Proc. 4th Int. Conf. on Evolutionary Compu-ting ICEC’97, Indianapolis, USA, 55-58, 1997.
- [29] Williamson S.G., Ranking algorithms for lists of partitions, SIAM J. of Computing, Vol. 5, 1976, 602-617.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-9a4714f0-6fc8-47af-88c4-f30d239fd120