ОПТИМІЗАЦІЯ ПРОЦЕДУР ДЕКОМПОЗИЦІЇ ПЕРМАНЕНТУ З ВИКОРИСТАННЯМ АЛГОРИТМУ РОЗПАРАЛЕЛЮВАННЯ

Context. The problem of efficiently finding all permutations of a list of N elements is a key problem in many areas of computer science, such as combinatorics, optimization, cryptography, and machine learning. The object of the study was to analyze the procedure of permanent decomposition and propose an algorithm for its parallelization using modern features of working with threads in C#.Objective. The goal of the work is the creation of the algorithm for parallelizing the generation of permutations using permanent decomposition processes.Method. The main research method is the comparison of various algorithms with proposed parallelized algorithm, taking into account such criteria as accuracy and speed. Scientific works [10, 9, 17] present algorithms, including the regular permanent decomposition algorithm and the Johnson-Trotter algorithm. The Johnson-Trotter’s algorithm is one of the most effective, so it has been taken as some kind of benchmark.It is worth mentioning that each paralleling process has its own disadvantages, including additional resources needed fot datasynchronization between threads. This can be minimized using both technical abilities of modern programming languages and optimization of the algorithm itself.Results. The developed parallelized algorithm have improved performance of the regular permanent decomposition algorithm for solving the problem of finding all permutations.Conclusions. The conducted experiments have confirmed the proposed parallelized algorithm’s version is better from a performance standpoint than the regular one. The prospects for further research may include the application of the parallelized version of the algorithm to some practical tasks and comparison of the results.