|
«INFORMATICS AND APPLICATIONS»
Scientific journal
Volume 8, Issue 1, 2014
Content | Bibliography | About Authors
Abstract and Keywords.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 LordenЃfs 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
|
|
