
Accession Number : ADA114970
Title : The Representation of Discrete Functions by Decision Trees.
Descriptive Note : Annual rept. 1 Feb 8131 Jan 82,
Corporate Author : TENNESSEE UNIV KNOXVILLE DEPT OF ELECTRICAL ENGINEERING
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 implementationindependent 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