August 1962 - Vol. 5 No. 8

August 1962 issue cover image

Features

Research and Advances

The description list of concepts

A concept is defined as a class of objects whose members can be distinguished by processing its properties. Property is defined to mean a partition of the set of all objects into disjoint classes. The formal definition of a concept is recursive in nature. A concept is described by a list structure. A one-to-one correspondence is established between the recursive definition of a concept and its description list structure. Like the definition, the description list structure of a concept is also built up from elementary list structures by a recursive process. The list structures obtained this way are compared with the description list structure discussed by the author in a previous publication.
Research and Advances

Further remarks on line segment curve-fitting using dynamic programming

In a recent paper, Bellman showed how dynamic programming could be used to determine the solution to a problem previously considered by Stone. The problem comprises the determination, given N, of the N points of subdivision of a given interval (&agr;, &bgr; and the corresponding line segments, that give the best least squares fit to a function g(x) in the interval. Bellman confined himself primarily to the analytical derivation, suggesting briefly, however, how the solution of the equation derived for each particular point of subdivision ui could be reduced to a discrete search. In this paper, the computational procedure is considered more fully, and the similarities to some of Stone's equations are indicated. It is further shown that an equation for u2 involving no minimization may be found. In addition, it is shown how Bellman's method may be applied to the curve-fitting problem when the additional constraints are added that the ends of the line segments must be on the curve.
Research and Advances

A procedure for inverting large symmetric matrices

In the least squares method for simultaneous adjustment of several parameters, the coefficients of the normal equations are the elements of a symmetric positive-definite matrix. In order to solve the normal equations and evaluate the precision measures of the resulting parameters, inversion of this matrix of coefficients is required. Many available procedures for matrix inversion do not take advantage of the symmetry. Thus, when programmed for a high-speed computer, all n2 elements must be stored and manipulated, whereas only n(n + 1)/2 of them are independent. In order to allow a computer of given memory capacity to handle a large matrix, the following procedure for inverting a symmetric matrix has been devised.1
Research and Advances

Analysis of a file addressing method

This paper presents a new file addressing method based on the calculation of an address from the identification of a record. For large recirculating type files, it seems to be more advantageous than customary ones. The probability distribution of the displacement of records from their calculated address, which is one less than the number of probes required to address a record, is computed on the basis of a Markov chain model. For the reader not interested in the mathematics, the introduction and the summary should be sufficient.

Recent Issues

  1. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  2. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  3. August 2024 CACM cover
    August 2024 Vol. 67 No. 8
  4. July 2024 CACM cover
    July 2024 Vol. 67 No. 7