April 1972 - Vol. 15 No. 4
Features
On the implementation of security measures in information systems
The security of an information system may be represented by a model matrix whose elements are decision rules and whose row and column indices are users and data items respectively. A set of four functions is used to access this matrix at translation and execution time. Distinguishing between data dependent and data independent decision rules enables one to perform much of the checking of security only once at translation time rather than repeatedly at execution time. The model is used to explain security features of several existing systems, and serves as a framework for a proposal for general security system implementation within today's languages and operating systems.
A system for interprocess communication in a resource sharing computer network
A system of communication between processes in a time-sharing system is described and the communication system is extended so that it may be used between processes distributed throughout a computer network. The hypothetical application of the system to an existing network is discussed.
An experimental laboratory for pattern recognition and signal processing
An interactive computer-controlled scanning and display system has been in operation at the IBM Thomas J. Watson Research Center for three years. The system includes two flying-spot scanners and a TV camera specially interfaced to a process control digital computer, dot-mode and vector displays, analog input and output facilities, and a variety of other experimental equipment. The system design and programming support are described and typical applications in scanner control, optical character recognition, and image processing are presented.
Hidden lines elimination for a rotating object
A method is presented of determining which parts of three-dimensional objects are visible and which are invisible when the objects are rotated about some axis. This paper describes a polygon comparison scheme in which the relationships of two polygons can be classified into tree types, and also discusses how the relationship is changed for each pair of polygons under rotation about some axis. A rotation table is defined for each pair of polygons, which remains fixed as long as rotation is about one axis and provides a means of rapidly determining the visible and hidden line relationship between two polygons. Additional work must be done to extend this approach to simultaneous rotation about several axes.
An implemented graph algorithm for winning Shannon Switching Games
In this tutorial paper a computer program which wins Shannon Switching Games is described. Since these games are played on graphs, the program is a good example of the implementation of graph algorithms.
The two players in a Shannon Switching Game, CONNECT and CUT, have nonsimilar goals. Either CONNECT, CUT, or the player moving first is guaranteed the existence of a winning strategy. The simple strategy explained in this paper is valid in all three cases. In fact, the major routines never need to know whether the computer is CONNECT or CUT.
Computers and society: a proposed course for computer scientists
The purpose of this paper is to describe a course concerned with both the effects of computers on society and the responsibilities of computer scientists to society. The impact of computers is divided into five components: political, economic, cultural, social, and moral; the main part of the paper defines each component and presents examples of the relevant issues. In the remaining portions the possible formats for such a course are discussed, a topic by topic outline is given, and a selected set of references is listed. It is hoped that the proposal will make it easier to initiate courses on this subject.
Complex gamma function with error control
An algorithm to compute the gamma function and the loggamma function of a complex variable is presented. The standard algorithm is modified in several respects to insure the continuity of the function value and to reduce accumulation of round-off errors. In addition to computation of function values, this algorithm includes an object-time estimation of round-off errors. Experimental data with regard to the effectiveness of this error control are presented. A Fortran program for the algorithm appears in the algorithms section of this issue.
Matrix computations with Fortran and paging
The efficiency of conventional Fortran programs for matrix computations can often be improved by reversing the order of nested loops. Such modifications produce modest savings in many common situations and very significant savings for large problems run under an operating system which uses paging.
Algorithm 421: complex gamma function with error control [S14]
This Fortran program computes either the gamma function or the loggamma function of a complex variable in double precision. In addition, it provides an error estimate of the computed answer. The calling sequences are: CALL CDLGAM (Z, W, E, 0) for the loggamma, and CALL CDLGAM (Z, W, E, 1) for the gamma, where Z is the double precision complex argument, W is the answer of the same type, and E is a single precision real variable. Before the call, the value of E is an estimate of the error in Z, and after the call, it is an estimate of the error in W.
Algorithm 422: minimal spanning tree [H]
This algorithm generates a spanning tree of minimal total edge length for an undirected graph specified by an array of inter-node edge lengths using a technique suggested by Dijkstra [1]. Execution time is proportional to the square of the number of nodes of the graph; a minimal spanning tree for a graph of 50 nodes is generated in 0.1 seconds on an IBM System 360/67. Previous algorithms [2, 3, 4, 5] require an amount of computation which depends on the graph topology and edge lengths and are best suited to graphs with few edges.
A note on Cheney’s nonrecursive list-compacting algorithm
Cheney's list-compacting algorithm [1] goes into an infinite loop when it traces a circular list consisting exclusively of non-items. While it may be reasonable to say that such lists should not exist, it would be very difficult to legislate out of existence programs which illegally create such lists because of bugs, and it would not do for the garbage collector to break down in this instance.
A comment on the double-chained tree
In 1963, Sussenguth [8] suggested that a file should be organized as a double-chained tree for searching and updating. Patt [5] then obtained the optimum double-chained tree under the assumption that no key may prefix another and that all terminal nodes (items of information) have equal probabilities of being searched. Stanfel [6, 7] explored the relation between the double-chained tree and variable length code [3] and solved a special integer programming problem which corresponds to the case of equal probabilities of terminal nodes and a finite set of available symbols for keys with different costs.
