Eigenschaften von Algorithmen

Einordnung des Artikels

• Einführung in die Informatik
  • Einführung in die Programmierung
    • Eigenschaften von Algorithmen

Einführung

Bisher:

Ein Algorithmus löst ein komplexes Problem, indem er eine Folge von elementaren Befehlen schrittweise abarbeitet. (Dabei ist den elementaren Befehlen der Zusammenhang zum eigentlichen Problem oft nicht mehr anzusehen.)

An mehreren Beispielen wurde dies demonstriert (siehe insbesondere Algorithmen und Computer):

• Multiplikation von mehrstelligen Zahlen: Zurückführung auf die Multiplikation und Addition einstelliger Zahlen.
• Umrechnen zwischen verschiedenen Zahlensystemen: Zurückführung auf Multiplikation und Division.

Untersucht man diese Algorithmen genauer, erkennt man zwei entscheidende Merkmale von Algorithmen:

1. Ein komplexer Vorgang wird in elementare Schritte (meist Rechenschritte) zerlegt.
2. Diese Schritte müssen in einer streng einzuhaltenden Reihenfolge abgearbeitet werden.

Die folgenden Abschnitte dienen dazu, den Algorithmus-Begriff weiter zu verschärfen, um schließlich zu formalen Sprachen zu gelangen, mit deren Hilfe dann Programme geschrieben werden können, die von einem Computer abgearbeitet werden. Mit formalen Sprachen ist gemeint, dass diese Sprachen - anders als unsere umgangssprachliche Formulierung eines Algorithmus - gewissen Regeln (einer Syntax) gehorchen, die streng eingehalten werden müssen. Diese Sprachregeln werden dann vom Compiler überprüft und das lauffähige Programm wird nur erzeugt, wenn keine Syntax-Fehler enthalten sind.

Präzisierung des Algorithmus-Begriffs

Durch die folgenden Begriffe kann schärfer formuliert werden, was ein Algorithmus ist.

Determiniertheit

Ein Algorithmus muss bei gleichen Eingabewerten gleiche Ausgabewerte liefern. Andernfalls nennt man ihn einen randomisierten Algorithmus.

Determinismus

Der jeweils nächste Schritt in der Ausführung des Algorithmus ist eindeutig festgelegt.

Ausführbarkeit

Jeder Schritt des Verfahrens muss ausführbar sein.

Finitheit

Die Anweisungen müssen in einem endlichen Text eindeutig beschreibbar sein.

Dynamische Finitheit

Der Algorithmus kann nur endlich viele Werte benutzen und darf nur endlichen Speicherplatz beanspruchen.

Terminiertheit

Der Algorithmus muss irgendwann enden. Andernfalls wird er als nicht-terminierender Algorithmus bezeichnet.

Definition von Algorithmus

Definition Algorithmus:

Schrittweise Vorschrift zur Berechnung gesuchter aus gegebenen Größen, in dem jeder Schritt aus einer Anzahl eindeutig ausführbarer Operationen und einer Angabe über den nächsten Schritt besteht.

Praktische Bedeutung der Eigenschaften von Algorithmen

1. Determiniertheit:

Es ist gar nicht so leicht, einen Algorithmus zu schreiben, der einen echten Zufallsprozess (wie einen Münzwurf oder das Würfeln) simuliert - echte Zufallszahlen kann ein Computer nicht erzeugen. Falls Sie irgendwann einen derartigen Zufallsgenerator brauchen, versuchen Sie besser nicht, ihn selber zu programmieren. Man tappt dabei immer wieder in die Falle, dass man eine Zahlenfolge erzeugt, die periodisch ist (oder sogar Periodenlänge 1 besitzt, also irgendwann nur noch den selben Wert ausgibt).

Gute Zufallsgeneratoren machen aber nichts anderes: sie erzeugen periodische Zahlenfolgen, deren Periode aber so lang ist, dass sie auf kurzer Distanz wie Zufallszahlen aussehen.

2. Determinismus:

Der Determinismus scheint dem zu widersprechen, was wir von vielen Programmen kennen: Ein Nutzer macht eine Eingabe und je nachdem welche dies ist, reagiert das Programm so oder so - also wurde eine zufällige Entscheidung getroffen.

Der Begriff des Determinismus darf nicht falsch verstanden werden: Ist in einem Programm eine Nutzereingabe vorgesehen, so ist sie als solche zu kennzeichnen. Und im Programm wird (vor der Eingabe) eine Variable definiert, die die Nutzereingabe speichert. Je nachdem welchen Wert diese Variable hat, wird später die eine oder die andere Anweisung ausgeführt. So gesehen ist der Ablauf deterministisch: Im Programm ist vorgesehen, unter welcher Bedingung die eine oder die andere Anweisung ausgeführt wird.

3. Ausführbarkeit:

Die Beschreibung der Ausführbarkeit hört sich abstrakt und fast schon nichtssagend an - sie soll ausdrücken, dass die Arbeitsschritte des Programms einfach formuliert werden müssen. Aber dahinter verbirgt sich ein großes praktisches Problem, das bei fast jeder Entwicklung eines neuen Programms auftritt. Der Auftraggeber des Programms ist meist nicht der Programmierer. Also muss der Auftraggeber erklären, was er haben möchte - der Fachausdruck dafür ist, er muss die Spezifikation des Programms formulieren. Und er wird dies in den Begriffen seiner Welt tun, die aber nicht die des Programmierers ist, das heißt beide haben eine völlig andere Vorstellung davon, was ein elementarer Rechenschritt ist und werden lange Zeit benötigen bis sie zueinander finden.

4. Finitheit:

In der Mathematik lassen sich zahlreiche Paradoxien mit Unendlichkeiten erzeugen. Die Beschreibung des Algorithmus muss endlich sein und kann dadurch keine Paradoxien hervorbringen.

5. Dynamische Finitheit:

In der Praxis tritt das Problem oft schon in abgeschwächter Form auf: Ein Programm kann durch einen Programmierfehler - wie man im Fachjargon sagt - ein Speicherleck (memory leak) haben. Dann beansprucht es immer mehr Hauptspeicher, obwohl für die zu erledigenden Aufgaben viel weniger Speicherplatz nötig wäre. Dies kann zur Verlangsamung des Programms oder sogar zum Absturz des Computers führen.

6. Terminiertheit:

Dass ein Programm terminieren muss, ist eine Forderung aus der Zeit als es nur Single-Tasking-fähige Rechner gab. Da man immer erst das Ende eines Programmes abwarten musste, bis man ein neues Programm starten konnte, durfte es keine Endlos-Schleifen geben.

Heute sind fast alle Programme mit graphischer Oberfläche nicht terminierende Programme, da sie nichts tun, wenn der Nutzer keine Eingabe macht. Ebenso das Betriebssystem: Es erfüllt seine Aufgabe bis der Nutzer den Computer ausschaltet - ein definiertes Ende ist im Algorithmus nicht vorgesehen.

Mit Algorithmus verwandte Begriffe

Äquivalente Algorithmen

Man nennt zwei Algorithmen äquivalent, wenn sie bei gleichen Eingabewerten die gleichen Ausgabewerte liefern (für die Multiplikation zweier Zahlen gibt es mehrere Verfahren, die sich in ihrer Komplexität unterscheiden können).

Relevanz für die Praxis:

In der Software-Entwicklung gibt es immer Zusatz-Anforderungen, die an ein Programm gestellt werden (und die vom Qualitäts-Management eingefordert werden). Der Programmierer hat also nicht nur irgendeinen Algorithmus zu entwickeln, der den gewünschten Anforderungen gerecht wird, sondern er muss weitere Nebenbedingungen beachten.

Aufgabe:

Welche Zusatz-Anforderungen können bei der Software-Entwicklung eine große Rolle spielen?

Abstrakte Algorithmen

Um zu betonen, dass ein Algorithmus niemals nur ein Problem löst, sondern immer eine ganze Klasse von Problemen, spricht man häufig von abstrakten Algorithmen.

Beispiel:

Ein Navigationssystem soll nicht nur den Weg vom Studienzentrum zum Bahnhof beschreiben, sondern für jede Eingabe eine Wegbeschreibung liefern.

Beispiel:

Bei den Schaltwerken wurde gezeigt, wie man aus Toggle-Flip-Flops einen Zähler bauen kann (dort wurden die Ergebnisse im Dualsystem ausgegeben und jedes Signal bewirkte, dass das Ergebnis um 1 erhöht wird). Naheliegend sind die Fragen:

• Wie baut man einen Zähler, der in einem beliebigen Zahlensystem hochzählt?
• Wie baut man einen Rückwärts-Zähler?
• Wie baut man einen Zähler mit beliebiger Schrittweite n, der also in jedem Schritt nicht um 1 sondern um n hochzählt?

Als Programmierer versucht man meist, ein Problem auf eine abstraktere Stufe zu heben. Denn oft ist dessen Lösung kaum mit einem Mehraufwand verbunden, man kann aber mehr Spezialfälle damit lösen.

Algorithmierung

Mit Algorithmierung wird die Tätigkeit beschrieben, wenn ein Algorithmus formuliert, aber noch nicht in die Programmiersprache übersetzt wird.

Typische Arbeitstechniken dabei sind:

1. Verfahren der schrittweisen Verfeinerung.
2. Formulierung des Algorithmus in Pseudocode.
3. Diagrammtechniken: zum Beispiel Flußdiagramm (= PAP, Programmablaufplan) oder Struktogramm.

Implementierung

Der Begriff Implementierung soll von der Algorithmierung abgrenzen und beschreibt den Vorgang, wenn ein Algorithmus tatsächlich in der höheren Programmiersprache geschrieben wird.

Es gibt noch zwei weitere Bedeutungen von Implementierung:

1. Wenn ein neues System eingeführt (implementiert) wird. In dieser Bedeutung wird Implementierung hier nicht verwendet.
2. Wenn später erklärt wird, welche Bedeutung in einem Programm Deklarationen haben, kann mit Implementierung eine spezielle Tätigkeit des Programmierers gemeint sein, die die Deklaration ergänzt: Nämlich wenn er zu einer bereits deklarierten Funktion den Quelltext schreibt, der die Deklaration erfüllt. (Mit der Deklaration einer Funktion wird definiert, wie die Funktion von anderen Teilen des Programms benutzt werden kann, aber noch nicht, welche Befehle sie ausführt; die Deklaration ist also etwas wie eine Schnittstelle.)