Русский
Volume 21 issue 3(PDF)
In this paper we give a survey of some results on the computa- tional complexity of algebras, in particular, obtained at the Department of Mathematical Cybernetics of the M.V. Lomonosov Moscow State University by the author and his students: Pospelov A.D., Chokaev B.V., Lysikov V.V.
Keywords: algebraic complexity, algebra, rank of algebra, bilinear complexity, multiplicative complexity, complexity of matrix multiplication.
For numerical simulation of phase transition in multicomponent solutions it is often used general Black oil model. In the study of the numerical instabilities of the model it has been discovered that they can arise from the mismatch thermodynamic functions near the critical point of solutions, which is known to be physically unstable by nature. All measured values because of fluctuations occurring in this region have significant measurement errors, leading to significant misalignment of model parameters and, respectively, to the numerical instabilities. We propose a physical approach to simulation such problems. It is explained some of the reasons for inaccurate of Black oil models.
The problem of chains is investigated. Results on the existence of chains obtained from given chain by moving of the end of the chain to a given point; Bounds of the minimum of the Euclidean distance between chains obtained from each other by moving of the end to a given point; possible number of chains obtained by moving the end to a given point and differing by the minimum number of elements from a given chain; the possible number of chains that are at the minimum distance from the given and obtained by moving the end of the chain to a given point, for n = 2 and n = 3. Algorithms for moving the end of a chain to a given point are described: an exponential algorithm that sorts out all possible chains with step ε, a linear algorithm giving an approximate solution for Euclidean distance, and a linear algorithm giving an exact answer for the Hamming distance and approximate for the Euclidean distance.
Keywords: chain, algorithm, upper bounds, lower bounds, Euclidean distance, Hamming distance.
The main cryptographic primitives used in security protocols are described (symmetric and asymmetric encryption systems, hash functions, secret sharing schemes), authentication protocols, and digital signature algorithms.
Keywords: protocols, security, cryptography, hash functions, authentication, digital signature.
The work presents algoritms for building test matrices for LDPC, which are codes based on a Tanner graph with a girth of 8. Other parameters of the graph, apart from the girth, include the division of degrees of character vertices: the ratio of portion of vertices with degrees 3 and 4 to their total number, as well as the speed of the code generated. The code is built for random speed and random division in linear time depending on the number of elements of the matrix.
Keywords: LDPC-codes, bipartite graph, division of degrees of vertices.
In the Ph.D. thesis [1] it has been found the upper bound on the minimal length of two words in regular language with similar image under alphabetic coding (if such pair of words exists at all). In this paper, we investigate the problem of finding corresponding lower bounds in subcase when regular languages have a linear growth function, and the coding scheme transforms all the letters of the input alphabet into the same symbol. For such encoding, the image of any word is uniquely determined by its length. Below we give lower bounds that coincide in order with the upper bounds from [1] for such languages and such coding. In addition, a more accurate upper estimate is given for this subcase.
Keywords: alphabetic coding, regular language, bonding.
We formulate and prove a criterion for the polynomial completeness of quasigroups in terms of precomplete classes of k-valued logic.
Keywords: quasigroup, polynomial completeness, quasilinearity.