Modern problems of program construction

Edited by prof. V.N. Kasyanov
Novosibirsk 2002

This volume is the ninth one in a series of books published in A.P. Ershov Institute of Informatics Systems on the problems of program construction and optimization. It describes solutions to actual problems of constructing efficient and reliable programs and software systems based on graph-theory methods, functional programming, network processing and visualizing tools.

The volume is of interest for system programmers, students and postgraduates working in the field of system and theoretical programming.

The articles are available in Russian only as PDF document

Hierarchical approach for drawing directed graphs

This article is a review of the methodology for automatic drawing of arbitrary directed graphs. Layered drawings with edges following one common direction are used to emphasize the hierarchy of vertices in such graphs. The approach described in this article is usually divided into three steps.

  1. Assignment of the vertices to layers so that all edges point to one direction.
  2. For each layer, an ordering of the vertices is computed in order to minimize the number of edge crossings.
  3. Coordinate assignment of vertices in the layer in order to minimize the total edge length and the number of edge bends.

The review contains a detailed description of each step of the algorithm. The author presents different solutions to the problems arising at each stage, gives references to original papers, and also compares these solutions in terms of satisfying aesthetic criteria and time complexity. The review also covers the related topics (edge and vertex labeling, dynamic layouts, open problems) and a number of methods to convert an arbitrary graph to a directed one.

The paper is available in Russian only as PDF document

Methods and techniques of adaptive hypermedia

Adaptive hypermedia is a relatively new research direction at the junction of hypermedia and user modeling. Adaptive hypermedia systems build a user model on the basis of goals, knowledge, preferences, and other characteristics of each particular user, and use this model when interacting with the user in order to adapt to his/her needs. This paper provides a brief survey of existing methods and techniques of adaptive content presentation and adaptive navigation support.

The paper is available in Russian only as PDF document

Translating components of a functional programming system (SFP)

The paper describes a system of functional programming (SFP) and its components: translator, debugging tools, internal representation of Sisal-programs, Sisal-to-C converter. Testing of SFP's translating components is also described.

The paper is available in Russian only as PDF document

Algorithms of fast search for fragments of photoimages

Search for fragments in images is an actual problem arising in many fields of human activity. It is desirable to perform it with maximal speed.

The aim of this work is to construct algorithms and programs that find a particular fragment in an image. The program here described consists of two parts: a computational kernel and a control shell that works as a user interface.

The main advantage of this new approach is the fact that all fragments are in a simultaneous search. This algorithm is one of the best in the world.

The paper is available in Russian only as PDF document

TRIZ_Computing system

This article is devoted to the methods of decision making in the theory for solving the inventive problems (TRIZ) and their application to the problem of conflict resolution. The algorithm of solving the inventive problems (ARIZ) and its analogue for resolution of conflict situations (ARPS) are considered. A graphical interface of TRIZ_Computing intended for conflict analysis is described. The program presents several examples.

The paper is available in Russian only as PDF document

Computer-aided decision making at the railway transport as a guarantee of railway safety

This article presents ARMs TCHB systems (ARMNaradchick, ARMZAVbrigadami). ARM TCHB is implemented within the framework of ASUT (locomotive facilities automated control system) concept developed in the Application Center of Ministry of Railways in collaboration with VNIIZhT, VNIIAS, West-Siberian and Moscow railways and other railway enterprises by instruction of the Department of locomotive facilities.

The main purpose of the system is to completely exclude mistakes of operating personnel during formation and work of locomotive brigades and engine drivers working as one person. The system is also intended for optimization of managing the locomotive brigades. Another task (which is not of less importance) of ARM TCHB (conjugate with ARM TCHD) is computer-aided preparating and sending reports on disposition and state of brigades to OKDB system in a real-time mode.

The paper is available in Russian only as PDF document

A pipeline model of transportation as a model of message passing

We show that the transportation problem with a pipeline model is the closest to the problem with a "wormlike" model of message passing..

The paper is available in Russian only as PDF document

The development of NUMA-architectures: current state

The aim of this paper is to consider the dynamic of development of NUMAarchitectures in the last decade.

The paper is available in Russian only as PDF document

A review of MPEG-like methods of video data encoding

The basic methods of video data encoding used in MPEG-like formats are considered, such as a search for motion vectors, encoding of residual image, and encoding of special data.

The paper is available in Russian only as PDF document

Virtual museum of informatics history in Siberia

The paper presents the project of a virtual museum of informatics history in Siberia. The Siberian informatics and programming school is briefly described, the structure, contents and user interface of the virtual museum are considered, and adaptive hypermedia problems are studied.

The paper is available in Russian only as PDF document

User interface of an integrated functional programming environment SFP

The paper is devoted to a part of a project on creation of IFPE (integrated functional programming environment) for the functional programming language Sisal. It describes the user interface of IFPE and some of its components, such as editor, translator, etc.

The paper is available in Russian only as PDF document

IS TRANSFORM: computer-aided system filling

This paper focuses on the current state of IS TRANSFORM and possible ways of extending its features. It also considers the methods of autoindexing and possible approaches to the decision of the problem of adequate autoindexing of documents and extracting information from them.

The paper is available in Russian only as PDF document

A project of a system for fast prototyping of a parallelizing compiler. Generalpurpose internal system representation

The first part of this paper presents a project of a research-and-training system for fast prototyping of the parallelizing compiler. It contains the tasks set to the system and shows how they relate to the process of compiler development. The architecture of the system is described together with its constituents working at certain stages of compilation and its main components, such as a scalable universal internal form (IF), "scenario" and the "scenario" language. In the second part of the paper, IF of the system, its "language" and "graph" components are considered in detail. Some new concepts are introduced, namely, the abstract syntactical graph and graph shadows for investigation of various internal graphtheoretical forms of programs.

The paper is available in Russian only as PDF document

Path kernel and cycle length in undirected graphs

Let τ(G) denote the number of vertices in the longest path of a graph G. A subset K of the set of vertices V of the graph G is called Pn-kernel of the graph G, if τ(G[K]) ≤ n-1 and every vertex xV (G\K) are adjacent to the terminal vertex of the path of length n in the graph G. Here the theorem on existence of a Pn-kernel of the graph G with the length of the maximal cycle n-2 has been proved.

The paper is available in Russian only as PDF document

Real-time tracking and velocity determination of objects moving on a plane

A logical module is discussed in the paper for a real-time object tracking system. Images obtained by a fixed video camera are used as input data. The output is information about objects viewed by the camera. A usual Pentium-2 computer is used as the hardware part.

The paper is available in Russian only as PDF document

Optimal data distribution in information systems according to the system component reliability

The article is devoted to the problem of optimal data distribution in information systems for the case of a distributed client-server system. The method of optimal distribution of tables is described. The proposed approach considers not only the system's component performance and data channel utilization, but also the system reliability. It is possible to use this method in the computation system design.

The paper is available in Russian only as PDF document

You are reporting a typo in the following text:
Simply click the "Send typo report" button to complete the report. You can also include a comment.