Pattern Theory: An Engineering Paradigm for Algorithm Design
Abstract
This report proposes Pattern Theory as a basis for an engineering theory of algorithms design. Pattern Theory (PT) begins with a general statement of the problem and then makes deliberate specializations. The problem of finding a pattern in a function is the essence of algorithm design. The key to PT is its measure of pattern-ness: Decomposed Function Cardinality (SFC). Low DFC indicates pattern-ness. The principal result is a demonstration of the generality with which DFC measures pattern-ness. This generality is supported theoretically by relating DFC to time complexity, program length and circuit complexity. A test is developed, based on DFC, for whether or not a function will decompose. This test is used in Ada Function Decomposition (AFD) programs. AFD produces a decomposition (i.e. an algorithm in combinational form) and DFC. The generality of DFC is also supported experimentally. The Pattern Theory approach to machine learning and data compression demonstrated greater generality than other approaches. The DFC's of over 800 nonrandom functions (numeric, symbolic, string based, graph based, images and files) were measured. Roughly 98% of the nonrandom functions had low DFC versus less than 1% for random functions. AFD found the classical algorithms for several functions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 26, 1991
- Accession Number
- ADA243214
Entities
People
- David A. Gadd
- Michael J. Noviskey
- Timothy D. Ross
- Timothy N. Taylor
Organizations
- Wright Laboratory