Parallelization of computations for generating combinations

• Autorzy: Novikov S.
• Języki publikacji: EN

Abstrakty

EN

An effective sequential algorithm and two parallel algorithms for generating combinations without repetitions of m out n of objects, represented by Boolean vectors, are proposed. One of them allows one to calculate starting and ending combinations for the subset, generated by each computing processor. The second algorithm firstly generates short (m-component) vectors on several computing processors. After that, by using special [n/m]-component vectors, it connects the short vectors into n-component Boolean vectors, each of which containing of exactly m units.

Słowa kluczowe

EN

sequential algorithm; parallel algorithm; Boolean vector; combinations without repetitions; combinations with repetitions; parallelization of computations

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2017
• Tom: Vol. 1-2(21)
• Strony: 47--62
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Novikov S.

• Institute of Mathematics and Computer Science, The John Paul II Catholic University of Lublin, Konstantynów Street 1H, 20-708 Lublin, Poland

Bibliografia

• 1. Lipski W.: Kombinatoryka dla programistów, Warszawa, Wyd. Naukowo-Techniczne, WNT, 274 pages, 2004.
• 2. Akl S.G.: Adaptive and optimal раrаllеl algorithms fоr enumerating permutations and combinations, The Computer Jouma1, 30. pp. 433-436, 1987.
• 3. Kokosiński Z.: On parallel generation of combinations in associative processor architectures, Tech. Rep. 96-1-007, University of Aizu, Aizu-Wakamatsu, Japan, 14 pages, 1996.
• 4. Torres M., Goldman A., Barrera J.: A parallel algorithm for enumerating combinations. Proceeding of the 2003 International Conference on parallel processing. https://pdfs.semanticscholar.org/d153/cf9b621cb3cbfdf943f5bde1d84c6b01a930.pdf
• 5. Zhou B.B., Brent R., Qu X., Liang W.F.: A novel parallel algorithm for enumerating combinations. In International Conference on Parallel Processing, Volume 2, pp. 70-73, 1996.
• 6. Novikov S.: Parallelization of computations for finding the rank of a rectangular matrix. Studia Informatica, Systems and information technology, Volume 1-2(17), Wyd. UPH, Siedlce, pp. 49-62, 2013.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).