Leseecke

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

Computational Commutative Algebra 1

M. Kreuzer, L. Robbiano
Springer-Verlag, Berlin, Heidelberg, New-York, 2008, 44,90€

ISBN 3-540-67733-X

Bei dem Buch Computational Commutative Algebra 1 handelt es sich um eine elementare Einführung in die kommutative Algebra mit CoCoA-Tutorials. Es besteht aus den drei Kapiteln Grundlagen (Polynomarithmetik), Gröbnerbasen und Erste Anwendungen, gefolgt von drei Anhängen über Inbetriebnahme und Programmierung mit CoCoA sowie einer kurzen Übersicht über vorhandene CoCoA-Programme.

Im ersten Kapitel werden Polynomringe über einem Körper behandelt. Themen sind eindeutige Primfaktorzerlegung (ohne Algorithmen, aber mit Berlekamp-Algorithmus in einem Tutorial), Monomordnungen, Division mit Rest und ein Abschnitt über homogene Polynome unter Einschluss der graduierten Version des Nakayama-Lemmas.

Das zweite Kapitel Gröbnerbasen beginnt mit einer Einführung von Polynomidealen und -moduln inklusive Syzygien. Es folgen Definition und Charakterisierung von Gröbnerbasen, der Eindeutigkeitssatz für reduzierte Gröbnerbasen sowie der Buchbergersche Algorithmus. Als Anwendungen werden konstruktive Beweise für den Hilbertschen Basissatz und Nullstellensatz gegeben.

Im dritten Kapitel Erste Anwendungen werden elementare Konstruktionsaufgaben aus der kommutativen Algebra mit Gröbnerbasentechniken gelöst. Dazu gehören die Berechnung des Syzygienmoduls mit Test auf Modulzugehörigkeit. Es folgt ein Abschnitt über elementare Modul- und Idealoperationen wie Berechnung des Durchschnitts, von Quotienten und Annullatoren. Der nächste Abschnitt über Modulhomomorphismen enthält die Berechnung von Kern und Bild von Homomorphismen sowie die Berechnung des Homomorphismenmoduls. Weitere behandelte Themen sind Lokalisierung und Saturierung mit Test auf Radikalzugehörigkeit und die Untersuchung von Algebra-Homomorphismen mit Transzendenztest bzw. Berechnung von Minimalpolynomen. Der letzte Abschnitt enthält schließlich die Lösung von Polynomgleichungssystemen und Berechnung von Radikalidealen im Falle nulldimensionaler Lösungsmengen (bzw. Ideale) über einem vollkommenen Körper.

Wichtige weitere Themen einer Vorlesung über algorithmische kommutative Algebra wie Radikalberechnung im allgemeinen Fall, Normalisierung, Primärzerlegung, die Berechnung von Dimension und Hilbertfunktionen sowie Anwendungen in der Algebraischen Geometrie bleiben weitgehend ausgeklammert.

Das Buch ist in einem aufmunternd lockeren Stil geschrieben und für Studierende gut zum Selbststudium geeignet. Der präsentierte Stoff wird durch viele Beispiele und Übungsaufgaben (teilweise mit Anleitungen im Anhang) ergänzt. Weiter sind jedem Abschnitt sorgfältig ausgearbeitete Tutorials angefügt, die zur Benutzung von Computeralgebrasystemen, insbesondere CoCoA, anregen sollen.

Das Buch kann aber auch unabhängig von CoCoA als Begleittext zu Vorlesungen empfohlen werden. Wie oben angedeutet, hätte sich der Referent allerdings eine etwas breitere Palette von behandelten Themen gewünscht. Dieses Manko wird aber möglicherweise mit dem geplanten zweiten Band behoben.

Rezension: B. Heinrich Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 28 - März 2001