CONTENTS

 

Stochastic Systems

Polyak B.T., Shcherbakov P.S. (ICS RAS, Moscow) Reachability and Attraction Domains for Linear Systems with Bounded Control: A Characterization via Invariant Ellipsoids

Ponyatskiy V.M. (KBP, Tula) Analysis of a Dynamic Plant with Constraints on the Output Coordinates Using the Invariant Plunging Method

Randomized Algorithms

Vakhitov A.T., Gurevich L.S. (SPbSU) Pseuogradient Method with Input Perturbations for Non-Stationary Unconstrained Optimization Problem

Misrikhanov M.Sh., Ryabchenko V.N. (METCC, Moskow) Randomized Algorithms for Computing the Invariant Zeros of Large-Scale Dynamic Systems

Queueing Systems

Aksenova E.A., Sokolov A.V. (IAMR KarSC RAS, Petrozavodsk) Analysis of Some Implementation Methods for Priority Queues

Drac A.V. (PU), Sokolov A.V. (IAMR KarSC RAS, Petrozavodsk) Allocation of $n$ Stacks and/or Queues in Single-Level Memory

Krivulin N.K. (SPbSU) Evaluation of Lyapunov Exponent for Stochastic Dynamic Models of Queuing Systems

Mosyagina E.N., Tchirkov M.K. (SPbSU) Optimal Control for Interdependent Periodically Nonstationary Stochastic Automata System in the Fuzzy Set Conditions

Learning and Adaptation

Vakhitov A.T.(SPbSU) Adaptive Parameter Estimation in the Multi-user Parallel Computing Systems

Vakhitov A.T., Gurevich L.S., Pavlenko D.V. (SPbSU) Stereovision Algorithms: A Survey

Le T.H. (SPbSU), Le A.V. (ELTEU, Hungary), Le T.K. (HueU, Vietnam) Statistical Methods of Automatic Word Extraction in Vietnamese Documents

Panshenskov M.A. (SPbSU) Adaptive Adjustment Method for Control Flow of Individual Tasks in Parallel Environment

Ponyatskiy V.M. (KBP, Tula) Analysis of Implementation Methods for Adaptive Control Systems with Kalman Filter

Khalidov V., Forbes F., Hansard M., Arnaud E., Horaud R. (Inria, Grenoble, France) Adaptive Audio-Visual Clustering for Multiple Object Localization

Shalymov D.S.( SPbSU) Cluster Stability Algorithms Based on Index or Stability Functions

Information Systems

Granichin O.N. (SPbSU), Granichina O.A.(HRSPU) Design of a Quality Monitoring Information System for the Education Process at the University Level

 

 

Stochastic Systems

Reachability and Attraction Domains for Linear Systems with Bounded Control: A Characterization via Invariant Ellipsoids

B. T. Polyak, P. S. Shcherbakov

Institute of Control Science, RAS, Moscow

boris@ipu.ru sherba@ipu.ru

Key words: attraction domain, invariant ellipsoid, linear matrix inequalities, absolute stability.

This paper is aimed at efficiently characterizing reachability and attraction domains of linear systems specified in the state space description. We consider bounded controls in the form of the linear static state feedback and saturated control. A description of reachability and attraction domains for such systems is given in terms of invariant ellipsoids using the apparatus of linear matrix inequalities and semidefi-nite programming formulation. Design of saturated control is based on the ideas of the theory of absolute stability.

Bibliogr.: 17 refs.

 

Analysis of a Dynamic Plant with Constraints on the Output Coordinates Using the Invariant Plunging Method

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: identification, dynamic plant, estimate, parameter, restrictions.

The approach for the analysis of the dynamic plant with constraints on the output coordinates based on the invariant plunging method is considered. The synthesis of algorithms for the estimation of a transfer ratio, time constant and a damping ratio for non-stationary dynamic plant with constraints on output coordinates is given. Simulation of the algorithms derived is performed and recommendations on their adjustment are presented. The estimation of a transfer ratio and time constant of the servodrive of the twirled pilotless aircraft is done using the agorithms proposed.

Bibliogr.: 8 refs.

 

Randomized Algorithms

Pseuogradient Method with Input Perturbations for Non-Stationary Unconstrained Optimization Problem

A. T. Vakhitov, L. S. Gurevich,

St. Petersburg State University

av38@yandex.ru, gurevich.lev@gmail.com

Key words: stochastic optimization, randomization, tracking, pseudo-gradient.

Applications of methods of stochastic optimization with simultaneous perturbations of input with two measurements on each step (SPSA type) to problem of global convex optimization of non-stationary functional are considered. Upper bound for estimation error of the algorithm is proven for almost arbitrary noise and one time differentiable functional.

Bibliogr.: 11 refs.

 

Randomized Algorithms for Computing the Invariant Zeros of Large-Scale Dynamic Systems

M. Sh. Misrikhanov, V. N. Ryabchenko,

Main electricity transmission company Center, Moskow

mms@mes-centra.ru rvn@mes-centra.ru

Key words: MIMO-system, invariant zeros, squaring up, eigenvalue problem, large electric power system.

An algorithm for the large dynamic MIMO-system invariant zeros determining problem is described. The problem of invariant zeros determining with the help of randomized squaring up of initial MIMO-system is reduced to the standard eigenvalues problem of numerical matrices. Practical applications of the algorithm proposed lie at the area of large electric power systems.

Bibliogr.: 10 refs.

 

 

Queuing Systems

Analysis of Some Implementation Methods for Priority Queues

E. A. Aksenova, A. V. Sokolov

IAMR KarSC RAS, Petrozavodsk

aksenova@krc.karelia.ru avs@krc.karelia.ru

Key words: priority queue, random walk, Markovs chains.

The paper presents the analysis of some priority queue realization methods. It is possible to produce operations: to insert, to delete the maximum, to find the maximum. Suppose that probabilities of operations are known. The priority queue is realized using array or k consecutive FIFO-queues. Mathematical models of this methods are developed. The task is to choose the method that maximizes the average time until memory overflow.

Bibliogr.: 9 refs.

 

Optimal Allocation of n Stacks and/or Queues in Single-Level Memory

A. V. Drac, A. V. Sokolov

Petrozavodsk University, IAMR KarSC RAS, Petrozavodsk

adeon88@mail.ru, avs@krc.karelia.ru

Key words: LIFO-stacks, FIFO-queues, linked list, Markovs chains, dynamical data structures.

This paper concerns issues related to building mathematical models and optimal algorithms of stacks and queues in single-level memory. These models are constructed as n-dimensional random walks.

Bibliogr.: 6 refs.

 

Evaluation of Lyapunov Exponent for Stochastic Dynamic Models of Queueing Systems

N. K. Krivulin

St. Petersburg State University

Nikolai@NK1200.spb.edu

Key words: stochastic dynamical system, Lyapunov exponent, idempotent algebra, queuing systems, mean service cycle time.

The problem of evaluation of Lyapunov exponent in queuing system analysis based on models and methods of idempotent algebra is considered. General existence conditions for the limit that determines Lyapunov exponent are given, and examples of evaluation of the limit for systems with matrices of particular types are presented. A method of evaluation of Lyapunov exponent is proposed based on some appropriate decomposition of the system matrix. A general approach to modeling of a wide class of queuing networks is considered, and examples of the models are given. It is shown how to find the value of mean growth rate of the system state vector through the evaluation of Lyapunov exponent. Results of evaluation of the mean growth rate for the models under consideration are presented.

Bibliogr.: 24 refs.

 

Optimal Control for Interdependent Periodically Nonstationary Stochastic Automata System in the Fuzzy Set Conditions

E. N. Mosyagina, M. K. Tchirkov

St. Petersburg State University

vakh@star.math.spbu.ru

Key words: periodically nonstationary stochastic automaton, automata system, fuzzy surroundings, fuzzy conditions, optimal strategy.

Synthesis procedure of complex optimal control for a periodically nonstationary stochastic utomat finite set, joined in an interdependent system, under condition of the fuzzy given goals representation in a complex particular tact and in view of non-stationary interdependent fuzzy conditions for controlling actions on automata, included in a system, are considered.

Bibliogr.: 5 refs.

 

Learning and Adaptation

Adaptive Parameter Estimation in the Multi-user Parallel Computing Systems

A. T. Vakhitov

St. Petersburg State University

av38@yandex.ru

Key words: scheduling, parallel computations, linear estimation, stochastic optimization.

The task of parallel computing system parameters estimation is described. The problem settings for the estimation of computing node performance, network bandwidth, task execution time are given. It is taken into consideration that the parameters can change in time. The estimates can be used by the scheduling algorithm. In the SPRInt laboratory of the SPbSU the scheduling service-broker for the modeling of the adron therapy experiments.

Bibliogr.: 14 refs.

 

Stereovision Algorithms: A Survey

A. T. Vakhitov, L. S. Gurevich, D. V. Pavlenko

St. Petersburg State University

av38@yandex.ru, gurevich.lev@gmail.com, dmit10@gmail.com

Key words: stereovision.

The stereovision problem is to obtain the distance based on inputs from two or more cameras. The input data may be a single image or video series. We consider the particular case when two images are compared.

Bibliogr.: 16 refs.

 

Statistical Methods of Automatic Word Extraction in Vietnamese Documents

Le Trung Hieu

St. Petersburg State University

Le Anh Vu University ELTE, Budapest, Hungary

Le Trung Kien Hue University, Vietnam

vkhhieukien@yahoo.com, leanhvu@inf.elte.hu, hieukien@hotmail.com

Key words: words localization in Vietnamese documents, statistical methods, adaptation.

In this paper, we implemented application of statistics on creating a Vietnamese list words and phrases. The aim of our projects is thus to build a common linguistic database that is freely and easily exploitable for the automatic processing of Vietnamese.

Bibliogr.: 15 refs.

 

Adaptive Adjustment Method for Control Flow of Individual Tasks in Parallel Environment

M. A. Panshenskov

St. Petersburg State University

mpansh@gmail.com

Key words: distributed computing, task scheduling, adaptive methods, communication.

The model of isolated task execution is formulated in extended control flow terminology. The two main classes of possible bottlenecks in the control flow are identified: data transfer through communication channels and task execution on the computing nodes. For each case the scheduling algorithm is proposed. The execution time upper bound depending on the size of the heterogeneous computing network is proposed.

Bibliogr.: 10 refs.

 

Analysis of Implementation Methods for Adaptive Control Systems with Kalman Filter

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: control system, adaptation, dynamic errors, Kalman filter, pass band.

Design of the control system with Kalman filter adapting to operating and revolting affecting in real interfering conditions is considered. The algorithm of adaptation implements functions of detection and decision making. The pass band of Kalman filter and parameters of the of control law are changed according to the magnitude of the dynamic control errors.

Bibliogr.: 14 refs.

 


Adaptive Audio-Visual Clustering for Multiple Object Localization

V. Khalidov, F. Forbes, M. Hansard, E. Arnaud, R. Horaud

Inria, Grenoble, France

vkhalidov@ih6208.spb.edu

Keywords: multimodal systems, mixture models, expectation maximization.

This paper addresses the issue of identifying and localizing those objects in a scene that are both seen and heard. In particular, the task of localizing human speakers is emphasized. We explain the benefits of a human-like configuration of sensors (binaural and binocular) for gathering both auditory and visual observations. It is shown that the identification and localization problem can be recast as the task of adaptive clustering the audio-visual observations into coherent groups. We propose a probabilistic generative model that captures the relations between audio and visual observations. This model maps the data to a representation of the common 3D scene-space via a pair of mixture models. Inference is performed by a Generalized Expectation Maximization (GEM) algorithm, which provides cooperative estimates of both the auditory activity and the 3D position of each object. Different versions of GEM are described and compared, their performance on the tasks of multiple and single speaker detection and localization is demonstrated.

Bibliogr.: 27 refs.

 

Cluster Stability Algorithms Based on Index or Stability Functions

D. S. Shalymov

St. Petersburg State University

shalydim@mail.ru

Key words: clustering, cluster validation.

Clustering is the subject of active research in several fields such as statistics, pattern recognition, machine learning etc. Review of several algorithms for assessing cluster stability is performed. The first group of described algorithms uses indexes, based on multivariate statistics, which compare dispersions within and between the clusters. The second group uses stability functions that measure the consistency of labels assignments to sample elements. Notion of clustering and cluster stability is introduced. Basic principles of clustering algorithms are discovered.

Bibliogr.: 11 refs.

 

 

Information Systems

 

Design of a Quality Monitoring Information System for the Education Process at the University Level

O. N. Granichin, O. A. Granichina,

St. Petersburg State University,

Herzen Russian State Pedagogical University

Oleg_granichin@mail.ru Olga_granichina@mail.ru

Key words: quality monitoring, educational process, information system, randomized balanced scorecard method.

The original approach to the designing of the information monitoring system of the university educational processs quality is described. The randomized balanced scorecard method is used for the convolution of versatile estimates.

Bibliogr.: 9 refs.