Buchbesprechung

T. E. Shoup Numerische Verfahren

Carl Hanser Verlag, München

1. Auflage 1985
   225 Seiten DM 48,-

Das Buch beschäftigt sich ausschließlich mit Lösungsverfahren für algebraische und transzendente Gleichungen (z. B. Newton-Methode), Gleichungssystemen (Gauss-Jordan/Seidel-Verfahren), Eigenwertproblemen (Tri-diagonalmatrix, Hessenbergform), Differentialgleichungen, Interpolation (linear, Lagrange, iterative, invers), Kurvenanpassung (Methode der kleinsten Quadrate, Spline-Funktion), Differentiation (numerisch) und Integration (Simpson, Romberg, Gauss). Damit ist ein breites Spektrum für den technischwissenschaftlichen Bereich abgedeckt.

Alle Programme sind in BASIC geschrieben und deshalb einfach auf andere Sprachen anzupassen. Viele würden sich vielleicht eine andere Programmiersprache wünschen, doch die Algorithmen sind nicht so kompliziert oder lang, daß dies ins Gewicht fallen würde.

Jedes Verfahren wird leichtverständlich erläuten und von Herleitungen und Grafiken unterstützt. Ein konkretes Beispiel mit Zahlenwerten zum Überprüfen des Programms fehlt ebenfalls nicht.

Das Buch behandelt in lockerer Form wichtige Verfahren, ohne dabei den Leser zu überfordern oder zu langweilen.

(mn)

Niklaus Wirth: Algorithmen und Datenstrukturen

B. G. Teubner, Stuttgart
3. überarb. Aufl. 1983 (in Pascal)
4. neubearb. Aufl. 1986 (in Modula-2) ca. 300 Seiten DM 38,-

Das bereits 1975 erschienene Buch von Nikiaus Wirth zählt, in Bezug auf dynamische Datenstrukturen und Sortieralgorithmen, zu einem der Standardwerke. Bis zur dritten Auflage sind die Beispiele dabei ausschließlich in PASCAL formuliert, die gerade erschienene 4. Auflage dagegen in MODULA-2. Sie wurde nochmals erweitert, entspricht jedoch im wesentlichen der hier vorliegenden Version.

Das Buch beginnt mit einer Einführung in die grundlegenden Datenstrukturen ARRAY, (varianter) RECORD, SET und (sequentielle) FILES.

Diese werden im vierten Kapitel noch um die erheblich leistungsfähigeren, dynamischen Strukturen erweitert. Dazu gehören Zeiger, Lineare Listen, Schlüssel-Transformationen und vor allem die Baumstrukturen (Binär- und Vielweg-bäume). Baumstrukturen sind zum Sortieren und nachfolgenden Suchen sehr gut geeignet, wobei der Optimierung und der Erstellung von ausgeglichenen Bäumen eine besondere Bedeutung zukommt. Das Buch liefert die hierfür erforderlichen Pascalprogramme und außerdem die Routinen zum Löschen, Einfügen und Durchsuchen. .

Die z. T. recht komplexen und damit auch komplizierten Verfahren werden anhand von etlichen Diagrammen verdeutlicht.

Im Kapitel über das Sortieren, wird eine große Anzahl von Strategien beschrieben und deren Vor- und Nachteile erläutert. Die Spanne reicht vom einfachen Bubble- und Shakersort über direktes/binäres Einfügen, direkte Auswahl, Shell- und Heap- und Merge-sort bis zum schnellen Quicksort (rekursiv und iterativ). Jeder Algorithmus wird ausführlich vorgestellt, wozu auch ein Probelauf und eine Berechnungsformel für die Anzahl der Operationen gehört. Den Abschluß bildet ein Zeitvergleich der vorgestellten Verfahren unter verschiedenen Bedingungen: geordnet, zufällig, umgekehrt sortiert und bei mächtigeren Daten. Der zweite Teil des Sortierkapitels behandelt Verfahren, die benötigt werden, wenn die Datenmenge nicht in den Häuptspeicher des Rechners paßt. Vorgestellt werden: Direktes Mischen, natürliches Mischen, ausgeglichenes n-Weg-Mischen und das Mehr-phasen-Sortieren.

Die 4. Auflage enthält, als Ergänzung zu den Sortierverfahren, noch verschiedene, schnelle Suchalgorithmen (Binäre-und Tabellensuchen, Mustersuchen in Zeichenketten, Knuth-Morris-Pratt- und Boyer-Moore Algorithmus), die zur Zeit der Erstauflage noch weitgehend unbekannt waren.

Das letzte Kapitel ist rekursiven Programmen gewidmet. Hier werden u.a. zwei graphisch interessante Routinen erklärt: die überlagerten Hubert- und Sierpinsi-Kurven. Auch das bekannte Acht-Damen-Problem wird mit Hilfe einer rekursiven Prozedur gelöst.

Jedes Kapitel wird mit einer Anzahl von Aufgaben abgeschlossen, die in erster Linie als Anregung für eigene Programmierübungen dienen sollen, denn die Lösungen werden nicht angegeben.

„Algorithmen & Datenstrukturen" ist ein wirklich interessantes Buch, das dem interessierten Programmierer eine wertvolle Hilfe und Programmbibliothek (Sortierprogramme, Baumstrukturen) ist. (mn)