Algorithm
From DmWiki
When programming a computer, you usually communicate with it through a programming language. These can be very basic languages like assembly, which is really just a human-readable substitute for the machine code executed by the CPU, or some high-level language like Java or C#.
Since there are so many languages out there, it would be nice to have a term that describes the way we talk to a computer independent of the language we use to talk to it. Such a set of instructions is usually refered to as an algorithm.
| Table of contents |
Layman's Definition
Often an algorithm is compared to a cooking recipe. In one way the comparison is very good. A recipe describes what you need to do to cook some dish and it does so by giving a set of instructions that are independant of the type of cooker you use and the knife you use to cut your veggies.
On the other hand, the comparison is flawed. If we were to design a computer programm following a usual cooking recipe:
Turn on stove Put kettle with water on stove Cut 500g carrots and 500g potatoes Add veggies to water Add spices Cook until veggies are soft
we would run into some serious problems. The above description isn't very accurate. What is soft and what spices should we actually add? A human can usually feel what he thinks is soft and he probably knows if he likes his veggies with salt or pepper. For a computer however, things need to be extremely precise.
The Algorithm
Since computers are machines that work with precise step by step instructions, we need a more exact definition. In contrast to the cooking recipe, an algorithm is a finite set of "well-defined" instructions. Well-defined means that it is only valid to use instructions in an algorithm that are unambiguous and precisely defined before the algorithm is written. Additionally, it has a well-defined "initial state". An initial state includes a beginning instruction as well as a set of input parameters to the algorithm.
Terminating vs Non-Terminating
Given a finite set of instructions, an algorithm can still take an infinite amount of time to run. It is extremely easy to construct such an algorithm. Assume there are two basic operations defined Ops = advance,jump. Advance simply continues execution of the algorithm at the next instruction in the algorithm, while jump continues the algorithm at the passed position.
0 advance 1 jump 0
Obviously this algorithm is valid. It contains only two operations and has an initial state in 0. Equally obviously, it will never stop its execution, and therefore falls into the category of non-terminating algorithms.
In most cases it is required that an algorithm terminates in finite time. (Paradoxically it is not possible to write an algorithm to decide wether another algorithm is terminating. In theoretical computer science this is commonly known as the halting problem (http://en.wikipedia.org/wiki/Halting_problem)).
Deterministic vs. Non-Deterministic
There are two main types of algorithms: deterministic algorithms and non-deterministic ones. A deterministic algorithm is the one you will usually be dealing with. Determinism means that for one instruction there is always only one possible following instruction. It is easy to see that almost any kind of algorithm will fall into this category, unless you own a computer that has a true random number generator, based on some seemingly random nucleus decay.
Since there is only one possible instruction following another we can deduce that a deterministic algorithm will always produce the same result, given the same input parameters.
A non-deterministic algorithm introduces the element of randomness. Here a set of instructions can have multiple possible following instructions. Although there are no non-deterministic algorithms on today's computers, algorithms involving pseudo-randomness are often referred to as being non-deterministic as well.
Algorithmic Strategies
When talking about algorithms there are a few standard terms that describe the strategy an algorithm uses to solve a problem.
The Greedy Strategy
Greedy algorithms try to solve a problem by applying tactics that solve a problem in the best way locally. An example for a greedy algorithm is bubble sort. Bubble sort compares and eventually swaps adjacent pairs, of sortable elements, which lets them "rise" up in the set that is to be sorted.
A more famous and useful example of a greedy algorithm is Dijkstra's path finding algorithm. Dijkstra's algorithm especially shows how greedy algorithms always use the immdediate solution to solving a problem.
Divide and Conquer
Rather than solving a problem locally, divide-and-conquer algorithms divide the problem space into smaller pieces, which may be easier to solve than the whole problem. A typical example is the binary search algorithm. Given that a data set is sorted, binary search looks at the median element of the set and compares the search value to it. Since it is known that the set is sorted, one half of the set can immediately be discarded for the search, thus cutting the problem in half. Divide-and-conquer algorithms often have a logarithmic complexity, which often makes them optimal strategies for many common problems.
