Accession Number : ADA327574

Title :   Foundations of Software Development.

Descriptive Note : Final rept. 1 Oct 92-30 Sep 95,

Corporate Author : KESTREL INST PALO ALTO CA

Personal Author(s) : Smith, Douglas R.

PDF Url : ADA327574

Report Date : NOV 1995

Pagination or Media Count : 19

Abstract : Algorithms and data structures are among the primary constituents of computer software and thus are among basic objects of study in Computer Science. This project is concerned with the structure and automated design of algorithms and data structures. Our scientific hypothesis is that there exist general algorithm, data structure, and design concepts that underlie and explain most of the detailed structure of conventional software systems. By abstracting and formalizing these concepts and showing how to mechanize their application, we can prepare the way for the coming generation of automated software design environments. Our approach involves identifying classes of algorithms that solve a broad range of useful problems. In particular we have emphasized formalizing abstract algorithms that make minimal assumptions about the structure of a problem. Once a class of algorithms has been identified we represent its essence as a theory, called an algorithm theory. Under ONR support we have developed algorithm theories and design tactics for divide and conquer, simple problem reduction, global search (binary search, backtrack, branch-and-bound), problem reduction generators (dynamic programming, generalized branch-and-bound, game tree search), local search, constraint propagation and others. These have all been at least partially implemented and tested in the KIDS system. KIDS has been used to derive over 70 algorithms. More recent work has focused on theories and operations on theories as the formal underpinings of algorithm design as well as data structure design and refinement and general software development.

Descriptors :   *ALGORITHMS, *SOFTWARE ENGINEERING, *SYSTEMS APPROACH, COMPUTER PROGRAMS, DATA BASES, GLOBAL, AUTOMATION, ENVIRONMENTS, COMPUTERS, THEORY, REDUCTION, SEARCHING, HYPOTHESES, DYNAMIC PROGRAMMING, GAME THEORY.

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE