[HaBo]

Scutus

Anzeige

Hallo HaBo!

Nachdem ich ein paar komplexere Aufgaben in Java bewältigen durfte, wollte ich nicht alles im Datenmüll versumpfen lassen und stelle es deswegen hier online.
Es steht hier noch die "Anleitung" unter der die Klassen zu definieren war. Es werden hier alle möglichen Themenbereiche angeschnitten, wer also ein paar Snippets braucht, kann sich gerne bedienen.
Es liegt neben dieser algebraischen Struktur noch ein Terminkalender (GUI-Entwickling mit Swing, Filtern von Terminen, Ablegen als Daten, usw.) und ein Reimwörterbuch (Konstruktion eines Baums, Umgang mit Zeichenketten, usw.) vor, falls Bedarf besteht, kann ich diese auch bereitstellen.

In meinem Code sind die Kommentare recht klein gehalten, da durch diese Anleitung vieles erklärt wird.

Algebraische Struktur

Zunächst einmal: Keine Panik! Die Aufgabe klingt mathematisch und hat viel Aufgabentext, Sie werden aber zum einen feststellen, dass Sie kein abgeschlossenes Mathematikstudium brauchen um die Aufgabe zu lösen und zum anderen hält sich der Codieraufwand in übersichtlichen Grenzen. Soviel zur Aufmunterung, jetzt geht die Aufgabe richtig los.

Eine Algebra (A, f1,f2,...,fn) ist, ganz allgemein gesprochen, eine Menge von Objekten A, das sogenannte Universum zusammen mit einer Menge von Funktionen {f1,...,fn}, die auf den Elementen des Universums arbeiten. Das Universum heißt auch Domäne der Funktionen. (Ganz allgemein gesprochen können Algebren zusätzlich auch noch eine Menge von Relationen enthalten, das lassen wir hier aber beiseite.)

Beispiele für gängige Algebren, mit denen man normalerweise zu tun hat sind z.B:

Die Natürlichen Zahlen zusammen mit der Additition und der Multiplikation (auf den natürlichen Zahlen).
Die Menge der komplexen Zahlen zusammen mit Addition und Multiplikation (hier sind das aber Operationen auf komplexen Zahlen).
Die Menge der ganzzahligen Matrizen zusammen mit der Matrixmultiplikation.
Die Menge {0,1} zusammen mit den booleschen Funktionen AND und OR.
und viele, viele mehr.
Alle oben genannten Algebren haben nur zweistellige Funktionen. Solche Funktionen nennt man Operationen auf dem jeweiligen Universum. Außerdem sind alle oben genannten Algebren sehr speziell insofern, als sie mehr oder weniger schöne Eigenschaften haben. Diese speziellen Algebren sind für uns von besonderem Interesse.

Das Ziel dieser Aufgabe ist die Entwicklung eines allgemeinen kleinen Algebrasystems, das wir dazu verwenden können um komplexere mathematische Objekte zu definieren (in unserem Fall werden das Polynome sein) und mit ihnen umgehen zu können, ohne dass dann dabei noch auf die zugrundeliegende Algebra Rücksicht genommen werden muss.

Beispiel: Polynome kann man auf unterschiedlichen Ringen definieren. Z.B. gibt es die Menge der Polynome auf den ganzen Zahlen, die Menge der Polynome auf den rationalen Zahlen, oder auch Polynome auf endlichen Körpern, wie etwa dem GF2, also dem Körper mit nur 2 Elementen. Allen diesen Mengen von Polynomen ist gemeinsam, dass sie zusammen mit der Polynomaddition und der Polynommultiplikation wieder einen Ring bilden. Die Polynomaddition und die Polynommultiplikation leitet sich dabei direkt aus Operationen der den Polynomen zugrundeliegenden Algebra ab. Und zwar immer auf die gleiche Weise. Das heißt, es ist möglich die Polynomoperationen ganz abstrakt und unabhängig von der zugrundeliegenden Algebra zu definieren. Es ist also z.B. nicht notwendig die Polynomaddition für Polynome über den rationalen Zahlen zu definieren und dann auch noch die Polynomaddition für Polynome über ganzen Zahlen. Beides funktioniert gleich, es muss nur die zugrunde liegende Algebra ausgetauscht werden.

Die Klasse Operation

Erstellen Sie ein package jpp.algebra und in diesem package die abstrakte Klasse Operation.java. Auch alle weiteren Klassen erstellen Sie bitte in diesem package, auch wenn es dann später nicht mehr explizit gefordert wird.

Diese Klasse steht für eine zweistellige Funktion auf ihrer Domäne. Die Domäne wird dabei durch den Parameter DomainElement angeben. Eine konkrete Operation könnte also z.B. mit der Klasse Integer parametrisiert werden. Die Bedeutung davon wäre, dass es sich dabei um eine Operation auf Instanzen der Integer-Klasse handelt.
Jeder Operation hat einen Namen, der im Attribut

gespeichert wird.
Implementieren Sie bitte einen Konstruktor

in dem das name-Attribut initialisiert wird.
Die folgenden Methoden sind in der Klasse Operation nur abstrakt vorhanden. In konkreten Operationen sind sie dann auch konkret zu implementieren

Die Methode führt die eigentliche Operation auf den beiden gegebenen Elementen der Domäne der Operation aus.
Eine Operation * ist assoziativ, falls für alle Elemente X, Y, Z der Domäne gilt: (X*Y)*Z = X*(Y*Z). Diese Methode liefert genau dann true zurück, wenn die Operation assoziativ ist.
public abstract boolean isCommutative();

Eine Operation * ist kommutativ, falls für alle Elemente X, Y der Domäne gilt: X*Y = Y*X. Diese Methode gibt genau dann true zurück, wenn die Operation kommutativ ist.
Ein neutrale Element einer Domäne D und einer Operation * ist ein Element e aus D, so dass für alle X aus D gilt: e*X=X*e = X. Diese Methode gibt genau dann true zurück, falls die Operation ein solches Element in ihrer Domäne besitzt. Hinweis: Wenn es ein neutrales Element gibt, so ist es eindeutig, jede Operation besitzt also höchstens ein neutrales Element in seiner Domäne.
Die Methode gibt genau dann true zurück, wenn das Argument e das neutrale Element der Operation ist.
Diese Methode liefert das neutrale Element der Operation zurück, falls ein solches Element existiert, und null sonst.
Ein Element X aus der Domäne einer Operation * ist invertierbar, falls es ein Element Y aus der Domäne gibt, so dass X*Y=E, wobei E das Neutrale Element der Operation ist. In diesem Fall heißt Y das inverse Element von X. Diese Methode liefert genau dann true zurück, wenn jedes Element ausgenommen der 0 (aus Einfachheitsgründen) der Domäne der Operation invertierbar ist.
Diese Methode liefert das inverse Element des Arguments e zurück, falls es ein solches bezüglich der Operation gibt und null sonst.
;

Diese Methode bekommt als Argument eine weitere Operation die auf der gleichen Domäne arbeitet wie die Operation dieser Methode. Sei diese Operation durch das Symbol * gegeben und sei die Operation des Arguments dieser Methode durch das Symbol + gegeben. Dann distribuiert * über +, falls für alle Elemente X,Y,Z der Domäne gilt X*(Y+Z) = X*Y + X*Z. Im Gegensatz zu den anderen abstrakten Methoden von Operation, kann für diese Methode kein Algorithmus angegeben werden, der ganz allgemein für jede mögliche gegebene Operation darüber entscheidet ob diese Operation über die gegebene distribuiert. Wir werden darum für jede konkrete Operation festlegen, über welche anderen (dann bekannten) Operationen distribuiert wird.
Implementieren Sie nun noch die folgenden nicht-abstrakten Methoden. Dabei können und sollen Sie sich, wo sinnvoll, der oben definierten abstrakten Methoden bedienen.

Die Methode gibt den Namen der Operation zurück.
Eine Gruppe ist eine Algebra (A, *), wobei * eine Operation mit den folgenden Eigenschaften ist:
* ist assoziativ.
* besitzt ein neutrales Element.
Jedes Element aus der Domäne von * besitzt ein inverses Element.
Die Methode liefert genau dann true zurück, wenn die Algebra bestehend aus der Domäne der Operation zusammen mit der Operation eine Gruppe ist.
Eine abelsche Gruppe (A, *) ist eine Gruppe, bei der die Operation * kommutativ ist. Die Methode liefert genau dann true zurück, wenn die Algebra bestehend aus der Domäne der Operation zusammen mit der Operation eine abelsche Gruppe ist.
Die Methode gibt genau dann true zurück, wenn die beiden Argumente jeweils Inverse Elemente voneinander bezüglich der Operation sind.
Die Methode gibt genau dann true zurück, wenn das Argument Instanz der Klasse Operation und ihr Name gleich dem Namen dieser Operation ist.

Operationen auf ganzen Zahlen

Implementieren Sie nun konkret die Addition auf ganzen Zahlen als Operation. Legen Sie dazu die Klasse

im package jpp.algebra an. Da es sich hierbei um eine konkrete (also nicht-abstrakte) Operation handelt, müssen Sie alle in Operation als abstrakt markierten Methoden nun konkret definieren.
Hinweise: Die Addition auf den ganzen Zahlen ist eine assoziative, kommutative Operation mit dem neutralen Element 0. Jedes Element besitzt ein Inverses. Obwohl Operationen auf den ganzen Zahlen denkbar sind, über die die Addition distribuiert, soll die Methode knownToDistributeOver immer false zurückgeben.
Diese Klasse steht für eine konkrete Operation. Eine Instanz der Klasse hat keine Attribute, insofern ist mehr als eine Instanz für die Klasse auch nicht sinnvoll; bei der Klasse handelt es sich also um ein sogenanntes Singleton. Implementieren Sie daher bitte keinen öffentlichen Konstruktor für diese Klasse, sondern nur einen privaten, nämlich

Dieser Konstruktor soll der IntegerAddtion den Namen "Integer Addition" zuweisen. Legen Sie außerdem das Attribut
an, das mithilfe des privaten Konstruktors initialisiert wird, sobald die Klasse zum ersten mal gebraucht wird. Wann immer dann eine Instanz von IntegerAddition benötigt wird, wird diese Konstante benutzt.
Analog verfahren Sie bitte um eine Operation für die Multiplikation auf ganzen Zahlen im package jpp.algebra zu erzeugen.

Die Multiplikation ist eine assoziative, kommutative Operation mit neutralem Element 1. Nicht jede ganze Zahl besitzt ein Inverses bezüglich dieser Operation. Die Methode knownToDistributeOver soll genau dann true zurückgeben, wenn das Argument IntegerAddition ist. Implementieren Sie die Klasse wieder als Singleton, und erzeugen Sie analog zu oben die Konstante
public final static IntegerMultiplication MULT.

Operationen auf rationalen Zahlen

Nun soll eine etwas komplexere Domäne als die der ganzen Zahlen implementiert werden. Dazu entwerfen Sie bitte einen Datentyp für rationale Zahlen, die jeweils als Bruch gespeichert werden. Erzeugen Sie dafür zunächst die Klasse

im package jpp.algebra. Die Klasse besitzt die folgenden Attribute:
private int numerator

Das ist der Zähler der rationalen Zahl.
Das ist der Nenner der rationalen Zahl.
Die Attribute bestimmen also den Wert des Bruchs. Die Klasse soll so implementiert werden, dass numerator und denominator immer einen gekürzten Bruch bilden. Darauf müssen Sie also bei der Implementation aller Methoden dieser Klasse achten. Am besten implementieren Sie dazu eine private Methode
die den Bruch kürzt. Dazu können Sie z.B. ggT(numerator, denominator) berechnen und beide Zahlen dann durch das Ergebnis teilen. Der ggT kann z.B. mit Hilfe des Euklidischen Algorithmus berechnet werden.
Erzeugen Sie den Konstruktor
Der Konstruktor wirft eine IllegalArgumentException, falls das Argument denom gleich 0 ist. Implementieren Sie außerdem die folgenden Methoden:
Die Methode gibt den Zähler des Bruchs zurück.
Die Methode gibt den Nenner des Bruchs zurück.
Die Methode setzt den Nenner des Bruchs auf den Wert des gegebenen Arguments.
Die Methode setzt den Zähler des Bruchs auf den Wert des gegebenen Arguments.
Erzeugt den String "[Zähler]/[Nenner]", wobei natürlich [Zähler] durch den Wert des Zählers und [Nenner] durch den Wert des Nenners des Bruchs ersetzt wird. Ist der Nenner gleich 1, so soll nur "[Zähler]" zurückgegeben werden. Ist der Zähler gleich 0, so soll nur "0" zurückgegeben werden.
Die Methode gibt genau dann true zurück, wenn das Argument eine Instanz der Klasse RationalNumber ist, die die für die gleiche rationale Zahl steht, wie diese RationalNumber. Achten Sie darauf, dass die 0 viele verschiedene Repräsentationen haben kann. Denken Sie auch daran, dass rationale Zahlen auch negativ sein können und wie eine negative Zahl als Bruch dargestellt werden kann.
Die Methode liefert genau dann true zurück, wenn die rationale Zahl negativ ist.
Erzeugen Sie nun die Operationen

und
die jeweils die Operation der Addition und der Multiplikation auf rationalen Zahlen darstellen. Beide Operationen sind assoziativ, kommutativ und besitzen ein neutrales Element. Bei der Addition besitzt jedes Element ein Inverses, bei der Multiplikation jedes bis auf die 0. Die Methode knownToDistributeOver liefert bei der Addition stets ein false bei der Multiplikation genau dann true, wenn das Argument die Addition auf den rationellen Zahlen ist. Beide Klassen sind Singletons. Erzeugen Sie für die Addition die Konstante
und für die Multiplikation die Konstante
.

Operationen auf endlichen Körpern

Schließlich sollen noch Operationen auf Restklassen implementiert werden. Ist Z die Menge der ganzen Zahlen und n eine natürliche Zahl, so ist nZ = {... -2n, -n, 0, n, 2n, ...} und Zn = {k+nZ : k aus {0,...,n-1}} die Menge der Restklassen modulo n. Jedes Element X aus Zn ist also eine Menge von Zahlen, so dass es für alle y aus X ein k aus {0,...,n-1} gibt, für das gilt, dass y äquivalent k modulo n ist.

Darum genügt es, wenn man die Elemente aus Zn mit den Resten modulo n identifiziert, also im obigen Beispiel würde X mit k identifiziert. Um es einfacher auszudrücken: Es sollen nun Addition und Multiplikation für die Rechnung modulo n implementiert werden.

Für diese Operationen ist das Modul, also die Zahl n, die die Restklasse definiert von besonderer Bedeutung. Darum führen wir das Interface

ein, das die Methode
vorgibt. Entwickeln Sie bitte die Klasse
als die Addition in einer Restklasse Zn. Im Gegensatz zu den bisherigen Operationen ist diese Klasse kein Singleton, weil über sie für jede ganze Zahl n eine neue Operation definiert werden kann. Insbesondere muss sich die Klasse das Modul n in einem Attribut merken:
Implementieren Sie bitte den Konstruktor
der das Modul initialisiert. Der Konstruktor wirft eine IllegalArgumentException, falls das Argument kleiner 2 ist. Der Name der konstruierten Operation sei "Addition modulo [mod]", wobei [mod] das Modul der Addition ist. Implementieren Sie auch die Methode
mit der auf das Modul zugegriffen werden kann. Implementieren Sie schließlich alle Methoden, die in der Klasse Operation abstrakt geblieben sind. Bei der Addition modulo n handelt es sich um eine assoziative, kommutative Operation mit neutralem Element 0. Jedes Element besitzt ein Inverses: Tatsächlich gilt für ein x aus {0,...,n-1}, dass x + (n-x) = n = 0 (mod n), also ist (n-x) das additiv Inverse von x.
Die Methode compute soll prinzipiell jeden Integer als Argument akzeptieren, die Ausgabe von compute soll aber stets im Bereich {0,...,n-1} liegen (hier ist n immer das Modul). Beachten Sie dabei, dass jede positive Zahl y (einschließlich der 0) äquivalent ist zu (y % n). Eine negative Zahl z ist äquivalent zu (n - ((-z) % n)).

Die Methode knownToDistributeOver gibt stets false zurück.

Entwickeln Sie nun noch die Klasse

analog zur Klasse RestAddition. Bei der Multiplikation modulo n handelt es sich um eine assoziative, kommutative Operation mit neutralem Element 1. Nicht jedes Element aus {0,...,n-1} besitzt ein inverses bezüglich dieser Operation, sondern nur die, die teilerfremd zu n sind. Zwei Zahlen x,y sind genau dann teilerfremd, wenn ggT(x,y)=1. Existiert das multiplikativ Inverse Element, so kann es mit Hilfe des erweiterten Euklidischen Algorithmus berechnet werden. Wir geben diesen Algorithmus hier im Pseudocode an:
extended_euclid(a,b)

1: wenn (b == 0) dann return (a,1,0)
2: (d',s',t') = extended_euclid(b, a mod b)
3: (d,s,t) = (d',t',s' - floor(a/b)*t')
4: return (d,s,t)
Der Algorithmus arbeitet nur auf positiven ganzen Zahlen korrekt, erwartet also als Argument ein Paar von positiven ganzen Zahlen (a,b). Der Algorithmus gibt ein Tripel von Zahlen (d,s,t) zurück, für das gilt:

d = ggT(a,b)
d = s*a + t*b
Ist also x aus {0,...,n-1} und ggT(x,n)=1, so ist extended_euclid(a,b) = (1,s,t), wobei 1 = s*x + t*n. Da tn == 0 (mod n) , ist also 1 = s*x modulo n. Mit anderen Worten s ist das das multiplikativ Inverse Element von x modulo n. Beachten Sie, dass die Zahlen s und t durchaus negativ sein können. Gegebenenfalls müssen Sie also ein negatives Ergebnis s noch in einen korrekten Repräsentanten aus {0,...,n-1} umrechnen (wie das gemacht wird, siehe oben).

Sie wissen nun, wie sie bestimmen, ob ein einzelnes Element aus {0,...,n-1} ein multiplikativ Inverses modulo n besitzt. Zur Berechnung der Methode elementsInvertible(), müssen Sie aber wissen, ob alle Elemente aus {0,...,n-1} invertierbar sind. Das ist genau dann der Fall, wenn für alle x aus {0,...,n-1} gilt: ggT(x,n) = 1. Das, wiederum, ist genau dann der Fall, wenn n eine Primzahl ist. (Eine Primzahl ist eine Zahl größer gleich 2, die nur durch sich selbst und die 1 teilbar ist.) Die Methode elementsInvertible() muss also genau dann true zurückgeben, wenn das modul eine Primzahl ist. Das lässt sich z.B. mit dem Sieb des Eratosthenes ermitteln.

Die Methode knownToDistributeOver gibt genau dann true zurück, wenn das Argument eine Addition auf der gleichen Domäne ist, also wenn die Operation eine RestAddition mit dem gleichen Modul wie die Multiplikation ist.

Algebren

Legen Sie nun die Klasse

an. Wie Sie sehen, ist die Klasse mit einem DomainElement parametrisiert. Alle Funktionen dieser Algebra werden als Argumente stets nur Instanzen dieser Klasse akzeptieren und zurückgeben.
Eine Algebra besitzt das Attribut

In dem konkrete Operationen unter ihrem Namen abgespeichert werden. Wie sie sehen, werden auch die Operationen mit DomainElement parametrisiert, es ist also gar nicht möglich eine Algebra mit Operationen zu erstellen, die auf unterschiedlichen Domänen arbeiten.
Implementieren Sie bitte den Konstruktor

in dem das operations-Attribut initialisiert wird, sowie die folgenden Methoden:
Die Methode fügt das Argument den Operationen der Algebra hinzu. Als Schlüssel für die Hashtabelle wird übrigens immer der Name der Operation verwendet. Die Methode wirft eine NullPointerException, falls die gegebene Operation gleich null ist.
Gibt die Operation, die den Namen des Arguments trägt zurück, falls eine solche Operation in der Algebra ist und null sonst. Die Methode wirft eine NullPointerException, falls der gegebene Name gleich null ist.
Wir wollen nun Klassen für spezielle Algebren entwickeln. Legen Sie zunächst die Klasse

an. Die Klasse enthält den Konstruktor
Dieser wirft eine NullPointerException, falls o == null ist und eine IllegalArgumentException, falls die Operation keine Gruppenoperation ist (d.h. sie muss assoziativ sein, es muss ein neutrales Element geben und jedes Element der Domäne muss invertierbar sein).
Des weiteren hat die Klasse die Methode

die die Gruppenoperation zurückgibt.
Entwickeln Sie als nächstes die Klasse

die fast genau das gleiche leistet, wie die Klasse Group, ihr Konstruktor muss aber zusätzlich prüfen, ob die Gruppenoperation kommutativ ist (und eine IllegalArgumentException werfen, falls nicht).
Schließlich entwickeln Sie bitte noch eine Klasse für einen Ring:

Ein Ring ist eine abelsche Gruppe mit einer weiteren Operation (meist als Multiplikation bezeichnet), die über die Addition distribuiert. Die Multiplikation bildet auf ihrer Domäne einen Monoid, d.h. sie ist assoziativ und es existiert ein neutrales Element. (D.h. eigentlich sind unsere Ringe immer sogenannte Ringe mit 1.) Entwickeln Sie den Konstruktor
der zunächst den Aufbau der abelschen Gruppe an seine Superklasse weitergibt. Dann überprüft der Konstruktor, ob die übergebene Multiplikation mit der Addition kompatibel ist, d.h. ob sie über die Addition distribuiert und ob es ein neutrales Element besitzt. Außerdem prüft der Konstruktor, ob die Multiplikation assoziativ ist und über ein neutrales Element verfügt. Trifft eine der obigen Bedingungen nicht zu, wird eine entsprechende aussagekräftige IllegalArgumentException geworfen. Ist einer der beiden Operationen null, wird eine NullPointerException geworfen.
Die Ring-Klasse enthält zusätzlich die folgenden Methoden:

Diese geben die entsprechenden Ringoperationen zurück.

Polynome

Wir haben nun die Infrastruktur um uns mit komplexeren algebraischen Objekten zu befassen. Beispielhaft soll das mit den Polynomen geschehen. Sei R = (U, +, *) ein Ring. Ein Polynom mit einer Variable x über R ist wie folgt definiert:

x ist ein Polynom und jedes c aus U ist ein Polynom über R
Sind p1 und p2 Polynome über R, so auch p1 + p2 und p1 * p2.
Anders ausgedrückt, gibt es für jedes Polynom p über R eine endliche Menge von Koeffizienten a0, a1, ... , ak aus U, so dass

p = a0 + a1*x1 + a2*x2 + ... + ak*xk.
Wir nennen ai den Koeffizienten des Exponenten i. Wir bemerken ausdrücklich, dass ai=0 sein kann für ein i aus {0,...,k}. Hier, wie im Folgenden schreiben wir das neutrale Element der Addition als 0 und das neutrale Element der Multiplikation als 1.
Interessant ist, dass sehr natürliche Operationen auf der Menge der Polynome so definiert werden können, dass diese Menge zusammen mit den Operationen selbst wieder einen Ring bildet.

Entwickeln Sie nun eine Klasse für Polynome:

Die Klasse hat mindestens die folgenden Attribute:
Das ist der dem Polynom zugrunde liegende Ring (oben mit R bezeichnet).
Das sind die Koeffizienten des Polynoms (oben mit a0, a1, ... , ak bezeichnet). In der Hashtable werden als Schlüssel jeweils die Exponenten abgespeichert und als Werte die dem jeweiligen Exponenten zugeordneten Koeffizienten. Ist ein Koeffizient eines Exponenten gleich 0, so gibt es für diesesn Exponenten keinen Eintrag.
Das ist der Grad des Polynoms, d.h. der größte Koeffizient der nicht 0 (das neutrale Element der Addition) ist (oben mit k bezeichnet).
Die Klasse hat die folgenden Konstruktoren:

Ist eines der Argumente null, so wird eine NullPointerException geworfen. Der Konstruktor erzeugt ein Polynom, dessen Grad unmittelbar von der Länge des Argumentarrays
coeffs abhängt. Dieses enthält die Koeffizienten des Polynoms und zwar ist ai = coeffs[i]. Folglich ist der Grad des Polynoms höchstens coeffs.length - 1. Hat das coeffs-Array die Länge 0, so wird das 0-Polynom (alle Koeffizienten sind 0) konstruiert.

Dieser Konstruktor erwartet die Koeffizenten des Polynoms schon direkt als Tabelle. Der Konstruktor soll 0-Koeffizienten ausfiltern, also nicht mit in seine Koeffiziententabelle übernehmen. Ist diese oder r gleich null, so wird eine NullPointerException geworfen.
Schreiben Sie bitte die folgenden Methoden für die Klasse:

Gibt den entsprechenden Koeffizienten aexponent zurück. Beachten Sie, dass jedes Polynom für jeden Exponenten auch einen Koeffizienten besitzt; fast alle sind aber 0.
Die Methode gibt den dem Polynom zugrunde liegenden Ring zurück.
Liefert den Grad des Polynoms.
Die Methode gibt genau dann true zurück, wenn das gegebene Polynom ein Polynom über dem gleichen Ring ist. Ist das Argument null, wird eine NullPointerException geworfen.
Ein Polynom ist immer genau dann additiv neutral gegebnüber der Polynomaddition, wenn jeder seiner Koeffizienten 0 ist. Mit anderen Worten: Das additiv neutrale Polynom ist das 0-Polynom.
Ein Polynom ist genau dann multiplikativ neutral, wenn alle seine Koeffizienten 0 sind, bis auf den Koeffizienten a0, welcher 1 ist.
Die Methode gibt genau dann true zurück, wenn das Argument ebenfalls ein Polynom über dem gleichen Basisring ist, und alle Koeffizienten übereinstimmen.
Gibt das Polynom als menschenleslichen String aus.
Nun sollen noch Addition und Multiplikation auf der Domäne der Polynome definiert werden. Entwickeln Sie dazu die Klasse

mit dem Konstruktor
.

Für die Polynomaddition wird der zugrundeliegende Ring benötigt, er muss also in einem Attribut gespeichert werden. Der Name der PolynomAddition soll auf "Polynom addtion based on [Basisaddition]" festgelegt werden, wobei [Basisaddition] der Name der Addition aus dem Basisring ist. Ist das Argument r gleich null, so wird eine NullPointerExcepetion geworfen.
Schließlich sollen alle Methoden einer Operation implementiert werden. Dazu ist zu bemerken, dass eine Polynomaddition stets eine assoziative, kommutative Operation ist mit neutralem Element 0 (das ist das Polynom, das nur aus der 0 besteht, d.h. alle Koeffizienten sind 0). Die Summe zweier Polynome

p(x) = a0 + a1*x1 +a2*x2 +... +ak*xk und
q(x) = b0 + b1*x1 +b2*x2 +... +bk*xm
ist definiert als
p(x)+q(x) = a0+b0 + (a1 + b1)*x1 + (a2 + b2)*x2 + ... + (an + bn)*xn,
wobei n = max(k,m). Bei den Symbolen "+" und "*" handelt es sich dabei um die Operationen der Addition und Multiplikation auf dem zugrundeliegenden Ring. Aus der Definition ist auch unmittelbar klar, dass jedes Polynom ein inverses bezüglich der Polynomaddition hat und wie dieses aussieht. Die Methode knownToDistributeOver soll immer false zurückgeben.
Die letzte Klasse, die Sie für diese Aufgabe entwickeln sollen, ist die Polynommultiplikation.

Entwickeln Sie den Konstruktor
analog zu dem der PolynomAddition.
Implementieren Sie die Methoden, die die abstrakte Klasse Operation vorgibt. Dazu folgende Informationen: Bei der Polynommultiplikation handelt es sich um eine assoziative, kommutative Operation mit neutralem Element 1 (das ist das Polynom, dessen Koeffizienten alle 0 sind, bis auf den des Exponenten 0, der ist 1). Die Polynommultiplikation ist für Polynome

p(x) = a0 + a1*x1 +a2*x2 +... +ak*xk und
q(x) = b0 + b1*x1 +b2*x2 +... +bk*xm
wie folgt definiert:
p(x)*q(x) = c0 + c1*x1 +c2*x2 +... +ck+m*xk+m
wobei ci = ∑s,t mit s+t=i as * bt. Das heißt, dass die Koeffizienten ci des Ergebnispolynoms die Summe der Produkte derjenigen Koeffizienten as und bt sind, deren Indizes s und t sich gerade zu i summieren. Auch hier stehen die verwendeten Symbole "+" und "*" für die Addition und die Multiplikation auf dem Basisring (bis auf das "+" in ck+m und xk+m: Hier handelt es sich um die normale Addition auf ganzen Zahlen).
Die Definition der Polynommultiplikation macht sofort klar, dass der Grad des Polynoms p(x)*q(x) der Summe der Grade von p(x) und q(x) entspricht. Da das neutrale Element der Polynommultiplikation vom Grad 0 ist können nur Polynome vom Grad 0 ein inverses Element bezüglich der Multiplikation haben. Das sind genau die konstanten Polynome, also Polynome der Form a0, wobei a0 ein Element des Basisrings ist. Für diese Polynome hängt es vom Basisring ab, ob sie ein multiplikativ inverses Element besitzen oder nicht.

Die Polynommultiplikation distribuiert über die Polynomaddition, vorausgesetzt die beiden Polynomringoperationen arbeiten auf dem gleichen Basisring.

----------

Viel Spaß!

Grüße

Angehängte Dateien

algebra.zip (61,9 KB, 4x aufgerufen)

miana

reimwörterbuch wäre super!