Kanarska I. Set-theoretic table operations and its complexity

The dissertation is devoted to the research of algorithms implementing intersection, union and difference in table algebras. For each set-theoretical operation are considered algorithms that implement them on tables. For each such operation, the basic, most natural algorithms that implement them are first considered, the found modifications of the basic algorithms are considered, which allow to significantly reduce the number of calculations. For all proposed algorithms time complexity was found in the worst case and on average, and calculated both the total number of computational actions and the complexity of each of the three data manipulations (addition, deletion and comparison) separately. On the basis of the theoretical estimates found for each of the three set-theoretical operations, the fastest algorithm that implements it is found. A software system has been developed that calculates the actual number of computations performed for each proposed algorithm and compares them with the theoretical estimates of complexity found on average. The software system confirmed the accuracy of the theoretical estimates found. Algorithms that implement set-table operations in the multitables, which the strings can be repeated are studied. For the set-theoretical multitable operations, the basic algorithms are considered, modifications of these algorithms are found that can reduce the number of computations; for all algorithms difficulty has been found in the worst case. With the help of computational experiments, the fastest algorithms implementing each set-theoretical operation for multitables was found. The following are the criteria in which the intersection, difference, projection, selection, join, active complement, division preserve the active domain.