Top-down synthesis of divide-and-conquer algorithms (Q1062770)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Top-down synthesis of divide-and-conquer algorithms |
scientific article |
Statements
Top-down synthesis of divide-and-conquer algorithms (English)
0 references
1985
0 references
A top-down method is presented for the derivation of algorithms from a formal specification of a problem. This method has been implemented in a system called CYPRESS. The synthesis process involves the top-down decomposition of the initial specification into a hierarchy of specifications for subproblems. Synthesizing programs for each of these subproblems results in the composition of a hierarchically structured program. The initial specification is allowed to be partial in that some or all of the input conditions may be missing. CYPRESS completes the specification and produces a totally correct applicative program. Much of CYPRESS' knowledge comes in the form of 'design strategies' for various classes of algorithms. The structure of a class of divide-and-conquer algorithms is explored and provides the basis for several design strategies. Detailed derivations of mergesort and quicksort algorithms are presented.
0 references
sorting
0 references
program synthesis
0 references
problem reduction
0 references
derivation of algorithms from a formal specification of a problem
0 references
hierarchy of specifications for subproblems
0 references
mergesort
0 references
quicksort
0 references