Algorithmus

Entstehung des Begriffs

Der Begriff Algorithmus stammt vom Namen des Mathematikers, Astronomen und Geographen Mohammad ibn Musa Al-Khwarismi, der in Bayt al-Hikma (Haus der Weisheit) in Bagdad Anfang des 9.Jahrhunderts forschte. Zwei seiner bedeutendsten Lehrbücher waren „Über das Rechnen mit indischen Ziffern“ und „Hisab al-Jabr wa-l-Muqabala“. Im letzteren Buch führte er die klassische Algebra (Al-Jabr), die Wissenschaft vom Lösen von Gleichungen, systematisch ein. Die Lateinischen Übersetzungen dieser Werke pflegte man mit „Dixit Algorismi…“ („Also sprach Algorismi…“) zu beginnen. Was danach folgte, waren klar definierte Schritte von Lösungsvorschriften, wie man im dezimalen Positionszahlensystem Rechenoperationen durchführen kann oder eine quadratische Gleichung in eine seiner sechs Normalformen/Problemtypen (mit nur positiven Parametern) durch al-Jabr (Vervollständigung) und al-Muqabala (Reduktion) transformieren kann und dann die (Wurzel-)Lösung eines Problemtyps schrittweise ermitteln kann (mit geometrisch anschaulicher Korrektheitsbegründung). Ein Algorithmus bezeichnete fortan diese Art der systematischen Angabe korrekter Schritte einer Rechenvorschrift zur Lösung einer Aufgabenstellung.

Eigenschaften

Algorithmen beschreiben Problemlösungsverfahren, die für die Realisierung in Form von Computerprogrammen geeignet sind, und sind daher der „Stoff“ der Informatik: sie sind zentraler Untersuchungsgegenstand in vielen, wenn nicht den meisten Bereichen dieses Fachgebiets [Sedgewick, 2002]. Algorithmen wurden mithilfe berechenbarer Funktionen auf Turing-Maschinen theoretisch erfasst. Für Wirtschaftsinformatiker sind ihre Eigenschaften sowie die Kunst, wie sie zur Lösung betriebswirtschaftlicher Probleme entwickelt werden, von größter Bedeutung.

Algorithmen müssen in einem endlichen Text beschrieben werden (Finitheit), in endlich vielen und in endlicher Zeit ausführbaren Schritten ablaufen (Ausführbarkeit/Terminierung) sowie bei gleichen Voraussetzungen das gleiche Resultat liefern (Determiniertheit). Darüberhinaus muss der Ablauf eines Algorithmus zu jedem Zeitpunkt eindeutig definiert sein (Determinismus) und nur endlichen Speicherplatz gebrauchen (dynamische Finitheit). Effiziente Algorithmen sind solche, die für die Lösung gleicher Probleme weniger Laufzeit und Speicherplatz benötigen.

Entwicklungsgrundsätze

Grundsätze für die Entwicklung effizienter Algorithmen werden oft aus Sicht einer Realisierung mittels imperativer Programmiersprachen mit den Grundbestandteilen Variablenzuweisung, Daten- und Rechenoperationen sowie Verzweigungsbedingungen und Schleifenanweisungen besprochen [Sedgewick, 2002], dabei speicherplatzsparsame und zugriffseffiziente Datenstrukturen [Knuth, 1997] nutzend. Im Folgenden seien einige grundsätzliche Algorithmen-Typen genannt:

• Greedy-Algorithmen lösen Probleme durch eine Folge getroffener Entscheidungen, die nicht revidiert werden. Auf dieser Methodik basieren heuristische Verfahren, bei denen Situationsbewertungen den lokal nächstbesten Schritt ermitteln.

• Greedy-Gegensatz bilden Backtracking- und Branch&Bound-Verfahren, bei denen Bäume alternativer Entscheidungen generiert und zur Laufzeit beschnitten werden. Darauf basieren viele Optimierungsverfahren (Gegensatz: Heuristiken).

• Rekursion: Eine mathematische Rekurrenz-Beziehung, wie Fakultät(0)=1, Fakultät(n)=n*Fakultät(n-1), lässt sich direkt in eine rekursive Funktion überführen, die sich selbst mit nächstniedrigerem Parameterzahl aufruft.

• Iteration: Falls wie bei Fibonacci-Zahlen Fib(0)=0, Fib(1)=0, Fib(n)=Fib(n-1)+Fib(n-2) die Anzahl der rekursiven Aufrufe wegen mehrfacher gleicher Berechnungen stark anwächst, bietet sich eine effizientere iterative Formulierung an, in der Ergebniswerte für aufsteigende Inputwerte zwischengespeichert und wiederverwendet werden.

• Divide-and-Conquer: Zerlege rekursiv-aufrufend das Gesamtproblem auf Teilprobleme, löse diese zuerst, dann füge die Teillösungen rekursiv-rücklaufend bis zur Gesamtlösung zusammen.

• Dynamische Programmierung nutzt prinzipiell Divide-and-Conquer mit iterativer Formulierung der resultierenden Rekurrenz-Beziehung.

• Normalform-Transformation dann Standardlösung: Gleichungssysteme mittels Gaus’scher Elimination in Dreiecksnormalform transformieren, dann Variablenwerte ermitteln oder bei der Wissensverarbeitung Formeln in konjunktive Normalform transformieren und darauf z.B. einen Resolutionskalkül anwenden.

• Formuliere eine betriebswirtschaftliche Problemstellung als lineares Programm bzw. als Netzwerkoptimierungsproblem, das dann mithilfe eines Standardoptimierers bzw. einer Standardmethode gelöst wird (Operations-Research-Methodik). Ähnlich deklarativ sind KI-Methoden aufgebaut.

• Eröffnungs- und Verbesserungsverfahren: Ermittle eine Anfangslösung mithilfe einer Heuristik, dann verbessere diese durch lokale Manipulationen.

• Lokale Suchverfahren funktionieren ähnlich, wobei Meta-Heuristiken lokale Optima zu umgehen versuchen. Diese und verwandte naturanaloge und evolutionäre Verfahren gehören dem Softcomputing  an.
  

Literatur

Knuth, D.E.: The Art of Computer Programming. 1.Volume: Fundamental  Algorithms, 2.Volume: Sorting and Searching. 3./2.Edition. Addison-Wesley. 1997/98

Sedgewick, R.: Algorithms (2. Edition). Pearson-Studium. Addison-Wesley. 2002.

Autor