4

Based on this definition of algorithm from Wikipedia:

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

An algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state.

Is "Wait for user input" or simply read() counted an step of algorithm?

I thought for the following reasons it may not fit in the definition:

  • It seems it's not an step which can be executed as an operation is executed.
  • It should wait for an external signal to get finished, it could be against of the self-contained in the definition.
  • Moreover the definition talks about an initial input, so I suppose the input should be already provided.

Am I correct?

Update: If it's not an step, then how would you represent the following sequence, is it an algorithm?

  • X = 5
  • Y = X + 4
  • if ( Y > 10) Z = Read() // get the user input
  • else Z = 1
  • if (Z > 2) Z = Z + X

Please note reading occurs conditionally, then we may not suppose the input should be already provided.

Community
  • 1
Ahmad
  • 1,806
  • 3
  • 20
  • 32
  • The reading is part of your program and happens indeed conditionally. But you could omit reading without changing the algorithm itself. That subtracts nothing. – Thomas Junk Feb 11 '15 at 13:10
  • @ThomasJunk You mean there is no difference if I substitute it with for example `Z=1`? then could I remove lines 3 and 4 and use `Z=1` instead? – Ahmad Feb 11 '15 at 13:50
  • You could write `z=rnd()` the algorithm would stay the same. – Thomas Junk Feb 11 '15 at 19:14
  • @ThomasJunk doesn't that change it to a non-deterministic algorithm, is it still fit in the above definition? If I accept the other answer, maybe the problem is with the definition itself. – Ahmad Feb 11 '15 at 19:42
  • @ThomasJunk I think my example corresponds more to [interactive communication](http://en.wikipedia.org/wiki/Interactive_computation) – Ahmad Feb 11 '15 at 19:49

3 Answers3

6

No. It is not.

Like a mathematical function, an algoritim transforms elements from a source set of information to a destination set. That works independently from the origins of the source set: Whether it stems from user (keyboard or otherwise) input, from a file containing the information or from punchcards. The input belongs to the preconditions of an algortihm: without input no need for calculation; but the method of gathering the input is neglectable and does not belong to the algorithm itself.

Update: You could substitute the reading-part itself with access to an array a[0]. The data retrieved/result by reading is part of the algorithm, the reading itself not. As I said: the source doesn't matter. Though the reading is part of your program's logic.

Take for example a sorting algorithm. A sorting algorithm is a well defined number of steps on a set to be sorted. Where the set originates has nothing to do with the algorithm - although every implementation has to take care of the problem, where to retrieve the data from.

That is of course a bit academic or one might say: philosophical.

Thomas Junk
  • 9,405
  • 2
  • 22
  • 45
  • Good! However **neglectable** differs from **is not**. then I conclude that is not :). – Ahmad Feb 11 '15 at 08:24
  • As I said: Data is the conditio sine qua non, but does not belong to the algortihm itself. If you look at an algortihm as a mathematical function: nobody would say »waiting for input« belongs to the function itself. – Thomas Junk Feb 11 '15 at 08:26
6

That definition of "algorithm" is extremely narrow. It applies only to non-interactive deterministic digital small-step algorithms.

However, algorithms need not be digital (consisting of discrete steps and operating on discrete values). They can also be continuous (consisting of discrete steps and operating on continuous values) or analog (continuous progress and operating on continuous values). They can be non-deterministic (actually, it turns out that non-determinism is just a form of interactivity). They can be interactive (i.e. interacting with an environment). They can be parallel (i.e. wide-step).

For example, the simple "bucket-of-rain" algorithm. This is an interactive digital small-step algorithm:

  1. every morning at 8:00 am you put a bucket in the yard.
  2. every evening at 8:00 pm you measure the amount of rain in the bucket, in grams, truncated down to an integer.

This is a perfectly valid algorithm. It even has steps and operates on discrete values (which isn't even necessarily required for it to be considered an algorithm).

It is, however, interactive. It depends on some environment outside of the algorithm. Mathematically, in algorithm theory, this is modeled as an oracle.

So, to answer your question: yes, what you have there, is an interactive algorithm, and the reading is definitely a part of it.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318
0

I think answering this question depends on our definition of "algorithm"

According to the given definition of the algorithm (in mathematics) the answer is "No"

I think in a general definition, the algorithm is just a recipe (set of instructions). We sometimes, confuse the algorithm with its execution. Execution of algorithm depends on its executor. Then the validity or feasibility (computability in the term of mathematics) of an algorithm depends on the executor.

A cooking recipe is also an algorithm, but you don't expect to give it to a computer and wait for your meal to be ready.

But computer can understand and perform the read() instruction then it is a valid instruction for it, and from this perspective the answer is "Yes". We shouldn't confuse this instruction with it's execution. the matter that the user will enter a data or not is not important, now every thing is just on paper (recipe).

But that read() instruction is usually used for a computer not for a computing algorithm (the algorithms we usually are familiar with and are supposed to be executed by Turing Machine). Computing algorithms are about calculation of functions or data processing and transforming, then read() is not a mathematical operator or is not important for it.

However, the example algorithm could be a computation which can not be written as a computing algorithm (a closed computation), the read() here occurs during computation. it's a type of interactive computation

In computer science, interactive computation is a mathematical model for computation that involves input/output communication with the external world during computation.

Ahmad
  • 1,806
  • 3
  • 20
  • 32