CONTENTS

Randomized Algorithms

Granichin O.N. (SPbSU) Stochastic optimization and system programming

Granichin O.N., Gurevich L.S., Stepanov E.V. (SPbSU) Mathematical model and algorithm for determining the bottom of the continental slope on the basis of bathymetric data

Isaev O.P. (SPbSU) The FPGA-based hardware implementation of the randomized image compression approach

Melnikov B.F., Pivneeva S.V., Rogova O.A.(TSU, Togliatti) The representativeness of randomly generated non-deterministic finite automata in terms of the associated basic automata

Labankova E.G. (IPU, Moscow) Analysis of the Hit-and-Run method of randomized generation of points in convex domains

Multi-Agent Systems

Amelin K.S. (SPbSU) Unmanned aerial vehicle for autonomous group

Amelina N.O. (SPbSU) The consensus problem for autonomous group of UAVs

Shcherbakov P.S. (IPU, Moscow) Several simple algorithms of multi-agent system control

Adaptive and Robust Systems

Tsyganova J.V., Tsyganov A.V. (Ulyanovsk) Identification of the stochastic linear system parameters using simulated annealing

Discrete Systems

Zaiceva D.V., Sokolov A.V. (Petrozavodsk) Analysis of some representation techniques in modelling of queues with two priorities

Krivulin N.K. (SPbSU) Evaluation of the Lyapunov exponent for a model of stochastic system with synchronization

Trubnikov V.N., Tchirkov M.K. (SPbSU) On equivalent conversion of R-fuzzy automata to stochastic ones

Tchirkov M.K., Shevchenko A.S. (SPbSU) Analysis of languages modelled by finite-nonstationary nondeterministic automata with stochastic input

Information Systems

Komarov C.N. (SPbSU) Integration of large scientific-educational institution information systems on the basis of the personal data

Le T.H. (SPbSU) A model for extracting lexical tokens in Vietnamese language processing system

Le T.H. (SPbSU) A model of morphological analysis of Vietnamese texts

 

Randomized Algorithms

Stochastic Optimization and System Programming

0. N. Granichin

Saint-Petersburg State University

01eg_granichin@mail.ru

Key words: randomized algorithms, Monte Carlo method, optimization and estimation, pattern recognition, cluster stability, compressive sensing, l-1-optimization, randomized measurements.

In theory and practice of system programming, many difficulties arise when studying "complex" systems. In many practical applications, traditionally efficient deterministic system and control methods fail to yield a result when the system is complex. In particular, this led to the notion of NP-hard problems.

Quite recently, the so-called randomized approach to management of complex systems has got wide applications. Within this approach, one might be able to solve a problem "efficiently with high probability,'1 which is often considered sufficient enough. A randomized algorithm is an algorithm where one or more steps are based on a random rule, that is, among many deterministic rules, one rule is selected according to a random scheme. Randomization has turned out to be a powerful tool for solving a number of problems deemed unsolvable with deterministic methods.

In this paper, use of randomized algorithms is discussed in the light of new results obtained recently by students of System Programming chair of Department of Mathematics and Mechanics of Saint-Petersburg State University.

Bibliogr.: 43 refs.

 

Mathematical Model and Algorithm for Determining the Bottom of the Continental Slope on the Basis of Bathymetric Data

0. N. Granichin.

L. S. Gurevich,

E. V. Stepanov,

Saint-Petersburg State University

01eg_granichin@mail.ru, gurevich.lev@gmail.com.

stepanov.yegor@gmail.com

Key words: continental slope, Monte Carlo method, randomized algorithm.

This paper presents the algorithm for determining the confidence zone within which the bottom of the continental shelf is located with high probability. It works in accordance with requirements of Convention and Commission on the limits of the continental shelf (New-York, 1999). The main features of the problem are incompleteness and inaccuracy of available information. Randomization techniques are used to avoid these difficulties.

Bibliogr.: 6 refs.

 


The FPGA-based Hardware Implementation of the Randomized Image Compression Approach

0. P. Isaev

Saint-Petersburg State University

01eg.p.isaev@gmail.com

The standard approaches to image compression are considered and evaluation of their numerical complexity is presented. A new approach is proposed, which is based on the principles of Compressive Sensing (CS) to reduce the image data dimension. The CS encoder model using the pseudorandom measurement algorithm is implemented. The convex algorithm with the minimum reconstruction error criterion to reconstruct the original signal from its sparse representation is devised. The FPGA-based hardware CS encoder is developed. The utilized logic for the 2-D-DCT and CS coders are compared. The experimental data is presented and the general advantages and drawbacks of the hardware design implementation for CS encoder is discussed. Key words: compressive sensing, compressive sampling, randomized measurements, ^i-optimization, FPGA, DCT.

Bibliogr.: 9 refs.

 


The Representativeness of Randomly Generated Non-deterministic Finite Automata in Terms of the Associated Basic Automata

B. F. Melnikov,

S. V. Pivneeva.

0. A. Rogova.

Togliatti State University

B.Melnikov@tltsu.ru, tlt.swetlana@rambler.ru, rogovaolgatlt@yandex.ru

Key words: non-deterministic finite automaton, basic automaton, algorithms for random generation, representativeness.

In this paper we consider several variants of random generation of non-deterministic finite automata. These versions are the improvements of the known van Zijl's algorithm based on random bit streams. Also, an approach to the verification of representativeness of input data is proposed, which is based on the algorithms for automata generating. One of the given criteria is specially selected characteristics of the equivalent basic automaton.

Results of computational experiments show that the random generation algorithm proposed in this article gives non-deterministic finite automata, which is more suitable for solving the selected subject domain.

Bibliogr.: 7 refs.

 


Analysis of the Hit-and-Run Method for Randomized Generation of Points in Convex Domains

E. G. Labankova

Institute of Control Sciences RAS

labankovae@mail.ru

Key words: randomized algorithms, Monte Carlo method, Hit-and-Run method, test of statistic hypotheses.

The paper is dedicated to the analysis of the behavior of the Hit-and-Run method which allows to to generate asymptotically uniformly distributed points in a given domain. This method finds more and more applications in control problems, hence, further and deeper analysis of its advantages and drawbacks is highly desired. The most important requirement to the Hit-and-Run is generation of uniformly distributed points. In the current work, several techniques are proposed to check the method on the uniformity. The first one is based on finding the minimum and maximum value of a linear function. We introduce a special estimate for the level of uniformity. In the second technique, the distribution function is exploited. For the same purpose, we also use the Kolmogorov-Smirnov test. Finally, the correlation of sequentially generated points is checked.

Bibliogr.: 16 refs.

 

 


Multi-Agent Systems

Unmanned Aerial Vehicle for Autonomous Group

K. S Amelin

Saint-Petersburg State University

konstantinamelin@mail.ru

Key words: unmanned aerial vehicles, navigation system, autopilot, actuators, autonomous group of unmanned aerial vehicles.

We consider the architecture of an unmanned aerial vehicle, whose technical equipment will meet the requirements for its successful functioning in an autonomous UAV group. The prototype of this newly created UAV is described.

Bibliogr.: 10 refs.

 


The consensus Problem for Autonomous Group of UAVs

N. 0. Amelina

St. Petersburg State University

Natalia_melina@mail.ru

Key words: consensus problem, virtual structure, multi-agent systems, control strategy, UAV.

Formation control strategies based on Virtual Structure are considered for the consensus problem for a group of autonomous UAVs.

Bibliogr.: 9 refs.

 


Several Simple Algorithms of Multi-agent System Control

P. S. Shcherbakov

Institute of Control Science, RAS, Moscow

sherba@ipu.ru

Key words: multi-agent systems, power iterations, linear algorithms.

The subject of this note is the algorithm of evolution of a point set on the plane devised in [1], which drives the whole system to a certain regular configuration. Generalizations of the algorithm are analyzed, certain new properties are studied, the connection to formation control methods is discussed, and new simpler algorithms of this sort are proposed.

Bibliogr.: 6 refs.

 

 


Adaptive and Robust Systems

Identification of the Stochastic Linear System Parameters Using Simulated Annealing

J. V. Tsyganova

Ulyanovsk State University

A. V. Tsyganov

Ulyanovsk State Pedagogical University

TsyganovaJV@mail.ru, andrew.tsyganov@gmail.com

Key words: stochastic linear systems, adaptive filtering, parameters identification, Kalman filter, auxiliary performance functional, simulated annealing.

In the present paper we solve the problem of stochastic linear system parameters identification using auxiliary performance functional (APF). To find a minimum of the AFP we use a metaheuristic simulated annealing method which does not require calculations of the AFP gradient. The results of the numerical experiments are provided.

Bibliogr.: 15 refs.

 

 


Discrete Systems

Analysis of Some Representation Techniques for Queues With Two Priorities

D. V. Zaiceva,

Petrozavodsk State University,

A. V. Sokolov,

IAMR KarSC RAS, Petrozavodsk

zaiceva@cs.karelia.ru, avs@krc.karelia.ru

Key words: priority queue, FIFO-queues, random walk, Markov chains, dynamical data structures.

This paper considers representation of queues with two priorities in single-level memory as two consecutive and linked FIFO-queues. Possible operations are "insert element," "delete an element with maximum priority," and "find element." Proposed are the algorithms of state enumeration, construction of appropriate regular Markov chains, and finding the optimal memory partition that minimizes the average percentage of lost items.

Bibliorg.: 9 refs.

 


Evaluation of the Lyapunov Exponent for a Model of Stochastic System With Synchronization

N. K. Krivulin

Saint-Petersburg State University

nkk@math.spbu.ru

Key words: stochastic dynamical system, Lyapunov exponent, event synchronization, convergence in distribution.

A model of a stochastic dynamical system with synchronization is considered. The dynamics of the system is represented through a linear vector equation with a second-order matrix in the idempotent semiring with maximum and addition as its operations. It is assumed that the off-diagonal entries of the system matrix are equal to zero, one diagonal entry is an exponentially distributed random variable, and the other is a nonnegative constant. The problem of evaluation of the Lyapunov exponent for the system includes change of variables with the result that instead of the random entries of the system state vector, new random variables are introduced which prove to be more convenient in analysis. For the variables, the sequences of their one-dimensional distribution functions are then introduced and their related convergence analysis is performed. The Lyapunov exponent is evaluated as the mean value of the limiting distribution.

Bibliogr.: 7 refs.

 


On Equivalent Conversion of M-fuzzy Automata to Stochastic Ones

V. N. Trubnikov, M. K. Tchirkov

Saint-Petersburg State University vakh08@mail.ru

Key words: stochastic finite automata, fuzzy finite automata, generalized stochastic languages, fuzzy languages, equivalent conversion of automata.

The paper examines possible ways of equivalent transformation of a fuzzy finite automaton defined over the field of real numbers into a stochastic finite automation with the same generalized language. Some sufficient conditions for such conversion are proved and a suitable algorithm is developed. An example is given.

Bibliogr.: 5 refs.

 


Analysis of Languages Modeled by Finite-nonstationary Nondeterministic Automata With Stochastic Input

M. K. Tchirkov,

A. S. Shevchenko

St. Petersburg State University

01eg_granichin@mail.ru

Key words: stochastic automata, stochastic languages, fmite-nonstatio-nary nondeterministic automata, modeling of stochastic languages by automata models with stochastic input.

The paper presents analysis of equivalence between stationary stochastic automata and generalized fmite-nonstationary nondeterministic automata with stochastic input. It is proved that they model the languages belonging to the same class. It is shown that for any generalized fmite-nonstationary nondeterministic automaton with stochastic input, equivalent abstract stochastic automaton presenting the same generalized stochastic language can be synthesized.

Bibliogr.: 10 refs.

 

 


Information Systems

Integration of Large Scientific-Educational Institution Information Systems on the Basis of the Personal Data

C. N. Komarov,

Saint-Petersburg State University, Stasn_Komarov@mail.ru

Key words: integration of information systems, interoperability.

The paper considers one of possible methods of integration of large scientific-educational institution information systems. It is based on association and actualization of the personal data of all physical persons involved in the basic business processes. The core of the system is a special PERSONNEL metacatalogue. An example of such system which was developed in St.Petersburg State University is presented.

Bibliogr.: 7 refs.

 


A Model for Extracting Lexical Tokens in the Vietnamese Language Processing System

Le Trung Hieu

Saint-Petersburg State University

vkhhieukien@yahoo.com

Key words: lexical analyis, recognize Vietnames lexical tokens, method Pattern-based.

In this paper, we propose a new model for extracting lexical tokens in the Vietnamese language processing system. The model uses a method based on comparison of patterns from a huge text body. It perform several basic functions such as as (i) separating various non-standard elements of the text and assigning them with corresponding lexical tokens (for example, number, punctuation marks, abbreviations, proper names, etc); (ii) determining the boundaries of sentences and paragraphs The key element of the model is the set of extracting rules. Our experimental data was generated from about 250 034 online news articles, which consist of about 15 000 000 sentences.

Bibliogr.: 14 refs.

 


A Model of Morphological Analysis of Vietnamese Texts

Le Trung Hieu

Saint-Petersburg State University

vkhhieukien@yahoo.com

Key words:morphilogical marking, morphological analysis, processing the Vietnamese language, Markov model, Vitterbi algorithm, hybrid method.

A new approach to the morphological analysis of Vietnamese text is proposed. Based on use of randomized models, a set of grammatical rules, and a process of "manual" marking of text by experts, it solves several problems. First, lexical tokens are recognized for non-standard elements of the text and segmentation of text based on the assigned descriptors. Second, an efficient search of every word can be performed via the associated morphological vocabulary. Third, this approach allows for an automatic morphological analysis of Vietnamese texts based on a Markov model and grammatical rules.

The main results, a formalized set of grammatical rules and annotated body of Vietnamese texts, can be used in the development of advanced processors of the Vietnamese language.

Bibliogr.: 13 refs.

 

 

Contents

Randomized Algorithms

Granichin O.N. (SPbSU) Stochastic optimization and system program
ming ............................................................................................................... 264

Granichin O.N., Gurevich L.S., Stepanov E.V. (SPbSU) Mathematical
model and algorithm for determining the bottom of the continental slope
on the basis of bathymetric data......................................................................... 265

Isaev O.P. (SPbSU) The FPGA-based hardware implementation of the
randomized image compression approach.......................................................... 266

Melnikov B.F., Pivneeva S.V., Rogova O.A.(TSU, Togliatti) The represen
tativeness of randomly generated non-deterministic finite automata in
terms of the associated basic automata ........................................................... 267

Labankova E.G. (IPU, Moscow) Analysis of the Hit-and-R,un method
for randomized generation of points in convex domains ................................ 268

Multi-Agent Systems

Amelin K.S. (SPbSU) Unmanned aerial vehicle for autonomous group 269

Amelina N.O. (SPbSU) The consensus problem for autonomous group
of UAVs ......................................................................................................... 270

Shcherbakov P.S. (IPU, Moscow) Several simple algorithms of multi-
agent system control........................................................................................... 271

Adaptive and Robust Systems

Tsyganova J.V., Tsyganov A.V. (Ulyanovsk) Identification of the stochastic
linear system parameters using simulated annealing........................................... 272

Discrete Systems

Zaiceva D.V., Sokolov A.V. (Petrozavodsk) Analysis of some represen
tation techniques for queues with two priorities .............................................. 273

Krivulin N.K. (SPbSU) Evaluation of the Lyapunov exponent for a
model of stochastic system with synchronization ........................................... 274

Trubnikov V.N., Tchirkov M.K. (SPbSU) On equivalent conversion of
I
R-fuzzy automata to stochastic ones................................................................. 275

Tchirkov M.K., Shevchenko A.S. (SPbSU) Analysis of languages model
led by finite-nonstationary nondeterministic automata with stochastic
input ............................................................................................................... 276