Computeralgebra

aus Wikipedia, der freien Enzyklopädie

Die Computeralgebra ist das Teilgebiet der Mathematik und Informatik, das sich mit der automatisierten symbolischen Manipulation algebraischer Ausdrücke beschäftigt.

Überblick

Hauptziel der Computeralgebra ist es, durch konservative Rechnungen algebraische Ausdrücke umzuformen und eine möglichst kompakte Darstellung zu erzielen. Die Wertigkeit und Präzision der Gleichung wird dabei nicht angetastet. Rundungen oder Näherungen werden nicht zugelassen. Eine Nebenbedingung ist hierbei, die verwendeten Algorithmen und Methoden effizient zu gestalten.

Die Disziplinen Mathematik und Informatik sind in der Computeralgebra eng miteinander verwoben, einerseits über die Komplexitätstheorie für die Analyse, andererseits über die Softwaretechnik für die praktische Umsetzung computeralgebraischer Algorithmen.

Einen Schwerpunkt bildet das exakte Rechnen mit ganzen, rationalen und algebraischen Zahlen sowie mit Polynomen über diesen Zahlenräumen. Eine weitere Anwendung ist das symbolische Lösen von Gleichungen aller Arten, das symbolische Summieren von Reihen, die symbolische Berechnung von Grenzwerten und das symbolische Differenzieren und Integrieren (auch Algebraische Integration genannt).

Praktische Anwendung erfahren solche Ergebnisse durch den Einsatz effizienter Algorithmen bei der Entwicklung und Verbesserung von Computeralgebrasystemen, die die rechnergestützte Manipulation algebraischer Ausdrücke ermöglichen. Diese Systeme sind auch ein immer wichtiger werdendes Werkzeug für Mathematiker und Naturwissenschaftler verschiedenster Fachrichtungen.

Zugrundeliegende Strukturen

Anders als in der Numerik, wo mit Gleitkomma-Approximationen der auftretenden Zahlen gerechnet wird, hat die Computeralgebra den Anspruch, stets exakt zu rechnen. Entsprechend ist es grundsätzlich notwendig, Anforderungen an die zugrundeliegenden Strukturen (in der Regel Gruppen, Ringe oder Körper) zu spezifizieren.

Gruppen

Alle endlichen Gruppen lassen sich im Computer darstellen, für unendliche Gruppen gibt es unter bestimmten Voraussetzungen Algorithmen, etwa für polyzyklische Gruppen.

Berechenbare Ringe

Ein Ring heißt berechenbar (oder „effektiv“), wenn folgende Bedingungen gelten:

  • Die Elemente des Rings können auf einem Computer dargestellt werden, insbesondere muss die Darstellung der Elemente endlich sein,
  • Gleichheit zwischen zwei Elementen kann in endlicher Zeit entschieden werden,
  • es gibt Algorithmen, mit denen die Ringoperationen „+“ und „·“ durchgeführt werden können.

Beispiele

Berechenbar sind etwa:

  • die natürlichen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \N}
  • die ganzen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z}
  • die rationalen Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Q}
  • alle Formen von endlichen Körpern.

Aus einem berechenbaren Ring Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R} lassen sich weitere berechenbare Ringe konstruieren:

  • Polynomringe über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R}
  • Rationale Funktionen über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R}
  • Matrizen über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R}
  • Alle endlichen algebraischen Erweiterungen der obigen Körper,
  • Alle endlichen transzendenten Erweiterungen der obigen Körper.

Formale Objekte

In der Computeralgebra werden neben den Elementen der zugrundeliegenden Bereiche noch weitere „formale“ Objekte betrachtet wie etwa

Hierbei geht es in der Regel nicht um die Berechnung von Zahlwerten, sondern beispielsweise um die Bestimmung von „geschlossenen Formeln“ als Lösungen.

Anwendungen

Bei den Anwendungen mathematischer Methoden in Naturwissenschaft und Technik stehen traditionell numerische Methoden im Vordergrund. Mit den symbolischen Methoden der Computeralgebra haben sich neue Anwendungsgebiete eröffnet, bei denen es auf exakte Lösungen ankommt und bei denen strukturmathematische Überlegungen, z. B. zur Beschreibung von Symmetrien, eingehen; ferner die Behandlung von Problemen, die von unbestimmten Parametern abhängen.

Dazu gehören etwa:

  • In der Physik und ihren technologischen Anwendungen: Gemischt symbolisch-numerische Berechnungen komplexer Probleme in der Himmelsmechanik, der Hochenergiephysik (Feynman-Integrale) und der Relativitätstheorie (Differentialgeometrie); Integration und Lösung von Differentialgleichungen in geschlossener Form; symbolische Berechnungen in den Algebren der Quantenmechanik; Klassifikation höherdimensionaler kristallographischer Gruppen zur Beschreibung von inkommensurabel modulierten Strukturen, Quasikristallen und magnetischen Strukturen.
  • In der Chemie: Anwendungen der Darstellungstheorie auf die Klassifikation von Graphen chemischer Verbindungen, insbesondere von Isomeren; Lösung großer Gleichungssysteme zur Bestimmung chemischer Reaktionsgleichgewichte bei variablen Reaktionsbedingungen, z. B. bei Verbrennungsprozessen und der Abgasregulierung.
  • In der Informationssicherheit: Algebraische Methoden der Fehlererkennung und -korrektur bei der Nachrichtenübertragung; kryptographische Kodierung von vertraulichen Nachrichten durch Public-Key-Verfahren mit Methoden der Zahlentheorie und der algebraischen Gruppen; Verifikation von Sicherheitsmechanismen (Protokollen).
  • In der Robotik: Bewegungsplanung und Regulierung autonomer Roboter z. B. in der Raumfahrt; zylindrisch algebraische Zellenzerlegung des Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R^n} ; geometrische Bildverarbeitung beim Maschinensehen.
  • Im computergestützten Entwurf (CAD): Flexible Inferenzsysteme für die geometrische Modellierung parametrisierter Probleme; Konstruktion von Übergangsflächen.
  • In der Kontrolltheorie: Untersuchung der Stabilität und Sicherheit von Kontrollsystemen mit Rückkopplung.
  • In der Genforschung: Klassifikation von DNA-Strukturen.
  • In der Ausbildung: Computeralgebrasysteme versprechen eine Verbesserung des Mathematikunterrichts, da es durch ihren Einsatz möglich wird, sich mehr auf die Unterrichtsinhalte zu konzentrieren. Ferner ist die Behandlung realistischerer anwendungsbezogener Aufgaben möglich.

Die Methoden der Computeralgebra erlauben in diesen Anwendungsbereichen eine automatische Behandlung von Problemen, die sonst nur mühsam mit Ad-hoc-Ansätzen angegangen werden konnten. Das große Potential dieser Methoden ist dabei noch lange nicht ausgeschöpft. Kontinuierliche Förderung dieser Anwendungen und der zugrundeliegenden Algorithmen kombiniert mit immer leistungsstärkerer Hardware werden dem Gebiet Computeralgebra weitere Entwicklungsmöglichkeiten geben.

Komplexitätsbetrachtungen

Effiziente exakte Arithmetik mit ganzen Zahlen

Will man die Zeitkomplexität von Aufgaben und Algorithmen zur exakten Arithmetik mit ganzen Zahlen klassifizieren, so muss zunächst ein Rechnermodell zugrunde gelegt werden. Eine Diskussion diverser Rechnermodelle findet sich im Kapitel Komplexität. Ein relativ eingängiges Modell ist die Mehrband-Turingmaschine, eine Variante der klassischen Turingmaschine, die mehrere Bänder mit je einem Schreib-/Lesekopf besitzt. Für Komplexitätsabschätzungen mit der Landau-Notation wird bei Bedarf unter der Bezeichnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{log}} ein Logarithmus zu einer nicht spezifizierten Basis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B>1} verwendet. Als Maß für die Zeit wird die Zahl der benötigten Bitoperationen gewählt, die in Landau-Notation von der Bitlänge des Inputs abhängig gemacht wird.

Die präzise mathematische Angabe von (Bit-)Komplexitäten für die exakte Arithmetik mit ganzen Zahlen muss zunächst mit der genauen Festlegung der Bitlänge einer ganzen Zahl starten: Ist die Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \in \mathbb Z} nicht null, so wird

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(a) := \lfloor \log_2 |a|\rfloor }

gesetzt; zusätzlich wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(0):=1 } definiert. Für die konkrete Speicherung einer ganzen Zahl wird zusätzlich mindestens noch ein Bit für das Vorzeichen benötigt.

Die Aufgaben der Vorzeichenbestimmung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{sgn}(a), } der Berechnung des Negativen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -a } sowie der Betragsbildung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |a| } sind alle in linearer Zeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(l) } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l=L(a)} durchführbar; die Addition Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a+b } sowie der Vergleich zweier Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a<b } sind in linearer Zeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(l) } mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l={\rm max}(L(a), L(b))} zu bewältigen. Der n-Shift Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^n\cdot a } ist in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n+l) } durchführbar.

Ein nicht-triviales Ergebnis der Computeralgebra ist die Erkenntnis, dass die Multiplikation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\cdot b} wesentlich schneller als in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left(l^2\right)} (was dem naiven Multiplikationsalgorithmus entspricht) lösbar ist. Eine Beschleunigung erreichte zunächst Anatoli Karazuba mit dem Karazuba-Algorithmus; dieser wurde dann als ein Spezialfall einer noch allgemeineren Algorithmenfamilie erkannt, die unter den Begriff Toom-Cook-Algorithmus subsumiert werden. Bahnbrechend war dann der von Arnold Schönhage und Volker Strassen 1971 vorgestellte auf diskreten Fourier-Transformationen basierende Schönhage-Strassen-Algorithmus, für den die Autoren selbst eine Komplexität von

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(l \cdot \log\, l \cdot \log\,\log\, l )}

nachwiesen. Bedenkt man, wie aufwendig der „naive“ Multiplikationsalgorithmus ist, so erscheint diese Komplexität unglaublich „schnell“. Da der Algorithmus allerdings ziemlich komplex und schwierig programmierbar ist, gibt es bis heute keine effiziente Implementierung in einem Computeralgebrasystem.

Da die Komplexität der Integer-Multiplikation in der gesamten Computeralgebra von absolut tragender Bedeutung ist, wurde hierfür eine Kurznotation

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \psi(l) := O(l \cdot \log\, l \cdot \log\,\log\, l)}

eingeführt. Ausgestattet mit dieser „schnellen“ Integer-Multiplikation kann nun der Katalog der Grundrechenarten für die Arithmetik in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Z} wie folgt vervollständigt werden: Die Aufgabe der Berechnung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^n} ist in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left(\psi(n l)\right)} durchführbar; für die (simultane) Berechnung der Binomialkoeffizienten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {n\choose 0}\cdots{n\choose n}} wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left(n\cdot\psi(n)\right)} benötigt. Die ganzzahlige Division Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a/b } (mit Quotient und Rest als Ergebnis) benötigt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left(\frac{l}{l_m} \cdot\psi(l_m)\right) } .

Die Berechnung des größten gemeinsamen Teilers Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rm gcd}(a,b)} benötigt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left(\left(\frac{l}{l_m} + {\rm log}\, l_m\right)\cdot\psi(l_m)\right) } .

In gleicher Komplexität ist auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rm gcdex}(a,b)} berechenbar, d. h. die Kofaktoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u, v} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rm gcd}(a,b) = ua+vb} werden mitberechnet.

Effiziente exakte Arithmetik mit rationalen Zahlen

Bevor exakte Arithmetik in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Q} konkret durchgeführt werden kann, muss erst eine kanonische Darstellung (Repräsentation) rationaler Zahlen gefunden werden; dieses Problem tauchte bei der exakten Arithmetik der ganzen Zahlen noch nicht auf. Rationale Zahlen sind Äquivalenzklassen „bedeutungsgleicher“ Brüche aus ganzen Zahlen; zum Beispiel sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{1}{2}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{2}{4}} unterschiedliche Repräsentanten der gleichen rationalen Zahl.

Die gängigste kanonische Darstellung rationaler Zahlen wird festgelegt, indem alle gemeinsamen Teiler aus Zähler und Nenner herausgekürzt werden: Jede rationale Zahl ist dann eindeutig durch einen gekürzten Bruch

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{p}{q}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\in \mathbb Z,} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q\in\mathbb N} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle {\rm ggT}(p,q) = 1}

repräsentierbar. Ist diese Festlegung einmal getroffen, so beinhaltet jede elementare Operation in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Q} wie Addition und Multiplikation auch notwendigerweise die Aufgabe des Herauskürzens des größten gemeinsamen Teilers aus Zähler und Nenner des Ergebnisbruches.

Dank der Resultate der exakten Arithmetik in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Z} sind damit die Operationen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a+b,\quad a-b, \quad a\cdot b, \quad a/b} alle in der Komplexität

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O\left( \psi(l)\cdot {\rm log}\, l \right) }

durchführbar. Von der Hoffnung, die Addition rationaler Zahlen in linearer Komplexität bewerkstelligen zu können, muss man hierbei Abschied nehmen.

Glücklicherweise kann die Berechnung des größten gemeinsamen Teilers sehr effizient mit Hilfe des Euklidischen Algorithmus berechnet werden. Der Euklidische Algorithmus spielt an vielen Stellen in der Computeralgebra in wechselnden Varianten eine tragende Rolle.

Effiziente exakte Arithmetik mit Polynomen in ℚ[x]

Es genügt hierbei, die Arithmetik in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb Z\left[x\right]} zu betrachten, da Operationen mit rationalen Polynomen in naheliegender Weise durch jeweiliges Ausklammern der Hauptnenner auf Operationen mit ganzzahligen Polynomen zurückgeführt werden können. Für Polynome Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\in \mathbb Z[x]} definiert man die (Koeffizienten-)Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L(f)} als das Maximum der Längen der einzelnen Koeffizienten.

Für die folgende Laufzeitentabelle wichtiger Berechnungsprobleme in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Z[x]} setzen wir folgendes voraus:

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f, g\in\Z\left[x\right]}
  • vom Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_f=\deg f} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_g=\deg g,} ferner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d = \max(d_f,d_g),\, d_m = \min(d_f,d_g)} ,
  • von der Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_f = L(f)} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_g = L(g),} ferner Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l = \max(l_f,l_g)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_m = \min(l_f, l_g)} ,
  • daneben sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a\in\Z} mit Bitlänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l_a = L(a)} .

Dann führen die (gemäß Bitkomplexität) schnellsten bislang bekannten Algorithmen zu folgender Laufzeittabelle:

Operation Komplexität als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(\dots)} bei ungleichen Eingabegrößen
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f+g} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d\, l} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_m\, l}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\cdot g} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \psi(d(l+\log d))} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f/g} Division mit Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \psi(d(l+\log d))} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{dl}{d_m l_m}\,\psi(d_m(l_m+\log d_m))}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{prem}(f,g)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{d}{d_m}\,\psi(d_m((d-d_m+1)l+\log d))}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f^k} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \psi(k d (l+\log d))} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(ax)} Skalierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d\,\psi(l+d l_a)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^d f\left(\frac{x}{a}\right)} Skalierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d\,\psi(l+d l_a)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(2x)} Skalierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d(l+d)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^d f\left(\frac{x}{2}\right)} Skalierung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d(l+d)} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle -}

Siehe auch

Literatur

Deutschsprachige Literatur:

  • Michael Kaplan: Computeralgebra. Springer, Berlin u. a. 2005, ISBN 3-540-21379-1.
  • Wolfram Koepf: Computeralgebra. Eine algorithmisch orientierte Einführung. Springer, Berlin u. a. 2006, ISBN 3-540-29894-0.
  • Attila Pethö: Algebraische Algorithmen. Herausgegeben von Michael Pohst. Vieweg, Braunschweig u. a. 1999, ISBN 3-528-06598-2.

Englischsprachige Literatur:

  • Peter Bürgisser, Michael Clausen, Mohammad Amin Shokrollahi: Algebraic Complexity Theory (= Die Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. 315). Springer, Berlin u. a. 1997, ISBN 3-540-60582-7 (Rezension).
  • Arjeh M. Cohen, Hans Cuypers, Hans Sterk: Some Tapas of Computer Algebra (= Algorithms and Computation in Mathematics. 4). Springer, Berlin u. a. 1999, ISBN 3-540-63480-0.
  • David Cox, John Little, Donal O’Shea: Ideals, varieties, and algorithms. 2nd Edition. Springer, New York NY ua. a. 1997, ISBN 0-387-94680-2.
  • Joachim von zur Gathen, Jürgen Gerhard: Modern Computer Algebra. 2nd Edition. Cambridge University Press, Cambridge u. a. 2003, ISBN 0-521-82646-2.
  • Keith O. Geddes, Stephen R. Czapor, George Labahn: Algorithms for Computer Algebra. Kluwer, Boston MA u. a. 1992, ISBN 0-7923-9259-0.

Weblinks

Abgerufen von „https://de.wikiup.org/index.php?title=Computeralgebra&oldid=224411677“