2018 year, volume 22, issue 4 (PDF)

In memory of Vyacheslav Alexandrovich Buevich

Mikhalevich I.F. Requirements, principles, practice of creating domestic hardware-software platforms for automated systems in the protected execution of the critical information infrastructure of the Russian Federation

The paper sets out a system of requirements and principles that determine the methodological aspects of creating domestic hardware-software platforms for automated systems in the protected execution as the basis of the critical information infrastructure of the Russian Federation, describes the experience of creating a protected hardware-software platform "Sintez-HSP"that fully satisfies the most strict requirements for information security, reliability, scalability, ensuring the independence of critical information infra the structure of foreign technologies and software.

Keywords: automated systems in the protected execution, hardware-software platform, information security, critical information infrastructure, Sintez-HSP

Birjukov A.G., Chernov A.V., Chernova Yu.G., Sharovatova Yu.I. Penalty, barrier, quasi-barrier functions and functions inverse to them

The methods of external penalty functions, internal penalty functions and quasi-barrier functions for solving problems of mathematical programming are considered. New quasi-barrier functions are proposed. The theorems of convergence of the indicated methods to the solution of mathematical programming problems are proved. The properties of these functions are considered for their transformations: differentiation, integration, construction of functions inverse to them.

Keywords: external penalty functions, internal penalty functions, barrier penalty functions, inverse functions, quasi-barrier functions, mathematical programming problem, differential barriers, power differential barriers, entropy differential barriers, convergence of differential barriers methods to solving mathematical programming problems.

Botkholov A.J. Applying of the Viterbi algorithm to the recovering of an erased fragment of a musical composition

The problem of the recovering of an erased fragment of a musical composition based on the Viterbi algorithm, namely, the method based only on the Viterbi algorithm, the method using the Viterbi algorithm and also shifted height and shifted duration, the method based on the Viterbi algorithm and the principles of musical harmony are obtained. The method with the best result was found (Viterbi algorithm combined with the method of musical harmony), the method for estimating of the similarity of fragments was introduced, examples of melodies, the tacts of which were best recovered, are given. All methods are written into the program in the Java language, which solves the given task, in addition, the program GuitarPro is used, which helps to translate all the necessary information about the melody into a text format.

Keywords: the Viterbi algorithm, shifted height, shifted duration, chord harmonization.

Ryjov A.P., Ogorodnikov N.M. On one method of information retrieval personalization

In this paper we consider the problem of fuzzy user concepts personalization using the action of modifiers on certain fuzzy sets. The existing algorithm of personalization was investigated and modified; for its new version the number of iterations performed was estimated.

Keywords: fuzzy sets, personalization.

Mironov Andrew M. New mathematical model of authentication protocols and verification method based on this model

Authentication protocols are distributed algorithms designed to provide authentication of agents and the transfer of confidential information (cryptographic keys, etc.) in an insecure environment. They are used, for example, in electronic payments, electronic voting procedures, database access systems, etc. On the reason of the large financial and social damage in the case of the incorrect execution of such protocols, it is necessary to use mathematical methods to justify their correctness and security. In the present work, a new mathematical model of such authentication protocols is introduced, which provides a possibility to describe both the protocols and their properties. It is shown a possibility to solve problems of verification of authentication protocols.

Keywords: authentication protocols, distributed algorithms, verification.

Parfenov D.V. Generation of the ensemble of discrete orthogonal polynomials with a given node set

A computationally efficient method for generation the ensemble of discrete orthogonal polynomials of complex variable is motivated and proposed. The ensemble keeps orthogonality at a given arbitrary separate node set with unitary weight function. The detailed algorithm implementation for coefficient computation and polynomial sampling is presented in GNU Octave/Mathworks Matlab language. The complexity estimate is the least attainable.

Keywords: digital signal processing, robust interpolation, orthogonal polynomials of discrete complex variable, arbitrary nodes, coefficient computation, optimal algorithm, computational complexity.

Bistrigova A.V. Letter to the editor concerning the paper by Z. A. Niyazova “Learning of arithmetic sum of monotone conjunctions”

The complexity of learning functions with respect to the number of monotone conjunctions in their representation is studied in the paper “Learning of arithmetic sum of monotone conjunctions” by Z. A. Niyazova. In particular, lower and upper bounds on the number of queries one needs to learn the function, having no more than 2 conjunctions, are presented there. Here, we show that this result can be improved upon by one query.

Keywords: exact learning, sum of monotone conjunctions, membership queries.

Konovalov A. Yu. All absolute arithmetically realizable predicate formulas are classically true.

It is proved that every absolute arithmetically realizable predicate formula is classically true, but there is a classically true predicate formula that is not absolute arithmetically realizable.

Keywords: constructive semantics, realizability, arithmetic realizability, absolute realizability, formal arithmetic.

Chasovskikh A.A. Reduced criterial system of are precomplete classes in linear automata classes over finite fields

The sets of all precomplete classes in the classes of linear automata over finite fields are found, which are reduced criteria systems in these classes.

Keywords: finite automaton, linear automaton, composition operations, superposition operations, feedback, completeness problem, precomplete class, criterial system, reduced criterial system, adder, delay.

Reports of the seminar "Theory of Automata"

Golikov K.A. Learning systems with descrete control

The report outlines the work to create a discrete-control system learning algorithm for acting and achieving goals. Learning is based on trials and misses. The entire experience of the system is stored in the Database. The algorithm is optimized by two criteria: the accuracy of achieving the goals and the maximum reduction in training time. The reduction in training time is implemented mainly by reducing the number of trials using prediction methods and interpolation by experimental data.

Keywords: positioning, learning algorithm, robot, interpolation, approximation.

Dergach P.S., Kudryavtsev V.B. On the properties of languages that are stable to the drop/paste operations

The article is devoted to the drop and paste operations, which have been promoted by V.I. Levenshtein. Closure operators are introduced for these operations. For the paste operator the existence, finiteness and uniqueness of the basis in closed classes are proved, and for the drop operator, non-existence for the infinite class and existence, finiteness and uniqueness for the finite are proved. The automata complexity of closed classes is investigated. The problems of completeness,precompleteness,expressibility are solved.

Keywords: drop and paste operations; closed class; regular language; basis; automata complexity; problems of completeness,precompleteness,expressibility.

← Back to archive