Definition:Algorithm

From ProofWiki
Jump to navigation Jump to search

Definition

An algorithm is a finite set of instructions (or rules) that defines a sequence of operations for solving a particular computational problem for all problem instances for some problem set.


An algorithm must have the following properties:


Finiteness

An algorithm must terminate after a finite number of steps.


Definiteness

Each step of an algorithm must be precisely defined.


Inputs

An algorithm has zero or more inputs.

These are values supplied either:

before the algorithm starts
as the algorithm runs.

These inputs are taken from specified sets of objects.


Outputs

An algorithm has one or more outputs.

These are values which are specifically determined by the inputs.


Effectiveness

An algorithm is supposed to be effective.

That is, its operations must be basic enough to be able to be done exactly and in a finite length of time by, for example, somebody using pencil and paper.


Parts of an Algorithm

Step

An algorithm consists of a finite set of steps, uniquely identified by means of a label, conventionally numeric.


A step of an algorithm consists of:

an operation
an instruction as to what the algorithm is to do next, which will be one of the following:
$(1): \quad$ By default: to move onto the next step in the sequence
$(2): \quad$ Based on the result of a condition, the specific step to perform next
$(3): \quad$ To terminate.


Operation

In an algorithm, an operation is part of a step of that algorithm.


It consists of one of two things:

an action

or:

a condition.


Action

In an algorithm, an action is part of a step of that algorithm.


It is an operation which changes the state of the algorithm in some manner.


Condition

In an algorithm, a condition is part of a step of that algorithm.


It is an operation which determines the outcome of a decision as to which step to execute next,


Comment

In an algorithm, a comment is a piece of explanatory information that helps the reader of that algorithm understand it better.


Formal Specification

An algorithm can be implemented formally as a computational method $\left({Q, I, \Omega, f}\right)$ as follows:


Let $A$ be a finite set of symbols.

Let $A^*$ be the set of all collations on $A$:

$\left\{ {x_1 x_2 \cdots x_n: n \ge 0, \forall j: 1 \le j \le n: x_j \in A}\right\}$


The states of the computation are encoded so as to be represented by elements of $A^*$.


Let $N \in \Z_{\ge 0}$.

Let $Q$ be the set of all ordered pairs $\left({\sigma, j}\right)$ where $\sigma \in A^*, j \in \Z: 0 \le j \le N$.

Let $I \subseteq Q$ such that $j = 0$.

Let $\Omega \subseteq Q$ such that $j = N$.


Let $\theta, \sigma \in A^*$.

Then $\theta$ occurs in $\sigma$ if and only if $\sigma$ has the form:

$\alpha \theta \omega$

where $\alpha, \omega \in A^*$.


Let $f$ be a mapping of the following type:

$f \left({\left({\sigma, j}\right)}\right) = \begin{cases}\left({\sigma, a_j}\right) : & \sigma_j \text { does not occur in } \sigma \\ \left({\alpha \theta_j \omega, b_j}\right) : & \alpha \text { is the shortest element of $A^*$ such that } \sigma = \alpha \theta_j \omega\end{cases}$
$f \left({\left({\sigma, N}\right)}\right) = \left({\sigma, N}\right)$


Analysis

There are two primary methods for analyzing algorithms formally:

Correctness

The primary method of validity for algorithms is using a Proof of Correctness.

This is correctness through verification of the algorithm accomplishing its purpose formally, and terminating in $k$ finite steps.


Complexity

The complexity of an algorithm is defined as the number of discrete steps needed to terminate as a function of the number of inputs.


Also see

  • Results about algorithms can be found here.


Historical Note

The word algorithm is a recent addition to the English language. It was still absent from major dictionaries as late as $1957$.


Linguistic Note

The word algorithm ultimately derives from the name Muhammad ibn Musa al-Khwarizmi.

It is strongly believed that it is the result of linguistic evolution of the archaic term algorism, with which algorithm ought not be confused (although some sources do not make the distinction).

The term was seen in German literature in its Latin form algorithmus at around the time of Gottfried Wilhelm von Leibniz, where the classical algorithms were referenced.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Algorithm&oldid=728945"