Leseecke

Modern Computer Algebra

J. von zur Gathen, J. Gerhard
Cambridge University Press, Cambridge, 1999, XIV + 754 Seiten, 109 $

ISBN 0-521-641764

Das Buch Modern Computer Algebra von J. von zur Gathen und J. Gerhard wird sich sicher zu einem Standardwerk über Computeralgebra entwickeln. Es ist sehr liebevoll aufbereitet mit historischen Einleitungen und Anmerkungen, vielen Beispielen, Bildern und Anwendungen sowie einer Vielzahl von Übungsaufgaben. Das Buch beginnt mit einer Sammlung motivierender Anwendungen, u.a. Modellierung von Cyclohexan-Molekülen und RSA-Verschlüsselung, die später nach der Entwicklung der nötigen Theorie wieder aufgegriffen werden.

Die Kapitel sind nach Wegbereitern der Computeralgebra benannt: Euklid, Newton, Gauß, Fermat und Hilbert. Das erste startet mit den grundlegenden Algorithmen zur Multiplikation und Division (mit Rest). Hauptthema aber ist der Euklidische Algorithmus in verschiedenen Spielarten und Anwendungen wie Kettenbrüche, Partialbruchzerlegung, Resultanten und Subresultanten etc. Alle diese Algorithmen wie auch die späteren sind durch sorgfältige Aufwandsanalysen begleitet. Flankiert wird dieses Kapitel durch Ausflüge in die Kalenderkorrektur, Tonsysteme und die Codierung mit BCH-Codes.

Hauptthema des zweiten Kapitels Newton ist die schnelle Arithmetik. Es beginnt mit einer Darstellung des Karatsuba-Algorithmus, der diskreten und schnellen Fouriertransformation bis zum Algorithmus von Schönhage und Strassen. Danach folgt eine Einführung des Newtonverfahrens mit Konvergenzverhalten (Julia-Mengen), Polynomwertberechnung und Interpolation. Anschließend wird mit dem schnellen Euklidischen Algorithmus das Hauptthema des ersten Kapitels weitergeführt. Es folgt ein Kapitel über schnelle Matrixmultiplikation mit dem (ersten) Algorithmus von Strassen sowie Verfahren für spezielle Matrizen, z. B. dünn besetzte (Wiedemann). Für die fortgeschritteneren und für die Komplexitätstheorie interessanten Algorithmen von Strassen und von Winograd wird auf die Literatur verwiesen. Beschlossen wird das Kapitel mit der stetigen Fouriertransformation mit Anwendung auf Bildkompression.

Das Kapitel Gauß ist der Faktorisierung von Polynomen gewidmet. Es enthält zunächst Algorithmen zur Faktorisierung von Polynomen über endlichen Körpern, z. B. die Algorithmen von Berlekamp und Cantor-Zassenhaus. Weiter die Henselsche Liftungsmethode in Polynomringen über p-adischen Zahlen, die zum Zassenhaus-Algorithmus zur Zerlegung ganzzahliger Polynome führt. Schließlich wird die Gitterbasisreduktion nach Lenstra-Lenstra-Lovasz beschrieben und mit deren Hilfe die Polynomialität der Primzerlegung ganzzahliger Polynome gezeigt. Als weitere Anwendungen werden u. a. simultane diophantische Approximationen behandelt und Angriffsmöglichkeiten auf Cryptosysteme vorgeführt.

Im Kapitel Fermat werden Primzahltest und Primzerlegungsalgorithmus für ganze Zahlen behandelt. Der erste Paragraph führt über das Studium von Carmichael-Zahlen zum Primzahltest von Solovay und Strassen. Der folgende enthält elementare Faktorisierungsalgorithmen wie Pollards - und (p-1)-Methode, Dixon's random square Methode (leider ohne Verfeinerung zum quadratischen Sieb) sowie eine Beschreibung der elliptischen Kurven-Methode von Lenstra. Beschlossen wird dieses Kapitel mit der Vorstellung von diversen Verschlüsselungssystemen, insbesondere dem auf obigen Resultaten aufbauenden RSA-Schema.

Das letzte Kapitel ist nichtlinearen algebraischen Gleichungssystemen gewidmet. Nach Einführung von Gröbnerbasen wird der Buchbergersche Algorithmus behandelt, und es werden geometrische Anwendungen gezeigt. Bei der Komplexitätsuntersuchung wird festgestellt, daß dieser grundlegende Algorithmus der Klasse der doppelt-exponentiellen Algorithmen angehört, wodurch seine Reichweite im allgemeinen sehr eingeschränkt ist. Es folgen Abschnitte über symbolische Integration, u. a. mit dem Algorithmus von Rothstein und Trager, und symbolische Summation mit dem Gosper-Algorithmus. Unter den Anwendungen sind u. a. Petri-Netze und automatisches Beweisen (von Formeln) zu finden. Schließlich wird zum Abschluß das Cyclohexan-Beispiel aus der Einführung ausführlich behandelt.

Das Buch deckt den Standardstoff einer ein- bis zweisemestrigen Vorlesung über Computeralgebra ab. Unter anderem wegen der vielen Beispiele, historischen Anmerkungen und Verweise ist es als Begleitlektüre sehr zu empfehlen. Da insbesondere die Themen der ersten beiden Kapitel sehr ausführlich behandelt und illustriert werden, ist dieses Buch auch zum Selbststudium geeignet. Es kann weiter Impulse für Vorlesungen an Fachhochschulen sowie für Arbeitsgemeinschaften an Schulen geben. Ich wünsche diesem Buch einen breiten Leserkreis.

Rezension: B. H. Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 27 - Oktober 2000

Graphs, Networks and Algorithms

Dieter Jungnickel
Springer, Berlin, pp. 589, 1999, 69,95 €

ISBN 978-3-642-32278-5

Das vorliegende Buch erschien nun als fünftes der Springer-Reihe Algorithms and Computation in Mathematics, welche von E. Becker, M. Bronstein, H. Cohen, D. Eisenbud und R. Gilman herausgegeben wird. Allerdings handelt es sich hierbei nicht um ein gänzlich neues Buch, sondern im wesenlichen um eine englische Übersetzung der dritten Auflage (1994) des in deutscher Sprache bei BI (inzwischen: Spektrum Akademischer Verlag) erschienenen Buchs Graphen, Netzwerke und Algorithmen.

Von einem algorithmischen Standpunkt aus gibt Graphs, Networks and Algorithms eine Einführung in die Grundbegriffe der Graphentheorie und der graphentheoretisch formulierbaren Probleme der kombinatorischen Optimierung. Jeder Algorithmus wird in Pseudo-Code dargestellt und auf seine asymptotische Komplexität hin untersucht. Der Autor macht klar, daß eine Komplexitätsanalyse von den verwendeten Datenstrukturen abhängig ist und bezieht diese immer in seine Ausführungen mit ein.

Die folgenden Themen werden behandelt: Kürzeste Wege, aufspannende Bäume, Greedy-Algorith-men, Flüsse, bipartite Graphen, Zirkulationen, Färbungen, Zusammenhangsfragen und Matchings. Das letzte Kapitel behandelt dann schließlich als typisches NP-vollständiges Problem das TSP (Traveling Salesman Problem = Problem des Handlungsreisenden). Hier werden sowohl praktikable Algorithmen zur Auffindung der besten Tour als auch solche zur Bestimmung guter Näherungslösungen diskutiert.

Das Buch enthält Lösungshinweise zu den zahlreichen Übungsaufgaben und einen ausführlichen Index. Es sollte (in der deutschen oder in der englischen Fassung) in keiner Bücherei fehlen.

Rezension: Wolfram Koepf (Leipzig) aus Computeralgebra-Rundbrief, Nr. 25 - Oktober 1999

Algebraic Complexity Theory

Bürgisser, P., Clausen, M., Shokrollahi, M.A.
Volume 315 der Grundlehren der mathematischen Wissenschaften, Springer-Verlag Berlin-Heidelberg-New York 1997, pp. 618, 105,35 $

ISBN 3-540-60582-7

Gegenstand des vorliegenden Buches ist die algebraische Komplexitätstheorie, d. h. "the study of the intrinsic algorithmic difficulty of algebraic problems within an algebraic model of computation''. Dies ist ein recht junges Gebiet der Mathematik, dessen Etablierung als eigenständiges Wissenschaftsgebiet gewöhnlich in die 50er und 60er Jahre datiert wird. Wie die Komplexitätstheorie insgesamt hat es seine Wurzeln einerseits im Bereich des Designs effektiver Algorithmen und andererseits in der Suche nach Invarianten, die die inhärente Schwierigkeit gewisser Probleme widerspiegeln. Es greift dazu anspruchsvolle Argumente aus vielen Bereichen der Mathematik auf, was eine einigermaßen umfassende monographische Darstellung ebenso wünschenswert wie schwierig macht.

Hier besteht in der vorhandenen Literatur noch eine Lücke, wie die Autoren unter Verweis auf eine Reihe von Übersichtsbeiträgen vermerken: "However, with the exception of the now classic monograph by Borodin and Munro (American Elsevier, 1975) a systematic treatment of this theory is not available.'' Das vorliegende Buch leistet einen wesentlichen Beitrag, diese Lücke auszufüllen. Es besteht aus 5 Teilen sowie einem informellen Einführungskapitel in die Fragestellungen der algebraischen Komplexitätstheorie.

Die 5 Teile behandeln im einzelnen folgende Aspekte:

Teil 1: Grundlegende Algorithmen (78 S.), führt asymptotisch schnelle Algorithmen zur Polynom-Multiplikation, zum Rechnen mit Potenzreihen (Algorithmen von Sieveking, Kung, Brent und Brent-Kung), zur GCD-Berechnung von univariaten Polynomen (Knuth-Schönhage) und zur Mehrfachevaluierung (Horowitz) ein und diskutiert Meyer auf der Heides Ergebnis zum Rucksackproblem.

Teil 2: Elementare untere Schranken (66 S.), führt das im Weiteren verwendete algebraische Berechnungsmodell (straight line programs und Berechnungsbäume) ein und beschreibt verschiedene Techniken zur Herleitung elementarer (d. h. linearer) unterer Komplexitäts-Schranken (Transzendenzgrad, Substitutionsmethode, Strassens Vermeidung von Divisionen, Derivationen).

Teil 3: High Degree (132 S.), zeigt, wie Konzepte der algebraischen Geometrie und der algebraischen Toplogie eingesetzt werden können, um nichtlineare untere Schranken herzuleiten.

Einen großen Teil des Buches nimmt Teil 4: Low Degree (236 S.) ein, in dem sehr detailliert Fragen der Matrixmultiplikation und der bilinearen Komplexität behandelt werden und der von den Autoren als "book within the book'' bezeichnet wird.

Das Buch beschließt ein kurzer Teil 5: Vollständigkeitsprobleme (32 S.), in dem Valiants nicht-uniformes algebraisches Analogon zur Problematik P vs. NP diskutiert wird.

Das Buch ist sehr ausführlich in der Argumentation und mit einer Vielzahl von Übungsaufgaben unterschiedlichen Schwierigkeitsgrads untersetzt. Es ist damit sowohl als Referenz als auch als Lehrbuch vorzüglich geeignet.

Vergleicht man es mit den in der Einleitung genannten Übersichtsbeiträgen, so fällt die starke Affinität zu Strassens Kap. 11 im Handbook of Theoretical Computer Science, Elsevier 1990, ins Auge, dessen Einfluß die Autoren auch dankend vermerken. Damit bleiben trotz der Dicke des Buches eine Reihe wichtiger Entwicklungen, wie sie etwa in v.z.Gathens Beitrag in Ann. Rev. Comp. Sci. 3 (1988), 317-344, für andere algebraische Teilgebiete (Polynomfaktorisierung, Permutationsgruppen) aufgerissen werden, außer Betracht.

Man mag eine solche Beschränkung mit Hinweis auf eben diese Dicke des Buches hinnehmen. Besonders bedauert es der Referent allerdings, daß dabei auch das ganze Thema der parallelen algebraischen Komplexität ausgeklammert wurde, die ebenfalls auf wichtige Ergebnisse verweisen kann. Eine wünschenswerte monographische Aufarbeitung dieser Ergebnisse, die bereits im Buch von Borodin/Munro begonnen wurde, könnte nahtlos an den entwickelten Begriffsapparat anschließen und hätte kaum einer Aufstockung des verwendeten mathematischen Apparats bedurft.

Rezension: Hans-Gert Gräbe (Leipzig) aus Computeralgebra-Rundbrief, Nr. 21 - Oktober 1997

Algorithmische Konzepte der Informatik
Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kryptographie

J. Hromkovic
B.G. Teubner Stuttgart, Leipzig, Wiesbaden, 2001, 286 Seiten, 28,00 €

ISBN 978-3-322-91131-5

In den letzten Jahren ist die Zahl der auf dem Büchermarkt verfügbaren Bücher zum Gegenstand der Theoretischen Informatik erfreulich angewachsen. Allen ist das Ziel gemeinsam, in die Hauptthemen der Theoretischen Informatik einzuführen und für die zum festen Bestandteil eines jeden Informatikcurriculums gehörenden Lehrveranstaltungen zur Theoretischen Informatik die notwendige Literaturbasis zu schaffen. Dabei fällt auf, dass in jüngster Zeit einige Autoren neue Wege gehen, den nicht leicht zu vermittelnden Stoff in einer Weise aufzubereiten, die es den im allgemeinen nicht sonderlich an theoretischen Konzepten interessierten Studierenden leichter macht, Sinn, Zweck und Nutzen theoretischer Konzepte zu erfassen, Aussagen und Beweisgänge auch ohne allzu tiefes vorausgehendes Studium der Mathematik zu verstehen und sich für wissenschaftlich exaktes Arbeiten und Anwenden zu motivieren.

Mit seinem Buch ”Algorithmische Konzepte der Informatik“ gelingt J. Hromkovic ein ausgezeichneter Beitrag zum Erreichen dieser Ziele. Während sich andere bewährte Einführungen in die Theoretische Informatik dominierend auf den klassischen Stoff der Berechenbarkeit, der Theorie der formalen Sprachen und der abstrakten Komplexitätstheorie orientieren, trägt Hromkovic verstärkt der Tatsache Rechnung, dass in den letzten Jahrzehnten die Theorie immer stärker auf die Bedürfnisse der Praxis eingegangen ist und über die Fülle neuer faszinierender Anwendungen auch neue Möglichkeiten entstanden sind, die Erkenntnisse der Theoretischen Informatik anschaulich zu vermitteln und bei den Studierenden die Motivation für dieses Studienfach zu erhöhen.

Wie der Titel des Buches richtig verspricht, bilden die algorithmischen Aspekte der Theoretischen Informatik den Hauptinhalt dieser Einführung. In einem einleitenden Kapitel unternimmt der Autor den interessanten Versuch, Studierenden das Beschäftigen mit dem Gegenstand der Theoretischen Informatik schmackhaft zu machen. Acht Kapitel sind den Themen Sprachen, Endliche Automaten, Turingmaschinen, Berechenbarkeit, Komplexitätstheorie, Algorithmik für schwere Probleme, Randomisierung und Kommunikation, Kryptographie gewidmet. Die Darstellung des Stoffes ist übersichtlich und gut verständlich. Dabei wird ein ausgewogenes Verhältnis zwischen der Prägung des intuitiven informalen Verständnisses und der präzisen Formalisierung und Beweisführung erreicht. Die Anzahl an benutzten Begriffen und Definitionen wird bewusst minimal gehalten. Jedes Kapitel ist mit einer relativ umfangreichen Zahl didaktisch gut ausgewählter Übungsaufgaben angereichert. Die am Schluss eines jeden Kapitels in einem gesonderten Abschnitt vorgenommene Zusammenfassung reflektiert den Studierenden noch einmal übersichtlich den besprochenen Stoff in seinem Zusammenhang.

Bleibt zu hoffen und zu wünschen, dass dieses Buch unter den Studierenden eine große Verbreitung findet und dann den erhofften leichteren und verständlicheren Zugang zum anspruchsvollen Lehrstoff der Theoretischen Informatik bringt.

Rezension: Karl Hantzschmann (Rostock) aus Computeralgebra-Rundbrief, Nr. 32 - März 2003

Arithmetik
Aus der Reihe The Art of Computer Programming

Donald E. Knuth
Springer-Verlag, Berlin, Heidelberg, New York, 538 Seiten, 2001, 538 Seiten, 52,95 €

ISBN 3-540-66745-8

Dies ist die deutsche Version von Kapitel IV des Standardwerkes "The Art of Computer Programming'' von Donald E. Knuth. Sie wurde von R. Loos in die deutsche Sprache übersetzt. Damit erhalten auch Studenten aus dem deutschsprachigen Raum, die mit der englischen Sprache Probleme haben, einen Zugang zu dieser wichtigen Lektüre.

Wie der Titel Arithmetik schon ausdrückt, behandelt das vorliegende Werk die vier Grundrechenoperationen für Zahlen, Polynome und - knapp gehalten - Potenzreihen. Das Werk beginnt mit einem Abschnitt über Stellenwertsysteme und deren geschichtliche Entwicklung. Es folgen Untersuchungen über Gleitkommaarithmetik und deren Genauigkeit bei einfacher und mehrfacher Präzision. Danach werden Algorithmen für Rechnungen mit beliebig großen ganzen Zahlen vorgestellt. Im weiteren wird generell die Arithmetik für ganze und rationale Zahlen detailliert abgehandelt. Knuth legt dabei unter anderem Wert auf die Berechnung des größten gemeinsamen Teilers zweier Zahlen und analysiert den Euklidischen Algorithmus. Danach wendet er sich Faktorisierungsmethoden und Primzahltests zu. Im anschließenden Abschnitt geht er auf Polynomarithmetik ein. Auch hier werden Faktorisierungsmethoden vorgestellt. Während das Verfahren von Berlekamp zur modularen Faktorisierung eingehend besprochen wird, werden die Anwendungen auf Faktorisierungen von Polynomen mit ganzen Koeffizienten eher stiefmütterlich behandelt. Insbesondere verzichtet er darauf, den berühmten LLL-Algorithmus einzuführen. Dafür gibt es einen Unterabschnitt über die Berechnung von Polynomwerten an vorgegebenen Stellen. Den Abschluss bildet ein kurzer Abschnitt über die Arithmetik von Potenzreihen.

Der Leser findet in diesem Buch wertvolle Hinweise für die Entwicklung von Algorithmen und deren Implementierung, soweit sie mit der Arithmetik der betrachteten Objekte zu tun haben. Einige Beachtung finden auch Implementierungsfragen auf unteren Ebenen, wo wenige Zeilen Assembler Code erhebliche Beschleunigung bringen können. Von Knuth wird hierfür ein fiktiver MIX-Rechner benutzt.

Hervorzuheben sind die reichhaltigen Literaturverweise (bis 1998) und die vielen interessanten und unterschiedlich schwierigen Übungsaufgaben, die von Standardstoff bis zu Forschungsprojekten reichen, wobei der Schwierigkeitsgrad stets recht exakt angegeben wird. Entsprechend viele Seiten des Buches gehen auf die Lösungen ein oder geben Anleitungen. Obwohl die ursprüngliche Fassung 25 Jahre alt ist, hat das Werk wenig von seinem Charme verloren, zumal es Literaturhinweise auf wichtige neuere Entwicklungen gibt. Dem Unterfangen des Übersetzers, dieses Werk deutschsprachiger Leserschaft näher zu bringen, wünsche ich viel Erfolg.

Rezension: Michael Pohst (Berlin) aus Computeralgebra-Rundbrief, Nr. 30 - März 2002