Algorithmen
Algorithmen sind aus
endlich vielen Schritten bestehende eindeutige Handlungsvorschriften zur Lösung von Problemen. Sie sind Gegenstand einiger Spezialgebiete der
Theoretischen Informatik, der Komplexitätstheorie und der Berechenbarkeitstheorie.
Definition
Turingmaschinen und der Algorithmusbegriff
Die mangelnde mathematische Faßbarkeit des Begriffs
Algorithmus führte in der ersten Hälfte des 20. Jahrhunderts zu einer Reihe von Definitionssansätzen: die Turingmaschine, Registermaschinen, der Lambda-Kalkül, rekursive
Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.
Es hat sich gezeigt, dass all diese Definitionen äquivalent sind; die so definierten "Algorithmen" also die gleiche Berechnungsstärke besitzen. Daher ist eine mögliche Definition die folgende:
- Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.
Church-Turing-These
Die Church-Turing-These besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine gelöst werden kann. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache.
Eigenschaften
Aus der Definition des
Algorithmus kann ein Teil dieser Eigenschaften abgeleitet werden, andere werden speziell gefordert um die
Klasse der
Algorithmen weiter einzugrenzen.
Determiniertheit
Ein Algorithmus ist determiniert, wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.
Determinismus
Ein Algorithmus ist deterministisch, wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Dabei gilt, dass jeder deterministische Algorithmus determiniert, während aber nicht jeder determinierte Algorithmus deterministisch ist. Algorithmen, bei in einzelnen Schritten Zufallszahlen eine Rolle spielen, sind meist nicht deterministisch, obwohl sie bei gleichen Eingaben stets das gleiche Ergebnis liefern können.
Finitheit
Statische Finitheit
Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeichen bestehen.
Dynamische Finitheit
Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.
Terminiertheit
Terminiertheit heißt: Ein
Algorithmus hält nach
endlich vielen Schritten an (bricht kontrolliert ab). Dies gilt für jede mögliche Eingabe. Würde ein
Algorithmus nicht terminieren (und somit zu keinem Ergebnis kommen), wäre die Folge eine so genannte Endlosschleife.
Darüber hinaus ist die Terminierung eines Algorithmus (das Halteproblem) nicht entscheidbar. Das heißt, das Problem, festzustellen, ob ein Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar.
Effektivität
Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.
Ein Mathematiker, der nicht irgendwie ein Dichter ist, wird nie ein vollkommener Mathematiker sein.
Karl Weierstraß
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld
• Dοrfplatz 25 • 17237 Blankеnsее
• Tel.: 01734332309 (Vodafone/D2) •
Email: cο@maτhepedιa.dе