Tools and techniques of programm construction and optimization

Edited by prof. V.N. Kasyanov
Novosibirsk 2005

This volume is the twelfth one in a series of books published in A.P. Ershov Institute of Informatics Systems. This volume is devoted to the tools and techniques of program construction and optimization.

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


Exploratory system for analysis of texts in a natural language

In the paper, the exploratory system developed by the authors for analysis of texts in a natural language is briefly described.

The paper is available in Russian only as PDF document


Comparative analysis of the search techniques using microarray data for regulation modules in the DNA sequences

This paper describes the problem of regulation modules search in the DNA sequences. The statement of the problem is given, as well as the review of three projects aimed at the problem solution: TOUCAN package, TELiS system and Composite Module Analyst. Advantages and shortcomings of different approaches are pointed out.

The paper is available in Russian only as PDF document


The calculation of the oil saturation coefficient based on results of nuclear oil-wells carotage

The paper considers the algorithms for calculation of oil saturation based on data of nuclear oil-wells carotage.

The paper is available in Russian only as PDF document


User Interface of Virtual museum of informatics history in Siberia

The user interface of the Virtual museum of informatics history in Siberia is presented. The museum is intended for acquisition, systematization and use of information about formation and development of informatics in Siberia. The museum is developed as an on-line information-retrieval adaptive hypermedia system. Information management interface and its components (navigation structure, information view, search, insert and update) are described. The user management interface and its components (user registration, authentication, authorization and management) are considered.

The paper is available in Russian only as PDF document


Introductory course of programming based on the Zonnon language

The paper presents an introductory course of programming based on a new language Zonnon being under development at the Institute of Computer Systems in Zurich. The language is designed as a modern alternative to the well-known language Oberon being an evolution of Pascal and Modula-2 languages.

The course is intended for use in that Russian universities and education organizations which now use the Pascal language in their introductory courses of programming and wish to move to a new course covering the concepts of modern languages, such as C#, Java and Ada.

The paper is available in Russian only as PDF document


Processing of data of microarray experiments with the use of the R language

The aim of this work is to describe an approach to identification of genes that changed their expression in several microarray experiments.

By the example of data from Affimetrix oligonucleotide chip, we describe the process of normalization and clasterization in the R GUI environment using Bioconductor packages.

This work can be used as a tutorial on application of R language and BioConductor package for processing the results of microarray experiments.

The paper is available in Russian only as PDF document


Semantic network as a formal method of description and processing of texts about program transformations

Computers are able to process only formalized languages but it is not the case with a natural language. This paper discusses the mechanisms used to extract, unify, and express information about program transformations in network notations. A semantic network or net, which is a graphic notation for representing information in patterns of interconnected nodes and arcs, is proposed as a formalized presentation of a text.

The paper is available in Russian only as PDF document


Path kernels and partitions in graphs with small lengths of cycles

Let τ(G) denote the number of vertices in the longest path of a graph G. For some pair of integers (a,b) with property a+b = τ(G) the graph G is (a,b)-decomposable, if the set of vertices V(G) has such partition on two subsets {A,B} that τ(G[A]) ≤ a and τ(G[B]) ≤ b. The subset K of the set of vertices V(G) is called Pn-kernel, if τ(G[K]) ≤ n-1 and every vertex v ∈ V(G)\K are adjacent with the terminal vertex of the path of length n-1 in the graph G. It is known that the existence of Pn-kernel in the graph G implies that the graph G is (τ(G)-n+1, n-1)-decomposable. Here the theorem on existence of P9-kernel in any graph G has been proved.

The paper is available in Russian only as PDF document


Review of virtual Internet-museums

A review of the so-called virtual Internet-museums is given and an attempt is made to tell the difference between the sites-representations of real museums and virtual museums themselves.

The paper is available in Russian only as PDF document


A method of algorithm parallelization by unimodular transformations

The aim of this paper is to present the theory of unimodular matrices used for loop parallelization. The wave front method here considered includes conversions, such as loop interchange, loop reverse and loop skewing. A nest of two loops with constant boundaries is taken as a program model. A transformation of the loop nest by means of a unimodular matrix that operates on index variables is studied in the paper. The following results are shown: correctness of application of the listed above transformations; assignment of matrices to appropriate transformations; possibility of parallel execution of the outer or inner transformed loop; existence of matrices that allow parallel execution; calculation of boundaries of a loop of a new nest. The described transformations change the relative order of execution of iterations of the loop nest and are used both to find out parallelism and to increase its degree.

The paper is available in Russian only as PDF document


A block of reducing optimizations for Sisal 3.0 compiler

The article describes a block of high-level reducing optimizations for Sisal 3.0 compiler. The reducing optimizing transformations are transformations which do not decrease any qualities of a program. The block performs the following high-level optimizations: Common Subexpression Elimination, Constant Folding, Constant Propagation, IF-transformations, Dead Code Elimination, etc.

The paper is available in Russian only as PDF document


Analysis of a module approach and its implementation in different programming languages

This work considers several basic programming methods, such as modular, structured and object-oriented. In the second part of the paper, we analyze implementation of a module in some programming languages and illustrate it with a functional language Sisal 3.0.

The paper is available in Russian only as PDF document


The interface system for a translator to the internal representation IR1

This paper describes the COM (Component Object Model) interface system which is used to represent translation from the generic textual program representation to internal representation IR1 based on the IF1 graph model. Requirements to the functionality of the interface system are presented, as well as possible ways of its enhancement.

The paper is available in Russian only as PDF document


Overview of debugging techniques for functional languages

The functional paradigm introduces its special features to the debugging process. Traditional debugging techniques are not applicable to some functional languages. In this article, a series of functional programming systems are reviewed and an attempt is made to classify the systems according to the debugging techniques employed.

The paper is available in Russian only as PDF document


Analysis of different types of DNA with autocorrelation function

The aim of this work is to study the DNA structure with autocorrelation function (AKF) analysis: to find some qualitative differences for DNA that serves different biological function.

The result of our research is that AKF of different DNA regions are similar, but differences are statistically significant. Regulatory regions are more correlated than exons (coding regions) which, in turn, are more correlated than randomly generated sequences.

The class of promoters (regulatory regions) has much more variable informational content than other sequences. Nature gets profit from supporting common informational similarity of DNA, but only functionally necessary parts have their own unique pattern.

The paper is available in Russian only as PDF document


Construction of a programme complex "Regulatory Sequences Analyzer" for recognition of cis-elements in the DNA sequence

This article presents documentation for the program complex "Regulatory Sequence Analyzer" developed by the authors for visualization of a search for potential cis-elements in the DNA sequence. The article provides a brief description of "Match" and "CoMatch" algorithms that are based on using weight matrices in a search for singular and double sites, correspondingly. The description of matrix libraries for these algorithms is given.

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.