Starting from an initial state and initial input the instructions describe a computation that, when executed, will proceed through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily some algorithms, known as randomized algorithms, incorporate random input. A partial formalization of the concept began with attempts to solve the the decision problem posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability" or "effective method"; those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939.
While there is no generally accepted formal definition of "algorithm," an informal definition could be "a set of rules that precisely defines a sequence of operations." For some people, a program is only an algorithm if it stops eventually; for others, a program is only an algorithm if it stops before a given number of calculation steps.A prototypical example of an algorithm is Euclid's algorithm to determine the maximum common divisor of two integers; an example (there are others) is described by the flow chart above and as an example in a later section.
examples:
Sorting example
An animation of the quicksort algorithm sorting an array of randomized values. The red bars mark the pivot element; at the start of the animation, the element farthest to the right hand side is chosen as the pivot.
High-level description:
- Assume the first item is largest.
- Look at each of the remaining items in the list and if it is larger than the largest item so far, make a note of it.
- The last noted item is the largest in the list when the process is complete.
Algorithm LargestNumber
Input: A non-empty list of numbers L.
Output: The largest number in the list L.
largest ← L0
for each item in the list (Length(L)≥1), do
if the item > largest, then
largest ← the item
return largest
- "←" is a loose shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
- "return" terminates the algorithm and outputs the value that follows.
No comments:
Post a Comment