Eng | Rus

“Informatics and Applications” scientific journal

Volume 8, Issue 1, 2014

Content   Abstract and Keywords   About Authors

ANALYSIS AND MODELING OF DISTRIBUTIONS IN HEREDITARY STOCHASTIC SYSTEMS.

  • I.N. Sinitsyn  Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Methods and algorithms for statistical and analytical modeling of one- and multidimensional distributions in hereditary stochastic systems (HStS) with Wiener and Poisson noises are considered. Nonlinear stochastic integrodifferential equations are presented. For dying physically realizable hereditary kernels, two ways of approximation (on the basis of linear operator equations and singular kernels) are described. Basic reduction algorithms of HStS to differential StS (DStS) are given. Detailed analysis of various approaches to statistical and analytical modeling of distributions in HStS reducible to DStS is given. These approaches are based: on the direct numerical integration DStS equations and numerical integration of equations for parameters (moments, quasi-moments, etc.) of orthogonal densities expansions. The detailed consideration of the method of statistical linearization (MSL) and of the method of normal approximation (MNA) in reducible HStS to DStS is presented. Numerical stability ofMSL andMNA algorithms is investigated. ForMSL problems, one-step strongmethods and algorithms of numerical integration (of various accuracy) for smooth and nonsmooth right hands ofHStS equations are described. Test examples for the IPI RAS software tool “IDStS” inMATLAB are considered. Special attention is paid to stochastic oscillations of the Duffing oscillator and the relay oscillator in hereditary stochastic media.

Keywords:  analytical and statistical modeling; differential system; hereditary kernel; hereditary system; integrodifferential system; parametrization of distribution; reducible system; singular kernel; stochastic system

ANALYSIS OF DELAYS IN SCHEDULING HOMOGENEOUS TASKS UNDER UNCERTAINTY.

  • Yu.E. Malashenko  Dorodnicyn Computing Center, Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation
  • I.A. Nazarova  Dorodnicyn Computing Center, Russian Academy of Sciences, 40 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The problem of management of the computationally resource-intensive tasks of search type allowing parallelization by the data is considered. Tasks arrive in a system at any time one by one or in groups; their service time is not known in advance. For processing planning, the optimization model is used which is based on current information on tasks performance: the sojourn time and the amount of data already processed. Using the model for each task, the portion of data to be processed in the plan period is determined. In calculations, required computational expenses are estimated and assumptions about the distribution laws of unknown tasks characteristics are not made. The proposed scheduling rule allows to form the order of task execution in dynamics, priority being given to “less intensive” tasks.

Keywords:  computationally intensive tasks; parallel computing; scheduling optimization; principle of guaranteed result

ESTIMATION OF RELIABILITY OF COMPLEX SYSTEMS WITH RENEWAL BASED ON ELEMENT TEST RESULTS .

  • I. V. Pavlov   Bauman Moscow State Technical University, 5, 2nd Baumanskaya Str.,Moscow 105005, Russian Federation

Abstract: The problem of confidence estimation of reliability of complex systems with network structure with repairable elements is considered. Estimation of reliability of a system is based on test results of its individual elements (subsystems). Existing methods for solving this problem are designed for relatively simple series-parallel structures consisting of elements with exponential distribution of time to failure. Solution of this problem is suggested for the more general model of “monotone structures” with independent renewable elements, as well as significantlymore general case of “aging” system elements (with monotonically increasing function of failure rate). It is assumed that elements of the system are restored regardless of the state of other elements. In addition, the solution of this problemis obtained in the natural, fromthe practical point of view, asymptotic behavior for the case of high reliability (fast recovery) system elements.

Keywords:  complex systems; network structures; reliability; time to failure; renewal time; resource function; failure rate function

EQUILIBRIUM PRINCIPLE APPLICATION TO ROUTING CONTROL IN PACKET DATA TRANSMISSION NETWORKS .

  • N. S. Vasilyev  Bauman Moscow State Technical University, 5, 2nd Baumanskaya Str., Moscow 105005, Russian Federation

Abstract: Annual exponential growth of data flows in large scale networks impels to search not only network hardware improvements but also more perfect routing control algorithms. In networks, it is impossible to use centralized algorithms of routing control. Parallel algorithms choice must be based on the principles of functional effectiveness and stability (equilibrium). In large-scale networks, there is a huge number of users’ pairs trying to achieve the maximally possible rate of data transmission by routing control. Thus, control must be based on multicriteria optimization ideas and methods. The Nash equilibrium (game formulation of the routing problem) formally presents optimality of transmission control in distributed systems. In the present paper, the equilibrium routing is proved to exist under general conditions. The solution is additionally shown to be effective in Pareto sense and computationally stable. An effective (quick and parallel) game theory algorithm is suggested and its convergence is proved.

Keywords: packet network; data flows; network metric; routing; vector criteria; multicriteria optimization; game problem; Nash equilibrium; Pareto effectiveness

ASYMPTOTIC PROPERTIES OF WAVELET THRESHOLDING RISK ESTIMATE IN THE MODEL OF DATA WITH CORRELATED NOISE .

  • A.A. Eroshenko   M.V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cibernetics, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Russian Federation
  • O.V. Shestakov  M.V. Lomonosov Moscow State University, Faculty of Computational Mathematics and Cibernetics, 1-52 Leninskiye Gory, GSP-1, Moscow 119991, Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: Wavelet thresholding techniques of denoising are widely used in signal and image processing. These methods are easily implemented through fast algorithms; so, they are very appealing in practical situations. Besides, they adapt to function classes with different amounts of smoothness in different locations more effectively than the usual linear methods. Wavelet thresholding risk analysis is an important practical task because it allows determining the quality of techniques themselves and equipment which is being used. In the present paper, asymptotical properties of mean-square risk estimate of wavelet thresholding techniques have been studied in the model of data with correlated noise. The conditions under which the unbiased risk estimate is consistent and asymptotically normal are given. These results allow constructing asymptotical confidence intervals for wavelet thresholding risk, using only the observed data.

Keywords:  wavelets; unbiased risk estimate; correlated noise; asymptotic normality

IMPLEMENTATION BASIS OF EXAFLOPS CLASS SUPERCOMPUTER .

  • I. Sokolov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, 44-2 Vavilov Str., Russian Federation
  • Y. Stepchenkov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, 44-2 Vavilov Str., Russian Federation
  • S. Bobkov  Scientific Research Institute for System Studies, Russian Academy of Sciences, 36 bld. 1, Nakhimovsky Prosp., Moscow 117218, Russian Federation
  • V. Zakharov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, 44-2 Vavilov Str., Russian Federation
  • Y. Diachenko  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, 44-2 Vavilov Str., Russian Federation
  • Y. Rogdestvenski  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, 44-2 Vavilov Str., Russian Federation
  • A. Surkov   Scientific Research Institute for System Studies, Russian Academy of Sciences, 36 bld. 1, Nakhimovsky Prosp., Moscow 117218, Russian Federation

Abstract: The paper deals with choice of a circuitry basis for implementation of microprocessors and communication environment of exaflops supercomputers. A comparative analysis of the characteristics of the digital circuits with different complexity which are implemented in the synchronous basis as well as in the self-timed (ST) one was performed. It has proved the fundamental advantages of ST circuits comparing to synchronous analogues: absence of hazards, a maximum reachable operability range, high performance, and relatively low power consumption. Transforming any synchronous circuit into its quasi-ST or ST implementation leads to extension of its operability range independently of its complexity. The advantages of ST circuits show up to the maximum extent when they are used for designing reliable equipment. Various methodologies of ST circuits development are discussed. A comparative analysis of ST circuit implementation in the generic basis of the delay-insensitive circuits that is suggested by the authors and in the NULL Convention Logic circuit basis is performed. It is demonstrated that the suggested basismakes it possible to synthesize the circuits with the best parameters of performance, complexity, and power consumption while developing standard digital circuits serving as the basis for designing high end computing systems and hardware.

Keywords: synchronous circuits; self-timed circuits; delay-insensitivity; NULL Convention Logic; performance; power consumption; fault tolerance

INFORMATION MODEL OF FULL-SCALE OBJECT AND ITS ATTITUDE CHANGES REPRESENTATION TECHNOLOGY .

  • O.P. Arkhipov   Orel Branch of Institute of Informatics Problems, Russian Academy of Sciences, 137 Moskovskoe Highway, Orel 302025, Russian Federation
  • Y.A. Maniakov   Orel Branch of Institute of Informatics Problems, Russian Academy of Sciences, 137 Moskovskoe Highway, Orel 302025, Russian Federation
  • D.O. Sirotinin   Orel Branch of Institute of Informatics Problems, Russian Academy of Sciences, 137 Moskovskoe Highway, Orel 302025, Russian Federation

Abstract: The article describes the information model of full-scale object and its attitude changes representation with the following integration of the obtained data into three-dimensional (3D) images technology. The proposed technology provides a simple way to create complex animations of 3D objects including changes of positions of various objects and of their form. The technology does not require highly qualified users or expensive equipment. It can be used to create educational software and encyclopedias, commercials, videos, movies, as well as for implementation presentation and transmission of visual information solutions, remote control systems, augmented reality, user interfaces, decision support systems, monitoring systems, and quality control.

Keywords:  stereoscopy; 3Dmodel; image processing; color characteristics; markers; 3Dreconstruction; animation

DYNAMIC CONTEXTS OF RELATIONAL-TYPE DATABASE .

  • S. V. Zykin   Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, 4 Acad. Koptyug Av., Novosibirsk 630090, Russian Federation

Abstract: The technology of dynamic formation of data presentation is sugessted. This technology is the development of online analytical processing. Data source is a relational database with any scheme (not necessarily hierarchical). Target data presentation is a composite table which allows to present multivariate data on a plane. This table assumes separate formation of dimensions with the following juxtaposition of measures to dimensions in the table. The foundation of data presentation is a table of connected joins, which satisfies contextual and logic restrictions. The algorithms used to form such tables are suggested and their properties are investigated. Special attention is given to contexts which are used to form tables of connected joins. The algorithm of directed search for creation of contexts is proposed and comparative analysis of algorithms of contexts formation is performed on an example. The investigated properties of contexts and the offered algorithms are intended to automate user work to form new data presentations.

Keywords:  relational database; context; lossless join; composite table

INTEGRATED MODELING OF LANGUAGE STRUCTURES FOR LINGUISTIC PROCESSORS OF KNOWLEDGE MANAGEMENT AND MACHINE TRANSLATION SYSTEMS .

  • E.B. Kozerenko   Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str., Moscow 119333, Russian Federation

Abstract: The paper is dedicated to research and integrated modeling of cognitive linguistic representations of language structures and the mechanisms for resolution of syntactic ambiguity in the process of creating linguistic processors for intelligent knowledge processing and machine translation systems. The technique of constructing the hybrid cognitive linguistic model for representation of language structures and resolution of their ambiguity on the basis of logical linguistic rules and vector spaces has been developed and specified. The method presented is new and rests on the modern level of development in science and technology. The following tasks have been carried out: comparative research of classification methods has been made with respect to linguistic problems; the effective method of mapping the vector of natural language structures into the expanded space of attributes for classification of new language objects and structures has been worked out; the focal sample of parallel texts of business and scientific documents in Russian, English, and French has been developed; the expanded system of new categories enhancing the representational power of the initial grammar variant has been formed; the extended semantic networks were employed for unified representation of the matched language structures and the experiments of vector spacesmethod application for resolution of syntactic ambiguity of the key language structures were performed; the grammatical formalismand the algorithmic representation have been designed of the parser in which the difficulties of translation including the language transformations are taken into account.

Keywords:  parallel texts; vector spaces; syntax; semantics; phrase structures; integrated models; machine translation; knowledge management

DEVELOPMENT OF LEARNING PROCESS CONTROL MODEL WITH COGNITIVE TECHNOLOGIES .

  • V.A. Marenko   Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, 4 Acad. Koptyug Av., Novosibirsk 630090, Russian Federation
  • O.N. Luchko  Omsk State Institute of Service, 13 Petrov Str., Omsk 644099, Russian Federation
  • O.S. Lupentsov  Omsk State Institute of Service, 13 Petrov Str., Omsk 644099, Russian Federation

Abstract: The paper describes the “Learning process” cognitive map in the form of a directed graph. Arcs of the directed graph are labeled with the agreed expert estimates. Objects on the cognitivemap are divided into the target factor and controlling factors. The quality of education is the target factor. Controlling factors are used to adjust the educational process. The paper provides information used to devise the model of the control factor of cognitive readiness of a student. Formalization of experimental data is carried out using the semantic differential method and fuzzy sets. The cognitive model of the educational process, which is a functional directed graph, is presented. The results of experiments simulating educational process management are shown. It is also shown that while the level of stability of external environment (viewed as a control factor) increases, the level of the quality of education (viewed as the target factor) also increases.

Keywords:  control; cognitive model; cognitive map; educational process; simulation experiment; semantic differential; fuzzy set

GENERAL BOUNDS FOR NONSTATIONARY CONTINUOUS-TIME MARKOV CHAINS .

  • A. I. Zeifman   Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
  • V.Yu. Korolev  Institute of Informatics Problems, 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
  • A.V. Korotysheva   Vologda State University, 15 Lenin Str., Vologda 160000, Russian Federation
  • S. Ya. Shorgin   Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: A general approach for obtaining perturbation bounds of nonstationary continuous-time Markov chains is considered. The suggested approach deals with a special weighted norms related to total variation. The method is based on the notion of a logarithmic norm of a linear operator function and respective bounds for the Cauchy operator of a differential equation. Special transformations of the reduced intensity matrix of the process are applied. The statements are proved which provide estimates of perturbation of probability characteristics for the case of absence of ergodicity in uniform operator topology. Birth–death–catastrophe queueing models and queueing systems with batch arrivals and group services are also considered in the paper. Some classes of such systems are studied, and bounds of perturbations are obtained. Particularly, such bounds are given for the Mt/Mt/S queueing system with possible catastrophes and a simplemodel of a queueing system with batch arrivals and group services is analyzed.Moreover, approximations of limiting characteristics are considered for the queueing model.

Keywords:  nonstationary continuous-time chains andmodels; nonstationaryMarkov chains; perturbation bounds; special norms; queueing models

ON APPROXIMATION AND CONVERGENCE OF ONE-DIMENSIONAL PARABOLIC INTEGRODIFFERENTIAL POLYNOMIALS AND SPLINES .

  • V.I. Kireev   Moscow State Mining University, 6 Leninskiy Prosp.,Moscow 119991, Russian Federation
  • M.M. Gershkovich  Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation
  • T.K. Biryukova  Institute of Informatics Problems, Russian Academy of Sciences, 44-2 Vavilov Str.,Moscow 119333, Russian Federation

Abstract: The methods for approximation of functions with one-dimensional (1D) integrodifferential polynomials of the 2nd degree and derived conservative parabolic integrodifferential splines are considered. In majority of applied computational tasks, accuracy of source data does not exceed precision of approximation by parabolic polynomials and splines. The nodes of conventional parabolic splines, based on differential matching conditions with approximated function (further named as differential splines), are shifted relatively to interpolation nodes in order to provide stability of approximation process. The shift between spline and approximation nodes complicates computational algorithms drastically. Additionally, traditional differential splines are not conservative, i. e., they do notmaintain integral characteristics of approximated functions. The novel integrodifferential parabolic splines that use integral deviation as criteria for matching a spline with a source function are presented. These splines are stable if spline nodes coincide with nodes of approximated functions and conservative with respect to sustaining area under curves. The theorems on approximation of mathematical functions with 1D integrodifferential parabolic polynomials and convergence of parabolic integrodifferential splines are proved. It is suggested to apply the proposed integrodifferential splines for development of mathematical data processing models for large area spread information systems.

Keywords:  spline; polynomial; integrodifferential; integrodifferential; approximation; interpolation; smoothing; estimation of errors; convergence theorem; mathematical data processing model

STABILITY ANALYSIS OF AN OPTICAL SYSTEM WITH RANDOM DELAY LINES LENGTHS .

  • E. Morozov   Institute of Applied Mathematical Research, Karelian Research Center, Russian Academy of Sciences, 11 Pushkinskaya Str., Petrozavodsk 185910, Russian Federation
  • L. Potakhina  Petrozavodsk State University, 33 Lenin Str., Petrozavodsk 185910, Russian Federation
  • K. De Turck   Ghent University, TELIN Department, 41 Sint-Pietersnieuwstraat,Gent B-9000, Belgium

Abstract: A new model of an optical buffer system is considered, in which the differences {.n} between the lengths of two adjacent fiber delay lines (FDLs) are random. This is an extension of themodel considered in [1] where these differences (also referred to as granularity) are constant, i. e., .n ß const. The system is modeled by utilizing the random-walk theory and closely-related asymptotic results of the renewal theory, such as the inspection paradox and the Lordenfs inequality. A stability analysis is performed based on the regenerative approach. Some numerical results are included as well, showing that the obtained conditions delimit the stability region with high accuracy.

Keywords:  optical buffer; stability; stochastic granularity; renewal theory; regeneration; inspection paradox; simulation

 

RUS