«INFORMATICS AND APPLICATIONS»
Scientific journal
Volume 11, Issue 1, 2017

Content | About  Authors

Abstract and Keywords.

ANALYTICAL MODELING OF WIDE BAND PROCESSES IN STOCHASTIC SYSTEMS WITH UNSOLVED DERIVATIVES

• I. N. Sinitsyn Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: Finite dimensional nonlinear nonstationary and stationary stochastic systems with unsolved derivatives with broadband Gaussian and non-Gaussian noises are considered. Such equations describe technical devices in informatics and control. Two methods of analytical modeling and sensitivity analysis of nonstationary and stationary processes based on the methods of statistical linearization (MSL) and normal approximation (MNA) are developed. Typical nonlinearities with unsolved derivatives and MSL coefficients and test examples are given. The developed analytical modeling algorithms based on MSL are the basis of software tools for modeling reliability and security of technical devices.

Keywords: analytical modeling; method of normal approximation (MNA); method of statistical linearization (MSL); normal (Gaussian) stochastic process; sensitivity to parameters; stochastic system with unsolved derivatives

CLASSIFICATION BY CONTINUOUS-TIME OBSERVATIONS IN MULTIPLICATIVE NOISE I: FORMULAE FOR BAYESIAN ESTIMATE

• A. V. Borisov Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The two-part paper is devoted to the estimation of a finite-state random vector given the continuous-time noised observations. The key feature is that the observation noise intensity is a function of the estimated vector that makes useless the known results in the optimal filtering. The estimate is obtained both in the explicit integral form and as a solution to a stochastic differential system with some jump processes in the right-hand side.

Keywords: Bayesian estimate; optimal filtering; stochastic differential system; random jump process; multiplicative noise

REVERSIBLE DATA COMPRESSION BY UNIVERSAL ARITHMETIC CODING

• A. I. Stefanovich Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• D. V. Sushko Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The paper considers the general approach to the reversible (lossless) digital data compression problem, which is based on universal arithmetic coding of data with unknown statistics. A model of a source with calculable sequence of states is used for data description. Within the approach, the tasks of obtaining specific compression methods and algorithms for particular data types are set up. The authors use computed tomography data (tomograms) as the object of the study and present two methods of lossless compression of tomograms. The first method encodes prediction errors of tomograms; the second method encodes components of discrete wavelet transform of tomograms. These methods are examined in details, effective compression algorithms are constructed, and individual estimates of bit rate are obtained for the algorithms. The bit rates of the constructed algorithms and the lossless compression algorithms of the JPEG 2000 standard are compared. The results demonstrate high quality of the constructed algorithms and indicate great potential of the approach in general.

Keywords: reversible data compression; lossless compression; universal coding; arithmetic coding; computed tomography

A PROBABILISTIC MODEL FOR ESTIMATION OF SOFTWARE ROBUSTNESS TO SHORT-TERM HARDWARE FAILURES

• S. L. Frenkel Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• V. N. Zakharov Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• B. M. Basok Moscow Technological University "MIREA," 78 Vernadskogo Ave., Moscow 119454, Russian Federation

Abstract: The paper shows the possibility of using a two-dimensional Markov model defined on direct product of state spaces of two finite-state machines (FSM), one of which is a program finite automaton model that is running under normal conditions and the other one is the same FSM in which at some point in time, there was a short-term failure (e. g., within the time of a single operation or one machine cycle), for estimation of software robustness to short-term hardware failures. Previously, this model was proposed for probabilistic verification of hardware systems. The robustness of a program is estimated by probability of the faulty FSM return on the path of transitions of the source machine after termination of the failure. At the same time, the authors assume that a change in the FSM transitions trajectory in a low-level (instruction-by-instruction) program model will be significant only if it corresponds to some corruption in the branching of said block-diagram. The model is analyzed in detail by the example of the block-diagram of a specific program.

Keywords: self-repairing software; transient faults; Markovian models; testing

ON SOME MATHEMATICAL AND PROGRAMMING METHODS FOR CONSTRUCTION OF STRUCTURAL MODELS OF INFORMATION FLOWS

• A. K. Gorshenin Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The flows of events in the modern information systems are not regular; so, the methods of analysis based on the classical theorems that are correct only under certain regularity conditions can lead to false conclusions including underestimation of risks of extreme events. The key problem of practical modeling and analysis of nonstationary information flows is selection of statistical methods for estimation of the unknown model parameters.
For these purposes, the so-called method of moving the separation of mixtures based on a special decomposition of the original sample into subsamples (windows) and data analysis for each window within the framework of the mixed probability models is traditionally used by the members of Prof. V. Yu. Korolev's Scientific School. The paper describes the methods of stochastic data analysis based on the mixed probability models that can enhance the effectiveness of complex information systems research. The development and application of the proposed methods can be useful for the appropriate areas of applied mathematics and computer sciences.

Keywords: information system; mixed probability models; moving separation of mixtures; statistical data analysis; extremal values; noisy data; threshold; Peak Over Threshold; Pickands - Balkema - de Haan theorem; Renyi theorem; online software; matrix computing

MULTILEVEL MODELS FOR PATTERN RECOGNITION TASKS WITH MULTIPLE CLASSES

• A. A. Dokukin Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• V. V. Ryazanov Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation
• O. V. Shut Belarusian State University, 4 Nezavisimosti Av., Minsk 220030, Republic of Belarus

Abstract: The problem of choosing binary subtasks for recognition tasks with multiple classes is considered from the points of view of the algebraic and logical approaches to recognition. The limits of their applicability were studied theoretically. The sufficient condition of correctness of algorithms is stated as a result of research of dependency between the first and the second level algorithms. Additionally, the paper proves that the object resolution method is applicable to constructing new objects using the precedent information. As an applied result, two modifications of the ECOC (error-correcting output codes) method are proposed. The first one is based on optimization of the binary subtasks set. The second one develops ideas of the fuzzy object resolution method with classes described by multisets of codes of their precedents. The proposed modifications make it possible to increase the initial method's quality in various situations, which is demonstrated by the example of model and real-world tasks.

Keywords: classification; multiclass task; ECOC; multilevel method; correctness; algebraic approach; logical approach; code class description

ALGORITHM OF TRANSFORMATION OF A GRAPH INTO ANOTHER ONE WITH MINIMAL COST

• K. Yu. Gorbunov A.A. Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences, 19-1 Bolshoy Karetny Per., Moscow 127051, Russian Federation
• V.A. Lyubetsky A.A. Kharkevich Institute for Information Transmission Problems of the Russian Academy of Sciences, 19-1 Bolshoy Karetny Per., Moscow 127051, Russian Federation, Faculty of Mechanics and Mathematics, M. V. Lomonosov Moscow State University, Main Building, Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation

Abstract: The authors study orgraphs with any number of chains and cycles. Edges of orgraphs have unique names - natural numbers. There is a fixed list of operations that transform one graph into another. A cost is assigned to each operation. The task is to find the path of transformations with minimal total cost. This problem has a wide range of practical applications. The task is probably NP-hard and, thus, can be solved only under constraints imposed on costs or graphs. Such solutions are proposed in the study. The corresponding algorithms are linear in time and memory and are proved to be exact (nonheuristic), i. e., to find the path of transformations with minimal cost. Many heuristic algorithms solving this problem are known and tested on various data, but the proposed solutions are the first exact solutions.

Keywords: orgraph with chains and cycles; graph transformation; graph transformation with minimal total cost; exact linear algorithm; graph constraint; cost constraint; conditional shortest solution

MODELING INDIVIDUALIZATION OF THE LEARNING PROCESS IN THE FORM OF WEB CONFERENCE USING A HIERARCHICAL FUZZY EXPERT SYSTEM

• A. S. Alekseychuk Faculty of Applied Mathematics and Physics, Moscow Aviation Institute (National Research University), 4 Volokolamskoye Highway, A-80, GSP-3, Moscow 125993, Russian Federation
• A. V. Panteleev Faculty of Applied Mathematics and Physics, Moscow Aviation Institute (National Research University), 4 Volokolamskoye Highway, A-80, GSP-3, Moscow 125993, Russian Federation

Abstract: The paper describes a model of educational process in the form of web conference. The problem of individualization of learning process for each student is solved by selecting the appropriate level of difficulty for each lesson. The proposed method of individualization is implemented using artificial intelligence methods. The paper describes a software system that implements distance learning in the form of web conference as well as management of the learning process with a built-in hierarchical fuzzy expert system. This system assigns the most recommended level of difficulty of the upcoming lessons to each student using available initial data about the student and his or her previous grades. The system automatically generates a schedule where students with similar levels of performance are grouped together. An example of calculations made by the expert system is provided.

Keywords: distance learning; web conference; expert system; hierarchical fuzzy inference

SUPRACORPORA DATABASE ON CONNECTIVES: TERM SYSTEM DEVELOPMENT

• Anna A. Zaliznyak Institute of Linguistics, Russian Academy of Sciences, 1-1 Bolshoy Kislovskiy Per., Moscow 125009, Russian Federation, Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• I. M. Zatsman Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
• O. Yu. Inkova University of Geneva, 22 Bd des Philosophes, CH-1205 Geneva 4, Switzerland

Abstract: The article considers a supracorpora database (SCDB) - a new type of linguistic information resource.
The SCDB contains aligned parallel texts wherein source language sentences are aligned with target language sentences. One distinctive feature of the SCDB is that it supports annotating the examined linguistic items (in this case, connectives). Another important feature is that cross-linguistic annotating makes it possible to reveal a wide spectrum of new entities and concepts, both in informatics and linguistics. For description of these entities and concepts, a new multidisciplinary term system is proposed. On the one hand, the proposed terms are used by linguists for description of new basic knowledge generated as a result of contrastive analysis of Russian connectives.
On the other hand, the design of architecture and functional subsystems of the SCDB is based on these terms, and they are used for the development of respective information, linguistic and software tools. Finally, the term system is required for comparison of the presented outcomes of the project with similar results of other projects.

Keywords: supracorpora database; term system; connectives; linguistic annotation; parallel texts; corpus linguistics; chronotypical faceted classification

ON UNIQUENESS OF CLEARING VECTORS REDUCING THE SYSTEMIC RISK

• Kh. El Bitar Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France
• Yu. Kabanov Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France, Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation, National Research University "MPEI," 14 Krasnokazarmennaya Str., Moscow, 111250, Russian Federation
• R. Mokbel Laboratoire de Mathematiques, Universite de Franche-Comte, 16 Route de Gray, 25030 Besancon, CEDEX, France

Abstract: Clearing of financial system, i. e., of a network of interconnecting banks, is a procedure of simultaneous repaying debts to reduce their total volume. The vector whose components are repayments of each bank is called clearing vector. In simple models considered by Eisenberg and Noe (2001) and, independently, by Suzuki (2002), it was shown that the clearing to the minimal value of debts accordingly to natural rules can be formulated as fixpoint problems. The existence of their solutions, i. e., of clearing vectors, is rather straightforward and can be obtained by a direct reference to the Knaster-Tarski or Brouwer theorems. The uniqueness of clearing vectors is a more delicate problem which was solved by Eisenberg and Noe using a graph structure of the financial network. The uniqueness results have been proved in two generalizations of the Eisenberg-Noe model: in the Elsinger model with seniority of liabilities and in the Amini-Filipovic-Minca type model with several types of illiquid assets whose firing sale has a market impact.

Keywords: systemic risk; financial networks; clearing; Knaster-Tarski theorem; Eisenberg-Noe model; debt seniority; price impact

INFORMATICS AND ITS ROLE FOR THE STUDY OF GENESIS AND PROPERTIES OF COMPLEX NATURAL SYSTEMS

• R. B. Seyful-Mulyukov Institute of Informatics Problems, Federal Research Center “Computer Sciences and Control” of the Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The paper considers the history of cognition of information as a phenomenon and informatics as its quantitative and qualitative development. The logical connection between such notions as information, informatics, complexity, and complex natural self-organizing systems is investigated. It is considered that information, besides its usual traditional meaning, is one of the main properties of matter. Informatics is considered as an instrument for cognition of development and structure of complex natural systems. Petroleum is chosen as an example of such system. It is proved that petroleum, as well as each its hydrocarbon molecule, possesses corpuscular properties, and petroleum as a whole has information volume calculated in bits. A new approach is proposed for petroleum accumulations exploration. It is based on the fact that petroleum generation is a discrete process. Consequently, the process of discovering petroleum accumulations has two stages. The first stage is characterized by static uncertainty and the second stage is characterized by dynamic uncertainty. Both types of uncertainty need to be removed. The paper presents technologies and methods of solving these problems.

Keywords: informatics; informatization; complex natural system; petroleum origin; petroleum exploration; static uncertainty; dynamic uncertainty