Top-Down Synthesis of Simple Divide and Conquer Algorithms.

Abstract

A new method is presented for the deductive synthesis of computer programs. The method takes as given a formal specification of a user's problem. The specification is allowed to be incomplete in that some or all of the input conditions may be omitted. A completed specification plus a computer program are produced by the method. Synthesis involves the top-down decomposition of the user's problem into a hierarchy of subproblems. Solving each of these subproblems results in the synthesis of a hierarchically structured program. The program is guaranteed to satisfy the completed specification and to terminate on all legal inputs. In this paper we present a framework for a top-down synthesis process, explore the structure of a class of divide and conquer algorithms, and present a method for the top-down synthesis of algorithms in this class. Detailed derivations of four sorting algorithms are presented. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1982
Accession Number
ADA122126

Entities

People

  • Douglas R. Smith

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Counter IED

DTIC Thesaurus Topics

  • Algorithms
  • Angular Acceleration
  • Cells
  • Computer Programs
  • Data Acquisition
  • Diameters
  • Engineering
  • Failure Mode And Effect Analysis
  • Hydraulic Cylinders
  • Load Cells
  • Materials
  • Natural Resources
  • Plants
  • Shear Stresses
  • Specific Gravity
  • Statistical Analysis
  • Yield Strength

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Operations Research
  • Software Engineering.