*Randomized
Algorithms*

Stochastic Optimization and System Programming

*0. N. Granichin*

*Saint- Petersburg*

*Key words: *randomized algorithms,

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__.

*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*

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*

*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*

*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*

*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, *

*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*

__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*

*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*

*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*

*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

Bibliogr.: 7 refs.

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

*Le Trung Hieu*

*Saint-Petersburg** State
University*

*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*

*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,

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,

agent system control........................................................................................... 271

*Adaptive
and Robust Systems*

Tsyganova J.V.,
Tsyganov A.V. (

linear system parameters using simulated annealing........................................... 272

*Discrete
Systems*

Zaiceva
D.V., Sokolov A.V. (

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

IR-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