Стохастические методы оптимизации в информатике

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,'¹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.

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.

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.

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