Eigenschaften von Algorithmen

1. Etymologie
2. Definition
   1. Intuitiv
   2. Wissenschaftlich
   3. Church'sche These
3. Merkmale
4. Vor- und Nachbedingungen
5. Komplexität
6. Literatur

Etymologie

Abgeleitet vom Namen des arabischen Mathematikers Muhammed Ibn Musa al-Kwarizmi (ca. 813-864).

Definition

Intuitiv

Anleitung zur Lösung eines berechenbaren Problems.

Wissenschaftlich

Turing-Maschine, Turing 1936.

Lambda-Kalkül, Church 1936.

Für Zeichenreihen, Markow 1951.

Church'sche These 1936

Jede im intuitivem Sinne berechenbare Funktion ist auch Turing-berechenbar.

Diese These wird heute von der Mehrheit der Informatiker akzeptiert.

Merkmale eines Algorithmus

Allgemeinheit. Löst Klasse von Problemen; Spezifikation via Parameter.

Determiniert­heit. Bei gleichen Eingabe- und Startwerten gleiche Endwerte (im Ggs. zu stochastischen A., die mit Zufallszahlen arbeiten).

Determinismus. Zu jedem Zeitpunkt der Bearbeitung gibt es nur eine Möglichkeit der Fortsetzung.

Terminierung. Halt nach endlicher Zeit (Betriebssystem- und Prozeß­steuerungen ausgenommen).

Vor- und Nachbedingungen eines Algorithmus

Wenn der Aufrufer die Vor­bedingungen eines A. einhält, verspricht dieser dafür im Gegenzug, die Nach­bedingungen zu garantieren. Anderenfalls ist das Ergebnis undefiniert. Die notwendigen Vorbedin­gungen sollten vom Programmierer des A. gut dokumentiert sein, damit der Aufrufer sich danach richten kann!

/* Vorbedingung: x >= 0 */
double sqrt(double x)
  {
  ..
  }
/* Nachbedingung: Ergebnis ist Wurzel von x */

Komplexität von Algorithmen

Die Komplexität Θ beschreibt als Asymptote a(x) der Laufzeitfunktion t = f(n) die wesentliche, grobfunktionale Abhängigkeit der Laufzeit eines Algorithmus von der Zahl n der zu verarbeitenden Elemente. Komplexitäten lassen sich somit leichter vergleichen als exakte Laufzeitfunktionen, was eine Einordnung der Algorithmen unter Laufzeitaspekten erleichtert.

Θ(n)	Komplexitätsgrad
c	konstant
log n	logarithmisch (organisch)
n	linear
n log n	Ordnung n log n
n2	quadratisch
n3	kubisch
nc	polynomial
cn	exponentiell
nn	superexponentiell

Beispiele

Algorithmus	Θ(n)
Fakultätsfunktion n!	nn+0.5
Fibbonaccifolge	1.618034n
Multiplikation quadr. Matrizen (3 Schleifen!)	n3
Bubble-Sort (2 Schleifen)	n2
Binärdarstellung	b; b = Anzahl Bits
Normale Suche	n
Quick-Sort	n log n
Schnelles Potenzieren n. Lègendre	log n
Binäre Suche	log n
Interpolationssuche	log log n
Stringsuche n. Knuth-Morris-Pratt	n+k; k = Länge Suchstring
Stringsuche n. Boyer-Moore	Ähnlich wie KMP-Suche
Hash-Suche	Schwer analysierbar, am schnellsten
Sieb des Erathosthenes	n log log n

Literatur

1. Sedgewick R.; Algorithmen; Addison-Wesley; Bonn; 1997; S. 22 ff.
2. Hermann D.; Algorithmen-Arbeitsbuch; Addison-Wesley; München; 1992; S. 19 ff.
3. Knuth D.E.; The Art of Computer Programming. Volume 1: Fundamental Algorithms; Addison-Wesley; Reading, MA; 1979
4. Ruhland J.; TOOL Informatik: Datenstrukturen und elementare Algorithmen; Vogel; Würzburg; 1991; S. 9 ff.