Accession Number : ADA114970

Title :   The Representation of Discrete Functions by Decision Trees.

Descriptive Note : Annual rept. 1 Feb 81-31 Jan 82,


Personal Author(s) : Gonzalez,R C ; Thomason,M G ; Moret,B M E

PDF Url : ADA114970

Report Date : 28 Feb 1982

Pagination or Media Count : 133

Abstract : As applications of digital systems continue to expand, the need arises for better methods of analysis of functions of discrete variables. Particularly important is the ability to gauge accurately the difficulty of a problem; this leads to measuring a function's complexity. This in turn requires an implementation-independent model of function evaluation, one that also shows the contribution of individual variables to the function's complexity. One such model, called a decision tree, is introduced; it is essentially a sequential evaluation procedure where, at each step, a variable's value is determined and the next action chosen accordingly. Decision trees have been used in switching circuits, data bases, pattern recognition, machine diagnosis, and remote data processing. The activity of a variable, a new concept that measures the contribution of a variable to the complexity of a function, is defined and its relation to decision trees is described. Based upon these results (which can be generalized to recursive functions and hierarchies of relations), a complexity measure is proposed. The use of that measure and of the concept of activity in testing large systems (where a number of variables may be inaccessible) is then examined, with particular emphasis on continuous checking of systems in operation. (Author)

Descriptors :   *Discrete distribution, *Functions(Mathematics), *Decision theory, Variables, Mathematical models, Digital systems, Sequences(Mathematics), Test and evaluation, Optimization

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE