Leseecke

Symbolic Asymptotics

J. R. Shackell
Springer Verlag, Berlin, Heidelberg, New York, 243 Seiten, 59,95 €

ISBN 3-540-21097-0

This book is the first text book about symbolic asymptotics, written by one of its major contributors. It deals with the question to calculate limits and asymptotic expansions of real functions symbolically.

The book contains the following chapters:
Chapter 1: Introduction. In the introduction the author explains the concepts of towers of fields, explog-functions etc., and shows by examples which algorithmic problems occur.
Chapter 2: Zero Equivalence. In this chapter zero equivalence of constants and of functions is considered. Schanuel’s Conjecture and Richardson’s Uniformity Conjecture are touched. Algorithms and examples are given. Modular methods and Hensel lifting are discussed. Systems of partial differential equations and differential ideals are introduced.
Chapter 3: Hardy Fields. The concept of Hardy fields is introduced, their closure properties and their relation to algebraic differential equations is discussed. Further properties of Hardy fields are investigated.
Chapter 4: Output Data Structures. Here asymptotic power series as well as multiseries which enable the use of different scales are introduced. Exponentials, logarithms, powers etc. of multiseries are treated. Finally the algebra of star products is investigated. Star products are generalizations of nested expansions and multiseries.
Chapter 5: Algorithms for Function Towers. To compute limits and asymptotic expressions, one regards functions as elements in a tower of Hardy fields

Problems that occur in this treatment are discussed, and an algorithm for the exp-log case is given. The exp-log case is generalized by adding exponentials, integrals, algebraic entensions etc. Finally Cartesian representations are studied.
Chapter 6: Algebraic Differential Equations. Nested forms of Hardy field solutions of algebraic differential equations are discussed, and an algorithm to detect such solutions is given. Theorems about the number of cases and ideas to reduce the complexity are given. Finally sparse differential equations are considered.
Chapter 7: Inverse Functions. Until recently it was unknown whether the inverse of an exp-log function is necessarily asymptotic to an exp-log function. That this is not the case was discovered by Shackell in 1993. However, inverses of Hardy field members that tend to infinity belong to a Hardy field, again. In this chapter the inversion of nested expansions is covered, and multiseries of inverse functions are discussed.
Chapter 8: Implicit Functions. In this chapter asymptotic series of implicit functions are considered.
Chapter 9: Star-Product Expansions. The rewriting of exp-log expressions into standard star expansion form is discussed. Growth classes in Hardy fields are introduced.
Chapter 10: Oscillating Functions. Oscillating functions are never members of Hardy fields. Hence this chapter deals with different methods for this purpose. The book finishes with an example.

Many algorithms and examples are discussed in the book. I would have been interested to read in detail which of these algorithms are implemented in an existing computer algebra system like Maple. It is not clearly stated which parts of the book are covered by Maple’s asympt command. However, on pp. 91–92 the author informs about Dominik Gruntz’s limit implementation in Maple, and announces a current update process of asympt by Bruno Salvy.

The book contains a wealth of information on symbolic asymptotics. It fills a gap in the literature and should be found in every library. The user of a computer algebra system who is interested to understand the output of a command like Maple’s asympt finds much interesting information. Actually many users might not even be aware about the complexity of such a command.

Rezension: Wolfram Koepf (Kassel) aus Computeralgebra-Rundbrief, Nr. 37 - Oktober 2005

Elliptische Kurven in der Kryptographie

A. Werner
Springer Verlag, New York, Berlin, Heidelberg, 2002, 22,95 €

ISBN 3-540-42518-7

Das vorliegende Buch entstand aus einer zweisemestrigen Vorlesung über Kryptographie und richtet sich an Mathematik- und Informatikstudenten ab dem fünften Semester. Der Text beginnt mit einem einleitenden Kapitel über RSA und das Problem des diskreten Logarithmus (DL). Im zweiten Abschnitt werden affine und projektive Kurven eingeführt und der Begriff der Singularität erklärt. Anschließend werden elliptische Kurven, deren Normalformen in verschiedenen Charakteristiken und die Addition von Punkten behandelt. Das dritte Kapitel umfaßt den Schoof-Algorithmus zur Bestimmung der Anzahl von Punkten elliptischer Kurven über endlichen Körpern sowie einen Abschnitt über supersinguläre elliptische Kurven. In den nächsten beiden Kapiteln geht es um allgemeine und spezielle Verfahren für die Lösung des DL-Problems sowie um praktische Konsequenzen. Dort findet sich außerdem die Behandlung digitaler Signaturen. In einem Anhang werden die benötigten Vorkenntnisse aus der Algebra und Zahlentheorie zusammengestellt.

Bereits im Vorwort wird darauf hingewiesen, daß gelegentlich Resultate ohne Beweis zitiert werden, um den Text für Studenten mit Grundkenntnissen in linearer Algebra und Algebra zugänglich zu machen. Diese Lücken finden sich vor allem im dritten und vierten Kapitel bei der Behandlung des Schoof-Algorithmus und der speziellen DL-Lösungsverfahren (für supersinguläre und anomale Kurven).

Wir haben im vergangenen Semester ein Proseminar zum Thema Kryptographie angeboten und dabei zunächst die Texte von Buchmann, Einführung in die Kryptographie und Werner als Literatur benutzt. Der Inhalt des einleitenden Kapitels und die allgemeinen Methoden zum DL-Problem sowie der Indexkalkül bilden die Schnittmenge der beiden Texte. Auf Wunsch der Studenten haben wir bei der Vorbereitung der Vorträge über elliptische Kurven andere Quellen hinzugezogen, um einige der Stellen zu ergänzen, an denen in dem vorliegenden Text nur Skizzen oder Ideen gegeben werden (soweit das im Rahmen eines Proseminares möglich war).

Meiner Meinung nach geht das Konzept der Autorin nicht ganz auf - wenn zu vieles nur oberflächlich behandelt werden kann, ist es schwierig, Verständnis für die Thematik zu gewinnen. Für eine Vorlesung (bei der den Studenten die Möglichkeit zum Nachfragen gegeben ist) eignet sich dieser Stil womöglich besser als für ein Buch, das auch zum Selbststudium genutzt werden soll. Dennoch: Für alle, die zunächst nur einen Überblick suchen und sich an den oben genannten Lücken nicht stören, ist der Text durchaus nützlich, da die behandelte Aspekte ausführlich und leicht verständlich erklärt werden.

Rezension: Julia Hartmann (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 34 - März 2004

Mathematik für Informatiker
Grundlagen und Anwendungen

Werner Struckmann, Dietmar Wätjen
Elsevier Spektrum Akademischer Verlag, 564 Seiten, 2016, 2. Aufl. , 29,99 €

ISBN: 3-6624-9869-3

Beurteilung

Anliegen des Buches ist es, den Stellenwert der Mathematik für die Informatik deutlich zu machen. Dies soll erreicht werden, indem die mathematischen Sachverhalte nicht nur präzise dargestellt, sondern auch viele ihrer Anwendungen in der Informatik ausführlich beschrieben werden.
Neben der Auffrischung der Kenntnisse in den Grundthemen der Analysis und Linearen Algebra behandelt dieses Buch hauptsächlich den Stoff des zweiten oder späterer Studienjahre. Zu jedem Kapitel gibt es Übungsaufgaben, zu welchen es die Lösungen im Internet gibt.
Die einzelnen Kapitel sind sehr ausführlich und mit vielen Beispielen. Das Buch ist daher zu empfehlen, wobei Studienanfänger sich vielleicht ein wenig überfordert vorkommen könnten, aber es ist ja auch ausdrücklich für spätere Semester konzipiert.

Inhalt

1. Logik
   (Aussagenlogik, Prädikatenlogik, Logik und Programmierung, Aufgaben)
2. Mengen, Relationen und Funktionen
   (Mengen, Relationen, Partielle und totale Funktionen, Berechenbarkeit und funktionale Programmierung, Aufgaben)
3. Zahlen
   (Zahlenmengen, Mächtigkeit von Mengen, Darstellung von Zahlen, Aufgaben)
4. Komplexität von Algorithmen
   (Folgen und Reihen, Stetige und differenzierbare Funktionen, Größenordnungen von Funktionen, Rekurrenzgleichungen und erzeugende Funktionen, Matroide, Aufgaben)
5. Graphentheorie
   (Grundbegriffe der Graphentheorie, Speicherung von Graphen, Bäume und Wälder, Planare Graphen, Euler'sche und Hamilton'sche Graphen, Färbung von Graphen, Matchingprobleme, Aufspannende Bäume und Wälder, Aufgaben)
6. Grundlagen der Zahlentheorie
   (Teilbarkeit und euklidischer Algorithmus, Primzahlen, Modulare Arithmetik, Bestimmung des modularen Inversen, Das RSA-Public-Key-Kryptosystem, Das Lösen von modularen Gleichungen und der Chinesische Restsatz, Aufgaben)
7. Halbgruppen und Monoide
   (Die grundlegenden Definitionen, Freie Halbgruppen und Monoide, Anwendungen in der Informatik, Aufgaben)
8. Gruppen
   (Einführung in Gruppen, Permutationsgruppen, Untergruppen, Zyklische Gruppen, Das ElGamal-Verfahren, eine Anwendung, Normalteiler, Faktorgruppen und direkte Produkte, Homomorphismen von Gruppen, Aufgaben)
9. Ringe und Körper
   (Einführung in Ringe und Körper, Ideale und Ringhomomorphismen, Euklidische Ringe und Hauptidealringe, Nullstellen von Polynomen, Endliche Körper, Aufgaben)
10. Kurzdarstellung der Linearen Algebra und einigen Anwendungen
    (Vektorräume und Basen, Matrizen und lineare Abbildungen, Lineare Gleichungssysteme, Determinanten, Eigenwerte und Diagonalisierung von Matrizen, Euklidische Vektorräume, Anwendungen im Information Retrieval, Singulärwertzerlegung, Anwendungen in der Computergraphik, Lineare Codes, Secret-Sharing-Verfahren, Allgemeine Algebra, Aufgaben)
11. Wahrscheinlichkeitstheorie
    (Abzählprobleme, Wahrscheinlichkeiten, Diskrete Zufallsvariable, Integralrechnung, Stetige Zufallsvariable, Stochastische Prozesse, Aufgaben)

• Literaturverzeichnis
• Index

Mathematik kompakt
für Ingenieure und Informatiker

Stry, Schwenkert:
Springer Verlag, 486 Seiten, 2. Auflage , 24,95 EUR

ISBN: 3-540-23434-9

Beurteilung

Das Buch deckt den relevanten Lehrstoff der Grundvorlesungen Mathematik für Informatiker und für die technischen Studiengänge in nur einem Band ab. Es orientiert sich an der praxisbezogenen Vorgehensweise von Fachhochschulen. Beispiele aus Technik und Wirtschaft sollen den Text erläutern oder dienen der Übung. Besonderer Wert wird auf die Anschaulichkeit und stetige Motivation gelegt.
Übungen gibt es sowohl im laufenden Text, als auch am Ende der Kapitel, jeweils mit den zugehörigen Lösungen. Außerdem gibt es am Ende eines jeden Kapitels Anwendungsbeispiele, einen kurzen Verständnistest und eine ausführlichere Zusammenfassung des behandelten Stoffs, insbesondere der wichtigsten Definitionen, Sätze und Beispiele.

Inhalt

1. Mathematische Grundbegriffe
   (Einführung, Mengen, Zahlen, Kombinatorik, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
2. Folgen und endliche Summen
   (Einführung, Folgen und ihre Eigenschaften, Endliche arithmetische und geometrische Folgen und Reihen, Vollständige Induktion, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
3. Funktionen
   (Einführung, Grundbegriffe, Grenzwerte bei Funktionen, Stetigkeit, Die elementaren Funktionen, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
4. Algebra
   (Einführung, Relationen, Gruppen, Ringe und Körper, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
5. Lineare Algebra
   (Einführung, Grundbegriffe, Das Skalarprodukt, Matrizen, Die Determinante, Lineare Gleichungssysteme, Die Inverse einer Matrix, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
6. Differentialrechnung
   (Einführung, Der Ableitungsbegriff, Ableitungen elementarer Funktionen und höhere Ableitungen, Ableitungstechniken, Extrema und Kurvendiskussion, Numerische Lösung nichtlinearer Gleichungen, Taylorpolynome, Funktionen in mehreren Veränderlichen, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
7. Reihen
   (Einführung, Konvergenz unendlicher Reihen, Konvergenzkriterien, Potenzreihen und Taylorreihen, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
8. Integration
   (Einführung, Grundbegriffe, Integrationstechniken, Uneigentliche Integrale, Mehrfachintegrale, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
9. Die komplexen Zahlen
   (Einführung, Der Körper der komplexen Zahlen, Die Gauß'sche Zahlenebene, Algebraische Gleichungen, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
10. Differentialgleichungen
    (Einführung, Grundbegriffe, Lösungstechniken, Lineare Differentialgleichungen, Lineare Differentialgleichungen mit konstanten Koeffizienten, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)
11. Wahrscheinlichkeitstheorie und Statistik
    (Einführung, Deskriptive Statistik, Wahrscheinlichkeitsrechnung, Zufallsvariable und Verteilungsfunktion, Kurzer Verständnistest, Anwendungen, Zusammenfassung, Übungsaufgaben, Lösungen)

• Tipps zum Studium
• Literaturverzeichnis
• Index

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