12.2017 - volume 21 issue 4 (PDF)

Kurilenko N.V. Formal definition of Thesis M

Thesis M is introduced and described in terms of its basic problems with confirming or disproving it. A mathematical formulation of the problem is proposed and the simplest properties of the model are discovered. An example of a one-dimensional continuous cellular stricture in which an oracle machine can be implemented is constructed.

Keywords: Church-Turing thesis, Thesis M, cellular automata, continuous cellular automata.

Kutyanin A.R. Recommender systems: overview of main statements and results

Main recommender algorithms are considered in this paper. A meaningful formulation of the problem of finding N best recommendations is given, pros and cons are described for all mentioned approaches. Also reader can find papers and results overview starting from appearance of the first recommendation systems up to the present.

Keywords: Recommender systems, recommendation, collaborative filtering, item-based, user-based, content-based filtering, knowledge- based filtering, hybrid recommender system.

Mironov A.M. Verification of programs by the method of invariants

We present a method of invariants for proving the correctness of computer programs. The basic concepts associated with this method are illustrated by examples of verification of sequential and parallel programs.

Keywords: program verification, Floyd’s method, invariants

Ryjov A., Ilin I. About one model of influence in social networks

In this paper we provide a model of influence in social networks and study some of its properties. Primary purpose of the research was the study of influence matrix. The influence is considered as a function dependent on time, status and opinion of agents, for further analysis we give the interpretation of opposed opinions of agents. We also give two simple examples of social network based on this model and several cases of convergence of influence matrix. We show some differences between structure of this model with a limit matrix of influence and several other influence models of social networks.

Keywords: social network analysis, influence models.

Alexeev D.V. On a 3-dimensional body reconstruction using its planar projections

This article is devoted to the problem of 3D image reconstruction from its planar projections up to affine and metric equivalence. The necessary and sufficient conditions for the existence of solution are found.

Keywords: affine transformation, congruent transformation, isometry, image recognition, stereo reconstruction, stereovision.

Nosov M.V. Perceptron algorithm and linear programming

In the work perceptron algorithm is applied to solve linear programming problem with a nonempty interior region.

Keywords: рerceptron algorithm, linear programming.

A.P. Ryjov, P.A. Novikov One model of digital habits

The paper proposes the formalization of ways of using the information technologies on the basis of the analysis of smartphone’s logs. The resulting model of human interaction with other people and information resources (digital world) can be used to personalize such a digital environment and, accordingly, to optimize such interaction. A scenario for using the model to personalize the news feed is described.

Keywords: personalization, digital footprint, fuzzy clustering.

Gasanov E.E. On the functional complexity of the two-dimensional domination problem

In this paper we study the two-dimensional domination problem in which the database is a set of points on the plane, and it is necessary for an arbitrary point of the plane, interpreted as a search query, find all the points from the database, which exceed the query by both coordinates. Functional complexity is the function of the dependence of search time on the memory size. The paper shows how, using the Bentley-Maurer method, we can obtain algorithms with different search time and memory size ratio.

Keywords: information-graph data model, two-dimensional domination problem, functional complexity, grid method.

Dergach Peter Sergeevich About the maximum coverage of positive integers with some kind of restrictions

In this thesis it is necessary to find the maximum length of the beginning of natural set, that can be covered by the union of arithmetic progressions without covering this way all natural set. There are also some kind of restrictions on beginning and step of these progressions, and on their total number. Depending on what type of restrictions take place, we have a class of various tasks. Some of them were solved in this paper. The most interesting cases are types of restrictions like "beginning+step"and "quantity".

Keywords: natural set, arithmetic progression, maximum coverage.

M. Zh. Zholbaryssov, Yu. S. Shutkin Boolean networks stabilization problem

Problem of Boolean networks stabilization is considered. A criterion of stabilization is found depending on fixed components of Boolean network: graph, Boolean transition functions, initial state, order of update.

Keywords: Boolean networks, stabilization.

Ronzhin D.V. Linear automata over rational numbers field

We consider a class of linear automata over the field of rational numbers. In this class we prove there are no finite \[K\]-full systems and no finite \[\Sigma\]-full systems with infinte additive of special form. We construct an infinite \[K\]-basis and an infinite \[\Sigma\]-basis, and also an infinite \[\Sigma\]-full sistem which contains no \[\Sigma\]-basis.

Keywords: linear automata, rational numbers field, composition operations, superposition operations, \[K\]-closure, \[\Sigma\]-closure.

Volume 21 issue 3(PDF)

Alekseev V.B. On some results in algebraic complexity theory

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.

Koldoba E.V. Numerical simulation of the general black oil model near the critical point of solution

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.

Berger I.O. Algorithms of moving of the end of chain to the given point

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.

Mironov A.M. Security Protocols, Part 1

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.

Ananiev K.Y. About methods of constructing LDPC-codes with preset characteristics

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.

Dergach P.S., Radjabov J.I. On the length of a minimal alphabetical bonding in linear regular languages

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.

Yugay V.L. A criterion for polynomial completeness of quasigroups

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.