Friday, April 8, 2011

THE AMAZING ALGORITHM

In math and in computer science an algorithm is a effective method expresed as a finest list of well defined instructions for calculating instructions.Algorithms are used for calculation, data processing, and automated reasoning.
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ödelHerbrandKleene 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.
One of the simplest algorithms is to find the largest number in an (unsorted) list of numbers. The solution necessarily requires looking at every number in the list, but only once at each. From this follows a simple algorithm, which can be stated in a high-level description English prose, as:
High-level description:
  1. Assume the first item is largest.
  2. 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.
  3. The last noted item is the largest in the list when the process is complete.
formal description: Written in prose but much closer to the high-level language of a computer program, the following is the more formal coding of the algorithm in pseudocode or pidgin code:
Algorithm LargestNumber
  Input: A non-empty list of numbers L.
  Output: The largest number in the list L.
  largestL0
  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, "largestitem" 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