Leseecke

Algorithmische Methoden
Zahlen, Vektoren, Polynome

P. Kügler, W. Windsteiger
Birkhäuser Verlag, 2009, 160 Seiten, 18,90 €

ISBN 978-3-7643-8434-0

Das vorliegende Buch ist als einsemestrige Einführung in die algorithmische Mathematik konzipiert, gerichtet an Studierende vorwiegend des dritten Semesters. Kenntnisse über die Grundstrukturen von Analysis und linearer Algebra (speziell Zahlen, Vektoren, Polynome) werden also vorausgesetzt – eine kurze Übersicht des benötigten Stoffs findet sich gleichwohl zu Beginn des jeweiligen Kapitels – und weite Teile des Buches sind mit der Implementation dieser Strukturen und der zugehörigen Rechenoperationen auf dem Computer befasst.

Das Buch umfasst vier Kapitel. Das erste Kapitel führt die Grundbegriffe des Buches ein, auf eher informelle Weise und anhand von Beispielen, die dann in den folgenden Kapiteln wiederholt aufgegriffen werden. Bei diesen Begriffen handelt es sich einerseits um Grundkonzepte der Informatik (Schleifen, Rekursion), und andererseits um Kriterien für die Bewertung von Algorithmen, zum Beispiel (relative und absolute) Rundungsfehler, die Kondition eines Problems, Korrektheit, Stabilität (vorwärts und rückwärts), Komplexität. Die im weiteren Verlauf des Buches entwickelten Algorithmen werden anhand dieser Qualitätsmerkmale analysiert und Weiterentwicklungen daraus motiviert. Wie an den aufgezählten Kriterien zu erkennen ist, liegt der Schwerpunkt der Analyse auf numerischen Aspekten.

Die algorithmische Umsetzung wird in einem recht intuitiven Pseudocode dokumentiert. Sämtliche im Buch beschriebenen Algorithmen wurden sowohl in MATLAB als auch in Mathematica implementiert (als Vertreter vorwiegend numerischer beziehungsweise symbolischer Mathematik-Pakete); die Implementationen sind frei über das Internet verfügbar.

Kapitel 2 behandelt die algorithmische Behandlung von Zahlbereichen, von natürlichen über rationale zu den reellen Zahlen. Es werden jeweils das Problem der Darstellung dieser Zahlen im Rechner und die mittlerweile gebräuchlichen (IEEE-)Standardlösungen dafür diskutiert, gefolgt von der Implementation der Grundrechenarten. Dabei werden neben den naheliegenden auch effizientere Lösungen präsentiert (etwa: der Karatsuba-Algorithmus zur Multiplikation ganzer Zahlen oder Henrici-Algorithmen für die Addition und Multiplikation in ).

Kapitel 3 ist mit der Übertragung der Grundrechenarten auf Vektoren – genauer, Elementen von d – befasst. Die Implementation des Gram-Schmidt-Orthonormalisierungsverfahrens mitsamt einer Analyse des Stabilitätsverhaltens, schließt das Kapitel ab. Das letzte Kapitel behandelt Polynome, und dort speziell Algorithmen zur Polynomdivision mit Rest, den euklidischen Algorithmus, Polynomauswertung und -interpolation. Am Ende jedes Kapitels finden sich Übungsaufgaben zur Vertiefung des Stoffes.

Die Autoren sind sichtlich um eine lebendige und problemorientierte Darstellung ihres Stoffes bemüht. Der Großteil der im ersten Kapitel entwickelten Kriterien beschäftigt sich mit dem Grundproblem der numerischen Mathematik, nämlich der approximativen Behandlung (potenziell) unendlicher mathematischer Objekte mit endlichen Speicherplatz- und Zeitressourcen. Die Darstellung in diesem Kapitel springt zeitweise munter zwischen algorithmischen Konzepten (Schleifen, Rekursion, etc.), numerischen Begriffen (Fehlerabschätzungen, Maschinengenauigkeit) und mathematischen Sätzen, was zumindest beim Rezensenten eine gewisse Desorientierung zur Folge hatte.

Das Bemühen, die nötigen Begriffe anhand möglichst konkreter Beispiele einzuführen, ist hier erkennbar und an einigen Stellen auch durchaus erfolgreich. Zumindest im ersten Kapitel aber scheint mir dies durch einen Mangel an Struktur und Kohärenz (zu) teuer erkauft. Eine weitere in meinen Augen problematische strukturelle Entscheidung der Autoren betrifft die Darstellung der reellen Zahlen im Computer, die erst im zweiten Kapitel ausführlich behandelt wird. Viele der in Kapitel 1 entwickelten numerischen Begriffe lassen sich aber meines Erachtens wesentlich präziser beschreiben und motivieren, wenn man explizit auf diese Darstellung verweisen kann; zudem wäre der Leser dann bereits hinreichend für die zugrundeliegende Problematik sensibilisiert.

Rezension: Hartmut Führ, Aachen aus Computeralgebra-Rundbrief, Nr. 45 - Oktober 2009

Analysis
Band 2 - Ein Lehrbuch

E. Behrends
Vieweg Verlag, Wiesbaden, 2007, 2. Aufl., 378 Seiten, 27,99 €

ISBN: 3-834-80102-X

Warum besprechen wir im Computeralgebra-Rundbrief ein Analysis-Buch? Der Grund ist einfach: Dieses Buch unterscheidet sich von ähnlichen Büchern durch die Themenwahl. Natürlich werden auch in diesem Buch die üblichen Themen einer Analysis-II-Vorlesung behandelt: Funktionenräume (punktweise und gleichmäßige Konvergenz, Räume stetiger Funktionen, Vollständigkeit), Integration (Hauptsatz, parameterabhängige Integrale, L_p-Normen), Anwendungen der Integralrechung (Weierstraßscher Approximationssatz, Kurvendiskussion, Kurvenlänge, Laplacetransformation, Differentialgleichungen), Differentialrechung im Rⁿ (lineare Abbildungen, Differenzierbarkeit und partielle Ableitungen, Satz von Taylor, Extremwertaufgaben, Koordinatentransformationen, Satz über implizite Funktionen, Extremwerte mit Nebenbedingungen).

Aber das Neue an diesem Buch ist, dass zusätzlich Themen behandelt werden, die zum Themenkreis der Computeralgebra gehören und die bisher nicht in Lehrbüchern dieser Art zu finden sind, obwohl sie wichtige Ergänzungen zu den eingeführten Begriffsbildungen darstellen.

Sehr interessant ist Abschnitt 6.6: exp(x²) hat keine "einfache" Stammfunktion. In diesem Abschnitt werden Körper mit Differentiation eingeführt, es werden algebraische und transzendente Körpererweiterungen betrachtet. Dann wird der Satz von Liouville und Ostrowski präsentiert, der elementare Stammfunktionen elementarer Funktionen charakterisiert. Schließlich gelingt der Beweis, dass die Funktion exp(x²) keine elementare Stammfunktion haben kann.

Es wird also in diesem Lehrbuch der Risch-Algorithmus zur Integration elementarer Funktionen an einem speziellen Beispiel vorgeführt. Dies ist meines Erachtens sehr lobenswert, da sich durch die immer häufigere Nutzung von Computeralgebrasystemen jeder Mathematikstudierende die Frage stellen sollte, wie eigentlich ein Computeralgebrasystem integriert. Wenn auch der Risch-Algorithmus momentan nicht in jedem Computeralgebrasystem verfügbar ist, so lernt man in diesem Lehrbuch immerhin, wie es gemacht werden könnte. Dies zeigt insbesondere, dass eine fehlende Ausgabe bei einem Computeralgebrasystem bedeuten kann, dass die Rechnung bewiesen hat, dass eine Ausgabe eines bestimmten Typs gar nicht existiert.

In einem weiteren Abschnitt (Abschnitt 7.5) wird die Transzendenz der Eulerschen Zahl e und die Irrationalität der Kreiszahl π bewiesen. In diesem Zusammenhang wird die Approximierbarkeit rationaler Zahlen genau untersucht, wobei hier ebenfalls klassische Resultate der Computeralgebra einfließen.

Das Buch ist sorgfältig geschrieben, sollte in keiner Bücherei fehlen und kann jedem Studierenden ans Herz gelegt werden.

Rezension: Wolfram Koepf (Kassel) aus Computeralgebra-Rundbrief, Nr. 35 - Oktober 2004

ClassPad im Mathematikunterricht
Nach einer Idee von Wolfram Koepf

Matthias Bernhard, Christian Wesselsky
Vieweg+Teubner, Wiesbaden, 2009, 185 Seiten, 22,99 €

ISBN 978-38348-0840-0

Hier erschien ein Klassiker des Computereinsatzes im Mathematikunterricht – Wolfram Koepfs „DERIVE für den Mathematikunterricht“ von 1996 – unter Nutzung eines anderen Werkzeugs teilweise neu. Eingesetzt wurde jetzt der Taschencomputer ClassPad von CASIO. CASIO unterstützt seit Jahren die Herausgabe von Veröffentlichungen, die dem Computereinsatz im Unterricht Impulse geben (wie dies auch Mitbewerber tun). Nach Ansicht des Rezensenten stellt die Bernhard-Wesselsky-Koepf-Veröffentlichung in diesem Kontext eine interessante Bereicherung dar. Manche Anregung kann direkt und unmittelbar im Mathematikunterricht der gymnasialen Oberstufe umgesetzt werden, anderes ist eher in Projektphasen und systematisierenden Wiederholungen einsetzbar und wieder anderes erhöht „nur“ den Weitblick der unterrichtenden Lehrerinnen und Lehrer. All das ist wichtig und lohnenswert. Praktiker vor Ort benötigen Materialien, die auch helfen, ihre Werkzeugkompetenz weiterzuentwickeln und diese nicht umfassend voraussetzen. In der vorliegenden Veröffentlichung sind Erlauterungen und Abbildungen konkret auf den ClassPad zugeschnitten. Es gibt zahlreiche Übungsaufgaben einschließlich Lösungen. Eine beiliegende CD-ROM stellt diverse Programme und elektronische Arbeitsblätter bereit. Damit geht das vorliegende Buch über die Koepf-Veröffentlichung von 1996 hinaus.

Das Buch von 2009 besteht aus sechs Kapiteln. Kapitel 1 (Geometrie) thematisiert Berechnungen an Dreiecken und die näherungsweise Berechnung von . Im Kapitel 2 (Kegelschnitte) geht es erwartungsgemäß um Ellipse, Parabel, Hyperbel sowie um Transformationen und Polarkoordinatendarstellung. Die Autoren machen sich für die (Wieder-)Aufnahme des Themas „Kegelschnitte“ in den schulischen Mathematikunterricht stark (wie auch bereits Koepf 1996), und zwar wegen dessen wissenschaftlicher Bedeutung, und verweisen darauf, dass ClassPad helfen kann, das Thema relativ zügig durchzunehmen. Dem ist einerseits zuzustimmen, andererseits ist dem entgegenzuhalten, dass Schule kollabieren würde, wäre sie in der Pflicht, alles Wichtige zu thematisieren. Schule nimmt immer eine inhaltliche Auswahl vor (über die man sicher streiten kann) und sollte sich ansonsten auf das Gewährleisten eines dauerhaft verfügbaren Wissens und Könnens ihrer Absolventen konzentrieren. Im Kapitel 3 (Flächenberechnung) werden mehrere numerische Integrationsverfahren behandelt und grafisch dargestellt, es geht um das Volumen und den Oberflächeninhalt von Rotationskörpern. Kapitel 4 (Partielle Integration) beschreibt im Grunde genommen, wie gewisse Grenzen des ClassPad beim Bestimmen von Integralen überwunden werden können – und zwar mithilfe des ClassPad selbst. Besonders interessante Schwerpunkte des Kapitels 5 (Lineare Gleichungssysteme und Matrizen) sind die Kondition linearer Gleichungssysteme und die Hilbert-Matrix. Eines der Einstiegsbeispiele in das Kapitel (Preisermittlung von Waschpulver, Bohnen und Milch mit Hilfe eines linearen Gleichungssystems) dürften kritische Schülerinnen und Schüler als für sie persönlich irrelevant erkennen. Im anwendungsorientierten Kapitel 6 (Einfache Differentialgleichungen) geht es um die Methode Trennung der Variablen und um lineare Differentialgleichungen erster Ordnung. Die Schwingungsgleichung wird genauer untersucht; auf Anschaulichkeit wird viel Wert gelegt.

Das Buch stellt einen interessanten Beitrag dar, Computer im Mathematikunterricht intelligent einzusetzen. Vier Themen aus Koepfs Buch von 1996 wurden nicht übernommen. Hierzu muss in der Originalveröffentlichung nachgeschlagen werden.

Rezension: Michael Fothe (Jena) aus Computeralgebra-Rundbrief, Nr. 47 - Oktober 2010

Codierungstheorie
Algebraisch-geometrische Grundlagen und Algorithmen

W. Lütkebohmert
Vieweg Verlag, Braunschweig, Wiesbaden, 2002, 49,95 €

ISBN 3-528-03197-2

Vorliegendes Buch entstand aus einer einsemestrigen Vorlesung des Autors an der Universität Ulm. Sie war an Hörer mit Grundkenntnissen in Algebra gerichtet. Ziel der Vorlesung war es, den Studenten einen Rundblick über algebraisch konstruierte lineare Codes zu vermitteln. Das aus der Vorlesung mit demselben Ziel entstandene Buch wurde dann noch durch einige für die geometrischen Goppa-Codes notwendige Grundlagen aus der kommutativen Algebra und der Geometrie algebraischer Kurven angereichert.

Das Buch besteht aus drei Teilen. Der erste Teil mit den Kapiteln 1 bis 5 enthält die Elementare Codierungstheorie. Er umfasst allgemeine Standardresultate über lineare Codes inklusive der Behandlung einiger wichtiger Codeklassen wie Hamming- und Golaycodes, zyklische Codes mit BCH-Codes sowie Reed-Solomon-Codes, eingerahmt von Codekonstruktionen wie Spreizung und Verkettung sowie den klassischen Schrankensätzen: Singleton-Schranke, Plotkin-Schranke, Hamming- und Eliasschranke sowie als untere Schranke die Gilbert-Varshamov-Schranke. Wohl auf Grund fehlender Vorkenntnisse der Hörer auf dem Gebiet der Elementaren Zahlentheorie wurde auf die Behandlung der Quadratische-Reste-Codes verzichtet.

Der zweite Teil des Buches umfasst die für die Behandlung der geometrischen Goppa-Codes notwendigen geometrischen Grundlagen und besteht aus Kapitel 6.1, 8 und 7. Dabei enthält Abschnitt 6.1 eine kurze Zusammenfassung (ohne Beweise) der für die Einführung der Goppa-Codes notwendigen Sätze wie Satz von Riemann-Roch, Residuensatz und Hurwitzsche Relativgeschlechtsformel. Kapitel 8 enthält die dazugehörigen Beweise und die Konstruktion singularitätenfreier Modelle von Kurven. In Kapitel 7 werden speziell Kurven über endlichen Körpern studiert und die Riemannsche Vermutung für die zugehörigen Zetafunktionen bewiesen, was schließlich auf die für das Studium der Goppa-Codes unverzichtbaren Schrankensätze für die Anzahl der rationalen Punkte führt.

Der dritte Teil, bestehend aus den Kapiteln 6 und 9, enthält die angestrebten Resultate über geometrische Goppa-Codes. Nach der allgemeinen Einführung konzentriert sich der Autor auf die Konstruktion langer Codes, zuvor behandelt er aber noch zum Vergleich die klassischen Goppa-Codes, die auch schon im Rahmen der elementaren Theorie hätten vorgestellt werden können. Darauf folgt – und das ist sicher ein Höhepunkt dieses Buches – eine geometrische Konstruktion der 1996 von Garcia und Stichtenoth gefundenen Artin-Schreier-Türme, deren Punktanzahl die Drinfeld-Vladut-Schranke erreichen. Dies führt schließlich zu einem elementaren Beweis des Satzes von Tsfasman-Vladut-Zink, der besagt, dass man mit geometrischen Goppa-Codes die Gilbert-Varshamov- Schranke übertreffen kann. In meiner Vorlesung Galoistheorie im vergangenen Wintersemester habe ich diesen Teil noch durch einige allgemeine Strukturaussagen über selbstduale Codes und Automorphismen sowie durch die Untersuchung spezieller Codeklassen wie elliptische und hermitesche Codes ergänzt. (Entsprechende Resultate sind in den Büchern von Tsfasman-Vladut: Algebraic-Geometric Codes bzw. Stepanov Codes on Algebraic Curves: zu finden.) Schließlich enthält das letzte Kapitel 9 noch die Standardalgorithmen zur Codierung und Decodierung geometrischer Goppa-Codes mit praktischen Hinweisen zur Implementierung.

Am Ende des Buches hat der Autor in zwei Anhängen noch einige benötigte Resultate aus der Kommutativen Algebra und der Algebraischen Geometrie zusammengestellt, die zumeist in weiterführenden Algebra-Vorlesungen behandelt werden.

Insgesamt ist das Buch als Grundlage für Vorlesungen und auch zum Selbststudium geeignet, wünschenswerte Ergänzungen sind in der Besprechung der einzelnen Teile angemerkt. Es ist ein geometrisches Pendant zu dem inzwischen über 10 Jahre alten bewährten Buch von Stichtenoth: Algebraic Function Fields and Codes, das geometrische Goppa-Codes in der zahlentheoretischen Sprache algebraischer Funktionskörper behandelt (und ganz auf die Elementare Codierungstheorie verzichtet, wofür aber z.B. das Büchlein von Willems: Codierungstheorie herangezogen werden kann). Ein Pluspunkt der vorliegenden Ausgabe ist der auch für Studierende erschwingliche Preis. Bei den konkurrierenden Büchern von Tsfasman-Vladut und Stepanov vom Kluwer-Verlag stellt der Preis selbst für Fachbibliotheken gelegentlich ein Anschaffungshindernis dar.

Rezension: Bernd Heinrich Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 34 - März 2004

A History of Algorithms
From the Pebble to the Microchip

Chabert, Jean-Luc (Ed.)
Springer, Berlin-Heidelberg-New York, 1999, 100 Abb., pp. 524, 78,92$
(französische Originalausgabe bei Éditions Belin, Paris, 1994)

ISBN 3-540-63369-3

Bei diesem Buch handelt es sich um die englische Übersetzung einer von einer Gruppe von französischen Mathematik-Historikern herausgegebenen und kommentierten Sammlung von über 200 Original-Texten zur Geschichte der Algorithmen. Der zeitliche Rahmen reicht dabei von der sumerischen und ägyptschen Zahldarstellung und Arithmetik bis zur formalen Präzisierung des Algorithmenbegriffes in den 30-er Jahren des 20. Jahrhunderts. Thematisch werden weit überwiegend numerische Algorithmen behandelt, algorithmische Problemstellungen etwa der Geometrie, der Logik, Algebra oder der diskreten Mathematik werden nicht betrachtet, wie auch Fragen der Komplexität allenfalls am Rande oder implizit angesprochen werden. Das Buch erhebt, auch unter den Beschränkungen, die sich die Autoren bewusst auferlegt haben, weder einen Anspruch auf enzyklopädische Vollständigkeit, noch ist es eine Art Lehrbuch. Vielmehr will es ein historisches "mathematisches Lesebuch'' sein, mit dem die Autoren die Absicht verbinden, die sie mit "...which offers a different perspective by giving pride of place to algorithms'' formulieren.

Das Buch gliedert sich in 15 thematisch abgeschlossene Kapitel, wobei in einer Einleitung und in einem Vorspann zu jedem der ausgewählten Texte jeweils deren historische Bedeutung und ihre Beziehungen untereinander (wie auch Querbezüge zu anderen Kapiteln) erläutert werden. Auch die Stellung im Werk des jeweiligen Autors und Anmerkungen zu dessen Werk und Wirkung insgesamt werden knapp, aber prägnant, kommentiert. Viele der (ins Englische übertragenen) Original-Texte werden zusätzlich noch in der heutigen Sprache der Mathematik nach-formuliert und interpretiert, wo dies für das Verständnis geboten erscheint.

Die ersten drei Kapitel beschäftigen sich mit den elementaren arithmetischen Operationen, (etwas aus dem Rahmen fallend, aber deshalb nicht weniger interessant) der Konstruktion von magischen Quadraten, sowie der berühmten regula falsi. Das vierte Kapitel behandelt Euklid's Algorithmus, Bezout's Identität, Kettenbrüche und Sturm'sche Ketten, und berührt damit auch die Ursprünge der Computeralgebra. Die drei folgenden Kapitel behandeln iterative, approximierende Verfahren zur Berechnung von π, Newton's Tangenten- und Polygonmethoden, sowie weitere Verfahren zur Wurzelberechnung. Dieser Weg in die Numerik wird, nach einem arithmetischen Kapitel (Primzahlen, Faktorisierung), weiter verfolgt mit den Themen: Lösen linearer Gleichungssysteme, Interpolation, Approximation von Integralen, approximierende Lösungen von gewöhnlichen Differentialgleichungen, Funktionsapproximation, sowie Konvergenzbeschleunigung. Das letzte Kapitel fällt etwas aus diesem Rahmen, indem es die Bemühungen von Gödel, Church, Kleene, Turing und Post um eine präzise Formulierung des Algorithmenbegriffes nachzeichet. So historisch wichtig dies ist, man muss wohl doch feststellen, dass der Anstoss zu dieser Entwicklung nicht aus der numerisch orientierten Mathematik kam.

Schließlich enthält dieses Buch, neben weiterführenden Bibliographien zu den einzelnen Kapiteln, ein Sammlung von über 200 Kurzbiographien der zitierten Mathematiker.

Was interessiert nun aus der Sicht der Computeralgebra an einem Buch, dessen Inhaltsverzeichnis, wie die Autoren selbst schreiben, "... might suggest that this is a standard work of numerical analysis'' ? Nun, die historische Perspektive der Algorithmik ist für sich genommen m.E. schon eine spannende Sache, wenn sie für den Nicht-Philologen so konzise und gut lesbar aufbereitet dargeboten wird. Außerdem: das kürzlich erschienene Buch Modern Computer Algebra von J. von zur Gathen und J. Gerhard das wohl gute Chancen hat, sich als ein Referenztext für die Algorithmik der Computeralgebra zu etablieren, betont historische Bezüge in erfreulicher Weise. Das kommt in den Überschriften "Euklid'', "Newton'', "Gauss'', "Fermat'', "Hilbert'' und den Einleitungstexten zu den einzelnen Abschnitten deutlich zum Ausdruck. Es ist alles andere als ein Zufall, dass diese "Riesen'', ebenso wie beispielsweise Cauchy, Euler und Lagrange, dort wie in dem hier besprochenen Werk herausragende Rollen spielen.

Rezension: Volker Strehl (Erlangen) aus Computeralgebra-Rundbrief, Nr. 26 - März 2000