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

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




«INFORMATICS AND APPLICATIONS»
Scientific journal
Volume 7, Issue 4, 2013

Content | References | About  Authors

Abstract and Keywords.

STUDY OF THE DYNAMICS OF MULTIDIMENSIONAL STOCHASTIC SYSTEMS BASED ON ENTROPY MODELING.

  • A. N. Tyrsin   Science and Engineering Center «Reliability and Resource of Large Systems and Machines», Ural Branch, Russian Academy of Sciences, Yekaterinburg 620049, Russian Federation, at2001@yandex.ru
  • O. V. Vorfolomeeva  Chelyabinsk State University, Chelyabinsk 454001, Russian Federation, ya.olga.work@yandex.ru

Abstract: A new entropy approach of modeling of dynamics of stochastic systems is described. It is based on the representation of the system in the form of a multidimensional stochastic vector. It is shown that the change in entropy of a multivariate stochastic system can be expressed in terms of dispersions and conditional correlations of a component of a random vector. This allows to reveal the cause of the change in the entropy of the system and to evaluate it quantitatively. It was found that the entropy of a stochastic system consists of two components that characterize its properties. The first component determines the limit entropy corresponding to the full independence of the elements of the system and defines the consideration of the integral object as consisting of components (additivity). The second component reflects the extent of interrelation between the elements of the system, defining the properties of the system as a whole (integrity). This approach makes it possible to use entropy models in the diagnostics and control of stochastic systems as well as efficient management. The advantages of the proposed approach include the simplicity of implementation and interpretation of the mathematical model, the universality and adaptability for stochastic systems of different nature, the possibility of its use on small samples of data. The article contains an example of the practical application of a mathematical model.

Keywords:  multidimensional random variable; entropy; dynamics; stochastic system; dispersion; correlation

A LIMIT THEOREM FOR GEOMETRIC SUMS OF INDEPENDENT NONIDENTICALLY DISTRIBUTED RANDOM VARIABLES AND ITS APPLICATION TO THE PREDICTION OF THE PROBABILITIES OF CATASTROPHES IN NONHOMOGENEOUS FLOWS OF EXTREMAL EVENTS.

  • M. E. Grigor’eva  Parexel International, Moscow 121609, Russian Federation, maria2grigoryeva@yandex.ru
  • V. Yu. Korolev  Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, victoryukorolev@yandex.ru
  • I. A. Sokolov   Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, isokolov@ipiran.ru

Abstract: The problem of prediction of the probabilities of catastrophes in nonhomogeneous flows of extremal events is considered. The paper develops and generalizes some methods proposed by the authors in their previous works. The flow of extremal events is considered as a marked point stochastic processwith not necessarily identically distributed intervals between points (events). The proposed generalizations are based on limit theorems for geometric sums of independent not necessarily identically distributed random variables and the Balkema–Pickands–De Haan theory. Within the framework of the construction under consideration, the Weibull–Gnedenko distribution appears as a limit law for geometric sums of independent not necessarily identically distributed random variables. The efficiency of the proposedmethods is illustrated by the example of their application to the problemof prediction the time of the impact of the Earth with a potentially dangerous asteroid based on the data of the IAU(International Astronomical Union) Minor Planet Center.

Keywords:  catastrophe; extremal event; random sum; geometric sum; law of large numbers; Weibull–Gnedenko distribution; Balkema–Pickands–De Haan theorem; generalized Pareto distribution

THE DISTRIBUTION OF THE RETURN TIME FROM THE SET OF OVERLOAD STATES TO THE SET OF NORMAL LOAD STATES IN A SYSTEM  M|M|1|<L,H>|<H,R>   WITH HYSTERETIC LOAD CONTROL .

  • Yu. V. Gaidamaka   Peoples’ Friendship University of Russia, Moscow 117198, Russian Federation, ygaidamaka@sci.pfu.edu.ru
  • A. V. Pechinkin  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, apechinkin@ipiran.ru
  • R. V. Razumchik   Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, rrazumchik@ieee.org
  • A. K. Samuylov  Peoples’ Friendship University of Russia, Moscow 117198, Russian Federation, asam1988@gmail.com
  • K. E. Samouylov  Peoples’ Friendship University of Russia, Moscow 117198, Russian Federation, ksam@sci.pfu.edu.ru
  • I. A. Sokolov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, isokolov@ipiran.ru
  • E. S. Sopin  Peoples’ Friendship University of Russia, Moscow 117198, Russian Federation, sopin2eduard@yandex.ru
  • S. Ya. Shorgin  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, sshorgin@ipiran.ru

Abstract: An analytical method for studying the parameters of the hysteretic control, which is implemented as one of the effective solutions to the overload problem in the network of SIP2servers, is suggested. As a mathematical model, the queuing system  M | M | 1 | <L,H> | <H,R>   with two loops hysteretic control was developed, where H is the overload onset threshold, L is the overload abatement threshold, and R is the discard threshold. Two methods of calculating the Laplace–Stieltjes transform of the distribution function of the return time from the set of overload system states to the set of normal load system states were obtained. The first method consists in solving a system of equations with return times for each state of the set of overload system states as unknowns, the second deals with the recurrence for the Laplace–Stieltjes transform of the distribution function of the return time for each state of the set of overload system states as rational fractional expressions. Both methods allow the effective calculations with standard software tools, as shown in the numerical example.

Keywords:  SIP-server overload; queueing system; hysteretic load control; return time to normal load states; Laplace–Stieltjes transform; distribution function

ABOUT ONE TASK OF OVERLOAD CONTROL.

  • M. G. Konovalov   Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, mkonovalov@ipiran.ru

Abstract: The article considers the relatively simple task of congestion control. On the server with a finite number of places of service and potentially infinite queue, jobs are running, coming from the random flow. Control means the adoption of the decision on admission or rejection of each newly incoming job. Accumulation of the queue may result in loss of quality of service, because the period of execution of jobs is limited. At the same time, the rejection of application causes the loss of income. It is proved that in the case of exponentially distributed service time and for input flows, described as the renewal process with an arbitrary interarrival time distribution, optimum is a simple threshold strategy. The dependence of the limiting average income on the threshold value is unimodal. This circumstance greatly facilitates the search for the optimal integer value of the threshold. Experimental analysis shows that this dependence has a place for arbitrary distribution of service time and for general type of Markov modulated input flows.

Keywords:  congestion control; overload control; threshold strategy; job flow

FUNCTIONS OPTIMIZATION OF LAB - CONTRAST GRADED TRANSFORMATION.

  • O. P. Arkhipov   Oryol Branch, Institute of Informatics Problems, Russian Academy of Sciences, Oryol 302025, Russian Federation, arkhipov12@yandex.ru
  • Z. P. Zykova  Oryol Branch, Institute of Informatics Problems, Russian Academy of Sciences, Oryol 302025, Russian Federation, zykzoya@yandex.ru

Abstract: The purpose of this study is to create algorithm for custom conversion of contrast distribution on stepped-tone scales. The idea is to find suitable Lab-contrast distribution, keeping in mind that scaled distortion of digital representation of pixels would keep the real perception of color contrast all the same, if only less bright. In order to approximately calculate the function of Lab-contrast gradual conversion, this study considers two families of parametric algorithms, the first one uses subset of pixels on the scale as parameters, while the another one uses many gradations as they are. The problem of selecting the set of optimal parameters is solved by comparison of range of calculation errors achieved on a set of typical examples by the function of Lab-contrast distribution on stepped-tone scales. The study shows the function of Lab-contrast distribution on stepped-tone scales that gives the least error and provides example that proves that with optimal set of parameters chosen, it is not only possible to avoid visual distortion but the details can also be improved. These findings may be useful in management of maps of RGB-color images for PC peripherals in order to improve perceptive quality of details.

Keywords:  color reproduction; color perception; Lab-coordinate; contrast; gradation

METHOD OF BIBLIOGRAPHIC INFORMATION EXTRACTION FROM FULL-TEXT DESCRIPTIONS OF INVENTIONS.

  • I. M. Zatsman   Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, iz_ipi@a170.ipi.ac.ru
  • V. A. Havanskov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, havanskov@a170.ipi.ac.ru
  • S.K. Shubnikov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, sergeysh50@yandex.ru

Abstract: The method of bibliographic information extraction from full-text descriptions of inventions, which is necessary for analysis of thematic linkages between science and technologies, is considered. The research objective consists in the development of principles for creation of domestic information systems for calculation of indicators of thematic linkages. This type of information systems is new to the Russian scientific and technical sphere. Their creation is necessary for monitoring and evaluation of research and development programs and decision-making at all stages of program activities. The suggested method of bibliographic information extraction from the texts in natural language differs a lot from available foreign and domestic analogs. First, this method considers the fact that bibliographic information can be found inside the natural language text of descriptions of inventions. Second, paper bibliographic information is the structured information object, which is generally multilingual.

Keywords:  linkages between science and technologies; methodology of indicator calculation; information systems; architectural decisions; bibliographic information; patent documents

ON CONVERGENCE OF THE DISTRIBUTIONS OF RANDOM SUMS TO SKEW EXPONENTIAL POWER LAWS.

  • M. E. Grigor’eva  Parexel International,Moscow 121609, Russian Federation, maria-grigoryeva@yandex.ru
  • V. Yu. Korolev  Faculty of Computational Mathematics and Cybernetics, M.V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, victoryukorolev@yandex.ru

Abstract: An extension of the class of exponential power distributions (also known as generalized Laplace distributions) to the nonsymmetric case is proposed. The class of skew exponential power distributions (skew generalized Laplace distributions) is introduced as a family of special variance-mean normalmixtures. Expressions for the moments of skew exponential power distributions are given. It is demonstrated that skew exponential power distributions can be used as asymptotic approximations. For this purpose, a theoremis proved establishing necessary and sufficient conditions for the convergence of the distributions of sums of a random number of independent identically distributed random variables to skew exponential power distributions. Convergence rate estimates are presented for a special case of randomwalks generated by compound doubly stochastic Poisson processes.

Keywords:  random sum; generalized Laplace distribution; skew generalized Laplace distribution; exponential power distribution; symmetric stable distribution; one2sided stable distribution; variance2mean normal mixture; mixed Poisson distribution; mixture of probability distributions; identifiable mixtures; additively closed family; convergence rate estimate

INVERSION OF SPHERICAL RADON TRANSFORM IN THE CLASS OF DISCRETE RANDOM FUNCTIONS.

  • O. V. Shestakov   Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, oshestakov@cs.msu.su
  • M. G. Kuznetsova  Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, m.g.kuznetsova@gmail.com
  • I. A. Sadovoy   Department of Mathematical Statistics, Faculty of Computational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, isadovoy@gmail.com

Abstract: The paper deals with the problem of reconstructing the probabilistic distributions of random functions from distribution of spherical projections that describe the images in certain types of tomographic experiments, including optoacoustic tomography, thermoacoustic tomography, and radiolocation. The problems of this kind arise when the object under study may randomly change its structure during the registration of the projection data and the time within which its structure changes radically is considerably smaller than the time of registration of a required number of projections. In such cases, the conventional tomographic approach cannot be used directly. The authors assume that a randomobject may have at most countable set of structural states which are described by integrable functions with compact support. For such discrete class of randomfunctions, the uniqueness of solution is proved and the reconstruction method is developed which is based on the properties of the so-called moments of projections. It is shown that the developed method is stable and gives adequate results when the projection data are corrupted by noise.

Keywords:  random functions; spherical Radon transform; stochastic tomography

THE INFORMATION-ANALYTICAL COMPUTER SYSTEM “MEGALITH” IN OPTIMIZATION OF THE DIAGNOSIS AND TREATMENT OF UROLITHIASIS.

  • M. P. Krivenko  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, mkrivenko@ipiran.ru
  • S. A. Golovanov  Research Institute of Urology, Moscow 105425, Russian Federation, sergeygol124@mail.ru
  • P. A. Savchenko  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, psavchenko@ipiran.ru
  • A. V. Sivkov  Research Institute of Urology, Moscow 105425, Russian Federation, uroinfo@yandex.ru
  • A. P. Suchkov  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, asuchkov@ipiran.ru

Abstract: In this article, that is the first of an expected series of scientific publications, the results of research on automation of the information and analytical processes of the urolithic disease (ULD) survey, diagnosis, and treatment are discussed. A significant role in creating the systems of ULD diagnostics has the development of information technologies for clinical data collection and formation of specialized databases. The possibility of creation and the ways of realization of information-analytical computer system of collection, storage, and processing of the clinical data of patients examination, as well as programming decision-making processes in the diagnosis ULD and the choice of schemes of treatment and prevention of this disease has been studied. The developed mathematical methods and algorithms may be applied to the further fundamental scientific researches in the field of development of mathematical methods of medical and biological systems modeling; besides, they may be applied for necessary mathematical tools creation.

Keywords:  informational - analytical system; urology; computer diagnostics; treatment scheme; scheme of prevention

ANALYSIS OF DATA HOMOGENEITY OF THE CHEMICAL COMPOSITIONS OF STONES IN CASE OF UROLITHIASIS.

  • M. P. Krivenko  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, mkrivenko@ipiran.ru
  • S. A. Golovanov  Research Institute of Urology, Moscow 105425, Russian Federation, sergeygol124@mail.ru
  • A. V. Sivkov  Research Institute of Urology, Moscow 105425, Russian Federation, uroinfo@yandex.ru

Abstract: The article considers the methods for researching homogeneity of the data on chemical composition of urinary stones. Multidimensionality of the data, scarce spectrum of various values of indicators, impossibility to apply simple adequate likelihood models to them, and, also, absence of experience in such type of modeling in the field of urology are the cause of the considered problems specificity. The test of significance based on distance between sets of points in Euclidean space is suggested and analyzed. It is used to analyze a composition of stones dependence on the sex of a patient. In the case of analysis of changes in the composition of stones with time (as time goes), the proposed criterion is used as an element of pairwise comparisons of data for different time intervals. That is the first time when the idea of approximation of emerging relationships between groups of data with the help of equivalence relations is used. It allows reasonably carrying out the stratification of the original data. The experiments produced statistically valid results about the features of urolithiasis depending both on the sex of the patient and the changes over time.

Keywords:  tests of homogeneity; stratification; bootstrap method; urolithiasis

PREDICTION AND CLASSIFICATION METHOD FOR CENSORED DATA.

  • T. V. Zakharova   Department of Mathematical Statistics, Faculty ofComputational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, lsa@cs.msu.ru
  • E. M. Abramova  Department of Mathematical Statistics, Faculty ofComputational Mathematics and Cybernetics, M. V. Lomonosov Moscow State University, Moscow 119991, Russian Federation, houselake@gmail.com

Abstract: The classification method for noninsulin-dependent diabetes mellitus patients cohort is presented and the technique for identification of diabetes mellitus indicators is described. The basic medical data we dealt with turned out to be unfit for classification. The main obstacle for applying classical discrimination approaches was insufficiency and incompleteness of original data. For data processing, the authors suggest to select different sets of discriminant characteristics and to obtain classification functions for each set. The number of these sets depends on data incompleteness degree. The more data are omitted, the more different sets are needed. Each patient finally refers to the group, for which he gets the greater number of matches in classification. This multistep procedure reimburses small sample size and insufficiency and incompleteness of original data.

Keywords:  hypothesis; censored data; discriminant variables; classification functions; forecasting

CONCEPTUAL DECLARATIVE PROBLEM SPECIFICATION AND SOLVING IN DATA INTENSIVE DOMAINS.

  • L. Kalinichenko  Institute of Informatics Problems, Russian Academy of Sciences,Moscow 119333, Russian Federation, leonidandk@gmail.com
  • S. Stupnikov  Institute of Informatics Problems, Russian Academy of Sciences,Moscow 119333, Russian Federation, ssa@ipi.ac.ru
  • A. Vovchenko  Institute of Informatics Problems, Russian Academy of Sciences,Moscow 119333, Russian Federation, itsnein@gmail.com
  • D. Kovalev  Institute of Informatics Problems, Russian Academy of Sciences,Moscow 119333, Russian Federation, dm.kovalev@gmail.com

Abstract: Various notations aimed at defining the semantics of a computation in terms of the application domains have been experienced for conceptual modeling. For example, entity-relationship (ER) approach and UML (Unified Modeling Language) diagrams allow one to specify the semantics informally. Ontology languages based on description logic (DL) have been developed to formalize the semantics of data. However, it is now generally acknowledged that data semantics alone are insufficient and still representation of data analysis algorithms is necessary to specify data and behavior semantics in one paradigm. Moreover, the curse of ever increasing diversity of multistructured data models gave rise to a need for their unified, integrated abstraction to make specifications independent of real data in data intensive domains (DID). To overcome these disadvantages, a novel approach for applying a combination of the semantically different declarative rule-based languages (dialects) for interoperable conceptual specifications over various rule-based systems (RSs) relying on the logic program transformation technique recommended by the W3C (World Wide Web Consortium) Rule Interchange Format (RIF) has been investigated. Such approach is coherently combined with the specification facilities aimed at the semantic rule-based mediation intended for the heterogeneous data base integration. The infrastructure implementing the multidialect conceptual specifications by the interoperable RSs and mediating systems (MSs) is introduced. The proof-of-concept prototype of the infrastructure based on the SYNTHESIS MS and RIF standard is presented. The approach for multidialect conceptualization of a problem domain, rule delegation, rule-based programs and mediators interoperability is explained in detail and illustrated on a real nondeterministic polynomial time (NP) complete use-case in the finance domain. The research results are promising for the usability of the approach and of the infrastructure for conceptual, declarative, resource independent and reusable data analysis in various application domains.

Keywords:  conceptual specification; W3CRIF; logic rule languages; SYNTHESIS; database integration; mediators; RIF-BLD; RIF-CASPD; multidialect infrastructure; rule delegation

PROBABILISTIC METHODS FOR SELF - CORRECTING HARDWARE DESIGN.

  • S. Dolev  Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel, dolev@cs.bgu.ac.il
  • S. Frenkel  Institute of Informatics Problems, Russian Academy of Sciences, Moscow 119333, Russian Federation, Moscow Institute of Radio, Electronics, and Automation  «MIREA», Moscow 119454, Russian Federation, fsergei@mail.ru
  • D.E. Tamir  Department of Computer Science, Texas State University, San-Marcos, TX 78666, USA, dt19@txstate.edu

Abstract: This paper presents several ways for extending the scope of program self-correction methods, based on the “randomself-reducibility” property, to hardware design issues. The concept can be utilized for both analog and digital hardware-design. The extension is based on sampling, polynomial-interpolation, and error-correcting codes. In particular, the authors suggest using the well-known reconstruction of real-numerical functions for correcting faults remaining in analog and digital hardware, e. g., arithmetic logic units (ALU), after manufacturing testing. The present approach can complement the state-of-the-art technique of program self-correction by uniformly testing samples of operations and verifying the results of these samples.

Keywords:  self-correcting; real function computation; data analysis; interpolation