Институт проблем информатики Российской Академии наук
Институт проблем информатики Российской Академии наук
Российская Академия наук

Институт проблем информатики Российской Академии наук




«INFORMATICS AND APPLICATIONS»
Scientific journal
Volume 13, Issue 1, 2019

Content | About  Authors

Abstract and Keywords.

INTERPOLATONAL ANALYTICAL MODELING IN COMPLEX STOCHASTIC SYSTEMS
  • I. N. Sinitsyn   Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Methods and algorithms for interpolational analytical modeling (IAM) of stochastic processes in complex continuous and discrete stochastic systems (StS) which are scalar (or vector StS reducible to scalar) are developed. Several types of continuous and discrete StS are considered. The IAM methods are based on evolutionary equations numerical interpolation solution for one-dimensional characteristic function (c.f.). Special attention is paid to c.f. sensitivity analysis. In basic IAM algorithms, the Kotel'nikov theorem was implemented. Some practical questions concerning interpolational formulae and number of intervals for interpolation are discussed. In the future, IAM for StS with known analytical structure for offline modeling will be based on spline-wavelet methods and for online modeling - on filtration approaches. Special attention should be paid to multidimensional distributions. Keywords: one-dimensional characteristic functions (c.f.); one-dimensional probability density (p.d.); stochastic processes (StP); stochastic system (StS)

Keywords: one-dimensional characteristic functions (c.f.); one-dimensional probability density (p.d.); stochastic processes (StP); stochastic system (StS)

STOCHASTIC DIFFERENTIAL SYSTEM OUTPUT CONTROL BY THE QUADRATIC CRITERION. II. DYNAMIC PROGRAMMING EQUATIONS NUMERICAL SOLUTION
  • A. V. Bosov   Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • A. I. Stefanovich   Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The second part of the optimal control problem investigation for the Ito diffusion process and the controlled linear output is presented. Optimal control for output dzt = atyt dt + btzt dt + ctut dt + at dwt of the stochastic differential system dyt = At(yt) dt + >t(yt) dvt and quadratic quality criterion defined by Bellman function having form Vt(y, z) = atz2 + @t(y)z + Yt(y) is determined numerically by an approximate solution to the grid methods of differential equations for the coefficients at, j3t(y), and 7 t(y). A model experiment based on a simple differential presentation for the RTT (Round-Trip Time) parameter of the TCP (Transmission Control Protocol) network protocol is considered in detail. The results of numerical simulation are given and allow one to assess the difficulties in the practical implementation of the optimal solution and define the tasks of further research.

Keywords: stochastic differential equation; optimal control; dynamic programming; Bellman function; Riccati equation; linear differential equations of parabolic type

ON A CLASS OF FILTERING PROBLEMS ON MANIFOLDS
  • K. A. Rybakov  Moscow Aviation Institute (National Research University), 4 Volokolamskoye Shosse, Moscow 125993, Russian Federation

Abstract: The goal of the paper is to describe stochastic differential systems whose trajectories belong to a smooth manifold as an application to the optimal filtering problem. An additional condition is that not only system trajectories belong to the given manifold, but also the estimation results for these trajectories (solution of the optimal filtering problem with the minimum mean-squared error) belong to this manifold. Diffusion and jump- diffusion systems are considered. These systems can be driven by the Wiener process and the Poisson process. The main result is the conditions on coefficients of the equation for the estimated random process. These conditions are obtained on the basis of the first integral concept for the stochastic differential equation and some of its properties.

Keywords: invariant; estimation; manifold; optimal filtering; random process; stochastic differential system

ON THE NUMBER OF MAXIMAL INDEPENDENT ELEMENTS OF PARTIALLY ORDERED SETS (THE CASE OF CHAINS)
  • E. V. Djukova  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 42 Vavilov Str., Moscow 119333, Russian Federation, Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
  • G. O. Maslyakov  Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
  • P. A. Prokofyev  Mechanical Engineering Research Institute of the Russian Academy of Sciences, 4 Bardina Str., Moscow 119334, Russian Federation

Abstract: One of the central intractable problems of logical data analysis is considered - dualization over the product of partially ordered sets. The authors investigate an important special case where each order is a chain. If the power of each chain is two, then the problem under consideration is to construct the reduced disjunctive normal form of a monotone Boolean function given by a conjunctive normal form. This is equivalent to enumerating irreducible covers of a Boolean matrix. Provided the growth of the row's number of the Boolean matrix to be less than the growth of the column's number, the asymptotic for the typical number of irreducible covers is known.
In the present work, a similar result is obtained for the dualization over the product of chains when the power of each chain is more than two. Obtaining such asymptotic estimates is a technically complex task and is necessary, in particular, to justify the existence of asymptotically optimal algorithms for the problem of monotonic dualization and various generalizations of this problem.

Keywords: problem of dualization; product of partially ordered sets; chain; covering of a Boolean matrix; ordered covering of an integer matrix; asymptotically optimal algorithm

VULNERABILITY ANALYSIS OF MULTIPOLAR NETWORKS AFTER STRUCTURAL DAMAGES
  • Yu. E. Malashenko  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 42 Vavilov Str., Moscow 119333, Russian Federation
  • I. A. Nazarova  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 42 Vavilov Str., Moscow 119333, Russian Federation
  • N. M. Novikova  Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 42 Vavilov Str., Moscow 119333, Russian Federation

Abstract: A method to obtain informative estimates of functionality changes in a multistock network system after possible damages has been proposed. Within the framework of the transmission model of single-commodity flow, the authors study the set of achievable flow vectors satisfying the standard conditions of conservation and constraints on the flows along arcs. To analyze the initial state of the system, for each stock arc, the maximum flow has been calculated separately and independently of the flow value across the remaining stock arcs. The corresponding minimal cut separates this stock vertex from the source. All arcs of the found minimal cut are removed model-wisely and in the network which is damaged in this way, the possibilities of transmission flows to other stock vertices have been estimated. The maximum flows for the vertex have been calculated and compared with their initial values. Estimates of losses have been compared for various minimal cuts. Influences of these structural damages have been constructed for all stock vertices. The vertices' aggregated characteristics of the structural damage effect have been calculated.

Keywords: structural network vulnerability; sensitivity to critical damage; multipolar flow model

LOCAL APPROXIMATION MODELS FOR HUMAN PHYSICAL ACTIVITY CLASSIFICATION
  • D. A. Anikeyev  Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation
  • G. O. Penkin  Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation
  • V. V. Strijov  Moscow Institute of Physics and Technology, 9 Institutskiy Per., Dolgoprudny, Moscow Region 141700, Russian Federation, A. A. Dorodnicyn Computing Center, Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The research is devoted to the time series classification. The time series is measured by an accelerometer of a wearable device. A class of physical activity is defined by its feature description of a time segment. To construct this description, the authors propose to use parameters of various approximation splines (algebraic, smoothing, adaptive regression, or spline with dynamic nodes). The logistic regression is used as a classifier. It delivers desired quality of the activity recognition. The authors analyze the space of the local approximation parameters. Classification accuracy depends on the method of this space construction. The computational experiment finds the optimal approximation parameters and parameters of the classifier.

Keywords: local approximation model; time series; classification; splines; feature space

INVERSION OF HOMOGENEOUS OPERATORS USING STABILIZED HARD THRESHOLDING WITH UNKNOWN NOISE VARIANCE
  • O.V. Shestakov  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: When inverting linear homogeneous operators, it is necessary to use regularization methods, since observed data are usually noisy. For noise suppression, threshold processing of wavelet coefficients of the observed signal function is often used. Threshold processing has become a popular noise suppression tool due to its simplicity, computational efficiency, and ability to adapt to functions that have different degrees of regularity at different domains. The paper discusses the recently proposed stabilized hard thresholding method that eliminates the main drawbacks of soft and hard thresholding methods and studies statistical properties of this method. In the data model with an additive Gaussian noise with unknown variance, an unbiased estimate of the mean square risk is analyzed and it is shown that under certain conditions, this estimate is asymptotically normal and the variance of the limit distribution depends on the type of estimate of noise variance.

Keywords: wavelets; threshold processing; unbiased risk estimate; asymptotic normality; strong consistency

ON THE UNIMODALITY OF THE INCOME FUNCTION OF A TYPE G|M|s QUEUEING SYSTEM WITH CONTROLLED QUEUE
  • Ya. M. Agalarov  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • V. G. Ushakov  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation

Abstract: The problem of maximizing the average income in a queuing system of type G|M|s on a set of pure stationary threshold strategies with single point switching access restriction mode is considered. The income function depends on the following parameters, measured in value units: the fee received for servicing requests, the cost of maintenance of the device, the deduction of income for the delay applications in the queue, the penalty for unserved applications. It is proved that the income function is unimodal on the set of considered threshold strategies. An algorithm for calculating the optimal threshold value and the corresponding maximum value income is proposed. The results of the computational experiment that illustrate the work of the proposed algorithm are given.

Keywords: multichannel queueing system; threshold management; maximizing income

A PRIORI FRECHET AND SCALED INVERSE CHI DISTRIBUTION IN BAYESIAN BALANCE MODELS
  • A. A. Kudryavtsev  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
  • S. I. Palionnaia  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
  • V. S. Shorgin  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: This article continues a series of authors' works in the field of modeling queuing systems using the Bayesian approach. The problem's statement is extended to a wider class of applied research - the study of the balance index of factors affecting the functioning of the system. It is assumed that the model parameters are divided into two classes, one of which includes factors that have a positive impact on the functioning of a complex aggregate and the other includes those that interferes with the functioning. The effectiveness of the system under study, of course, depends on the ratio of positive and negative factors, called the balance index. In the framework of the Bayesian approach, it is assumed that the factors are random variables with known a priori distributions. In a wide range of applied problems, it is reasonable to use gamma-type distributions. In this paper, the mixtures of particular generalized gamma distribution cases - the Frechet distribution and the scaled inverse chi distribution - are considered.

Keywords: Bayesian approach; scaled inverse chi distribution; Frechet distribution; gamma-exponential function; balance models; mixed distributions

POLYNOMIAL ALGORITHMS FOR CONSTRUCTING LOCAL AFFINITIES OF QUADRATIC BOOLEAN FUNCTIONS
  • O. A. Logachev  Information Security Institute, M. V. Lomonosov Moscow State University, 1 Michurinskiy Prosp., Moscow 119192, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • A. A. Sukayev  Information Security Institute, M. V. Lomonosov Moscow State University, 1 Michurinskiy Prosp., Moscow 119192, Russian Federation
  • S.N. Fedorov  Information Security Institute, M. V. Lomonosov Moscow State University, 1 Michurinskiy Prosp., Moscow 119192, Russian Federation

Abstract: Due to the affine normal form, one can consider a Boolean function as affine on certain flats in its domain - so-called local affinities. This Boolean function representation - affine approximation - could be useful for solving systems of nonlinear equations over two-element field. The problem of solving these systems (of a special sort) arises, in particular, in some methods of the information security tools design and analysis. The paper describes an approach to finding local affinities for quadratic Boolean functions which is based on Dickson's theorem. By this, one obtains affine normal forms for such functions. Besides, the paper concerns the efficiency of corresponding algorithms. This approach can be profitable for constructing efficient methods of solving systems of quadratic Boolean equations via "approximation" of corresponding Boolean functions by their affine normal forms.

Keywords: Boolean function; system of quadratic Boolean equations; vector space partition; flat; local affinity; Dickson's theorem; affine normal form (ANF) of Boolean function; algebraic cryptanalysis

OPTIMIZATION OF HYPERPARAMETERS OF NEURAL NETWORKS USING HIGH-PERFORMANCE COMPUTING FOR PREDICTION OF PRECIPITATION
  • A. K. Gorshenin  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation , Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Leninskie Gory, GSP-1, Moscow 119991, Russian Federation
  • V. Yu. Kuzmin  "Wi2Geo LLC," 3-1 Mira Prosp., Moscow 129090, Russian Federation

Abstract: The paper describes the procedure for tuning hyperparameters of the neural network for analyzing spatial meteorological data using the tools of the hybrid high-performance computing system. The comparison of precipitation forecasting accuracy has been carried out on the basis of such methods as grid and random searches. It has been demonstrated that even with a relatively small number of random choices of combinations of hyperparameters, it is possible to obtain an accuracy comparable to brute force, with moderate time costs. These results show the ability to automatically build a neural network architecture based on the general model for solving applied problems.

Keywords: artificial neural network; forecasting; deep learning; hyperparameters; high-performance computing; CUDA

SYNTHESIS OF GEODATA IN SPATIAL INFRASTRUCTURES BASED ON RELATED DATA
  • S. K. Dulin  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation, Research & Design Institute for Information Technology, Signalling and Telecommunications on Railway Transport (JSC NIIAS), 27-1 Nizhegorodskaya Str., Moscow 109029, Russian Federation
  • N. G. Dulina  A. A. Dorodnicyn Computing Center, Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation
  • S. Kozhunova  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Synthesis of spatial data from various sources available on the Web is the main task for modern applications that use information retrieval in the network and are aimed at making decisions based on geodata. This work is devoted to the synthesis of spatial data with an emphasis on its application in Spatial Data Infrastructures (SDIs).
The possibilities for integrating SDIs and semantic contexts are discussed subject to an agreed description and use of object characteristics relations. Classification and decomposition of synthesis processes in a service-oriented structure for servicing a wide range of queries are proposed.

Keywords: data synthesis; spatial data infrastructure; related data; semantic network

GOAL-ORIENTED DEVELOPMENT OF LINGUISTIC KNOWLEDGE SYSTEMS: IDENTIFYING AND FILLING OF LACUNAE
  • I. M. Zatsman  Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The description of the process of goal-oriented development of linguistic typologies as forms of knowledge representation about linguistic units in question is given. The task is to identify and fill the lacunae in the system of modern knowledge about the linguistic units. For identifying the lacunae, the selection of a reliable authority that reflects the current level of knowledge in the relevant subject area is necessary. The process of identifying the lacunae is a type of annotation of texts containing the linguistic units, using methods and means of informatics. As the source of new knowledge, parallel texts are used to fill the lacunae. They include original literary works and their translations. The objective of the paper is to describe the approach to identifying the lacunae in the process of annotating parallel texts containing the linguistic units and their translations.

Keywords: linguistic typology; parallel texts; computational linguistics; discovering new knowledge; information technology; goal-oriented development of typologies

RESOURCE QUEUING SYSTEMS WITH GENERAL SERVICE DISCIPLINE
  • A. V. Gorbunova  Peoples' Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • V. A. Naumov  Service Innovation Research Institute, 8A Annankatu, Helsinki 00120, Finland
  • Yu. V. Gaidamaka   Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • K. E. Samouylov   Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The article gives an overview of resource queuing systems with the concentration on the methods of their investigation. A valuable part of the article is devoted to the method, which leads to a significant simplification of the system analysis while maintaining high accuracy of the estimate, and in some cases without any loss of accuracy Simplification is to consider a system with random resource amount release at the instant of a customer departure instead of a system with the exact resource amount release equal to the occupied by the customer at the beginning of service. Subsequently, for the case of a Poisson flow of arrivals and exponential service time, the equivalence of the results for the initial and the simplified models was rigorously proved. In addition, a significant part of the paper is devoted to the overview of publications on the recurrent service discipline.

Keywords: resource queueing systems; continuous resource; discrete resource; limited resource; recurrent service; heterogeneous network; stationary distribution; semi-Markov process

COMPARATIVE ANALYSIS OF PERFORMANCE MEASURES FOR A WIRELESS MACHINE-TO-MACHINE NETWORK MODEL OPERATING WITHIN TWO RADIO RESOURCE MANAGEMENT POLICIES
  • E. V. Markova  Peoples' Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • A. A. Golskaia  Peoples' Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • I. L. Dzantiev  Peoples' Friendship University of Russia, 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation
  • I. A. Gudkova   Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation
  • S. Ya. Shorgin   Peoples' Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya Str., Moscow 117198, Russian Federation, Institute of Informatics Problems, Federal Research Center "Computer Science and Control" of the Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Currently, information and communication technologies (ICT) deeply penetrate into many areas of modern life. For example, the concept of integrating ICT and the Internet of Things for managing Smart City infrastructure allows city authorities to monitor changes and the situation in the city using sensors. Thus, specialized systems collect data automatically without human intervention. An important parameter in determining the performance of wireless networks of machine-to-machine (M2M) interaction - data transfer rates, blocking probabilities, becomes the distance between the device (sensor) and the radio transmitting equipment (base station, BS). Therefore, describing such a network in the form of a queuing system with streaming (guaranteed data transfer rate) or elastic traffic (nonguaranteed speed), it is necessary to consider the incoming stream of requests for data transmission of M2M devices in such a way as to take into account the distance between devices and BS. In this paper, there is built a cell model of a wireless network with stationary M2M devices that are in a passive or active state, shown by points that appear randomly on a plane. The devices generate streaming traffic which depends on the distance from the BS, the device transmit power, and the noise level. The state of the system is described by the vector of variable length, the components of which are the distance of each active device to the BS. Two different disciplines of radio resource separation are considered - "round robin" and "full power," which differ in the distribution of the time interval for servicing an M2M device and the data transfer rate provided. There is built a random process with states enlarged by the number of users and a formula for calculating the probability of blocking a data transfer request is proposed.

Keywords: wireless network; LTE; machine-to-machine communication; channel quality indicator; Shannon's formula; uniform distribution; round robin policy; full power policy; blocking probability