09.2014 volume 18 issue 3 (PDF)

I.K. Nikiforov On the Intellectuality of Materials and Constructions

By analyzing the basic definitions of intelligence from various sources, the question is raised about the admissibility of applying the term intelligence to constructions and materials.

Keywords: intelligence, cognition, reason (reason), creativity, knowledge, abstraction, cybernetics, adaptation.

N.B. Novikov On one of Smale's problems

Based on the analysis of the history of scientific discoveries, as well as data from cognitive psychology and the theory of artificial intelligence, it was established that the main factors that exclude the algorithmic nature of creative activity in science are the probabilistic nature of inductive inference, the trial and error method (the method of sequential enumeration), the factor of chance in scientific discovery, and Gödel's incompleteness theorem. This allows us to solve S. Smale's 18th problem: what are the limits of intelligence, both artificial and human?

Keywords: creative activity, artificial intelligence, inductive inference, the factor of chance in scientific discovery, Gödel's incompleteness theorem.

D.V. Alekseev On the issue of restoring a three-dimensional body from flat projections

The paper considers the problem of restoring a three-dimensional image from the codes of its flat projections. An algorithm is described that works significantly faster than the one previously proposed in [3]. The results of computer experiments are presented to compare the speed of these algorithms: the old and the new.

Keywords: pattern recognition, affine transformations, geometric recognition, stereo vision.

D.A. Balakin, T.V. Matveeva, Yu.P. Pytyev, O.V. Falomkina Comparative Analysis of the Quality of Probabilistic and Possibility Models of Measuring and Computing Converters

The article considers computer modeling of probabilistic and possibility models of measuring and computing converters (MCC) based on two versions of the possibility theory and the dependence of the quality of the MCC as a measuring instrument on the quality of the measuring converter. A comparison of the quality of the MCC for the probabilistic and possibility models of measurement is carried out, and the problem of measurement reduction for the measurement model described by the second version of the possibility theory is solved.

Keywords: measuring and computing systems, reduction, sensor quality, second version of the possibility theory.

I.V. Malygin On the problem of forecasting ice jams on rivers

The problem of forecasting the formation of ice jams on northern rivers is considered. In the case when the locations of jams are known, it is necessary to forecast the power of the phenomenon. The combinatorial-logical approach of pattern recognition theory was used for the solution.

Keywords: pattern recognition, tests.

R.V. Shapovalov, D.P. Vetrov, A.A. Osokin, P. Koli Learning an Algorithm for Semantic Image Segmentation on a Sample with Various Types of Annotations

In the traditional formulation, the problem of semantic image segmentation uses a training sample of images labeled pixel by pixel. Obtaining such labeling requires significant human effort. A method for learning semantic segmentation is proposed that allows using less detailed information, the acquisition of which in practice requires less effort, for example, dense frames around objects in the image or a set of unique image labels.

Keywords: machine learning, structural support vector machine, loss function, semantic image segmentation.

G.V. Bokov On the Decidability of Derivability of Closed Terms and Expressibility of Operations on Them

The paper studies algebras of closed terms whose operations are defined by first-order formulas with a single equality predicate. For such algebras, it is shown that in the general case, the problem of derivability of terms is algorithmically undecidable. When considering special cases of the derivability problem, a Galois correspondence is constructed between operations and finite automata over terms. On its basis, sufficient conditions for the algorithmic decidability of special cases of the problem of derivability of terms and the problem of expressibility of operations on terms are proved.

Keywords: algebras of terms, derivability problem, expressibility problem, automata over terms, Galois correspondence.

E.E. Gasanov, D.V. Efremov Background Algorithm for Solving a Two-Dimensional Dominance Problem

The paper studies search algorithms used in the background mode and proposes a mathematical model of these algorithms based on the concept of an information graph. The paper also proposes a background algorithm for solving a two-dimensional dominance problem with linear memory costs and a constant average search time. For comparison, we note that a non-background algorithm, whose average search time is equal to a constant plus the average time to enumerate the answer, requires quadratic memory costs.x

Keywords: information graph model, dominance problem, background search.

M.V. Nosov Estimation of the Number of Polynomially Defined Functions

The paper presents the derivation of an estimate of the number of ways to partition the vertices of a unit cube by a polynomially defined surface.

Keywords: Boolean function, polynomial separability.

V.V. Osokin, M.V. Shegay Sentiment Analysis of Russian-Language Text

The task of sentiment analysis plays an important role in natural language processing. The problem of classifying Russian-language text into two classes depending on its emotional coloring is considered: positive and negative. The naive Bayesian classifier is used as a classifier. Various methods for feature selection are used, the obtained results are compared with the results of classification of English-language text. The accuracy of 78.4% is achieved on the given test data set.

Keywords: sentiment analysis, naive Bayesian classifier, feature selection.

T. R. Sytdykov Linear algorithm for constructing signal routing trees

The paper considers the problem of constructing a signal routing tree with given values ​​of signal delays to the tree leaves. An algorithm is proposed that, for a given multiset of natural numbers, constructs a tree in linear time with delays to the tree leaves that coincide with the elements of the given multiset, or says that such a tree cannot be constructed.

Keywords: synthesis of large integrated circuits, signal routing, buffer tree.

A.A. Chasovskikh Completeness conditions for linear-p-automaton functions

The completeness problem for the class of linear-automaton functions over the field GF(2) with composition operations was previously solved. In the present paper, this result is generalized to the class of linear-automaton functions over GF(p) for a prime p. All precomplete subclasses are found in the class under consideration.

Keywords: finite automaton, linear automaton, linear-automaton function, composition operations, completeness problem, completeness criterion, precomplete classes, adder, delay.

Yu.S. Shutkin Modeling of circuit control systems

The general problem of constructing various types of circuit control systems and some functionals of their complexity are considered. Particular attention is paid to the complexity of circuit modeling on a computer. A general method for modeling circuits that implement Boolean functions is proposed.

Keywords: circuits from functional elements, contact circuits, complexity of control systems, modeling.

← Back to archive