in reply to Algorithms

First the definition:
What is an algorithm? : A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps.

That's a very unusual definition of an algorithm. I've never heard of a definition that requires an algorithm to be recursive. And if algorithms need to be established, how do you call a new way of solving a problem?

In his wonderful series The Art of Computer Programming (if you haven't read it yet, run to your nearest bookstore now and buy it - it will be the best $150 you've ever spend), Knuth dedicates the first paragraph (nine pages, including exercises(!)) to the meaning of the concept algorithm. Quoting him:

The modern meaning for algorithm is quite similar to that of recipe, process, method, technique, procedure, routine, rigmarole, except that the word "algorithm" connotes something just a little different. Besides merely being a finite set of rules that gives a sequence of operations for solving a specific type of problem, an algorithm has five important features:
  1. Finiteness.
  2. Definiteness.
  3. Input.
  4. Output.
  5. Effectiveness.

Each of the above points is further explained, but I've omitted the explaination.

Cormen, Leiserson and Rivest start their Introduction to Algorithms (another "must have") with:

Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

If you wonder why Knuth requires an algorithm to be finite (that is, the algorithm terminates eventually) and CLR don't, the latter further define correct algorithms, which must terminate.

Abigail

Replies are listed 'Best First'.
Re: Re: Algorithms
by tommyw (Hermit) on Jun 24, 2003 at 12:53 UTC

    I've never heard of a definition that requires an algorithm to be recursive.

    I'd suspect that the original text has got something to do with recursive function theory. In that sense, an algorithm is recursive, since solving a problem involves:
    moving from the intial condition to an intermediate state
    moving from the intermediate state to another intermediate state (between 0 and a finite number of times
    moving to the final state

    Obviously, this is a recursive structure, which only bottoms out when you get to the atomic operations of the language.

    --
    Tommy
    Too stupid to live.
    Too stubborn to die.

[reply]

      Just thought add that the mathematical concept of recursion and the computational concept of recursion are different. Recursion in a mathematical sense can be handled by both iterative solutions or recursive solutions in the computational sense.


      ---
      demerphq

      <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
[reply]
[d/l]
Re: Re: Algorithms
by batkins (Chaplain) on Jun 24, 2003 at 22:26 UTC
    That's a very unusual definition of an algorithm. I've never heard of a definition that requires an algorithm to be recursive. And if algorithms need to be established, how do you call a new way of solving a problem?

    Reread the original post and notice the word especially.

    milkbone - perl/tk instant messaging - it's the only way to fly

    You know anyone who'll debug two million lines of code for what I get this job?
    - Dennis Nedry

[reply]

In Section Meditations