Algorithmen und Datenstrukturen

Das sogenannte logische Paradigma führt uns zu den deduktiven Algorithmen. Deduktive Algorithmen basieren auf logischen Aussagen und sind die Grundlage von Programmiersprachen wie PROLOG (für PROgramming in LOGic).

Logische Algorithmen bestehen aus einer Reihe von logischen Aussagen und einem Auswertungsalgorithmus für Anfragen. Daher sind sie nicht in dem Sinne Algorithmen, wie wir sie bisher betrachtet haben – erst die Kombination der drei Bestandteile, logisches Programm, Auswertungsalgorithmus und konkrete Anfrage, legen eine Berechnungsfolge fest. Während die meisten sonstigen Programmiersprachen applikative und imperative Elemente mischen, werden aufgrund dieser Unterschiede deduktive Elemente nur in speziellen logischen Programmiersprachen eingesetzt.

Für Leser, die nur an der Programmierung etwa in Java interessiert sind, erscheinen logische Algorithmen daher vielleicht als überflüssiger Ballast – allerdings werden wir sehen, dass die Realisierung des notwendigen Auswertungsalgorithmus eine anspruchsvolle Aufgabe für den Entwerfer von Algorithmen und Datenstrukturen ist.

3.4.1Logik der Fakten und Regeln

Wir beginnen die Diskussion deduktiver Algorithmen mit der Definition logischer Aussagen und Aussageformen. Ein Beispiel für eine natürlichsprachige Aussage ist der Satz Susanne ist Tochter von Petra. Eine Aussageform ist ein Aussage mit Unbestimmten: X ist Tochter von Y. Durch eine Belegung der Unbestimmten kann eine Aussageform in eine Aussage transformiert werden:

Statt natürlichsprachiger Aussagen und Aussageformen verwenden deduktive Algorithmen atomare Formeln:

In unserer bisherigen Terminologie entsprechen atomare Formeln (ungeschachtelten) booleschen Funktionstermen mit Variablen.

Basierend auf diesen Konzepten, können wir nun die Logik der Fakten und Regeln definieren. Wir beginnen mit der Festlegung des Alphabets der verwendeten Symbole:

Das Alphabet bildet also eine Untermenge der Symbole des bekannten Datentyps bool.

Atomare Formeln haben nun die Form P(t₁, …, t_n). Unter Fakten verstehen wir atomare Formeln ohne Unbestimmte. Regeln sind nun wie folgt definiert (α_i ist atomare Formel):

Der Teil vor dem

wird dabei als Prämisse bezeichnet, der andere Teil als Konklusion. Auch leere Prämissen sind dabei möglich (diese entsprechen der Prämisse true).

Das folgende Beispiel verdeutlicht diese Festlegungen. Wir haben zwei Fakten wie folgt notiert:

Passend zu den beiden Fakten können wir eine Regel mit Unbestimmten definieren:

Basierend auf der Bedeutung der Implikation können wir nun die Ableitung neuer Fakten betrachten. Nach folgendem Prinzip können wir dabei vorgehen:

Diese Vorgehensweise setzt die bekannte logische Regel des modus ponens um. Anhand unserer Beispielfakten und -regeln können wir das Verfahren erläutern.

ersetzt jede Unbestimmte in der Regel (3) durch eine Konstante. Die rechte Seite der Regel ergibt nun den neuen Fakt

Nach diesen Festlegungen sind wir nun bereit, deduktive Algorithmen zu definieren.

3.4.2Deduktive Algorithmen

Definition 3.7 Deduktiver Algorithmus

Aus einem deduktiven Algorithmus sind neue Fakten ableitbar. Die Menge der Fakten F(D) enthält alle direkt oder indirekt aus D ableitbaren Fakten.

Ein deduktiver Algorithmus definiert keine direkte Ausgabefunktion wie applikative und imperative Algorithmen – es sei denn, wir betrachten die Faktenmenge F als Ausgabe. Ein konkretes Ergebnis analog zu einer Ausgabe liefert uns erst die Beantwortung von Anfragen. Eine Anfrage γ ist eine Konjunktion von atomaren Formeln mit Unbestimmten.

Eine Antwort auf eine Anfrage ist eine Belegung der Unbestimmten in γ, bei der aus allen α_i Fakten aus F(D) werden. Enthält γ keine Unbestimmten, sind die beiden möglichen Antworten true und false.

Wir werden diese Konzepte nicht weiter formal vertiefen, da deduktive Algorithmen nicht im Fokus dieses Buches liegen. Stattdessen verdeutlichen wir sie an dem Beispiel der Addition zweier Zahlen, die durch die Nachfolgefunktion ausgedrückt werden soll (vergleiche auch Beispiel 3.4 auf Seite 62). Der deduktive Algorithmus lautet:

Ausgehend von der Aussage n + 0 = n (erste Regel) werden mit der zweiten Regel schrittweise die Fakten mit dem zweiten Summanden 1, 2, 3 usw. abgeleitet.

Bei dieser Realisierung der Addition können wir beispielsweise die folgenden Anfragen stellen:

Diese Beispiele zeigen, dass wir mit einem deduktiven Algorithmus eine wesentlich flexiblere Beschreibung einer Berechnungsvorschrift zur Verfügung haben als bei den beiden anderen Berechnungsparadigmen.

Die bisherige Beschreibung gibt uns allerdings kein effizientes Verfahren, eine Anfrage zielgerichtet zu beantworten – wir müssten zuerst alle abgeleiteten Fakten bestimmen, egal welche Anfrage gestellt wurde.

Die Beschreibung eines vollständigen Algorithmus zur effizienten Anfragebearbeitung würde den Rahmen dieses Buches sprengen. Wir werden stattdessen kurz die Idee skizzieren und an Beispielen verdeutlichen, da diese Idee uns später bei der Behandlung von Algorithmenmustern wieder begegnen wird.

Ein informaler, nichtdeterministischer Algorithmus zur Beantwortung einer Anfrage kann wie folgt ablaufen:

Die Abbildung 3–2 zeigt den Ablauf anhand der Anfrage add(3,2,5). Die Auswertung erfolgt in den folgenden Schritten:

Als zweites Beispiel betrachten wir die Anfrage add(3,2,X). Abbildung 3–3 zeigt die Auswertung dieser Anfrage. Im Gegensatz zur Auswertung von add(3,2,5) können wir nicht sofort alle suc-Formeln eliminieren, da wir keine sinnvolle Belegung für suc(z’,X) angeben können. Als Ergebnis bauen wir eine Kette von suc-Formeln auf, die erst am Ende aufgelöst werden kann.

Hier zeigt sich ein Problem unseres Algorithmus: Wir hätten ja auch z′ = 10 und X = 11 setzen können und den gefundenen Fakt aus entfernen können. Man kann sich leicht klar machen, dass wir dann in eine Sackgasse geraten wären: Der entstandene Term add(3,1,10) ist nicht korrekt auflösbar (wir könnten zwar weiter Regel (2) anwenden, würden aber nie Regel (1) anwenden können).

Unser Verfahren ist somit nichtdeterministisch im folgenden Sinne: Wenn der Algorithmus erfolgreich hält, haben wir eine Lösung gefunden. Hält er aber nicht oder mit einem nichtleeren γ, so kann das an einer falschen Entscheidung bei der Abarbeitung liegen.

Abbildung 3–4 zeigt, dass das Verfahren bei mehreren möglichen Lösungen unterschiedliche Lösungspfade wählen kann und somit auch die gefundene Lösung nichtdeterministisch bestimmt wird. In Abbildung 3–4 werden die beiden erfolgreichen Berechnungen für die Anfrage add(X,Y,1) gezeigt.

Wie kann man aber nun die vollständige Antwort einer Anfrage bestimmen? Hierzu müssen alle möglichen Berechnungspfade systematisch ausprobiert werden. Ein derartiges Verfahren wird als Backtracking bezeichnet. In Abschnitt 8.4 werden wir derartige Verfahren intensiv untersuchen, die insbesondere bei Planungs- und Suchaufgaben sinnvoll zum Einsatz kommen können.

Abschließend möchten wir noch einmal betonen, dass wir nur einen sehr vereinfachten Formalismus eingeführt haben. So haben wir keine Negation zugelassen, die einer besonderen Behandlung bedürfte. Auch haben wir die Probleme des Erkennens von Endlosrekursionen und unendlichen Belegungsmengen nicht betrachtet. Die vereinfachte Darstellung sollte jedoch einen Einblick in die Basisideen deduktiver Ansätze geben, die in speziellen Büchern oder Vorlesungen ausführlicher behandelt werden.

3.5Weitere Paradigmen

Bisher hatten wir Algorithmenparadigmen kennen gelernt, die dem klassischen Algorithmenbegriff entsprechen. Die Berechnung wird hierbei in Form von elementaren Berechnungsschritten ausgedrückt, die zu Berechnungen zusammengesetzt werden. Schon das logische Paradigma passte nicht mehr ganz zu dieser Charakterisierung von Algorithmen, da die Berechnungsfolge vom Interpreter und nicht mehr vom Algorithmenentwerfer festgelegt wird und auch von der konkret zu lösenden Aufgabe abhängt.

Einige neuere Ansätze des Problemlösens passen noch weniger zum klassischen Algorithmenbegriff, werden aber trotzdem oft als Algorithmenparadigmen bezeichnet. Eine passendere Bezeichnung wäre hier Programmierparadigmen, da Programme erzeugt werden, ohne dass direkt ein Lösungsalgorithmus angegeben wird. Zu nennen sind hier unter anderem genetische Algorithmen, neuronale Netze, Quanten-Computing und DNA-Computing. Wir werden die ersten beiden genannten Ansätze kurz vorstellen, aber nicht ins Detail gehen.

3.5.1Genetische Algorithmen

Genetische Algorithmen sind, wie auch einige andere der genannten Ansätze, durch Prinzipien der Informationsverarbeitung in der Natur inspiriert. Die DNS der Tier- und Pflanzenwelt kann als Analogon zu einem Programm aufgefasst werden, indem Gene als ein in einem 4-Buchstaben-Alphabet kodiertes Programm interpretiert werden, das den Bauplan etwa eines Tieres (inklusive einiger Aspekte des Verhaltens!) festgelegt. In der Natur gibt es keine Programmierer, die Fortpflanzung mit der Kombination aus männlichem und weiblichem Erbgut zusammen mit Mutationen verändert das Erbgut; die natürliche Auslese führt zur Ausprägung von Eigenschaften und letztendlich zu neuen Arten. Durch Auslese driftet der Gen-Pool langfristig in eine Richtung, die besser an die auslesenden Umweltbedingungen angepasst ist.

Umgesetzt in die Denkweise der Informatik, arbeitet ein genetischer Algorithmus wie folgt:

Genetische Algorithmen sind typischerweise einsetzbar für Optimierungsfragen, in denen eine sehr gute Näherungslösung, aber nicht notwendigerweise die optimale Lösung gesucht wird (wir werden später sehen, dass Problem existieren, für die die optimale Lösung nicht mit vertretbarem Aufwand berechenbar ist).

Um das Prinzip zu verdeutlichen, skizzieren wir als Beispiel eine Lösung des n-Damen-Problems mittels genetischer Algorithmen. Das n-Damen-Problem ist eine Verallgemeinerung des Acht-Damen-Problems auf beliebige Zahlen n: Gesucht sind beim Acht-Damen-Problem alle Konfigurationen von 8 Damen auf einem 8x8-Schachbrett, so dass keine Dame eine andere bedroht. Eine Dame bedroht dabei bekanntlich alle Felder derjenigen Spalte und Zeile, auf der sie steht, sowie zusätzlich alle Felder der durch sie gehenden Diagonalen. Abbildung 3–5 zeigt zwei Lösungen dieses Problems.

Eine direkte algorithmische Lösung dieses Problems behandeln wir später in Abschnitt 8.4.2.

Um das n-Damen-Problem mithilfe eines genetischen Algorithmus zu lösen, müssen wir zunächst eine Kodierung der Lösungskandidaten (Phänotypen) festlegen. Es bietet sich an, hierzu einen Vektor (Chromosom) mit n Elementen (Genen) zu verwenden, der die Positionen der n zu platzierenden Damen angibt. Wir nutzen außerdem aus, dass in jeder Zeile des Schachbretts offenbar genau eine Dame stehen muss, und ordnen daher jedes Element des Vektors einer Zeile des Schachbretts zu. Jedes Vektorelement (Gen) muss dann nur noch die Spaltenposition der Dame in der zugehörigen Zeile angeben. Folglich hat jedes dieser n Gene einen Wert aus der Menge von n möglichen Werten, nämlich den Spaltennummern 1 bis n. Die Vektoren

Eine Anfangspopulation von Kandidatenlösungen wird erzeugt, indem man zufällige Vektoren der Länge n mit Werten aus 1 bis n erzeugt. Zur Bewertung einer Kandidatenlösung zählen wir einfach, wie viele Paare von Damen es gibt, die in dieser Kandidatenlösung in der gleichen Spalte oder Diagonale stehen. Da die Fitness gewöhnlich ein zu maximierender Wert ist, definieren wir die Fitness als die Negation dieser Anzahl. Wir haben mit dieser Bewertung außerdem ein Abbruchkriterium, denn wenn eine Kandidatenlösung eine Bewertung von 0 erhält (keine Paare von Damen in der gleichen Spalte oder Diagonale), so ist das n-Damen-Problem gelöst. Die beiden Lösungen v₁ und v₂ aus Abbildung 3–5 haben die Fitness 0, die Vektoren

Aus einer Generation werden nun Kandidaten als Eltern für die Folgegeneration derart ausgewählt, dass Kandidaten mit hoher Fitness größere Chancen für das Weiterkommen haben, aber der Gen-Pool nicht zu stark verarmt. Zur Auswahl der Kandidatenlösungen als Eltern für die nächste Generation kann man beispielsweise die Turnierauswahl verwenden. D.h., es werden aus der aktuellen Population jeweils (zufällig) k Chromosomen ausgewählt (der Parameter k gibt die Turniergröße an). Das beste dieser Chromosomen (das Chromosom mit der höchsten Fitness) gewinnt das Turnier und gelangt so in die nächste Generation. Die Anzahl Turniere bestimmt die Größe der nächsten Generation.

Nun müssen auf den Elternkandidaten Mutationen und Kreuzungen (Crossover) durchgeführt werden, wobei die Operationen zufallsgesteuert mit einer vorgegebenen Wahrscheinlichkeit auftreten — der Gen-Pool sollte langsam »in die richtige Richtung« driften, aber sich nicht durch zu viele Mutationen chaotisch entwickeln. Zur Veränderung der Kandidatenlösungen benutzen wir einfache Mutations- und Crossover-Operatoren. Die Mutation besteht in der zufälligen Änderung eines Vektoreintrags, was dem Versetzen einer Dame in eine andere Spalte entspricht. Beim Crossover schneiden wir die beiden Elternchromosomen an einer zufällig gewählten Stelle durch und vertauschen die Chromosomenteile auf einer Seite des Schnittpunktes (sogenanntes 1-Punkt-Crossover). Dadurch werden durch die Elternchromosomen dargestellte Teillösungen neu zusammengesetzt.

Der genetische Algorithmus läuft nun wie beschrieben in einer Schleife als Generationenfolge ab. Nach dem Erzeugen der zufälligen Anfangspopulation werden die Chromosomen bewertet. Hat ein Chromosom die Fitness 0, so wird die durch dieses Chromosom beschriebene Lösung ausgegeben und der Algorithmus abgebrochen. Andernfalls werden die Chromosomen für die nächste Generation ausgewählt, mit den genetischen Operatoren verändert und erneut bewertet.

Der Pseudocode zu Algorithmus 3.1 fasst den erläuterten Ablauf noch einmal kompakt zusammen.

Algorithmus 3.1 Grundprinzip genetischer Algorithmen

Initialisiere erste Generation G;

BesteFitness = max { Fitness(x) |x in G };

if BesteFitness = 0 then break;

Bestimme G′ aus G als Eltern der neuen Generation G;

// etwa durch n Turniere aus je k zufällig aus G gewählten x

G = {};

for each x in G′ do

with probability 0.7 do x = mutate(x) od;

with probability 0.2

do wähle y aus G′ aus;

x = crossover(x, y);

od;

G = G union { x };

od;

return Kandidaten x aus G mit Fitness(x) = BesteFitness;

Die einzelnen Schritte müssen jetzt noch verfeinert werden. Näherungslösungen kann man dadurch erhalten, indem die BesteFitness nicht auf Gleichheit mit 0, sondern auf das Überschreiten einer Schwelle getestet wird. Das Sprachkonstrukt with probability soll einen mit einer vorgegebenen Wahrscheinlichkeit zu betretenden Programmzweig kennzeichnen und kann durch einen Vergleich mit einer generierten Zufallszahl ausprogrammiert werden.

Für Einzelheiten zu genetischen Algorithmen verweisen wir auf weiterführende Lehrbücher, etwa [Goo98, Mic98].

3.5.2Neuronale Netze

Während sich genetische Algorithmen an den Prinzipien der Vererbung orientieren, bilden neuronale Netze (kurz NN) das Analogon zur Informationsverarbeitung in Nervenzellen und damit insbesondere in Gehirnen. Neuronen eines neuronalen Netzes entsprechen dabei den Nervenzellen.

Ein neuronales Netz ist aus vielen Neuronen zusammengesetzt, die miteinander (durch Nervenbahnen) verbunden sind:

Ein NN ist ein massiv paralleles System aus sehr einfachen Prozessoren, das Eingangssignale in Ausgangssignale (eventuell nach einer Einschwingphase bei Rückkopplungen) umsetzt. Typische Anwendungen von NN sind daher die Signalverarbeitung bei Sensordaten oder allgemeine Mustererkennungsprobleme.

Das Besondere an NN ist die Möglichkeit, Muster in den Eingangssignalen zu lernen. Hierzu wird etwa beim überwachten Lernen ein Trainingsdatensatz mit den gewünschten Ausgangsdaten erweitert. Beim Lernen können die Gewichte angepasst werden, Schwellwerte und Output-Funktionen geändert oder sogar die Topologie verändert werden. Die Auswahl (und Größe) des Trainingsdatensatzes hat neben der Topologie großen Einfluss auf das gelernte Verhalten. So kann es zum sogenannten Overfitting kommen, indem ein Netz genau den Trainingsdatensatz lernt und nicht das durch diesen repräsentierte abstrakte Muster.

Das einfachste neuronale Netz besteht nur aus einem Neuron. Als Beispiel wollen wir an dieser Stelle das Perzeptron betrachten, das ein einfaches lineares Neuronenmodell, ergänzt um eine Schwellwertfunktion, darstellt. Ein solches Perzeptron summiert die Eingabewerte an den Eingängen x₁, …, x_n auf und entscheidet anhand des Vergleichs dieser Summe mit einem Schwellwert, ob es »feuert«, d.h. den Wert 1 ausgibt, oder nicht und somit den Wert 0 liefert. Die Eingabewerte werden außerdem noch mit Gewichten w₁, …, w_n versehen. Aufgrund der Verwendung eines Schwellwertes θ werden Perzeptronen auch als Schwellwertneuronen bezeichnet (Abbildung 3–6).

Mit einem derartigen einfachen Perzeptron kann man beispielsweise die booleschen Operatoren UND und ODER berechnen, wobei die Wahrheitswerte an die Eingänge x₁ und x₂ gelegt werden und y entsprechend 0 für »falsch« bzw. 1 für »wahr« liefert. Für UND können dazu die Gewichte wie folgt belegt werden: w₁ = 2, w₂ = 2 sowie θ = 3. Bei einer Eingabe x₁ = 1, x₂ = 1 ergibt sich nach der obigen Vorschrift

, was für y den Wert 1 und somit »wahr« liefert. Eine Kombination von 0 und 1 als Eingabewerte würde entsprechend 2< 3 und damit »falsch« liefern. Ein Perzeptron für die Berechnung von ODER funktioniert in der gleichen Weise, allerdings müssen hier Gewichte und Schwellwert beispielsweise wie folgt gesetzt werden: w₁ = 2, w₂ = 2 sowie θ = 1. Für die Eingabe x₁ = 1, x₂ = 0 ergibt sich hierbei

(»wahr«); bei x₁ = 0, x₂ = 0 ist das Ergebnis wegen 0 < 1 wie erwartet »falsch«.

Das Lernen (oder besser Trainieren) erfolgt für ein solches einfaches Perzeptron durch Anpassung der Gewichte. Dazu werden zunächst die Gewichte w_i mit Zufallswerten initialisiert und anschließend Trainingsdatensätze (Eingabedaten mit bekannten Ausgabewerten) an die Eingänge x₁, …, x_n gelegt. Durch Vergleich des vom Netz berechneten Wertes y mit dem korrekten (erwarteten) Wert t aus der Trainingsmenge kann die Änderung der Gewichte Δw_i ermittelt werden:

Der Parameter η wird als Lernrate bezeichnet und muss hinreichend klein gewählt werden (z.B. 0.1), um im Fehlergebirge ein Minimum zu finden. Mit diesem Δw_i lassen sich schließlich die Gewichte wie folgt anpassen, bis die Trainingsbeispiele korrekt klassifiziert werden:

Wie leicht einzusehen ist, genügt für komplexere Aufgabenstellungen ein einzelnes Neuron natürlich nicht mehr. Selbst bei vermeintlich einfachen Problemen wie der Berechnung der booleschen Operation XOR (exklusives ODER: das Ergebnis wird »wahr«, wenn nur eine der beiden Eingaben »wahr« ist) versagt es. Der Grund liegt darin, dass die Perzeptron-Funktion (die Kombination aus Aktivierungs- und Ausgabefunktion) eine einfache Funktion ist, durch welche die n-dimensionale Eingabemenge lediglich in zwei Teile zerlegt wird:

Das Perzeptron feuert nur für Werte aus dem einen Teil. Eine Menge, die durch die Funktion (genauer die (n − 1)-dimensionale Hyperebene

derart zerlegt werden kann, wird als linear separabel bezeichnet. Für die XOR-Operation existiert eine solche Hyperebene bzw. im zweidimensionalen Fall eine solche Gerade nicht (Abbildung 3–7). Lösen kann man dieses Problem durch das Einfügen zusätzlicher Schichten von Neuronen, wodurch nun tatsächlich neuronale Netze aus mehreren Neuronen entstehen. Ein derartiges Netz, das die XOR-Operation berechnet, ist in Abbildung 3–8 mit seinen Gewichten und Schwellwerten angegeben. Für solche Netze sind jedoch auch komplexere Lernverfahren notwendig, die die Fehlersignale von der Ausgabe in geeigneter Weise in die inneren Schichten weiterleiten.

Der praktische Einsatz neuronaler Netze war über viele Jahre nur mäßig erfolgreich. Erst durch Entwicklungen der letzten 10-15 Jahre konnten speziell mehrschichtige Netze trainiert werden, die zu großen Fortschritten im Bereich des maschinellen Lernens geführt haben. Eine besondere Rolle spielt dabei das sogenannte Deep Learning mittels »tiefer« Netze. Derartige Netze zeichnen sich durch mehr als eine Zwischenschicht (»Hidden Layer«) aus. Diese Zwischenschichten können neue Abstraktionen der Eingabedaten (»Features«) lernen und repräsentieren – daher wird diese Form des Lernens auch als »Representational Learning« bezeichnet.

Für tiefe Netze existieren verschiedene Architekturen oder auch Netzwerktopologien. Die bekanntesten sind Convolutional Neural Networks (CNN – »faltende« NN) und Recurrent Neural Networks (RNN – rekurrente NN). CNN sind speziell für räumlich angeordnete Daten in Form von 2D- oder 3D-Matrizen wie Bilder oder Videos geeignet. Hierbei werden kleinere Bereiche eines Bildes über sogenannte Kernel (Filter) in mehreren als Convolutional Layer bezeichneten Schichten verarbeitet und im nachfolgenden Pooling Layer komprimiert. RNN sind dagegen rückgekoppelte Netze, bei denen die Ausgabe einer Schicht wieder als Eingabe der gleichen oder auch vorhergehender Schichten genutzt werden kann. Auf diese Weise können sequenzielle bzw. zeitlich kodierte Daten wie Sprache oder Text verarbeitet werden.

Es gibt viele weitere Varianten neuronaler Netze und der mit ihnen verbundenen Lernverfahren, deren Diskussion den Rahmen dieses Buches sprengen würde. Auch hier verweisen wir daher wieder auf weiterführende klassische Literatur [Zel94, Bra95, BKK03] sowie speziell zum Deep Learning [GBC17].

3.6Umsetzung in Java

In den vorangegangenen Kapiteln haben wir im Wesentlichen abstrakte Konzepte zur Beschreibung von Algorithmen verwendet. Nun wollen wir kennen lernen, wie Algorithmen mithilfe der Programmiersprache Java implementiert werden können. Hierzu werden wir imperative Sprachkonstrukte sowie die Definition und den Aufruf von Methoden (Funktionen) vorstellen.

3.6.1Ausdrücke und Anweisungen

Bereits bei der informalen Einführung des Algorithmenbegriffs haben wir Anweisungen als die elementaren Arbeitsschritte eines Algorithmus kennen gelernt. Neben Operationen auf Datentypen zählen hierzu insbesondere auch Kontrollstrukturen wie Schleifen oder Verzweigungen. Die Existenz solcher imperativen Sprachkonstrukte ist daher auch charakteristisch für die große Klasse von imperativen Programmiersprachen, zu denen auch Java gehört.

Java bietet eine ganze Reihe von verschiedenen Anweisungsformen. Hierzu gehören u.a.:

Anweisungen werden in Java grundsätzlich durch ein »;«-Zeichen abgeschlossen. Die einfachste Form einer Anweisung – die leere Anweisung – besteht daher nur aus einem Semikolon.

Ausdrücke

Eine weitere Form von Anweisungen wird unter Verwendung von Ausdrücken gebildet. Ausdrücke oder Terme sind dabei:

Durch das Anhängen eines »;«-Zeichens wird aus einem Ausdruck eine Anweisung formuliert, wie dies in den folgenden Beispielen illustriert ist:

Blöcke

Eine Folge von Anweisungen kann zu einem Block zusammengefasst werden, indem sie durch geschweifte Klammern eingeschlossen wird:

Blöcke sind insbesondere dort wichtig, wo aus syntaktischen Gründen nur eine einzelne Anweisung stehen darf, etwa im Zusammenhang mit Kontrollstrukturen. Da ein Block wie eine einzelne Anweisung behandelt wird, lassen sich auf diese Weise auch mehrere Anweisungen einsetzen.

Ein Block schränkt auch die Sichtbarkeit von Variablen bzw. deren Gültigkeitsbereich ein. Eine Variable ist nur innerhalb des Blockes sichtbar – d.h., auf sie kann zugegriffen werden –, in dem sie deklariert wurde (siehe Abbildung 3–9).

Die für die Formulierung von imperativen Algorithmen notwendigen Kontrollstrukturen wurden bereits in Abschnitt 2.1.3 eingeführt, so dass wir uns im Folgenden auf die Darstellung der syntaktischen Besonderheiten in Java beschränken können. Grundsätzlich lassen sich folgende Kontrollstrukturen unterscheiden:

Bedingte Anweisungen

Bedingungen werden mithilfe der if-Anweisung formuliert, die folgende Syntax aufweist:

Die Anweisung anweisung₁, die eine einzelne Anweisung oder ein Block sein kann, wird nur dann ausgeführt, wenn die Bedingung bedingung erfüllt ist, d.h. der Ausdruck den Wert true besitzt. Optional kann noch ein else-Zweig hinzugefügt werden, der nur dann zur Ausführung kommt, wenn die Bedingung nicht erfüllt ist:

Wichtig ist, dass der Bedingungsausdruck in Klammern angegeben wird und einen Wert vom Typ boolean liefert, wie die beiden folgenden Beispiele verdeutlichen:

In diesem Zusammenhang sei auch auf den ?:-Operator von Java hingewiesen, mit dem ebenfalls bedingte Ausdrücke formuliert werden können. Allerdings handelt es sich nicht um eine Anweisung, sondern um einen Operator:

Der Wert dieses Ausdrucks nimmt den Wert von ausdruck₁ an, wenn bedingung wahr ist, andernfalls den Wert von ausdruck₂. Auf diese Weise lässt sich eine Anweisung wie

Soll nicht nur in Abhängigkeit von einer Ja-Nein-Entscheidung verzweigt werden, so muss dies über eine Folge von if-else-Anweisungen implementiert werden. Wenn etwa im folgenden Beispiel die Variable i die ganzzahligen Werte 0 bis 3 annehmen kann und zu jedem Wert eine entsprechende Textausgabe erfolgen soll, lässt sich dies wie folgt formulieren:

Eine Alternative bietet die Auswahl- oder switch-Anweisung, die folgende Syntax besitzt:

switch (ausdruck) {

case auswahlwert₁:

// Anweisungen für Fall #1

[ break; ]

case auswahlwert₂:

// Anweisungen für Fall #2

[ break; ]

…

case auswahlwert_n:

// Anweisungen für Fall #n

[ break; ]

default:

// Anweisungen für alle anderen Fälle

[ break; ]

}

Bei der Auswahlanweisung handelt es sich um eine verallgemeinerte Form der Fallunterscheidung. Für jeden Wert des Ausdrucks ausdruck kann eine eigene Anweisungsfolge angegeben werden. Der Ausdruck selbst muss einen ganzzahligen Wert vom Typ char, byte, short oder int liefern, die Auswahlwerte müssen Literale (Konstanten) sein. Seit der Version 7.0 sind aber auch Zeichenkettenliterale zugelassen. Zu dem berechneten Wert des Ausdrucks wird – sofern vorhanden – die Anweisungsfolge des korrespondierenden case-Zweigs ausgeführt. Existiert kein entsprechender Zweig, so wird zum optionalen default-Abschnitt verzweigt. Zu beachten ist jedoch, dass nach der Ausführung der letzten Anweisung eines case-Zweigs nicht etwa zum Ende der switch-Anweisung gesprungen wird, sondern die nächstfolgende Anweisung ausgeführt wird, auch wenn diese zum nächsten case-Zweig gehört. Dieser Kontrollfluss kann jedoch durch die optionale break-Anweisung unterbrochen werden, so dass die Ausführung nach der switch-Anweisung fortgesetzt wird. Auch wenn diese Regelung auf den ersten Blick umständlich erscheint, ist dies doch durchaus sinnvoll. Es lassen sich auf diese Weise mehrere Auswahlwerte kombinieren, wie das folgende Beispiel demonstriert:

int i = ...;

switch (i) {

case 0:

System.out.println("Null");

break;

case 1:

case 2:

System.out.println("Eins oder Zwei");

break;

default:

System.out.println("Mehr als Zwei");

break;

}

Seit Version 14 gibt es switch auch als Ausdruck, der einen Wert liefert und damit beispielsweise auf der rechten Seite einer Zuweisung eingesetzt werden kann. Dazu muss hinter den case-Klauseln entweder ein Wert mit yield zurückgegeben werden oder es ist eine Pfeilnotation -> zu verwenden:

Pfeilnotation und yield dürfen allerdings nicht in einem switch-Ausdruck gemischt werden.

Schleifen

Schleifen als eine weitere wichtige Kontrollstruktur sind in drei Ausprägungen vorhanden:

Solange der Ausdruck bedingung den Wert true liefert, wird die Anweisung bzw. der Block anweisung ausgeführt. Dies bedeutet, dass die Bedingung vor jedem Durchlauf der Schleife überprüft wird, was wiederum zur Folge haben kann, dass die Anweisung im Schleifenrumpf nicht ausgeführt wird, wenn die Bedingung schon vor dem ersten Durchlauf nicht erfüllt ist. Ein einfaches Beispiel für die Anwendung der while-Schleife ist eine Zählschleife, die die Werte von 5 bis 1 ausgibt:

In der Bedingung wird überprüft, ob der Wert von i noch größer 0 ist. In diesem Fall wird der Wert ausgegeben und anschließend um eins verringert.

Allerdings sollte hier innerhalb der Schleife eine geeignete Abbruchbedingung eingeführt werden. Das Verlassen der Schleife ist dann über die noch vorzustellenden Sprunganweisungen möglich.

Die Notation der do-while-Schleife spiegelt den Unterschied zur while-Schleife wider:

Die Anweisung bzw. der Block anweisung werden ausgeführt, solange der Ausdruck bedingung den Wert true liefert. Die Überprüfung der Bedingung erfolgt hier nach jedem Durchlauf, d.h., der Schleifenrumpf wird mindestens einmal ausgeführt. Das obige Beispiel der Zählschleife kann mittels der do-while-Schleife in folgender Weise formuliert werden:

Zusätzlich zu den bedingten Schleifen gibt es mit der for-Schleife noch eine Variante, die explizit mit Zählvariablen arbeitet. Die Syntax lautet hier:

Der Schleifenrumpf besteht wiederum aus einer Anweisung bzw. einem Block. Der »Schleifenkopf« umfasst drei Ausdrücke mit folgender Bedeutung:

An diesem Schema sollte deutlich werden, dass es sich bei der for-Schleife eigentlich nur um eine syntaktische Variante der while-Schleife handelt, da auch hier die Bedingung vor jedem Durchlauf geprüft wird. Allerdings ist mit der for-Schleife eine kompaktere Schreibweise möglich. So kann die obige Zählschleife wie folgt formuliert werden:

Die Ausdrücke im Schleifenkopf können auch ganz oder teilweise weggelassen werden, wobei beim Fehlen des Bedingungsausdrucks der Wert true eingesetzt wird. Die folgende Schleife ist daher eine Endlosschleife:

Mit Version J2SE 5.0 wurde in Java noch eine weitere Variante der for-Schleife eingeführt, die speziell zum Durchlaufen von Kollektionen (siehe auch Kapitel 13) und Feldern gedacht ist. Die Syntax lautet:

wobei ausdruck hier ein Feld oder ein Objekt mit einer speziellen Schnittstelle sein muss. Die einzelnen Elemente dieses Feldes werden nacheinander der in parameter angegebenen Variablen zugewiesen. So kann z.B. in folgender Weise über alle Elemente eines Feldes iteriert werden:

Mit einer Schleife können wir auch auf einfache Weise für unser in Abschnitt 2.5.2 eingeführtes Tic-Tac-Toe-Spiel prüfen, ob ein Spieler gewonnen hat, d.h., ob in einer Zeile, Spalte oder Diagonale drei Spielsteine des gleichen Spielers vorhanden sind. Betrachten wir hierzu den Zeilentest für einen gegebenen Spieler:

char spieler = ’o’; // Welcher Spieler?

// alle Zeilen durchlaufen

for (int zeile = 0; zeile < 3; zeile++) {

boolean sieg = true;

// in der aktuellen Zeile alle Spalten durchlaufen

for (int spalte = 0; spalte < 3; spalte++) {

// … und prüfen, ob dort ein Stein des Spielers liegt

sieg = sieg && (spielfeld[zeile][spalte] == spieler);

}

if (sieg)

System.out.println(spieler + " hat gewonnen!");

}

Für den Test auf drei gleiche Spielsteine nutzen wir den logischen UND-Operator, indem die Variable sieg mit dem Ergebnis des Vergleichs über UND verknüpft wird. Nur wenn alle drei Vergleiche in einer Zeile den Wert true liefern, hat die Variable am Ende des Durchlaufs der äußeren Schleife den Wert true. Für einen vollständigen Test muss der obige Ablauf natürlich auch noch spalten- und diagonalweise durchgeführt werden.

Die dritte Form von Kontrollstrukturen, die wir in diesem Abschnitt vorstellen wollen, sind die Sprunganweisungen. Diese Anweisungen ermöglichen die Unterbrechung des Kontrollflusses eines Programms und die Fortsetzung an einer anderen, definierten Stelle.

Die break-Anweisung haben wir bereits im Zusammenhang mit der switch-Anweisung kennen gelernt. Mit dieser Anweisung wird die Ausführung des aktuellen for-, while-, do- bzw. switch-Blockes abgebrochen und nach diesem Block fortgesetzt, wie das folgende Beispiel verdeutlichen soll:

Auch die continue-Anweisung unterbricht den Kontrollfluss der aktuellen Schleife. Im Gegensatz zu break wird jedoch die Schleife mit der nächsten Iteration fortgesetzt, d.h., es wird zurück zum Anfang der Blockes gesprungen und – bei bedingten Schleifen – zuvor die Bedingung überprüft. So werden im folgenden Beispiel nur die ungeraden Werte der Zählvariablen ausgegeben, da für gerade Werte der aktuelle Durchlauf abgebrochen wird.

Schließlich erlaubt die return-Anweisung das Beenden der Ausführung einer Methode und den Rücksprung zur Aufrufstelle. Optional kann hier noch ein Wert zurückgegeben werden, der das Ergebnis einer Berechnung darstellt. Die return-Anweisung ist somit insbesondere für Methoden von Bedeutung, die einen Wert berechnen (Funktionen). Die Syntax dieser Anweisung ist wie folgt:

Der optionale Ausdruck ausdruck wird ausgewertet und der Ergebniswert an den Aufrufer zurückgegeben. Ein Beispiel ist die Methode plus, die die Summe zweier Zahlen berechnet.

Weitere Beispiele zur Anwendung der return-Anweisung werden wir in den folgenden Abschnitten vorstellen.

3.6.2Methoden

Funktionen und Prozeduren werden in Java in Form von Methoden implementiert. Den Begriff der Methode haben wir in Abschnitt 1.4 bereits als eine logische Einheit einer oder mehrerer Anweisungen eingeführt. Methoden bilden somit ein wesentliches Strukturierungsmittel für Programme. Da Java eine streng objektorientierte Sprache ist, müssen Methoden immer im Kontext einer Klasse definiert werden. Sie können mit Parametern aufgerufen werden und Ergebnisse zurückliefern. Typ und Reihenfolge der Parameter sowie der Ergebnistyp müssen im Rahmen der Methodendefinition festgelegt werden. Die Notation einer solchen Definition für eine Methode name ist im Wesentlichen wie folgt:

Die Sichtbarkeit legt fest, ob die Methode außerhalb der Klasse aufgerufen werden kann. Hierfür stehen die folgenden Schlüsselwörter, die in gleicher Weise für Attribute anwendbar sind:

Wir werden später noch auf die Konsequenzen der Sichtbarkeit im Zusammenhang mit Vererbung zurückkommen. Zunächst genügt es, dass wir zwischen öffentlichen Methoden, d.h. Methoden, die allgemein nutzbar sind, und privaten Methoden, die nur innerhalb der Klasse als Hilfsmethoden genutzt werden sollen, unterscheiden.

Das Schlüsselwort static gibt an, dass es sich bei der Methode um eine Klassenmethode handelt, die ohne ein existierendes Objekt aufgerufen werden kann. Für die nächsten Beispiele, in denen wir die objektorientierten Eigenschaften von Java noch nicht nutzen, werden wir also im Wesentlichen mit Klassenmethoden arbeiten.

Die Angabe datentyp definiert den Ergebnistyp der Methode. Hier kann jeder Java-Datentyp (primitiver oder Referenzdatentyp) eingesetzt werden. Wird durch die Methode kein Ergebnis zurückgegeben, so ist der Pseudotyp void zu verwenden, der für »keine Rückgabe« steht.

Die Parameterliste besteht aus einer Folge von Parameterdeklarationen, die durch Komma getrennt sind und jeweils Datentyp und Bezeichner umfassen. Der Bezeichner ist dabei nur innerhalb der Methode gültig und hat keinen Bezug zum Aufrufer. Die Zuordnung der Parameter beim Aufruf erfolgt ausschließlich über die Reihenfolge.

Ein erstes Beispiel für die Definition einer Methode haben wir bereits in Programm 1.1 angegeben. Die dort definierte Methode main ist eine Klassenmethode, die ein Feld von Strings als Parameter erwartet und kein Ergebnis liefert.

Ein weiteres Beispiel ist eine Methode zur Berechnung der Fakultät einer Zahl. Der imperative Algorithmus wurde bereits in Beispiel 3.19 vorgestellt, die Java-Implementierung ist in Programm 3.1 angegeben.

Programm 3.1 Imperative Berechnung der Fakultät

import algoj.IOUtils;

public class FacImperative {

public static int factorial(int x) {

int y = 1;

while (x > 1) {

y = y * x;

x −−;

}

return y;

}

public static void main(String[ ] args) {

int z;

System.out.print("Zahl: ");

z = IOUtils.readInt();

System.out.println("Fakultät(" + z + ") = " +

factorial(z));

}

Zunächst wird eine Klasse FacImperative definiert. Die eigentliche Fakultätsberechnung erfolgt in der Klassenmethode factorial. Diese Methode erwartet die Zahl, von der die Fakultät zu berechnen ist, als Parameter und gibt das berechnete Ergebnis zurück. Neben dem Parameter x wird eine weitere Variable y benötigt, zu der in jedem Schritt der aktuelle Wert von x multipliziert wird und deren Wert am Ende als Ergebnis zurückgeliefert wird. Die Methode factorial wird daher mit einem Parameter vom Typ int sowie dem Ergebnistyp int definiert.

Diese Methode kann nun genutzt werden, um die Fakultät einer Zahl zu ermitteln. Da das Programm interaktiv sein soll, muss im ersten Schritt – nach einer Eingabeaufforderung – die Zahl vom Benutzer eingelesen und in der Variablen z abgelegt werden. Da dieses Einlesen in Java etwas aufwendiger ist, verwenden wir die Hilfsmethode readInt aus der Klasse IOUtils, die eine Zahl über die Tastatur einliest und als Ergebnis zurückgibt. Der Quelltext dieser Klasse ist im Anhang A angegeben. Damit diese Klasse auch im Java-Programm verfügbar ist, muss sie zuvor über die Anweisung

am Anfang der Klassendatei FacImperative.java (wie in Programm 3.1 dargestellt) eingebunden werden.

Eine Methode wird in Java einfach durch Angabe ihres Namens und – in Klammern – der Parameterwerte aufgerufen. Sowohl die Parameterangaben als auch der Aufruf selbst sind dabei Ausdrücke. Dies bedeutet, dass die zu übergebenden Werte zuvor berechnet werden können und dass auch ein Methodenaufruf in einem Ausdruck eingesetzt werden kann. So wird beispielsweise in Programm 3.1 die Methode factorial als Teilausdruck des Parameters für die Methode println aufgerufen. Die Auswertung der Ausdrücke erfolgt dabei von innen nach außen: Nehmen wir z.B. den Wert z = 3 an, dann wird zuerst der Methodenaufruf factorial (3) ausgeführt und das Ergebnis 6 in den Ausdruck "Fakultät(" + 3 + ") = " + 6 eingesetzt. Da es sich bei dem ersten Term "Fakultät (" um eine Zeichenkette handelt, wird der +-Operator als Konkatenation von Zeichenketten interpretiert und die resultierende Zeichenkette an die Methode println übergeben.

Das obige Beispiel demonstriert eigentlich nur einen Spezialfall des Methodenaufrufs, da hier eine statische Methode aus der gleichen Klasse aufgerufen wird. Wird dagegen eine Methode genutzt, die zu einer anderen Klasse gehört, so muss sie durch Voranstellen des Namens und gegebenenfalls des Paketes – getrennt durch ein ».« – qualifiziert werden. Für die Methode factorial bedeutet dies zum Beispiel, dass bei der Verwendung in einer anderen Klasse der Aufruf wie folgt notiert werden muss:

Der Aufruf der Methode readInt der Klasse IOUtils ist ein weiteres Beispiel. Bei den Ausgabemethoden print bzw. println handelt es sich dagegen nicht um Klassenmethoden, so dass hier der Methodenaufruf durch das Objekt (bzw. genauer die Objektreferenz) qualifiziert wird. In diesem Fall bezeichnet die Variable out ein konkretes Objekt, das die Ausgabe repräsentiert. Auf Objekte werden wir aber noch im Kapitel 12 zurückkommen.

Bei der Übergabe von Parametern an Methoden ist die unterschiedliche Behandlung von primitiven Datentypen und Referenzdatentypen zu beachten. Parameter von primitiven Datentypen werden immer kopiert, d.h., es wird in der Methode für den Parameter ein neuer Speicherbereich mit der Kopie des Wertes angelegt. Man bezeichnet dies auch als call by value. Im folgenden Beispiel ist die Konsequenz dieses Prinzips demonstriert: Die Methode inkrement1 soll eigentlich den Wert des Parameters p um eins erhöhen. Da aber beim Aufruf von inkrement1 eine Kopie des Wertes erzeugt wird, wird der Inhalt der Variablen x nicht erhöht. Der Wert dieser Variablen ist daher auch nach dem Aufruf von inkrement1 unverändert:

Parameter von Referenzdatentypen werden dagegen immer als Referenz (call by reference) übergeben. Dies bedeutet, dass die Parametervariable in der Methode auf den gleichen Speicherbereich wie die beim Aufruf übergebene Variable verweist. Auf diese Weise kann der Parameter der Methode auch für den Aufrufer sichtbar modifiziert werden, wie dies im nächsten Beispiel gezeigt wird. Hier wird als Referenzdatentyp ein int-Feld verwendet, dessen erstes Element inkrementiert wird. Nach dem Aufruf von inkrement2 hat dann auch das Element x[0] den Wert 5:

Seit der Version J2SE 5.0 können Methoden auch variable Parameterlisten besitzen, d.h., dass sowohl die Anzahl der Parameter als auch deren Typ beim Aufruf einer Methode variieren. Hierzu muss der Basistyp aller Parameter angegeben werden, gefolgt von … und einem Parameternamen. Innerhalb der Methode kann die Parameterliste dann als Feld verarbeitet werden. Das folgende Beispiel illustriert dies anhand einer einfachen Methode zur Ausgabe:

Diese Methode kann nun mit einer unterschiedlichen Anzahl von Parametern (in diesem Fall vom Typ String) aufgerufen werden:

Wird als Parametertyp java.lang.Object verwendet, kann im Prinzip jedes Objekt als Parameter übergeben werden. Dies erfordert natürlich innerhalb der Methode eine sorgfältige Typprüfung. Demzufolge sollten variable Parameterlisten nur dort eingesetzt werden, wo die Flexiblität wirklich benötigt wird. Ein Beispiel hierfür ist die Methode printf der PrintStream-Klasse(n), von denen u.a. System.out eine Instanz ist. Mit dieser Methode ist eine formatierte Ausgabe möglich, wobei neben einem Formatstring, der angibt, wie die Ausgabe erfolgen soll, eine variable Liste von auszugebenden Objekten als Parameter verwendet wird:

Alle anderen Zeichen im Formatstring, die nicht durch ein vorangestelltes % gekennzeichnet sind, werden direkt ausgegeben. Dies schließt auch Tabulatoren (\t) und Zeilenumbrüche (\n) ein. Da das Prozentzeichen als Kennzeichnung für einen Formatstring verwendet wird, muss es doppelt angegeben werden, um es in die Ausgabe zu übernehmen. Im folgenden Beispiel wird dies angewendet:

In diesem Beispiel wurde auf den Positionsparameter verzichtet, da die Parameter in der Reihenfolge ihres Auftretens ausgegeben wurden. Es lässt sich aber auch eine andere Reihenfolge erzwingen:

Mit diesen Beispielen wollen wir zunächst die Einführung der Java-Sprachkonstrukte abschließen. Es sei noch einmal betont, dass wir bisher im Wesentlichen nur eine imperative bzw. prozedurale Sichtweise verfolgt haben, die aber für das Verständnis der folgenden Kapitel sowie die praktische Umsetzung der darin behandelten Algorithmen ausreichend ist. Auf fortgeschrittene Konzepte der Objektorientierung, mit denen eigentlich erst die Möglichkeiten von Java richtig erschlossen werden können, werden wir im Teil III gemeinsam mit den Datenstrukturen eingehen.

3.6.3Applikative Algorithmen und Rekursion

Den Begriff der Rekursion haben wir in den Abschnitten 2.1.5 und 3.2 bereits als ein wichtiges Konzept der Informatik hervorgehoben, das als allgemeines Prinzip insbesondere auch für applikative Algorithmen von großer Bedeutung ist. Es erscheint daher sinnvoll, die Implementierung rekursiver Algorithmen in Java noch anhand einiger ausgewählter Programme zu verdeutlichen.

Als erstes Beispiel wollen wir wieder die Berechnung der Fakultät einer Zahl betrachten, allerdings diesmal mit dem rekursiven Algorithmus aus Beispiel 3.6 auf Seite 63. Das Grundgerüst des Programms entspricht dem der Klasse FacImperative (Programm 3.1): Wir benötigen eine Methode factorial, die als Ergebnis die Fakultät der Zahl liefert, die als Parameter übergeben wurde. Die main-Methode bildet wieder den Testrahmen, in dem eine Zahl vom Benutzer abgefragt und das berechnete Ergebnis ausgegeben wird.

Programm 3.2 Rekursive Berechnung der Fakultät

import algoj.IOUtils;

public class FacRecursive {

public static int factorial(int x) {

if (x < = 1)

return 1;

else

return x * factorial(x − 1);

}

public static void main(String[ ] args) {

int z;

System.out.print("Zahl: ");

z = IOUtils.readInt();

System.out.println("Fakultät(" + z + ") = " +

factorial(z));

}

Die Methode factorial in Programm 3.2 ist eine direkte Umsetzung des rekursiven Algorithmus. Für den Fall, dass x ≤ 1 gilt, liefert diese Methode einfach den Wert 1. Damit werden die Fälle 0! = 1 und 1! = 1 abgedeckt. In allen anderen Fällen kommt die Vorschrift fac(x) = x · fac (x − 1) zur Anwendung, d.h., die Methode factorial wird erneut aufgerufen, wobei als Parameter der um eins verringerte Wert eingesetzt wird. Das Ergebnis dieses Aufrufs, der unter Umständen weitere Aufrufe der Methode impliziert, wird dann mit dem aktuellen Wert von x multipliziert. Dieses Produkt wird schließlich als Fakultät von x zurückgegeben.

Die Arbeitsweise bzw. die Ablaufstruktur dieses Programms lässt sich einfach verfolgen, wenn in die Methode fakultaet zu Beginn die Ausgabe des aktuellen Parameterwertes aufgenommen wird:

Bei der Abarbeitung wird dann sichtbar, dass sich die Methode factorial für jeden Wert zwischen x und 1 selbst aufruft.

Im zweiten Beispiel wollen wir eine andere Problemklasse betrachten, die aber das Prinzip der Rekursion in grafisch ansprechender Form verdeutlicht: rekursive oder selbstähnliche geometrische Objekte. Hierbei handelt es sich um Gebilde wie z.B. Kurven einer unendlichen Länge oder Mengen von Quadraten, die durch schrittweises Verfeinern nach einem regelmäßigen Muster entstehen. Bekannte Vertreter sind u.a. die Hilbert- und Sierpinski-Kurven, die Schneeflockenkurve sowie der Pythagoras-Baum, der hier behandelt werden soll.

Die Grundidee des Pythagoras-Baumes (Abbildung 3–10) besteht darin, dass ein Quadrat, das durch eine Grundlinie festgelegt ist, berechnet und gezeichnet wird. Solange die Kantenlänge nicht zu klein ist, werden rekursiv weiter kleinere Teilbäume (in der Abbildung gestrichelt gezeichnet) an den Schenkeln eines Dreiecks auf dem Quadrat gezeichnet. Der Winkel ø ist dabei ein Parameter, der die Gestalt des Baumes beeinflusst. Für verwertbare Grafiken sollte dieser Winkel im Bereich von 20° … 48° liegen.

Die Implementierung des Pythagoras-Baumes gibt uns die Gelegenheit, auf einige Aspekte der Programmierung von Grafikausgabe einzugehen, ohne die Vorstellung der objektorientierten Konzepte vorwegnehmen zu müssen.

Wir nutzen dazu die GUI-Bibliothek Swing, die Klassen für die Programmierung grafischer Benutzerschnittstellen bereitstellt. Für unser Beispiel genügt die Klasse javax.swing.JFrame, die ein Fenster auf dem Bildschirm repräsentiert. Diese Klasse definiert einige Methoden, die in einer Subklasse überschrieben, d.h. neu implementiert werden können. In unserem Fall ist nur die Methode paint von Bedeutung, die aufgerufen wird, wenn das Fenster dargestellt werden soll. Der Parameter dieser Methode ist ein Objekt der Klasse java.awt.Graphics, die u.a. Methoden zum Zeichnen von einfachen geometrischen Objekten anbietet.

Mit diesem Wissen kann nun der Pythagoras-Baum in Java implementiert werden. Die Klasse wird als Subklasse von JFrame vereinbart, indem nach dem Klassenbezeichner das Schlüsselwort extends gefolgt vom Bezeichner der Superklasse angegeben wird. Als Attribut dieser Klasse ist noch tanphi vereinbart, das den Wert tan ? aufnimmt, der für die Winkelberechnung benötigt wird. In der paint-Methode wird zunächst die Zeichenfläche durch Aufruf der Methode clearRect gelöscht, wobei als Größe eine Fläche von 500 × 500 Bildpunkten fest eingestellt ist. Im Anschluss daran wird die Methode paintTree mit den Koordinaten der Grundlinie des ersten Quadrats aufgerufen (Programm 3.3).

Programm 3.3 Programm zum Darstellen des Pythagoras-Baumes

import java.awt.*;

import javax.swing.JFrame;

class PythagorasTree extends JFrame {

// phi ist einer der Winkel der entstehenden Dreiecke,

// tan (phi) kann etwa zwischen 0.5 und 1.1 variiert

// werden, um zu verwertbaren Bildern zu gelangen.

double tanphi = 1.0;

// Die eigentliche Zeichenroutine

public void paint(Graphics g) {

g.clearRect(0, 0, 500, 500);

paintTree(g, 200, 400, 280, 400);

}

// rekursive Pythagoras-Funktion

void paintTree(Graphics g, double x1, double y1,

double x2, double y2 ) {

// (1) Eckpunkte bestimmen

double dx = x2 − x1; double dy = y1 − y2;

double x3 = x1 − dy; double y3 = y1 − dx;

double x4 = x2 − dy; double y4 = y2 − dx;

// (2) vollständiges Quadrat zeichnen

g.drawLine((int)x1, (int)y1, (int)x2, (int)y2);

g.drawLine((int)x2, (int)y2, (int)x4, (int)y4);

g.drawLine((int)x4, (int)y4, (int)x3, (int)y3);

g.drawLine((int)x1, (int)y1, (int)x3, (int)y3);

// (3) Koordinaten des neuen Eckpunktes errechnen

double v = (x3 + x4) / 2− (dy / 2 * tanphi);

double w = (y3 + y4) / 2− (dx / 2 * tanphi);

if (dx * dx + dy * dy > 2) {

// (4) kleine Teilbäume zeichnen

paintTree(g, x3, y3, v, w);

paintTree(g, v, w, x4, y4);

}

Die eigentliche Methode zum Zeichnen des Baumes ist paintTree. Hier werden zunächst aus den beiden Punkten (x₁, y₁) und (x₂, y₂) der Grundlinie die anderen beiden Eckpunkte (x₃, y₃) und (x₄, y₄) des Quadrates abgeleitet (1) und durch Aufruf von drawLine mit Linien zu einem Quadrat verbunden (2).

Im nächsten Schritt werden unter Anwendung der Gleichungen im rechtwinkligen Dreieck über den Tangens von ø die Koordinaten (v, w) des neuen Eckpunktes berechnet (3). Wenn die Kantenlänge des gezeichneten Quadrates noch groß genug ist (in unserem Beispiel: wenn das Quadrat der Kantenlänge größer 2 ist), dann werden rekursiv der linke und rechte Teilbaum gezeichnet (4), indem als Grundlinie der neuen Quadrate (x₃, y₃), (v, w) sowie (v, w), (x₄, y₄) verwendet werden. Das Abbruchkriterium für die Rekursion ist damit das Erreichen einer minimalen Kantenlänge. Die Bezeichnung der verwendeten Variablen stimmt mit den Bezeichnungen in Abbildung 3–10 überein, so dass die Bedeutung der einzelnen Variablen leicht nachvollzogen werden kann.

Programm 3.4 umfasst die für die Ausführung notwendige main-Methode. Hierbei wird die Fensterklasse PythagorasTree instantiiert und mit einigen Eigenschaften (Fenstergröße, Programmende beim Schließen des Fensters, Sichtbarkeit) versehen.

Programm 3.4 Hauptprogramm für den Pythagoras-Baum

public class PythagorasTreeFrame {

public static void main(String[] args) {

JFrame frame = new PythagorasTree();

frame.setSize(500, 500);

frame.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);

frame.setVisible(true);

}

Wird das Programm 3.4 ausgeführt, so ergibt sich die Ausgabe aus Abbildung 3–11 für einen Winkel von 45° (tan ø = 1). Da dieser Parameter in der obigen Implementierung fest kodiert ist, erfordert eine Änderung natürlich eine Neuübersetzung sowie den Neustart. Hier besteht also Raum für Verbesserungen und Experimente.

Die Umsetzung der weiteren rekursiven Algorithmen, die wir bisher kennen gelernt haben, wie z.B. zur Berechnung des größten gemeinsamen Teilers oder die Lösung zu den Türmen von Hanoi, seien dem Leser als Übungsaufgabe überlassen.

3.4Das logische Paradigma

3.4.1Logik der Fakten und Regeln

3.4.2Deduktive Algorithmen

Definition 3.7 Deduktiver Algorithmus

3.5Weitere Paradigmen

3.5.1Genetische Algorithmen

Algorithmus 3.1 Grundprinzip genetischer Algorithmen

3.5.2Neuronale Netze

3.6Umsetzung in Java

3.6.1Ausdrücke und Anweisungen

Ausdrücke

Blöcke

Bedingte Anweisungen

Schleifen

3.6.2Methoden

Programm 3.1 Imperative Berechnung der Fakultät

3.6.3Applikative Algorithmen und Rekursion

Programm 3.2 Rekursive Berechnung der Fakultät

Programm 3.3 Programm zum Darstellen des Pythagoras-Baumes

Programm 3.4 Hauptprogramm für den Pythagoras-Baum