June 1971 - Vol. 14 No. 6
Features
Generation of Rosary permutations expressed in Hamiltonian circuits
Systematic generation of a specific class of permutations fundamental to scheduling problems is described.
In a nonoriented complete graph with n vertices, Hamiltonian circuits equivalent to 1/2(n - 1)! specific permutations of n elements, termed rosary permutations, can be defined. Each of them corresponds to two circular permutations which mirror-image each other, and is generated successively by a number system covering 3·4· ··· ·(n - 1) sets of edges. Every set of edges {ek}, 1 ≤ ek ≤ k, 3 ≤ k ≤ n - 1 is determined recursively by constructing a Hamiltonian circuit with k vertices from a Hamiltonian circuit with k - 1 vertices, starting with the Hamiltonian circuit of 3 vertices. The basic operation consists of transposition of a pair of adjacent vertices where the position of the pair in the permutation is determined by {ek}. Two algorithms treating the same example for five vertices are presented.
It is very easy to derive all possible n! permutations from the 1/2(n - 1)! rosary permutations by cycling the permutations and by taking them in the reverse order—procedures which can be performed fairly efficiently by computer.
An approach to the optimum design of computer graphics systems
Display system designers are faced with the difficult task of selecting major subsystems in an intelligent way. Each subsystem is chosen from large numbers of alternatives; the selection is based on considerations such as system response time, system cost, and the distribution of data storage and processing between the graphics processor and its supporting data processing system. The work reported here develops an objective, quantitative design procedure and helps give a better understanding of how to configure display systems. This is accomplished by means of a mathematical model of a computer driven graphics system.
The parameters of the model are functions of the capabilities of the graphics hardware and of the computational requirements of the graphics application. The model can be analyzed using numerical queueing analysis or simulation to obtain an average response time prediction. By combining the model with an optimization, the best graphics system configuration, subject to a cost constraint, is found for several applications. The optimum configurations are in turn used to find general display system design guidelines.
Computer science: a conceptual framework for curriculum planning
Two views of computer science are considered: a global view which attempts to capture broad characteristics of the field and its relationships to other fields, and a local view which focuses on the inner structure of the field. This structure is presented in terms of the kinds of knowledge, problems, and activities that exist within the discipline, as well as the relations between them. An approach to curriculum planning in computer science is presented which is guided by the structure of the field, by the fact that change is an important feature of the situation, and by the expectation that computer science will continue to increase its working contacts with other disciplines.
Numerical properties of the Ritz-Trefftz algorithm for optimal control
In this paper the Ritz-Trefftz algorithm is applied to the computer solution of the state regulator problem. The algorithm represents a modification of the Ritz direct method and is designed to improve the speed of solution and the storage requirements to the point where real-time implementation becomes feasible. The modification is shown to be more stable computationally than the tradiational Ritz approach. The first concern of the paper is to describe the algorithm and establish its properties as a valid and useful numerical technique. In particular such useful properties as definiteness and reasonableness of condition are established for the method. The second part of the paper is devoted to a comparison of the new techniques with the standard procedure of numerically integrating a matrix Riccati equation to determine a feedback matrix. The new technique is shown to be significantly faster for comparable accuracy.
A note on compiling fixed point binary multiplications
An algorithm is developed for compiling, as a sequence of shifts, additions, and subtractions, many fixed point binary multiplications involving a constant. The most significant characteristics of the algorithm are the simplicity of the test which determines if the algorithm should be applied and the degree to which it “suggests” efficient object code.
On the meaning of names in programming systems
It is assumed that there is a similarity of function between the data names of a programming language and the file names of an operating system. The two functions are discussed in terms of the same basic concepts in order to identify the extent to which they overlap. It is suggested that there is some similarity between the idea of a file directory and a storable object of type context. Manipulations with contexts are then discussed at length.
It is noted that there is a simple extension of Church's &lgr; notation that deals nicely with these ideas of context manipulation. Whereas a function can be regarded as the abstraction based upon the first two terms of the expression &lgr;(namelist)(expression)(valuelist), it is found that a context can be viewed as an abstraction based upon the first two terms in the equivalent expression &mgr;(namelist)(valuelist)(expression).
This note is an extension of the ideas expressed by Morgan [1]. He suggests a new form of interrupt which he proposes to use to control the execution of a program, in his case a file management system called DPL [2]. Simply stated, he has attached to every subroutine a Boolean expression which, if true, would cause that subroutine to be executed. Since his implementation is via software, a relatively time-consuming check must be made whenever some condition in the program changes (e.g. some variable has a value changed). A rather simple hardware addition to existing machines can easily implement this interrupt. The following is such a proposal.
In discussing his binary summation method [1] Linz mentions two defects: “It is more difficult to program than the standard method, and it is difficult to use unless all numbers are available at the start of the summation.” A defect not mentioned is the extra storage space (approximately N words) required for the Sij. The last two of these three defects can be removed by proper combination of partial sums. In the adjacent PL/I program, the only storage needed is for the M-component vector T, where M ≧ [log2 N]. N must be even, and B is a number not expressible as a sum of A(I)'s, e.g. B = -1 if A(I) ≥ 0, or B = 1E + 75 for reasonably sized A(I).
