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.

← Back to archive