Algorithmen

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten.

Eng verwandt mit dem Begriff Algorithmus ist die Turingmaschine, aus der sich der Begriff des Algorithmus formulieren lässt:

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.

Eigenschaften eines Algorithmus sind:

1. Finitheit: Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein.
2. Ausführbarkeit: Jeder Schritt des Verfahrens muss ausführbar sein.
3. Dynamische Finitheit: Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen.
4. Terminierung: Das Verfahren darf nur endlich viele Schritte benötigen.

Darüber hinaus erfüllen Algorithmen in der Praxis die folgenden zusätzlichen Eigenschaften:

1. Determiniertheit: Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern.
2. Determinismus: Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert.

Algorithmen sind Gegenstand von Spezialgebieten der Theoretischen Informatik, der Komplexitätstheorie und der Berechnbarkeitstheorie.

Beispiel: Rete-Algorithmus für ein Expertensystem

Von Razorbliss - Eigenes Werk, CC0, Link