Algorithmen, Datenstrukturen, Funktionale Programmierung. Eine praktische Einfuhrung mit Caml Light 3-8273-1056-3 [PDF]

Zitiervorschau

Algorithmen Datenstrukturen Funktionale Programmierung

Jürgen Wolff von Gudenberg unter Mitarbeit von Jens Klöcker

Algorithmen Datenstrukturen Funktionale Programmierung Eine praktische Einführung mit Caml Light

Die Deutsche Bibliothek – CIP-Einheitsaufnahme Wolff von Gudenberg, Jürgen Frhr.: Algorithmen, Datenstrukturen, funktionale Programmierung: Eine praktische Einführung mit Caml Light / von Jürgen Wolff von Gudenberg. - Bonn: Addison-Wesley, 1996 ISBN 3-8273-1056-3

c 1996 Addison Wesley Longman Verlag GmbH Satz: Jens Klöcker, Würzburg. Gesetzt mit LATEX 2 Belichtung, Druck und Bindung: Bercker Graphischer Betrieb, Kevelaer Produktion: Claudia Lucht Umschlaggestaltung: Tandem Design, Berlin


Das verwendete Papier ist aus chlorfrei gebleichten Rohstoffen hergestellt und alterungsbeständig. Die Produktion erfolgt mit Hilfe umweltschonender Technologien und unter strengsten Auflagen in einem geschlossenen Wasserkreislauf unter Wiederverwendung unbedruckter, zurückgeführter Papiere. Text, Abbildungen und Programme wurden mit größter Sorgfalt erarbeitet. Verlag, Übersetzer und Autoren können jedoch für eventuell verbliebene fehlerhafte Angaben und deren Folgen weder eine juristische Verantwortung noch irgendeine Haftung übernehmen. Die vorliegende Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten. Kein Teil dieses Buches darf ohne schriftliche Genehmigung des Verlages in irgendeiner Form durch Fotokopie, Mikrofilm oder andere Verfahren reproduziert oder in eine für Maschinen, insbesondere Datenverarbeitungsanlagen, verwendbare Sprache übertragen werden. Auch die Rechte der Wiedergabe durch Vortrag, Funk und Fernsehen sind vorbehalten. Die in diesem Buch erwähnten Soft- und Hardwarebezeichnungen sind in den meisten Fällen auch eingetragene Warenzeichen und unterliegen als solche den gesetzlichen Bestimmungen.

Vorwort Dieses Buch stellt grundlegende Algorithmen und Datenstrukturen in einer Form vor, die auch für Anfänger verständlich ist. Vorkenntnisse aus der Informatik, insbesondere die Kenntnis einer Programmiersprache, werden nicht vorausgesetzt. Unser Ziel ist eine praktische Einführung, in der dem Leser mit einer Vielzahl von Beispielen die wesentlichen Ideen, die hinter den gängigen Verfahren stecken, nahegebracht werden. Er soll aber auch das Handwerkszeug zur Analyse begreifen und anwenden lernen. Da die verwendete Beschreibungssprache vom Rechner interpretiert werden kann, lassen sich alle Algorithmen direkt ausprobieren. Weil andererseits die Algorithmen und die Eigenschaften der Datenstrukturen durch Funktionen und Wertemengen auf relativ abstrakter Ebene beschrieben werden, bietet das Buch auch dem theoretisch Interessierten einen Einstieg in Methoden, die Korrektheit von Algorithmen zu beweisen und ihre Laufzeit abzuschätzen. Für die funktionale Sichtweise, in der ein Programm oder ein Algorithmus eine Funktion ist, die für eine Eingabe eine Ausgabe berechnet, und die Verwendung von CAML LIGHT sprechen folgende Argumente: Der hohe Abstraktionsgrad erlaubt übersichtliche Programme. Funktionale Sprachen werden zur Spezifikation beim »Programmieren im Großen« verwendet und deshalb in Zukunft an Gewicht gewinnen. Die Semantik ist klar zu formulieren. Die Rekursion, eines der wesentlichen Hilfsmittel der Informatik, wird von Anfang an behandelt. Datenstrukturen lassen sich so eingeben, wie sie definiert sind. Bei Algorithmen ist die funktionale Spezifikation ausführbar. Durch Interpretation ist die direkte Interaktion zwischen Benutzer und Rechner gewährleistet.

6

Im ersten Teil des Buches werden die Algorithmen mit der Sprache CAML LIGHT kurz, prägnant und präzise im Sinne eines Pseudocodes entworfen. Auf diese Weise wird der Leser mit der funktionalen Programmierung vertraut gemacht. Der Vorteil dieser Vorgehensweise ist, daß der Pseudocode vollständige Programme beschreibt und somit die Entwürfe direkt ausführbar sind. Der zweite Teil bietet eine tutorielle Einführung in die Sprache CAML LIGHT und im letzten Kapitel eine vollständige Beschreibung des Sprachkerns. Die Sprache verfügt darüber hinaus über eine Vielzahl von Erweiterungsmodulen, die von der graphischen Darstellung einer Funktion bis zum animierbaren WWW-Browser reichen. Deren Behandlung würde den Rahmen dieses Buches bei weitem sprengen. CAML LIGHT ist eine leicht portierbare, typisierte funktionale Sprache, die interpretiert wird, aber bei Bedarf auch kompiliert werden kann. Das CAML LIGHTSystem wurde von der INRIA Rocquencourt entwickelt und ist frei und kostenlos erhältlich. Wir empfehlen dem Leser, sich Zugang zu einem CAML LIGHT-System zu verschaffen und während des Lesens die Beispiele durchzuarbeiten (siehe Anhang A.4).

Das Buch ist entsprechend aufbereitet. Die Beispiele wurden während des Setzens dem CAML LIGHT-Interpreter zugeleitet – das wird durch eine schreibende Hand ✍ verdeutlicht – und dessen Ausgaben – mit einem ausgestreckten Zeigefinger ☞ gekennzeichnet – in den Text eingefügt. In diesem Sinne ist das Buch ein interaktiv entstandenes Dokument. Um diese Interaktion nachvollziehen zu können, sollte sich der Leser die Beispiele vom WWW-Server des Verlages laden. Die Vorgehensweise ist in Anhang B beschrieben. Entsprechend seiner Gliederung in zwei Teile kann das Buch auf verschiedene Art gelesen werden. Der vornehmlich an Algorithmen und Datenstrukturen interessierte Leser wird mit dem ersten Teil vorlieb nehmen. Will er gleichzeitig noch etwas tiefer in die funktionale Programmierung einsteigen, wird ein verschränktes Vorgehen empfohlen, etwa in der Kapitelreihenfolge 1, 9, 10, 2, 3, 11, 12, 4, 5, 6, 7, 13, 8, 14. Kapitel 15 dient zum Nachschlagen. Hat ein Leser schon Vorkenntnisse über Algorithmen und will die funktionale Programmierung erlernen, kann er mit Teil 2 beginnen und die zitierten Beispiele bei Bedarf im ersten Teil nachschlagen. Dieses Buch ist aus der Grundvorlesung Praktische Informatik 1 an der Universität Würzburg entstanden, deren Inhalt eine Einführung in Algorithmen und Datenstrukturen ist. Allen, die zu ihrer Gestaltung und damit zum Gelingen des Bu-

7

ches beigetragen haben, sei herzlich gedankt. Hier sind vor allem Markus Klingspor, Jochen Seemann und Jens Klöcker zu nennen. Ganz besonders hervorzuheben ist der Beitrag von Jens Klöcker zu diesem Buch. Nicht nur, daß er die Umsetzung des Manuskriptes in die endgültige Form mit bewundernswerter Akribie besorgte oder einige Beispiele beisteuerte; er entwarf im Rahmen seiner Diplomarbeit auch den hier vorgestellten Heapsort-Algorithmus sowie weitere Einzelheiten und steuerte den Anhang über das CAML LIGHTSystem bei. Die Syntaxdiagramme in Kapitel 15 wurden mit einem von ihm entwickelten CAML LIGHT-Programm automatisch erzeugt. Auch meine Familie möchte ich in meinen Dank mit einbeziehen. So ließen mich Thilo, Diana und Laila trotz neuer interessanter Spiele ab und zu an meinen Rechner, und meine Frau Anna unterstützte das Buchprojekt in voller Hinsicht. Dem Addison-Wesley Verlag danke ich für die Aufnahme des Buches in seine Lehrbuchreihe und für die gute Zusammenarbeit mit den Lektoren Dr. Bernd Knappmann und Fernando Pereira. Würzburg, im Juli 1996

Jürgen Wolff von Gudenberg

Inhaltsverzeichnis T EIL I Kapitel 1

A LGORITHMEN

Der Algorithmusbegriff . . . . Programmentwicklungszyklus Programmierparadigmen . . . Von Quotienten und Teilern . . Darstellung von Algorithmen . Eigenschaften von Algorithmen

15 . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Vollständige Induktion . . Einfache Endrekursion . . Schrittweise Verfeinerung Bottom-Up-Entwurf . . . Divide & Conquer . . . . . Iteration und Rekursion .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Datenstrukturen im Überblick Funktionstypen . . . . . . . . Datenstrukturen . . . . . . . . Typkonstruktion . . . . . . . . Rekursive Datentypen . . . . Parametrisierte Typen . . . . Abstrakte Datentypen . . . .

Listen und ihre Implementierung 4.1 4.2

15 20 21 26 30 38 47

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

Datenstrukturen und Datentypen 3.1 3.2 3.3 3.4 3.5 3.6 3.7

Kapitel 4

13

Entwurf und Analyse von Algorithmen 2.1 2.2 2.3 2.4 2.5 2.6

Kapitel 3

D ATENSTRUKTUREN

Algorithmen und Programmierung 1.1 1.2 1.3 1.4 1.5 1.6

Kapitel 2

UND

47 49 57 62 66 73 85

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

85 87 88 93 95 96 97 101

Listen als abstrakte Datentypen . . . . . . . . . . . . . . . 101 Listen als Felder . . . . . . . . . . . . . . . . . . . . . . . . 109

10

Inhaltsverzeichnis

4.3 4.4 4.5 4.6 4.7 Kapitel 5

Kapitel 9

Einführung . . . . . . . . . . Elementare Sortierverfahren Sortieren durch Mischen . . Quicksort . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Bäume . . . . . . . . . . . . . . . . . . Der Heap als Prioritätswarteschlange Heapsort . . . . . . . . . . . . . . . . . Suchbäume . . . . . . . . . . . . . . . . AVL-Bäume . . . . . . . . . . . . . . . Selbstanordnende Bäume . . . . . . . 2-3-4-Bäume . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

125 126 132 139 143

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

143 153 160 162 166 175 179

Definition und Datenstruktur . . . . . . . . . . . . . . . . 189 Offene Hashtabellen . . . . . . . . . . . . . . . . . . . . . 190 Kollisionsauflösung innerhalb der Tabelle . . . . . . . . . 194 201

Backtracking-Algorithmen . . . . . . . . . . . . . . . . . . 201 Branch & Bound-Verfahren . . . . . . . . . . . . . . . . . 210 Greedy-Algorithmen . . . . . . . . . . . . . . . . . . . . . 220

E INFÜHRUNG

IN

C AML L IGHT

Ausdrücke und Funktionen 9.1

113 114 117 118 121

189

Systematisches Probieren 8.1 8.2 8.3

T EIL II

. . . . .

125

Hashverfahren 7.1 7.2 7.3

Kapitel 8

. . . . .

Bäume und Suchbäume 6.1 6.2 6.3 6.4 6.5 6.6 6.7

Kapitel 7

. . . . .

Sortierverfahren 5.1 5.2 5.3 5.4

Kapitel 6

Verkettete Listen . . . . . . . . . . . . . Rekursive Listen . . . . . . . . . . . . . . Vergleich der Listenimplementierungen Keller oder Stapel . . . . . . . . . . . . . Schlangen . . . . . . . . . . . . . . . . .

225 227

Konstanten und Ausdrücke . . . . . . . . . . . . . . . . . 228

Inhaltsverzeichnis

9.2 9.3 Kapitel 10

11

Vereinbarung und Aufruf einfacher Funktionen . . . . . 233 Testen und Fehlerabbruch . . . . . . . . . . . . . . . . . . 243

Vordefinierte strukturierte Datentypen

249

10.1 Listen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 10.2 Paare und Tupel . . . . . . . . . . . . . . . . . . . . . . . . 255 10.3 Vektoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Kapitel 11

Definition neuer Typen 11.1 11.2 11.3 11.4

Kapitel 12

Vorhandene Typkonstruktoren Typoperatoren . . . . . . . . . . Verbunde . . . . . . . . . . . . . Varianten . . . . . . . . . . . . .

261 . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

Funktionen höherer Ordnung

261 263 265 267 271

12.1 Curry-Funktionen . . . . . . . . . . . . . . . . . . . . . . . 271 12.2 Funktionen höherer Ordnung . . . . . . . . . . . . . . . . 274 Kapitel 13

Module

287

13.1 Abstrakte Datentypen und Datenkapselung . . . . . . . . 287 13.2 Kernmodule . . . . . . . . . . . . . . . . . . . . . . . . . . 289 13.3 Standardmodule . . . . . . . . . . . . . . . . . . . . . . . . 293 Kapitel 14

Imperative Konstrukte 14.1 14.2 14.3 14.4 14.5

Kapitel 15

Ein- und Ausgabe . . . . . . . . . Anweisungsfolgen . . . . . . . . Referenzen und Speichervariable Ausnahmen . . . . . . . . . . . . Schleifen . . . . . . . . . . . . . .

Syntax und Semantik

299 . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

299 301 302 306 308 309

15.1 Formale Darstellung . . . . . . . . . . . . . . . . . . . . . 309 15.2 Syntaxdiagramme und informelle Semantik . . . . . . . . 312 Anhang A

Das Caml Light-System

331

12

Inhaltsverzeichnis

A.1 A.2 A.3 A.4

Interpreter . . . . . . Compiler . . . . . . . Sonstige Werkzeuge . Verfügbarkeit . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

331 334 336 337

Anhang B

Beschaffung der Beispiele

339

Anhang C

Verzeichnis der Algorithmen

341

Anhang D

Literatur

345

Teil I Algorithmen und Datenstrukturen

Kapitel 1 Algorithmen und Programmierung Der Entwurf von Algorithmen, ihre Programmierung und der Umgang mit Datenstrukturen gehören zum Handwerkszeug eines jeden Informatikers. Wir wollen in diesem Buch sowohl Algorithmen als auch Datenstrukturen vornehmlich aus funktionaler Sicht betrachten. Die Spezifikation eines Algorithmus’ und die wesentlichen Eigenschaften einer Datenstruktur werden auf relativ abstrakter Ebene durch Funktionen beschrieben, d. h. ein Programm oder ein Algorithmus ist eine Funktion, die für eine Eingabe eine Ausgabe berechnet. So wird es möglich sein, viele Algorithmen auf hohem Niveau, ohne eine Vielzahl von Details beachten zu müssen, präzise und übersichtlich zu formulieren und trotzdem direkt auf einem Rechner ablaufen zu lassen. Die Programmierung wird also nicht zu kurz kommen. Da wir auch hier eine funktionale Sprache – CAML LIGHT – verwenden, ist der Schritt vom theoretischen Entwurf bis zur ausführbaren Funktion äußerst klein, sofern überhaupt ein Unterschied besteht.

1.1

Der Algorithmusbegriff

Zuerst wollen wir erläutern, was wir unter einem Algorithmus verstehen. Die Herkunft des Wortes gibt uns keine Möglichkeit zu einer Übersetzung. Der Begriff wurde aus dem Namen des persischen Mathematikers und Astronomen A L H WÂRIZMÎ hergeleitet. Er bezeichnet ein systematisches, reproduzierbares Problemlösungsverfahren und ist keineswegs auf Mathematik oder Informatik beschränkt. Auch im täglichen Leben haben wir vielfach mit Algorithmen zu tun – Kochrezepte, Bauanleitungen, Gebrauchsanweisungen oder Bedienungsanleitungen seien hier als Beispiele genannt.

16

Kapitel 1

Algorithmen und Programmierung

Ein Algorithmus ist, da nachvollziehbar und »mechanisch« ausführbar, eine gute Grundlage für ein Programm. Der Algorithmenentwurf ist also eine Vorstufe zur Programmierung. Wir betrachten nun eines der angeführten Beispiele etwas genauer. A L G O R I T H M U S 1.1 N USSKUCHEN -1 Z UTATEN : 300 g Zucker, 9 Eier, 300 g Nüsse, Semmelbrösel, Marmelade, 1 Zitrone. M ETHODE : Zucker, Eigelb und Zitronensaft schaumig rühren, geriebene Nüsse und Semmelbrösel dazugeben, Eischnee unterziehen, 50–80 Minuten backen, auseinanderschneiden und mit Marmelade füllen. – Alg. 1.1 – Nun soll dieses Buch natürlich kein Backbuch werden. Deshalb wollen wir hier auch eine erste, einfache mathematische Aufgabe lösen, nämlich die Summe von gegebenen ganzen Zahlen bestimmen. Eine erste Formulierung des Summationsalgorithmus’ lautet A L G O R I T H M U S 1.2 S UMME -1 E INGABE : eine Menge von ganzen Zahlen. A USGABE : deren Summe. M ETHODE : Nimm eine Zahl nach der anderen und bilde ihre Summe. – Alg. 1.2 –

1.1

Der Algorithmusbegriff

17

Das ist allerdings noch recht vage und nicht viel mehr als eine Umformulierung der Aufgabe. Wir müssen noch festlegen, wie eine Zahl nach der anderen genommen werden soll. Wir brauchen einen Zugriff auf einzelne Zahlen. Setzen wir eine Funktion voraus, die eine Zahl aus der Ausgangsmenge auswählt, und legen fest, daß die Summe von null Zahlen gleich ist, dann kommen wir zu folgendem Verfahren: A L G O R I T H M U S 1.3 S UMME -2 E INGABE : eine Menge von ganzen Zahlen. A USGABE : deren Summe. M ETHODE : Falls die Menge leer ist, so ist ihre Summe . Sonst wähle eine Zahl aus und addiere ihren Wert zur Summe der restlichen Elemente. – Alg. 1.3 – Einen solchen Algorithmus, der sich selbst wieder aufruft, nennen wir rekursiv. Damit werden wir uns noch ausführlich beschäftigen. Nun leiten wir aus den zwei Beispielen mögliche Merkmale eines Algorithmus’ ab: Es gibt Zutaten oder Eingaben: – Eier, Zucker, Nüsse, – eine Menge von ganzen Zahlen. Es wird ein Ergebnis oder eine Ausgabe geliefert: – ein Kuchen, – die Summe der Elemente. Verschiedene Funktionseinheiten treten in Aktion: – Backofen, Küchenmaschine, – Addition.

18

Kapitel 1

Algorithmen und Programmierung

Es findet eine Zerlegung in einfachere Vorschriften (Teilalgorithmen) statt: – Eischnee schlagen, Teig rühren, Backofen einschalten, – Test auf leere Menge. Der Grad dieser Zerlegung hängt vom Kenntnisstand und der Ausrüstung des Handelnden ab: – Das Schlagen von Eischnee ist für Geübte klar. Anfänger sollten wissen, daß man vor dem Schlagen Eigelb und Eiweiß trennen muß. – Die ganzzahlige Addition ist bekannt. Die elementaren Operationen werden ausgeführt: – Eier aufschlagen, Nüsse mahlen, – Zahl addieren. Eine angepaßte Datenstruktur ist wichtig: – Wir brauchen eine Repräsentation der Zahlenmenge. Eine Zustandsänderung tritt ein: – Aus den Zutaten wird ein Kuchen. – Die Summe wird berechnet. Für einige Funktionen ist die zeitliche Abfolge wichtig: – Man muß zuerst den Teig rühren und dann Eischnee unterziehen. Verschiedene Fälle werden unterschieden: – Eine Menge kann leer sein, oder nicht. Wiederholungen der gleichen Operation werden durchgeführt: – Man muß 9 Eier aufschlagen. – Implizit enthält auch der Summationsalgorithmus eine Wiederholung, denn er wird ja für die restlichen Zahlen wieder aufgerufen. Es können Nebenwirkungen auftreten: – Die Küche wird verschmiert. Die Zutaten sind verbraucht. Der Algorithmus terminiert: – Beim Nußkuchen nach Ablauf der Backzeit.

1.1

Der Algorithmusbegriff

19

– Da endlich viele Zahlen gegeben sind und die Restmenge in jedem Schritt ein Element weniger enthält, wird sie am Ende schließlich leer sein und der Algorithmus mit Ausführung der ersten Alternative terminieren. Insbesondere die Nebenwirkungen sind natürlich unerwünscht. Die Beschreibung erfolgte hier in der angemessenen Fachsprache. Oft werden zusätzlich Bilder oder graphische Darstellungen eingesetzt. Wir werden in diesem Kapitel verschiedene Fachsprachen für Algorithmen aus dem Bereich der Informatik vorstellen und verwenden. Hierzu gehören auch graphische Repräsentationen. Eine Klasse solcher Fachsprachen – die funktionalen Sprachen – stellen den Aufruf von Funktionen in den Mittelpunkt. Als Beispiel noch einmal das Backrezept, jetzt im »Küchenfunktionalkauderwelsch«: A L G O R I T H M U S 1.4 N USSKUCHEN -2 M ETHODE : Rufe für die Zutaten die Funktion »Nußtorte backen« auf. Oder eine Stufe genauer: 1. Rufe auf »Nüsse mahlen«. 2. Rufe auf »Teigrühren« für Eigelb, Zitrone und Zucker. 3. Rufe auf »Eischnee schlagen« für Eiweiß 4. Rufe auf »Zusammenrühren« für die Ergebnisse von 1, 2 und 3. 5. Rufe auf »Backen« für das Ergebnis von 4. – Alg. 1.4 – Und unser Summationsbeispiel liest sich nun in funktionalem Pseudocode so: A L G O R I T H M U S 1.5 S UMME -3 M ETHODE : sei die Menge der Zahlen, hier dargestellt als Liste. Wir wählen immer de

ren erstes Element aus und bezeichnen es mit
  , die Restliste nennen wir    und     teste, ob die Liste leer sei.

20

Kapitel 1

✍ 




 

Algorithmen und Programmierung



  
     
 
    





 

– Alg. 1.5 – Zum Schluß dieses Abschnitts wiederholen wir noch einmal unsere erste Definition eines Algorithmus’. D EFINITION 1.1 Ein Algorithmus ist ein systematisches, reproduzierbares Problemlösungsverfahren.

1.2

Programmentwicklungszyklus

Algorithmenentwurf ist ein wesentlicher Teil des Lösungsvorgangs zu einem Problem. Wir gehen hier nur von Problemen aus, deren Lösung auf einem Computer bestimmt werden kann. Dann läßt sich der Problemlösungsprozeß, den man jetzt auch als Programmentwicklungsprozeß betrachten kann, grob in fünf Schritte untergliedern: Analyse des Problems, genaue Spezifikation, Modellbildung, Entwurf von Algorithmen und zugehörigen Datenstrukturen, Implementierung in einer Programmiersprache, Organisation, d. h. Einbau in existierende Rechnerumgebung, Tests, Unterstützung, Optimierung und Wartung. Dieses Vorgehensmodell, das wir in Anlehnung an die Anfangsbuchstaben der einzelnen Schritte das Vokalmodell nennen, wird nicht nur ein einziges Mal durchlaufen. Man wird in der Regel in jedem Schritt Fehler machen oder falsche Entscheidungen treffen, die erst im nächsten oder einem späteren Schritt bemerkt werden und deshalb ein Zurückgehen erfordern. Der ganze Prozeß läuft also zyklisch ab. Wir konzentrieren uns in diesem Buch auf den zweiten Schritt und dort wiederum auf Standardprobleme der Informatik wie z.B. Listenverwaltung und Sortierverfahren, die zwar sicher schon in einigen hundert Versionen existieren, aber auch ständig gebraucht und auf neue Situationen angepaßt werden müssen und die deshalb von jedem Informatiker beherrscht werden sollten.

1.3

Programmierparadigmen

21

Um eine zu trockene Vorgehensweise zu vermeiden, wollen wir auch den dritten Schritt behandeln: die Implementierung in einer Programmiersprache. Da dies auf möglichst hohem, abstraktem Niveau geschehen soll, um nicht durch Implementierungsdetails den Blick auf das Wesentliche zu verdecken, wählen wir die funktionale Programmiersprache CAML LIGHT, die uns zuerst als Pseudocode in der Algorithmenbeschreibung begegnen wird. Der Vorteil einer funktionalen Programmiersprache liegt auch darin, daß sowohl die formale Spezifikation als auch die Algorithmendarstellung funktional erfolgen kann, und somit kein Bruch in der Darstellung der ersten drei Schritte vorliegt. Diese Schritte werden in der Praxis immer verzahnt ablaufen – es gibt Entwicklungszyklen. Der vierte Schritt, der seinen Namen »Organisation« nur wegen des Vokalmodells erhielt, validiert gewissermaßen durch Tests die Gültigkeit des Algorithmus’. Er ist der erste für den ein Computereinsatz zwingend nötig ist. Natürlich kann ein Test nie die Korrektheit eines Programms beweisen. Wir werden deshalb beim Entwurf schon sehr sorgfältig vorgehen und versuchen, alle Sonderfälle zu berücksichtigen. Ein formaler Beweis der Korrektheit von Algorithmen würde jedoch in den meisten Fällen den Rahmen dieser Einführung sprengen. Besonders der fünfte Schritt wird immer wieder unterschätzt, obwohl in der Praxis oft mehr als 50 % des Aufwandes in ihm stecken. Stellen wir die ersten vier Schritte noch einmal zusammen: 1. Analyse des Problems und eventuell genauere Darstellung (Spezifikation). 2. Herausfinden eines Lösungsweges und Entwicklung eines Algorithmus’. 3. Übersetzung des Algorithmus’ in eine computerverständliche Form. 4. Einsatz des Computers zur Erstellung der Lösung. Wir konzentrieren uns hier auf Schritt 2. Bei den behandelten Problemen ist die genaue Spezifikation offensichtlich. Wir werden unsere formale Darstellung von Algorithmen sehr nahe an der Sprache CAML LIGHT wählen, so daß Schritt 3 trivial ist und wir sofort ausführbare Algorithmen erhalten.

1.3

Programmierparadigmen

Ein Paradigma ist eine Methodologie oder auch Vorgehensweise. In diesem Abschnitt wollen wir das funktionale und das imperative Programmierparadigma gegenüberstellen. Die Definitionen in diesem Kapitel sind bewußt etwas allgemein gehalten.

22

Kapitel 1

1.3.1

Algorithmen und Programmierung

Funktionales Programmieren

Den Begriff des Algorithmus’ als reproduzierbares Problemlösungsverfahren spezialisieren wir wie folgt: D EFINITION 1.2 Ein funktionaler Algorithmus ist ein Problemlösungsverfahren, das durch Hintereinanderausführung von elementaren Funktionen aus gegebenen Anfangswerten Resultate erzeugt. Hier ist natürlich noch einiges offen. Wir wollen von Fall zu Fall festlegen, welches die elementaren Funktionen sind. Wir kommen so zu einer Schachtelung von Funktionen oder zu einer schrittweisen Verfeinerung. So kann z.B. die Bestimmung des größten gemeinsamen Teilers für einen Algorithmus zur Bruchrechnung als elementare Funktion auftreten, die aber ihrerseits wieder durch einen Algorithmus beschrieben wird, der sich auf elementarere Funktionen wie etwa ganzzahlige Division mit Rest abstützt. Zur Vereinbarung einer Funktion gehört die Angabe des Definitions- und des Wertebereiches – es werden die Funktionsargumente eingeführt und in Form eines (arithmetischen oder sonstigen) Ausdrucks die Wirkung der Funktion auf die Argumente beschrieben. Man erhält aus einem Ausdruck, in dem Variablennamen vorkommen, durch Abstraktion eine Funktion, indem man einige Namen zu Parametern oder Argumenten der Funktion erklärt. Betrachten wir ein Beispiel. Aus dem Ausdruck die Nachfolgerfunktion für ganze Zahlen: ✍ ☞








erhält man durch Abstraktion

  


  "!#

Um diese Funktion bequem für unterschiedliche Argumente aufrufen zu können, geben wir ihr einen Namen:










     ✍  ☞ $%!%&&'(#)#* +!




Mit Angabe des Definitions- und des Wertebereiches lautet die vollständige Funktionsvereinbarung:

1.3

✍  ☞



 





Programmierparadigmen

23

    




  $! &&  "!#

oder in gewohnter mathematischer Schreibweise  



mit

 



Die genaue Kommentierung dieser im Schreibmaschinenstil abgesetzten Programmblöcke verschieben wir bis zum Abschnitt 1.5. Innerhalb eines Funktionsausdrucks werden Argumente miteinander, mit benannten oder direkt hingeschriebenen Konstanten und mit Werten, die bei der Anwendung von anderen Funktionen als Ergebnis auftreten, verknüpft. Für die üblichen arithmetischen Operationen wird dabei die infix-Schreibweise verwendet, bei der der Operator zwischen den beiden Operanden steht. Ansonsten wird der Funktionsname vor die Argumente geschrieben. Letztere können selbst wieder das Ergebnis eines Funktionsaufrufes sein, die Funktionen werden verschachtelt aufgerufen oder hintereinander ausgeführt. D EFINITION 1.3 Ein funktionales Programm ist eine Folge von Wertbestimmungen. Darunter versteht man Funktionsaufrufe, die Anfangswerte auf Endwerte abbilden, oder auch Funktionsdefinitionen. Anfangs- und Endwerte können Zahlen, Zeichen, Wahrheitswerte, beliebige Datenstrukturen oder auch Funktionen sein. Eine Funktion wird aus elementaren Operationen oder Funktionen durch Komposition und Fallunterscheidung zusammengesetzt. Die einfachste Fallunterscheidung ist dabei ein bedingter Ausdruck, der einen von zwei möglichen Werten berechnet. Allgemein ist sie eine Funktion, die abhängig von einem Auswahlwert eine von mehreren Funktionen aufruft. Die Ausführung eines Programms bestimmt nacheinander die angegebenen Werte. Dabei kann es sich um Funktionen handeln, die üblicherweise einen Namen erhalten, oder Ausdrucksauswertungen (Funktionsanwendungen), die ebenfalls benannt werden können. A L G O R I T H M U S 1.6 A BSOLUTBETRAG E INGABE : eine ganze Zahl  .

24

Kapitel 1

Algorithmen und Programmierung

A USGABE : ihr Absolutbetrag 
. M ETHODE : Verwende die Funktion:









✍       

☞ $  ## * +!#



*



Die Berechnung des Absolutbetrages von

 






   



– Alg. 1.6 – wird nun durch den Aufruf



✍   

☞   durchgeführt. Ein wichtiges Hilfsmittel ist auch die Rekursion. Damit bezeichnet man die Tatsache, daß sich eine Funktion selbst innerhalb ihrer Definition aufruft. Dieses Verfahren haben wir im Summationsalgorithmus 1.1.5 bereits verwendet.

1.3.2

Imperatives Programmieren

D EFINITION 1.4 Ein imperativer Algorithmus ist ein mit endlich langem Text beschriebenes Problemlösungsverfahren. Es enthält Objekte und Aktionen, wobei jede Aktion eindeutig ausführbar und die Reihenfolge der Aktionen eindeutig festgelegt ist. Aktionen sind Steuerungsaktionen oder Zuweisungsaktionen, die eine Zustandsänderung der Objekte bewirken. Der zentrale Begriff für das imperative Programmieren ist also der des Zustands eines Objekts. Ein Objekt ist im einfachsten Fall eine ganze Zahl, der Zustand ist dann der Wert. Dieses Modell lehnt sich eng an das übliche VON N EUMANNsche Rechnermodell an, in dem Werte für Objekte im Speicher des Rechners gehalten werden. Der Speicherbereich für ein Objekt wird durch eine Variable – einen symbolischen, frei gewählten Namen – angesprochen, seine Größe und die korrekte Interpretation des dort gespeicherten Bitmusters durch seinen Typ bestimmt. D EFINITION 1.5 Ein imperatives Programm beschreibt eine Transformation eines Anfangszustandes des Datenspeichers in einen Endzustand.

1.3

Programmierparadigmen

25

Dabei gehört das Anlegen des Speichers und seine korrekte Initialisierung durchaus zu den Aufgaben des Programms. Die Hintereinanderausführung der Anweisungen legt den Programmablauf fest. Dabei kommen Bedingungen und Wiederholungen (Schleifen) vor. Durch eine Zuweisungsaktion oder Einleseprozedur wird der Wert einer Variablen verändert. Besonders deutlich wird der Unterschied zwischen funktionaler und imperativer Sicht bei der einfachen Aufgabe, zwei Eingabewerte zu vertauschen. Im funktionalen Modell wird eine Funktion definiert: A L G O R I T H M U S 1.7 TAUSCH , FUNKTIONAL E INGABE : zwei Werte. A USGABE : die gleichen Werte in vertauschter Reihenfolge. M ETHODE : Verwende die Funktion:


       "$ &            "#!  

 
     

✍  ☞ %!



– Alg. 1.7 – Im imperativen Modell wird eine Hilfsvariable benötigt. A L G O R I T H M U S 1.8 TAUSCH , IMPERATIV E INGABE : zwei Variable, d. h. Wertbezeichner. E RGEBNIS : Jede Variable bezeichne den anderen Wert. M ETHODE : Verwende eine Hilfsvariable und führe die Aktionen

26

Kapitel 1









 





Algorithmen und Programmierung






aus. – Alg. 1.8 – Die Namen für Wertbezeichner sind im funktionalen Fall relativ unwichtig, so daß man sich nicht darum kümmern wird, welchen Wert nun  bezeichnet. Im imperativen Ansatz trägt genau das zur Zustandsbeschreibung bei. Genau genommen sind hier schon die Problemstellungen verschieden. Natürlich kann man aber auch die Aufgabe im jeweils anderen Modell lösen. Das imperative Paradigma liegt näher an der Hardware, das funktionale näher an der logischen Sicht eines Problems. Daraus kann man schließen, daß ein imperatives Programm in der Regel effizienter in Laufzeit und Speicherbedarf ist. In unserem Tauschbeispiel wird im funktionalen Modell in der Tat nicht nur eine Hilfsvariable benötigt, sondern es wird ein neues Zahlenpaar als Funktionsergebnis erzeugt. Daraus kann man aber auch schließen, daß die Programmierung im funktionalen Modell oft einfacher ist und übersichtlichere Programme ermöglicht. Diese Tatsache wollen wir uns in der Folge zunutze machen.

1.4

Von Quotienten und Teilern

Bevor wir unsere allgemeinen Betrachtungen über Algorithmen fortsetzen, wollen wir zwei einfache Beispiele besprechen – die Division mit Rest und die Berechnung des größten gemeinsamen Teilers. Als erstes Beispiel entwerfen wir einen Algorithmus, der für zwei natürliche Zah

 den ganzzahligen Quotienten  und den Rest  bestimmt, so len und mit daß


 

mit

 


gilt. Als Elementaroperationen stehen Addition und Subtraktion zur Verfügung.




Wir beobachten, daß im Fall  die Lösung offensichtlich durch  und  gegeben ist. Im anderen Fall subtrahieren wir
von und berechnen die zu

1.4

Von Quotienten und Teilern





und 
.
Haben wir diese Aufgabe gehörenden für 
 
  Werte   
 gilt  und  . Daraus folgt    und    die Lösung des ursprünglichen Problems. 



27






gelöst, so . Somit sind

Es sieht aber so aus, als hätten wir nichts gewonnen. Wir haben eine Aufgabe durch die gleiche Aufgabe mit unterschiedlichen Eingabewerten ersetzt. Wir bleiben hartnäckig und machen trotzdem weiter. Läßt
sich das neue Problem wiederum nicht direkt lösen, so kann die Subtraktion von erneut durchgeführt werden. Wir wenden also gleichen Algorithmus
rekursiv
 denvorausgesetzt an. Dieser Prozeß terminiert, weil war und für 
die fortgesetzte Subtraktion irgendwann einen Wert kleiner als liefert. Diese Problemtransformation kann man als Algorithmus auffassen und dieser führt in der Tat zum Ziel. Für die detaillierte Beschreibung wollen wir die zugehörige Funktion in zwei Schritten entwickeln. Im ersten kümmern wir uns um die Bestimmung des Divisionsrestes. A L G O R I T H M U S 1.9 MODULO

E INGABE : zwei natürliche Zahlen A USGABE : der Divisionsrest 




.

 
.

M ETHODE : Verwende die Funktion: "     ✍ 

      ☞ %!




und mit

   
         +  

 

 #  # ##+!#

– Alg. 1.9 – Die Definition einer rekursiven, sich selbst aufrufenden Funktion kennzeichnen    . wir durch Voranstellen von  Ein Aufruf dieser Funktion liefert nach entsprechend vielen rekursiven Aufrufen

den gewünschten Wert. Zum Beispiel erzeugt   
 nacheinander die Aufrufe

28

Kapitel 1

   

Algorithmen und Programmierung








   




 




um das Ergebnis  zu ermitteln. Um auch den ganzzahligen Quotienten bei der Division mit Rest zu bestimmen, müssen wir nur noch die Zahl der rekursiven Aufrufe, die Rekursionstiefe, mitzählen. Wir fügen also einen dritten Parameter  hinzu und geben nun ein Zahlenpaar als Funktionswert zurück. A L G O R I T H M U S 1.10 GANZZAHLIGE D IVISION E INGABE : zwei natürliche Zahlen A USGABE : der Quotient 











und mit

und der Rest 




sowie die Zahl .

 


der Division von




durch .

M ETHODE : Folgende Funktion leistet das Gewünschte: ✍ 

   
   " 


   



   "  

☞ %

      

          
     
 "  + 

 














 #  # #    "!#

– Alg. 1.10 – Schachtelungen von Ausdrücken werden dabei durch die  dargestellt.

   Klausel

Der Algorithmus verwendete neben Addition und Subtraktion noch die bedingte Auswertung eines Ausdrucks, deren Bedeutung intuitiv klar ist. Wir haben durch Angabe des Algorithmus, von dessen Korrektheit und Terminierung wir uns überzeugt haben, bis auf die Eindeutigkeit folgenden Satz bewiesen.

1.4

Von Quotienten und Teilern

S ATZ 1.1 Für zwei natürliche Zahlen tient  und der Rest  , so daß

 






mit





und ,

29

, existieren der ganzzahlige Quo-




gilt. Dabei sind  und  eindeutig bestimmt. Der Beweis der Eindeutigkeit setzt die Existenz zweier verschiedener Lösungen voraus und zeigt dann, daß sie gleich sind. Die Beschreibung eines Algorithmus’ durch eine rekursive Funktion mag auf den ersten Blick ungewohnt erscheinen. Sie ermöglichte aber den Beweis der Korrektheit, den wir im obigen Beispiel nur informell geführt haben (es fehlte eine Induktion über die Rekursionstiefe), und ist trotzdem noch direkt ausführbar. Wir haben sogar zur Algorithmenbeschreibung die Syntax der realen Programmiersprache CAML LIGHT verwendet! Der Vorteil der funktionalen Vorgehensweise tritt stärker in Erscheinung, wenn wir von der Formulierung eines Satzes ausgehen und ihn nicht schrittweise entwickeln wollen. Dies führen wir in unserem zweiten Beispiel durch. Um den größten gemeinsamen Teiler (ggT) von zwei Zahlen zu bestimmen, verwenden wir den folgenden Satz von E UKLID. S ATZ 1.2 Der größte gemeinsame Teiler zweier natürlicher Zahlen gegeben durch 

 falls  



  
  



     sonst 





und ,

, ist

Der Beweis ist für die erste Alternative und folgt für
die zweite aus dem Satz
 klar        , dann muß jeder Teiler von der Division mit Rest: Ist mit
auch  teilen. Damit stimmt der größte von und gemeinsame Teiler von und
mit dem von
und  überein. Dieser Satz läßt sich sofort in einen Algorithmus umsetzen. Wir verwenden anstelle der Funktion    aus dem vorigen Beispiel den Operator  , der den gleichen Wert liefert.

30

Kapitel 1

Algorithmen und Programmierung

A L G O R I T H M U S 1.11 GG T E INGABE : zwei natürliche Zahlen




und mit




.

A USGABE : 
der größte gemeinsame Teiler

   . M ETHODE : Satz von E UKLID: " ✍ 





☞






         
  

            





 #  # ##+!#

– Alg. 1.11 – Die Korrektheit dieses Algorithmus’ ist gegeben, da er mit dem Satz von Euklid fast wörtlich übereinstimmt.

1.5

Darstellung von Algorithmen

Algorithmen im täglichen Leben werden in der jeweils angemessenen Fachsprache formuliert. Oft wird die Darstellung durch Graphiken oder Bilder unterstützt, in denen etwa die einzelnen Schritte zum Zusammenbau eines Schrankes schematisch aufgezeichnet sind. Auch für Informatik-Algorithmen haben sich verschiedene, teilweise genormte Darstellungsformen durchgesetzt. Die einzelnen Formen unterscheiden sich dabei in ihrem Detaillierungsgrad, ihrem Abstraktionsniveau und der Striktheit, mit der die Beschreibungssprache definiert ist und angewendet werden muß. Die Skala reicht hierbei von einer verbalen Beschreibung bis zum ausführbaren Programm. Wir wollen die Algorithmen und Datenstrukturen vornehmlich in der funktionalen Sprache CAML LIGHT notieren. Das erlaubt eine präzise Formulierung und hat außerdem den Vorteil, daß sie direkt ausführbar sind. Wir brauchen uns nicht an eine Algorithmendarstellung und an eine unterschiedliche Programmiersprache zu gewöhnen. CAML LIGHT ist so einfach, daß wir uns ihren Gebrauch neben-

1.5

Darstellung von Algorithmen

31

bei aneignen können. Eine detailliertere Beschreibung der Sprache findet sich im zweiten Teil des Buches. Auch der Algorithmenentwurf geschieht wie die gesamte Problemlösung in mehreren Schritten oder Verfeinerungsstufen. Wir werden diese Stufen oft durchlaufen und jeweils die problemangepaßte Darstellung verwenden. Auch eine graphische Notation von Algorithmen werden wir kennenlernen. Generell gilt für alle Darstellungsformen: Jeder Algorithmus hat einen Namen, der den Zweck des Algorithmus bezeichnen sollte. Es folgt die Beschreibung der Eingabe, d. h. des Definitionsbereiches durch Angabe von Datentypen oder Bedingungen. Die vom Algorithmus verwendeten Größen sollten vollständig angegeben werden. Einige dieser Größen werden explizit als Parameter übergeben, andere sind aus der Umgebung bekannt. Der Wert, den der Algorithmus als Ausgabe liefern soll, ist ebenfalls anzugeben und durch seinen Datentyp und weitere einschränkende Bedingungen zu charakterisieren. Die bisher aufgezählten Punkte bieten eine Spezifikation des Problems. Sie beschreiben das »Was« eines Algorithmus’, aber nicht das »Wie«. Zu einer vollständigen Spezifikation gehört natürlich noch mehr, wie etwa die Schnittstellenbeschreibung sämtlicher verwendeter Elementaroperationen oder der benötigte Speicherplatz. So detailliert werden wir aber nicht vorgehen. Wir notieren Algorithmen gemäß folgender, bereits mehrfach angewendeter Schablone: A L G O R I T H M U S 1.12 S CHABLONE E INGABE : A USGABE : M ETHODE : – Alg. 1.12 –

32

Kapitel 1

1.5.1

Algorithmen und Programmierung

Verbale Beschreibung

Die eigentliche Beschreibung der Vorgehensweise des Algorithmus’ wird hier durch einen möglichst verständlich formulierten Klartext erläutert, im einfachsten Fall durch Angabe einer Formel als Berechnungsvorschrift oder durch eine zeitliche Abfolge von elementaren Funktionsaufrufen. Wir verwenden also Text oder Formeln, die wir oft durchnumerieren, um die Hintereinanderausführung zu umschreiben. Wiederholungen von Funktionsaufrufen sind üblich, etwa bis eine Bedingung über die Eingabewerte erfüllt ist. Durch die verbale Beschreibung wird ein Überblick über den Ablauf des Algorithmus’ vermittelt. Es besteht allerdings oft die Gefahr der Mißinterpretation oder der Ungenauigkeit. Die Ein- und Ausgabe wird von uns selten formal und nicht immer vollständig angegeben werden, weil aus dem Kontext ohnehin klar ist, was gemeint ist.

1.5.2

Pseudocode

Etwas formaler ist die Beschreibung durch Pseudocode. Wir setzen hier nur die elementaren Operationen voraus, die, wie z. B. die ganzzahlige Addition, immer vorhanden sind. Mit ihnen gebildete Ausdrücke können direkt hingeschrieben werden.





Namen für Werte werden mittels der  -Klausel eingeführt. Zwischen  und  steht der Name, der den nach dem Gleichheitszeichen angegebenen Wert bezeichnet. Dieser Wert kann entweder durch einen normalen Ausdruck bestimmt werden oder eine Funktion sein. Funktionen notieren wir nach folgendem Mu ster mit einleitendem Wortsymbol    , gefolgt von dem Argumentnamen und hinter dem Zuordnungspfeil  , dem das Funktionsergebnis berechnenden Ausdruck.     
   
 

  
      % 

 "
 

   
  

Die aktuellen Namen und der Ausdruck sind einzusetzen. Hinter dem Funktionsnamen kann zur Klarstellung der Argumentbereich und der Wertebereich der Funktion durch  getrennt angegeben werden. Die Schreibweise entspricht dann, wie bereits im Beispiel der Funktion 
 aus Abschnitt 1.3.1 gesehen, ziemlich genau der üblichen mathematischen Notation.

1.5

Darstellung von Algorithmen

33

Treten mehrere Argumente auf, so sind sie vorerst zu klammern, sie entsprechen so einem Argument aus dem als kartesisches Produkt zusammengefaßten Definitionsbereich. Dieser Pseudocode ist nichts anderes als ein Teil der Sprache CAML LIGHT und damit ausführbar. Wir wollen den von uns angegebenen Code auch in den meisten Fällen ausführen bzw. interpretieren lassen. Betrachten wir hierzu einige Beispiele. Dem von uns eingegebenen Code wird in der ersten Zeile das Zeichen ✍ vorangestellt. Jede vollständige Phrase, das ist etwa ein Ausdruck oder eine Funktionsdefinition, wird durch ein doppeltes Semikolon abgeschlossen. Die Antwort des Interpreters erscheint durch ☞ eingeleitet darunter. B EISPIEL 1.1 Ein Ausdruck:







✍ 
       ☞  #   



Der Ausdruck hat den ganzzahligen Wert  . Vereinbarung eines Wertes:



  ✍  ☞

 #  

    ✍ 

☞ ✍ ☞




 #    





 

 #  

Die Variable bezeichnet den ganzzahligen Wert   ,  . Folglich ist ihre Summe  . Nachfolgerfunktion: ✍  ☞ $!


          


&&  "!#

Der Wert dieser Phrase ist eine Funktion, die ganze Zahlen auf ganze Zahlen abbildet und 
 heißt. Der Funktionsaufruf kann durch

34

Kapitel 1

Algorithmen und Programmierung




✍ 
 ☞    erfolgen. Funktion für ein Paar von Argumenten beliebigen Typs:

        

    * 
 

✍ 

          * +!#

☞ 

    

oder ausführlich (eingeschränkt auf ganze Zahlen): ✍  ☞ 



 
             

     *


      

  #  # ##+!#

Bedingte Ausdrücke formulieren wir als:





  




"
           
     %

Auch allgemeinere Formen der Fallunterscheidung sind zugelassen. So können etwa bestimmte Strukturen oder Werte der Eingabeargumente überprüft werden. Als Beispiel betrachten wir das Vorzeichen (Signum) einer Zahl, das durch

    





 



 

für  für  für 

definiert ist. A L G O R I T H M U S 1.13 S IGNUM E INGABE :   . A USGABE :      .





1.5

Darstellung von Algorithmen

35

M ETHODE : Verwende: ✍ 

        

  
 
  
    ☞  $     "!#



– Alg. 1.13 – Wir geben für das Argument gewisse Muster vor und filtern den aktuellen Wert der Reihe nach gegen diese Muster. Sobald eines paßt, wird der zugehörige Ausdruck berechnet. Im Beispiel wird also nur für die erste Alternative ausgeführt. Das Ausfiltern von Mustern – englisch »pattern matching« – bietet vor allem bei der Unterscheidung von Strukturen eine sehr übersichtliche Form der Argumentzuordnung. Wir werden im Verlauf des Buches sehr viel mit Folgen oder Listen zu tun haben.  Eine leere Liste bezeichnen wir mit
 , eine mit zwei Elementen mit
 und allgemein können wir eine Liste mit

in das erste Element und die Restliste zerlegen. Solche Strukturen lassen sich beim »pattern matching«herausfiltern. A L G O R I T H M U S 1.14 M AXIMUM EINER L ISTE E INGABE : Liste von natürlichen Zahlen. A USGABE : deren Maximum. M ETHODE : Das Maximum der leeren Liste ist . Das Maximum einer einelementigen Liste ist das Element. Das Maximum einer längeren Liste ist das (in  definierte) Maximum des ersten Elementes und des Maximums der Restliste. In CAML LIGHT lautet das: "     ✍ 





36

Kapitel 1

Algorithmen und Programmierung

  

 

         $%' " $   # * +!# ☞   "








– Alg. 1.14 – Man beachte, daß die einelementige Liste hier nur zur Demonstration von Mustern extra untersucht wurde. Sie ist eigentlich bereits als Spezialfall


 in der dritten Alternative enthalten.

1.5.3

Graphische Elemente und Datenflußdiagramme

Bei der Musterauswahl ist das textuelle Notieren oft umständlich, während ein kleines Bild sehr viel klarer ausdrücken kann, was gemeint ist. Deshalb werden zur Unterstützung des Pseudocodes auch häufig graphische Darstellungen verwendet. Setzt sich ein Algorithmus aus vielen Funktionen zusammen, so verschafft oft ein Datenflußdiagramm Übersicht. In diesem werden die wichtigsten Funktionen als »Teiche« dargestellt, die durch »Datenflüsse« verbunden sind. Ein Beispiel hierfür zeigt Abbildung 1.1. Eingabe

Funktion 1

Zwischenergebnis

Funktion 2

Ausgabe

Abbildung 1.1: Funktionen und Datenflüsse

Zur Darstellung von permanenten Speichern, Ein- bzw. Ausgabegeräten o.ä. gibt es, wie in Abbildung 1.2 zu sehen, graphische Elemente für externe Quellen und Senken. Datei

Eingabe

Funktion 1

Ausgabe

Bildschirm

Abbildung 1.2: Externe Quellen und Senken

1.5

Darstellung von Algorithmen

Datei

37

Datei Funktion 1

Tastatur

Bildschirm

Abbildung 1.3: Aufteilung und Kombination von Flüssen x

(1 - x) / 10

f (x)

Abbildung 1.4: Direkte Ausdrucksangabe in einer Funktion

Diese Art der Darstellung wird in der Softwaretechnik beim Programmieren im Großen verwendet, um den Weg der Daten durch ein Informationssystem zu veranschaulichen. Dabei werden nur die Schnittstellen der einzelnen Funktionen betrachtet und nicht ihre Rümpfe. Datenflüsse können außerdem aufgeteilt und mit einem Operator wieder zusammengefaßt werden. Abbildung 1.3 zeigt ein Beispiel. Wir wollen Datenflußdiagramme auch zur Beschreibung unserer doch recht kurzen Algorithmen einsetzen und dabei auch genauer den Funktionsablauf verfolgen. Wir schreiben dazu in einen »Teich«, der ja in unserem Modell eine aktive Einheit ist, den zu berechnenden Ausdruck wie in Abbildung 1.4 hinein. Um auch bedingte Ausdrücke und Fallunterscheidungen darstellen zu können, erweitern wir unsere »Wasserlandschaft« durch »Staudämme«, die den gesamten Einlauf in einen »Funktionsteich« unterbinden. Diese Staudämme werden von Bedingungen repräsentierenden »Schaltzentralen« gesteuert, die je nach Wahrheitswert eine andere Funktion aktivieren. In unseren Diagrammen wird dabei der Steuerstrom für den linken Ausgang geschaltet, falls die Bedingung erfüllt ist, und anderenfalls der rechte Zweig angestoßen. Insbesondere bei vielen ineinandergeschachtelten bedingten Ausdrücken oder Fallunterscheidungen ist eine graphische Darstellung dem textuellen Pseudocode überlegen. B EISPIEL 1.2 Es soll eine Funktion für die Ausführung der Aktionen »einzahlen« und »abheben« auf einem Bankkonto entworfen werden. Dazu wird zunächst die Schnittstelle der Funktion – also deren Ein- und Ausgabewerte – festgelegt. Das entsprechende Datenflußdiagramm zeigt Abbildung 1.6.

38

Kapitel 1

Algorithmen und Programmierung x

x