TIME EFFICIENT ALGORITHM FOR THE GENERALIZED0 ENTROPYCALCULATION OF TWO-DIMENSIONS WORDS BY THE METHOD OF A SLIDING WINDOW
Journal Title: Современные информационные технологии и ИТ-образование - Year 2018, Vol 14, Issue 3
Abstract
In the article we consider methods for calculating the entropy of two-dimensional words of finite length over in finite alphabet, with reference to the problem of self-organization of rod-like particles on a torus. Monitoring the change in entropy allows a better understanding of the processes occurring during self-organization. To calculate the entropy, we use the sliding window method, which consists in finding unique configurations of windows in the matrix and counting the number of these configurations. Then, the entropy is calculated from the obtained counter values. The basic time complexity is required by the algorithms for counting the number of windows. Value of entropy is calculated quickly using known counters. Therefore, we purpose variants of asymptotically time efficient algorithms for counting the number of identical windows using the methods of conversion into an index, a search tree and a prefix tree. In this case, entropy is always calculated in the same way. The results of an experimental study of the software operating time implementations of these algorithms are presented: the minimum, maximum, and average operating time on a number of experiments for certain window sizes. The conclusions about the effectiveness of various algorithms, depending on the size of the window were made. We show the non-representativeness of the entropy calculated by the direct path is due to the disproportionately large number of possible existing unique configurations, even with small dimensions of the alphabet and the window. Finally, we purpose the method of quickly generalized entropy of two-dimensional words calculating instead of direct entropy.
Authors and Affiliations
Ilya Sedyakin, Michael Uljanov
Keywords
Related Articles
- EP ID EP515228
- DOI 10.25559/SITITO.14.201803.560-566
- Views 109
- Downloads 0
EDUCATIONAL PROGRAM ON HPC TECHNOLOGIES BASED ON THE HETEROGENEOUS CLUSTER HYBRILIT (LIT JINR)
The article highlights the issues of training personnel for work with high-performance computing systems (HPC), as well as of support of the software and information environment which is necessary for the efficient use o...
SFIA - THE SYSTEM OF IT PROFESSIONAL STANDARDS FOR THE DIGITAL ECONOMY
SFIA is a system of professional IT standards, it’s first version was developed at the beginning of this century in the UK for the information age, and the current sixth version meets the requirements of the digital econ...
INNOVATIVE DIDACTIC ELECTRONIC RESOURCES AND TEACHER'S PRODUCTS IN IT-EDUCATION
The article describes the design and implementation of computer support for the teacher’s activities, which combines such opportunities as data accounting and analysis, the use of pedagogical technology, and the situatio...
COMPARISON OF SOLVING A STIFF EQUATION ON A SPHERE BY THE MULTI-LAYER METHOD AND METHOD OF CONTINUING AT THE BEST PARAMETER
A stiff equation, linked with the solution of singularly perturbed differential equations with the use of standard methods of numeral solutions of simple differential equations often lead to major difficulties. First dif...
NONTRIVIAL PERIODIC SOLUTIONS OF THE SIN-GORDON EQUATION
In this paper, we study the problem of time-periodic solutions of the sin-Gordon equation with Neumann and Dirichlet boundary conditions on an interval. The novelty of the paper lies in the fact that in previous papers t...