main| new issue| archive| editorial board| for the authors| publishing house|
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house



No. 7. Vol. 21. 2015

To the contents

E. Yu. Orekhov, Associated Professor, e-mail:, Ufa State Aviation Technical University

A Method of Generating Instances to Test the Heuristic Algorithms for Integer Problems

We suggest a method of equiprobable generation of instances for an integer-valued problem. The method is based on the uniform generator for the continuous analog of the problem in combination with the acceptance-rejection method. The efficiency criterion of the method is defined. The conditions of the method being worth while are stated. We also give an example of applying the method to equiprobable generation of instances for an integer cutting-packing problem.
Keywords: random equiprobable generation, continuous analog, acceptance-rejection method, efficiency criterion, integer cutting-packing problem

P. 483488

L. F. Komosko, Research Intern,, M. V. Batsyn, Leading Research Fellow, e-mail:, Laboratory of Algorithms and Technologies for Networks Analysis, National Research University Higher School of Economics, Nizhny Novgorod

Efficient Graph Coloring by Means of Bitwise Operations

Graph coloring problem is one of the classical combinatorial optimization problems. This problem consists in finding the minimal number of colors in which it is possible to color vertices of a graph so that any two adjacent vertices are colored in different colors.
The graph coloring problem has a wide variety of applications including timetabling problems, processor register allocation problems, frequency assignment problems, data clustering problems, traffic signal phasing problems, maximum clique problem, maximum independent set problem, minimum vertex cover problem and others. In this paper a new efficient heuristic algorithm for the graph coloring problem is presented. The suggested algorithm builds the same coloring of a graph as does the widely used greedy sequential algorithm in which at every step the current vertex is colored into minimal feasible color. Computational experiments show that the presented algorithm performs graph coloring much faster in comparison with the standard greedy algorithm. The speedup reaches 5,6 times for DIMACS graphs.
Keywords: graph coloring, heuristic, bitwise operations, greedy algorithm, sequential coloring

P. 488494

V. A. Bogatyrev, Professor, e-mail:, A. V. Bogatyrev, Post Graduate, Saint Petersburg National Research University of Information, Technologies, Mechanics and Optics

Optimization of Redundant Routing Requests in a Clustered Real-Time Systems

The investigated cluster system is designed to work in real time when exposed to faults, failures and errors in the requirement of the accuracy and timeliness of the results of service requests with the condition that the delay in the queue is less than the specified maximum permissible value.
The aim of the research was to increase the functional reliability of the cluster real-time in the redundant service requests made by a group of nodes in terms of failures and errors of calculation.
To achieve the objectives of the proposed organization of the redundant distribution of queries in the cluster and the real-time model to assess the probability timeliness, and accuracy of redundant service requests. Proposed and solved the problem of optimal reservation requests in a cluster, which consists in finding the ratio of reservation requests, which guarantees the maximum probability of obtaining accurate and timely delivery of service in at least one of the nodes, receiving a request to redundant execution.
The high efficiency redundant queries in real time, while reducing the optimal ratio of redundancy in case of increase of the intensity of requests, due to the influence of increasing the ratio of the reserve to increase the load on all the nodes, leading to the existence of the border intensity, above which the reservation is not appropriate. The efficiency in the allocation of queries adaptively set the multiplicity of the reservation, pre-computed during the optimization process, depending on changes in the intensity of the input stream.
Keywords: reliability, timeliness, real time, cluster, query, backup, optimization

P. 495502

Yu. I. Petrov, PhD, Educational, Programs Manager, e-mail:, Kaspersky Lab, Yu. A. Karnaukhov, Head of Production Department, e-mail:, IN-Media AG

"FK-Monitoring" Software as a Tool for a Business Process Monitoring

The last decades are characterized by the sharp growth of informatization of economic, administrative and manufacturing processes both in state and commercial structures. Mainly it is explained by aspiration of the organizations to increase efficiency of their activity and, respectively, to strengthen their competitive positions; first of all nowadays it is possible by using of various information systems (IS). Among other types information analytical systems (IAS) are of great importance and allow providing adoption of highly effective administrative decisions and support of elements of strategic planning. At the same time systems of this type are usually developed on demand (custom-made) since the requirements to in and out information, to processing of internal documentation and to reports are strongly depend on company specifics.
Article considers issues of design and implementation of software (analytical information system) for production monitoring at IN-Media AG Company (Switzerland). The software suite includes three components: FK-Server (both console and windowed versions, fetches and parses data from production lines), FK-Client (visualize and analyze data from FK Server, including wide-range statistics and planning ability) and FK Web Client (shows actual production information on non-desktop computer devices). FK Client is a core multi-user component and has bilingual user interface language (can be switched between Russian and German).
The architecture of the software suite is suggested, illustrations of its functioning are presented.
Keywords: information system, analytical information system, software, business process, monitoring, publishing holding, OLAP, Delphi, PostgreSQL

P. 503510

N. A. Avdeev, Senior Researcher, e-mail:, P. N. Bibilo, Head of Laboratory, e-mail:, United Institute of Informatics Problems of National Academy of Sciences of Belarus

Enhanced Capabilities of Digital Systems Computer Aided Design Using VHDL'2008

In this paper the new and changed features of VHDL-2008 (standard IEEE Std 10762008) are introduced briefly. The emergence of new VHDL features is largely due to the need to write complex testing programs and to make various types of simulations in order to verify the original design specifications of a digital system. The possibility to use PSL (Property Specification Language) is added to standard VHDL'2008. PSL is a fully-oriented to verification of projects using assertions. For functional verification using the random test patterns generation and the functional coverage, the protected type is added, that is based on a concept similar to classes of object-oriented programming. The possibilities appear to use arrays with unconstrained range, fixed and floating-point numbers, hierarchical links to signals, new features for bit-string literals writing, new set of predefined matching relational operators and logical operators and other features. The standard packages are expanded: real_vector, time_vector, integer_vector, boolean_vector types, maximum and minimum functions for all basic types are added to the STANDARD package; new read and write procedures are added to the TEXIO package. New package ENV is added to the standard library STD. The readers are assumed to be familiar already with VHDL'1993.
Keywords: computer aided design, digital system, VHDL, testing, functional verification

P. 510520

K. A. Shcheglov, Graduate Student, A. Yu. Shcheglov, Professor, e-mail:, St. Petersburg National research university of IT, Mechanics and Optics, Russia

The Reservation Methods Capabilities to Enhance Integral Information and Operational Security Level of Modern Informational Systems

We do research informational system elements reservation problem. We do illustrate the principal difference of setting the task for informational system elements reservation (to enhance functional reliability and informational security level). We identified and justified the fundamental contradictions of using reservation methods in informational security, which place limits on their effective practical usage while solving information security problems like enhancing confidential level, integrity and availability of information, including contradictions, which prevent effective solutions based on known reservation methods (in context of functional reliability and informational system security level enhancing problem). We do suggest the reservation method with dividing information between informational system elements, which allows to solve problem of enhancing integral information and operational security level and also define an assessment of its effectiveness.
Keywords: informational system, reservation, reliability, resiliency, informational security, information accessibility, confidential information, information integrity, information operational security

P. 521527

. A. Peregudov, Adjunct, e-mail:, . . , Associate Professor, e-mail:, Military Education-Science Center of Military Air Forces "Professor N. E. Zhukovsky and Yu. A. Gagarin Military Air Academy", 394064, Voronezh, Russian Federation

Estimation of Security of a Network Packet Radio from Imitation of User's Terminals at Level of the Procedure of Random Multiple Access to the Environment Type S-ALOHA

Modern network packet radio are often subjected to destructive impact, one of the main ways which is to simulate user's terminals at the level of the procedure of random multiple access to the environment type S-ALOHA. Existing models procedure of random multiple access environment does not provide the ability to estimation of security of a network packet radio from imitation of users terminals at level of the procedure of random multiple access to the environment type S-ALOHA. The proposed model for assessment of the security of the network packet radio from imitation of user's terminals at the level of the procedure of random multiple access to the environment type S-ALOHA using analytical dependences, based on the application of probability theory, Markov processes and determining the probability of successful delivery unblocking packages user's terminals and determining the probability of blocking these terminals. Model can be applied in the design of many priority networks packet radio, at system engineering of management by behavior of such networks, including adaptive protection against imitation of user's terminals and algorithms of the procedure of random multiple access to the environment type S-ALOHA, resolving collisions.
Keywords: network packet radio, S-ALOHA, destructive impact, Markov model, security

P. 527534

A. G. Trofimov1, 2, Associate Professor, e-mail:, I. V. Kolodkin1, Student, V. L. Ushakov2, Associate Professor, B. M. Velichkovsky2, 3, Professor
1Russia, National Research Nuclear University "MEPhI"
2Russia, NRC "Kurchatov Institute"
3Russia, The NBIC-faculty, Moscow Institute of Physics and Technology

Agglomerative Method for Spatial Time Series Segmentation Based on Travelling Waves

We propose an agglomerative segmentation method for spatial time series based on the characteristics of traveling waves. To measure the intensity of the traveling waves we consider phase locking value and coherence. The calculation of these values was based on the analysis of the cross-spectra. Experimental researches on real data of electroencephalography (EEG) show that the proposed method provides better segmentation quality than traditional segmentation algorithms for EEG signals.
Keywords: spatial time series, travelling-wave, hierarchical clustering, segmentation, phase-locking value, coherence, brain microstates, electroencephalogram (EEG)

P. 535543

S. L. Belyakov, Professor, e-mail:, M. L. Belyakova, Associate Professor, e-mail:, A. I. Brehacheva, Student, Southern Federal University, Taganrog, Russia

Geographic Information Models for Decision-Making Based on the Experience

This paper deals with the problem of improving the assurance of decision-making based on the experience accumulated in the geographic information system. The assurance is understood as an extent of accordance of the decision made to the reality as it is. The decision must be adapted to the real world situation with minimal damage in case of failure. The problem of the modern approach of the usage of the experience that is atomic performance of situations and solutions is pointed out. Atomicity appears as an inability of fractional modification. Situations and solutions presented in the atomic form are impossible to adapt to specific cases. The conceptual model of the experience metaphor that enlarges the atomic presentation by a set of situations' and solutions' allowable transformation is offered. The transformations are described by the visual cartographic objects. It allows you to set the spatial or temporal boundary of changing situations and solutions. The special aspects of decision-making process that are based on image matching are analyzed. The topological patterns for the classification of the extent of nearness are described; the correlation for the nearness' estimation in case of image crossing is presented. The procedure of graphic presentation of experience of images' nearness' estimation is considered. The effectiveness of graphic presentation from the perspective of continuity of processes and situations of the real world is estimated.
Keywords: decision-making, uncertainty, geographic information systems, precedent analysis, graphic presentation of knowledge, logic of figurative reasoning

P. 544550

V. V. Naumova1, Head of Lab., e-mail:, I. N. Goryachev2, Lead Geologist, e-mail:, S. V. Dyakov1, Junior Researcher, e-mail:, A. B. Belousov1, Graduate Student, e-mail:, K. A. Platonov1, Programmer, e-mail:
1Far East Geological Institute Far East Branch of Russian Academy of Sciences, Vladivostok
2Kompany "MagadanGeology", Magadan

Modern Technologies for Development of the Information Infrastructure Supporting Scientific Geological Investigations in the Russian Far East

In article approaches and software of virtual integration of distributed data to create an information infrastructure for Geology of the Far East of Russia, designed for virtualization to access data from different technological systems using common rules and international standards are discussed. The authors set themselves the task to design an information infrastructure that would support researches and make possible solution of a wide circle of geological problems using secondary sources of information and new services of their processing as the basis. To achieve the task, development of new models and techniques of the already existing array of data processing is considered with the aim of further development of a unified access point to geographically-distributed scientific data on geology of the Russian Far East, such as: satellite images, GPS databases, scientific publications, quantitative data, expertise and so on.
Keywords: distributed information systems, the integration of geterogeneous data access control to information resources

P. 551559

To the contents