Unter einem Algorithmus versteht man eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie von einem mechanisch oder elektronisch arbeitenden Gerät durchgeführt werden kann.

Aus der Präzision der sprachlichen Darstellung des Algorithmus muss die Abfolge der einzelnen Verarbeitungsschritte eindeutig hervorgehen. Hierbei sind Wahlmöglichkeiten zugelassen. Nur muss dann genau festlegen, wie die Auswahl einer Möglichkeit erfolgen soll. [INFODUDEN]


Algorithmen besitzen folgende charakteristische Eigenschaften:

1. Im allgemeinen löst ein Algorithmus eine Klasse von Problemen. Die Auswahl eines einzelnen Problems erfolgt über Parameter.
2. Algorithmen sind determiniert (Determiniertheit), d. h.: wird ein Algorithmus mit den gleichen Eingabewerten und Startbedingungen wiederholt, so liefert er stets das gleiche Ergebnis.
3. Die Beschreibung eines Algorithmus besitzt eine endliche Länge (statische Finitheit). Ferner darf zu jedem Zeitpunkt, zu dem man die Abarbeitung eines Algorithmus unterbricht, der Algorithmus nur endlich viel Platz belegen (dynamische Finitheit).
4. Für die Praxis sind meist nur solche Algorithmen von Bedeutung, die für jede Eingabe nach endlich vielen Schritten ein Resultat liefern und anhalten (Terminierung). Ausnahmen sind z. B. Steuerungsalgorithmen eines Rechnersystems.
5. Ein Algorithmus heißt deterministisch (Determinismus), wenn zu jedem Zeitpunkt seiner Ausführung höchstens eine Möglichkeit der Fortsetzung besteht.

Kurz gesagt, sind Algorithmen deterministische Verfahren zur Lösung von Problemen in endlich vielen Schritten und mit endlichem Platzbedarf.

Unter Komplexität eines Algorithmus versteht man den erforderlichen Aufwand an Betriebsmittel, den ein Algorithmus zur Ausführung benötigt:

• Wieviel Speicherplatz benötigt der Algorithmus?
• Wie lange braucht der Algorithmus zur Problemlösung? (Laufzeit)

Zur Beantwortung dieser gestellten Fragen orientiert man sich nicht an irgendwelche Hochgeschwindigkeitsrechner oder an Rechner, welche mit besonderen Speicherplatzoptimierungen ausgestattet sind; die Aussagen zum Aufwand werden viel allgemeiner getroffen

1. unabhängig von der Rechenmaschine,
2. lediglich abhängig von den Größen der Eingabe, welche sich auf die Laufzeit bzw. auf den Speicherplatzbedarf bei Ausführung des Algorithmus auswirken.

Eine vollständige Komplexitätsabschätzung eines Algorithmus gliedert sich in drei Fälle:

1. best case (der günstigste Fall)
   Der günstigste Fall ereignet sich bei bestimmten Eingabegrößen, für die der Algorithmus minimalen Speicherplatz bzw. minimale Laufzeit benötigt.
2. average case (der Normalfall bzw. Durchschnittsfall)
   Oft lässt sich eine Wahrscheinlichkeitsverteilung angeben, die beschreibt, wie häufig die einzelnen Eingabewerte im Schnitt auftreten.
   Die Average-case-Komplexität ist dann das gemäß der Wahrscheinlichkeitsverteilung gewichtete Mittel der Laufzeit bzw. des Speicherplatzbedarfs für alle Eingaben. [INFODUDEN]
   Kurz: Im Durchschnittsfall ist ein mittlerer erwarteter Aufwand erforderlich.
3. worst case (der schlechteste Fall)
   Der schlechteste Fall ereignet sich bei bestimmten Eingabegrößen, für die der Algorithmus maximalen Speicherplatz bzw. maximale Laufzeit benötigt.

Wenn sich Laufzeit und Speicherplatz reziprok verhalten, spricht man vom Raum-Zeit-Tradeoff oder Time-space-trade-off.

Eine kürzere Laufzeit bringt oftmals einen größeren Speicherplatzbedarf mit sich und umgekehrt.
Zum Beispiel legt man im voraus einige Werte von rechenintensiven Funktionen in ein Array, in eine so genannte Lookup-table ab, um später auf diese Werte in kürzerer Zeit zugreifen zu können, jedoch kostet dies mehr Speicherplatz. Die Spieleentwickler speichern beispielsweise häufig benutzte Sinus-Werte in einer Lookup-table.

Mit diesem Begriff, zu deutsch teile und herrsche, ¹ beschreibt man folgende Problemlösungsstrategie:

1. Zerlege das Problem in Teilprobleme
2. Finde die Lösungen der Teilprobleme
3. Setze die Gesamtlösung als Kombination der Lösungen zusammen

Ist eine solche divide-and-conquer Strategie für ein Problem bekannt, so kann man sie sofort als rekursives Programm niederschreiben, wobei die Rekursion stoppt, wenn das Problem so trivial ist, dass die Lösung unmittelbar bekannt ist, siehe [INFO2002].

Im Folgenden finden Sie ein abstraktes Gerüst eines divide-and-conquer Programms (dac), das eine bestimmte Klasse von Problemen löst: ein (Teil-) Problem wird in maximal zwei kleinere Teilprobleme zerlegt.

Divide-and-conquer-Algorithmen sind z. B. QuickSort und MergeSort.

Beim dynamischen Programmieren will man verhindern, bereits gelöste Teilprobleme mehrmals berechnen zu müssen. Um dies zu verhindern, werden verhältnismäßig, aufwendig berechnete Teillösungen in einer Tabelle zwischengespeichert. Diese Teillösungen werden im Bedarfsfalle einfach nur aus der Tabelle gelesen, anstatt diese erneut zu berechnen. Dabei spart man Zeit, jedoch benötigt man für die Tabelle (Lookup-Table) zur Zwischenspeicherung mehr Speicherplatz (Time-Space-Trade-Off).

Im Gegensatz zu divide-and-conquer, welches eine top-down-Methode ist, ist dynamisches Programmieren eine bottom-up-Methode. Das heißt, um für ein Problem der Größe n eine Lösung zu finden, werden alle für das Problem relevanten Teilprobleme der Größe 1, 2, ..., n - 1 gelöst und diese Lösungen in einer Tabelle untergebracht. Um jeweils eine nächstgrößere Teillösung berechnen zu können, muss auf die bisher berechneten Tabelleneinträge zugegriffen werden.

Dynamisches Programmieren wird typischerweise zur Lösung von Optimierungsproblemen angewandt. Die Bezeichnung „Programmierung” ist historisch bedingt und bezeichnet ein Verfahren, das mit einer Tabelle arbeitet.

Eine wichtige Voraussetzung zur Anwendung des Verfahrens ist, dass die optimale Lösung für ein Problem der Größe n im Inneren aus optimalen Teillösungen kleinerer Größe zusammengesetzt ist (Bellmannsches Optimalitätsprinzip).

Weiterhin ist dynamisches Programmieren vor allem dann effizient einsetzbar, wenn im Spektrum der verschiedenen Teillösungen viele davon „überlappend” sind. Das hat die Konsequenz, dass die optimale Lösung eines Teilproblems, die einmal berechnet und in der Tabelle fixiert ist, im Rahmen der Berechnung verschiedener größerer Teilprobleme immer wieder verwendet werden kann, und nicht wieder neu berechnet werden muss.

Die Entwicklung eines Algorithmus, der auf dem Prinzip der dynamischen Programmierung beruht, erfolgt in mehreren Schritten, beschrieben in [ALGOKURZ]:

1. Charakterisiere den Lösungsraum und die Struktur einer erwünschten optimalen Lösung.
2. Definiere rekursiv, wie sich eine optimale Lösung — und der ihr zugeordnete Wert — aus kleineren optimalen Lösungen — und deren Werten — zusammensetzt.
3. Konzipiere den Algorithmus in einer bottom-up Weise so, dass für n = 1, 2, 3, ... tabellarisch optimale Teillösungen — und deren zugeordnete Werte — gefunden werden. Beim Finden einer bestimmten optimalen Teillösung der Größe k > 1 hilft hierbei, dass bereits alle optimalen Teillösungen der Größe < k bereitstehen.

Ein bekanntes Beispiel für einen Algorithmus, der auf dynamischem Programmieren beruht, ist der Cooke-Younger-Kasami-Algorithmus zur Lösung des Wortproblems bei kontextfreien Grammatiken. [ALGOKURZ]

Greedy-Algorithmen sind mit dem dynamischen Programmieren verwandt, jedoch einfacher. Die Grundsituation ist dieselbe: Es geht um ein Optimierungsproblem; es soll sukzessiv eine optimale Lösung — in Bezug auf eine gegebene Bewertungsfunktion konstruiert werden.

Während man beim dynamischen Programmieren solche optimalen Lösungen für alle kleineren Teilprobleme konstruiert und mit Hilfe dieser in einer Tabelle eingetragenen Daten die nächstgrößere optimale Lösung konstruiert, verzichtet man bei Greedy auf die Buchführung mittels einer Tabelle. Statt dessen wird der nächste Erweiterungsschritt zu einer (hoffentlich) optimalen Lösung lediglich aufgrund der lokal verfügbaren Information getätigt.

Nehmen wir an, es gibt eine Gewichtsfunktion w, die die „Güte” einer Lösung (auch einer Teillösung) misst. Es soll eine Lösung mit maximalem w-Wert konstruiert werden. Wir starten mit der leeren Lösung. Schrittweise wird die bisher konstruierte Teillösung erweitert. Wenn zur Erweiterung dieser Teillösung k Erweiterungsmöglichkeiten zur Verfügung stehen, die auf die vergrößerten Teillösungen l1, l2, ..., lk führen, so wird diejenige Teillösung li mit w(li) maximal ausgewählt.

Der Name Greedy (gefräßig) erklärt sich dadurch, dass ein Greedy-Algorithmus nach der Methode „Nimm immer das größte Stück” vorgeht.

Dieses Greedy-Prinzip kann in vielen Fällen funktionieren und tatsächlich auf eine optimale Lösung führen — ohne den Aufwand, der bei dynamischem Programmieren betrieben werden muss. [ALGOKURZ]