Algorithmus

1

Einleitung

Algorithmus, eine Folge von Anweisungen (Rechenschritten), die einen Prozess definieren, der mit gewissen Dateneingaben beginnt und nach endlicher Zeit ein durch die Eingabedaten eindeutig bestimmtes Resultat liefert. Allgemeiner werden auch Algorithmen betrachtet, die abhängig von den Eingabedaten möglicherweise ohne Resultat enden oder überhaupt nicht enden. Schließlich gewinnen auch probabilistische Algorithmen zunehmend an Bedeutung. Diese benutzen neben den Eingabedaten Zufallszahlen und das Resultat beantwortet die gestellte Frage nur mit einer gewissen Wahrscheinlichkeit richtig.

Der Begriff des Algorithmus ist ein zentraler Begriff der modernen Mathematik, der sich nicht ohne Einschränkungen auf einfachere Grundbegriffe zurückführen lässt. Er bildet den Ausgangspunkt für die in neuerer Zeit zu beobachtende starke Hinwendung zur konstruktiven Mathematik. Danach erfordert die allgemeine Lösung eines Problems einen Algorithmus zu dessen Lösung.

2

Beispiele von Algorithmen

Die Addition von Zahlen ist wohl der erste Algorithmus, den wir in der Schule lernen: Die Eingabe besteht aus zwei Zahlen, die Ausgabe aus der Summe dieser Zahlen. Die Rechenschritte, die den Additionsalgorithmus bilden, lauten: Schreibe die Zahlen untereinander, beginne von rechts die untereinanderstehenden Ziffern (mit Ziffernübertragung) zu addieren.

Der euklidische Algorithmus (siehe hierzu auch Zahlentheorie) zur Berechnung des größten gemeinsamen Teilers zweier ganzer Zahlen wird wegen seines Alters, seiner Prägnanz und Effektivität mitunter als der Urvater aller Algorithmen bezeichnet.

Das Gauß’sche Eliminationsverfahren ist der grundlegende Algorithmus zur Lösung linearer Gleichungssysteme.

Algorithmen sind keineswegs auf das Rechnen mit Zahlen beschränkt. Es gibt z. B. Algorithmen, die Buchstabenrechnungen, wie (a + b)²= a² + 2ab + b², durchführen können, die Texte verarbeiten oder die versuchen, Texte in andere Sprachen zu übersetzen.

3

Laufzeit von Algorithmen und ein Jahrhundertproblem

Für viele Anwendungen ist die Laufzeit eines Algorithmus von entscheidender Bedeutung. Diese gibt in Abhängigkeit von der „Größe” der Eingabedaten die Anzahl der vom Algorithmus durchzuführenden Bitoperationen, also logische oder arithmetische Operationen auf 0 und 1, an. Beispielsweise wird die Größe einer einzugebenden ganzen Zahl N durch ihre Stellenzahl, also etwa logN, gemessen. Ein Algorithmus, der N verarbeitet, gilt als schnell oder effektiv, wenn seine Laufzeit polynomial ist, d. h. wenn sie ein Polynom in logN ist, insbesondere also durch eine Potenz von logN begrenzt wird. So ist z. B. die Laufzeit des euklidischen Algorithmus linear in der Größe logN der Eingangszahlen, ist also sehr schnell. Versucht man dagegen zu testen, ob eine Zahl N Primzahl ist, indem man sukzessive N durch alle Zahlen <√N zu teilen versucht, so ist die Laufzeit dieses Verfahrens N^1/2, also von exponentiellem Wachstum. Ein solches Verfahren ist für große Zahlen N nicht brauchbar. Die durch Carl Friedrich Gauß angeregte intensive Suche nach Algorithmen zur Primzahlerkennung von polynomialer Laufzeit war bis vor kurzem vergebens. Man kannte nur probabilistische Algorithmen. Die Entdeckung eines deterministischen Algorithmus von polynomialer Laufzeit im August 2002 durch die indischen Mathematiker M. Agraval, N. Kajal und N. Saxena wurde als eine echte Sensation aufgenommen. Allgemein gilt nämlich als wichtigstes offenes Problem der Komplexizitätstheorie von Algorithmen die Frage, ob für Probleme, zu deren Lösung es probabilistische Algorithmen polynomialer Laufzeit gibt, auch stets deterministische Algorithmen dieser Laufzeit existieren. Dies ist eines der sieben Millennium-Probleme, für deren Lösung je eine Million US-Dollar ausgesetzt wurden. Für das Problem der Primzahlerkennung einer Zahl N ist die Antwort also positiv, für das Problem der Primfaktorzerlegung von N aber ist die Antwort unbekannt. Eine positive Antwort würde in diesem Fall fast alle derzeitigen Verschlüsselungsverfahren obsolet machen, da diese auf der Annahme beruhen, dass man große Zahlen nicht in realistischer Zeit in Primfaktoren zerlegen kann.

4

Unlösbare algorithmische Probleme

Wenn alle Versuche fehlschlagen, einen Algorithmus zur Lösung eines Problems zu finden, besteht der Verdacht, dass es prinzipiell einen solchen Algorithmus nicht geben kann. In der Tat konnte man in neuerer Zeit für eine Reihe wichtiger mathematischer Probleme beweisen, dass es keinen allgemeinen Algorithmus zu deren Lösung geben kann. Zwei berühmte Beispiele:

Das 10. Hilbert’sche Problem, vorgestellt von David Hilbert auf dem Mathematikerkongress in Paris 1900 im Rahmen seiner 23 Probleme für das nächste Jahrhundert, fragt, ob es einen allgemeinen Algorithmus gibt, der zu entscheiden gestattet, ob eine diophantische Gleichung lösbar ist oder nicht. Die negative Antwort wurde 1970 durch Yuri V. Matiyasevich gegeben.

Das Wortproblem der Gruppentheorie, gestellt 1912 von Max Dehn, besagt: In einer Gruppe, die durch eine Reihe erzeugender Elemente und Relationen zwischen diesen gegeben ist, ist zu entscheiden, ob zwei Elemente, die als „Wort” in den Erzeugenden vorgelegt sind, gleiche Elemente der Gruppe sind. Die negative Antwort wurde 1955 von Sergej Novikov gegeben.

Natürlich schließen solche Ergebnisse nicht aus, dass für spezielle diophantische Gleichungen (siehe unbestimmte Gleichung), wie z. B. die Gleichung der Fermat’schen Vermutung, oder für spezielle Gruppen, wie z. B. Gruppen mit einer Relation, das Problem doch algorithmisch lösbar ist.

Siehe auch al-Khwarizmi