Journal:Informatica
Volume 7, Issue 4 (1996), pp. 455–468
Abstract
The performance of a computer network is commonly measured by the maximum minimum time required to move a certain amount of data between any 2 nodes in the network. Due to the advances in technology, certain links in the network may be upgraded, for instance to optical fibre links, so that better performance can be achieved. In this paper, we study the LINK UPGRADE problem for networks. We first show that the LINK UPGRADE problem is NP-complete. We also show that, a closely related problem, the MINIMUM COST LINK UPGRADE problem is NP-complete even if the underlying topology of the network is a linear array. However, for certain classes of networks, the LINK UPGRADE problem can be solved in polynomial time. For general networks, we provide effective heuristics for the above problems.
Journal:Informatica
Volume 7, Issue 4 (1996), pp. 431–454
Abstract
Adaptive Control Distributed Parameter Systems (ACDPS) with adaptive learning algorithms based on orthogonal neural network methodology are presented in this paper. We discuss a modification of orthogonal least squares learning to find appropriate efficient algorithms for solution of ACDPS problems. A two times problem linked with the real time of plant control dynamic processes and the learning time for adjustment of parameters in adaptive control of unknown distributed systems is discussed.
The simulation results demonstrate that the orthogonal learning algorithms on a neural network concept allow to find perfectly tracked output control distributed parameters in ACDPS and have rather a good perspective in the development of generalised ACDSP theory and practice in the future.
Journal:Informatica
Volume 7, Issue 4 (1996), pp. 419–430
Abstract
Teaching of computer programming by electronic mail has been held in Lithuanian schools since 1992. School students of upper grades (8–12) took part in the experiments. The experiments showed that students cope better with first stages of programming (specifying the problem, etc.) than with the last ones (programming, debugging). The analysis of programming products (made by their peers) by students themselves may be expected to be an important component of learning and teaching.
The outcome of three year work is summarized and discussed. Observations and conclusions are presented. Distance teaching perspectives are discussed.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 389–405
Abstract
This paper presents the framework for well-understood domain analysis as a decisive stage for the successive process of domain-specific software tools building. Specific features of the well-understood domain analysis are formulated. Initial model of the tools to be built and the analysis process are described. Analysis is performed with the reusability concept in mind and as a result essential domain knowledge is extracted. The latter is defined by a term “domain knowledge template”.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 371–388
Abstract
It is desirable in many applications, that a set of cooperating processes do not loose their coordination due to failures. This paper presents a fault-tolerant protocol for a network of processors, which form a logical ring on a physical broadcast medium. The presented protocol makes possible for a set of processes to reestablish their normal operation after transient or permanent process failure or transient communication failures. The protocol is described, model for the system is developed, and in the framework of this model it is proved, that the system reaches a stable and correct configuration in finitely many steps after failure.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 361–370
Abstract
The queueing system theory is well developed. Such an important problem as the efficient of customer service in efficiency a multichannel queueing system with different productivity of service channels is well developed, too. Exact formulas are obtained from which the loss probability can be computed (if the input stream of customers distributed as Poisson and service time of the customer is the exponential service time). However, these formulas are very complex. So, in this paper, two theorems are proved, in which upper and lower estimates of the loss probability are presented. These estimates are simple formulas that don't become more complex with the growing number of service channels in the queueing system.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 349–360
Abstract
In this paper, we present an effective performance driven placement with global routing algorithm for macro cells. Our algorithm uses a hierarchical, divide and conquer, quad-partitioning approach. The quad-partitioning routine uses the Tabu Search technique. Our algorithm uses the concept of proximity of regions to approximate the interconnection delays during the placement process. In addition, our algorithm can handle modules whose positions are fixed or are restricted to a particular subregion on the layout frame. Our experimental results indicate the superiority of our placement method in terms of quality of solution and run time when compared to Lin and Du (1990).
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 337–348
Abstract
In the application of Dantzig–Wolfe decomposition to block-angular linear programming problems with R natural blocks. it is possible to have from 1 to R subproblems structurally while solving all R independent subproblems computationally. Early literature on the topic was inconclusive regarding the relative merits of such formulations. This paper attempts clarification by characterizing the significance of the degree of decomposition as well as presenting extensive empirical results.
Journal:Informatica
Volume 7, Issue 3 (1996), pp. 311–336
Abstract
We consider a possibility of automating the analysis of a computer program realizing the objective function of an extremal problem, and of distributing the calculation of the function value into parallel processes on the basis of results of the analysis. The first problem is to recognize the constituent parts of the function. The next one is to determine their computing times. The third problem is to distribute the calculation of these parts among independent processes. A special language similar to PASCAL has been used to describe the objective function. A new scheduling algorithm, seeking to minimize the maximal finishing time of processing units, was proposed and investigated. Experiments are performed using a computer network.