Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B:

1. Sei A die größere der beiden Zahlen A und B (entsprechend vertauschen, falls dies nicht bereits so ist)
2. Setze A = A – B
3. Wenn A und B ungleich sind, dann fahre fort mit Schritt 1, wenn sie gleich sind, dann beende den Algorithmus: Diese Zahl ist der größte gemeinsame Teiler.

Beispiel:

Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus benutzt:

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens Muhammad ibn Musa al-Chwarizmi (* ungefähr 783, † ungefähr 850), des Autors des Buchs Hisab al-dschabr wa-l-muqabala (825, Regeln zur Wiederherstellung und Reduktion), durch das die Algebra in dem Westen verbreitet wurde. Die lateinische Fassung beginnt mit: "Dixit Algorithmi..." womit der Autor gemeint war. Das Wort Algebra stammt ebenfalls (al-Jabr – "Einrenkung") aus dem Titel des Buchs. Ursprünglich stand das Wort Algorism ca. für die Regeln zur Arithmetik mit arabischen Ziffern. Heute steht es für alle geregelten Prozeduren, mit denen Probleme aller Art gelöst werden können.

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace, in ihren Notizen zu Charles Babbage's Analytical Engine, festgehalten. Sie gilt darum als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Die mangelnde mathematische Genauigkeit in der gängigen Definition eines Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Insbesondere steht die natürliche Sprache mit ihren Unschärfen und Widersprüchlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit in dem Wege.

In der ersten Hälfte des 20. Jahrhunderts wurden eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Der bekannteste ist wohl Alan Turings Konzept der Turing-Maschine als abstraktes Modell eines Computers.

Andere gängige Konzepte sind beispielsweise rekursive Funktionen, insbesondere der Lambda-Kalkül, Zeichen-Ersetzungssysteme wie Markov-Algorithmen oder Chomsky-Grammatiken oder verallgemeinerte abstrakte Programmiersprachen mit den Grundelementen Sequenz, Auswahl und Wiederholung.

Um die Mitte des 20. Jahrhunderts konnte, unter maßgeblicher Beteiligung von Alan Turing selbst, gezeigt werden, dass all diese Methoden ebenso leistungsfähig sind wie eine Turing-Maschine: Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren.

Aus diesem Grunde ist heutzutage die Church-Turing-These: "Jeder Algorithmus kann durch eine Turingmaschine ausgeführt werden" allgemein akzeptiert. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache.

Formal ist ein Algorithmus eine Beschreibung eines Verfahrens zur Lösung einer bestimmten Klasse von Problemen. Dabei müssen folgende Bedingungen erfüllt sein:

1. Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit).
2. Der Ablauf des Verfahrens ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).
3. Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
4. Das Verfahren darf zu dem Ausführen nicht unendlich viel Speicherplatz benötigen (Dynamische Finitheit).
5. Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein. (Ausführbarkeit)
6. Der Algorithmus darf ca. endlich viele Schritte benötigen. Jeder einzelne Schritt muss in endlicher Zeit ausführbar sein. (Terminierung)

Eine Ausnahme bilden stochastische Algorithmen, bei denen der jeweils nächste Verfahrensschritt von einer Wahrscheinlichkeitsregel abhängen kann.

kurz: wenn gleiche Startwerte vorhanden sind, muss das gleiche Ergebnis raus kommen

Algorithmen sind determiniert: Werden sie mit gleichen Parametern und Startwerten aufgerufen, liefern sie immer das gleiche Resultat. Ausnahme bilden randomisierte und stochastische Algorithmen, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

kurz: es darf ca. stets eine Möglichkeit vorhanden sein (--> sonst stochastisch)

Deterministisch heißen alle Algorithmen, bei denen zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung besteht. Gibt es mehrere Möglichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen, so spricht man von stochastischen, randomisierten oder probabilistischen Algorithmen. In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber in praktischen Algorithmen nicht vorkommen kann.

kurz: die Beschreibung ist endlich

Die Beschreibung eines Algorithmus ist nicht unendlich groß. Als statische Finitheit wird die Endlichkeit des Quelltextes genannt. Der Quelltext darf ca. begrenzten, wenn auch bei Bedarf sehr viel Speicherplatz in Anspruch nehmen.

kurz: Fülle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich

Zu jedem Zeitpunkt der Ausführung darf der von einem Algorithmus benötigte Speicherbedarf ca. endlich groß sein. Andernfalls wäre der Algorithmus nicht ausführbar. Dies wird als dynamische Finitheit genannt.

kurz: bricht nach absehbarer Zeit kontrolliert ab (Ausnahme z.B. Betriebssystem)

Algorithmen sind terminierend, sie kommen nach einer endlichen Zahl von Schritten zu einem Ergebnis. Die tatsächliche Zahl der Schritte kann jedoch willkürlich groß sein. Steuerungssysteme und Betriebssysteme erfüllen dieses Merkmal nicht. Donald Knuth schlägt vor nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu nennen.

Die Erforschung und Analyse von Algorithmen ist Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in einer Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in theoretischen Pseudosprachen (Pseudocode) geschrieben und behandelt.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt, die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, d.h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren ggT gesucht wird, oder wie viele Elemente sortiert werden müssen etc.

Das Verhalten bezüglich Terminierung, d.h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

In einzelnen Library-Beschreibungen gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Ãœbersicht gibt die Liste von Algorithmen.

Auch in dem Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:

Prozess	Ausführender	Algorithmus	Typische Anweisung
Kuchenbacken	Bäcker	Rezept	nimm 1 Pfund Mehl / rolle Teig aus
Spielen einer Klaviersonate	Pianist	Partitur
Bedienung eines Handys	Anrufer	Bedienungsanleitung	drücke die # Taste
Bau eines Radios	Radiobastler	Schaltplan und Montageanleitung	verbinde Transistor T1 mit T5
Kassieren in dem Supermarkt	Kassiererin an Registrierkasse	Bedienungsanleitung für Registrierkasse, Funktionsplan der Registrierkasse	Eintasten von 17,82 +

• Approximationsalgorithmus
• Datenstruktur
• Determinierter Algorithmus
• Deterministischer Algorithmus
• Entscheidungsproblem
• Genetischer Algorithmus
• Greedy Algorithmus "gieriger" Algorithmus, z.B. zur Zerlegung von Brüchen in Summen von Stammbrüchen
• Komplexitätsklassen
• MMIX (virtuelle Maschine von Donald E. Knuth zur Darstellung von Algorithmen)
• Online-Algorithmus
• Optimierungsproblem
• Probabilistischer Algorithmus
• randomisierter Algorithmus
• Sortierverfahren
• Stochastischer Algorithmus
• Suchverfahren