Hausaufgaben

empfohlen: wenigstens 5,3,4,2 mit Papier und maxima.

1. zur Ordnung auf Monomen:

   Variable und ihre Ordnung:

   newtype V = V Natural deriving Eq
   instance Ord V where compare (V i) (V j) = compare j i
   

   dann ist V₀ > V₁ > V₂ > ....

   Monome und ihre Ordnung:

   type D = Natural
   newtype Mono v = Mono (M.Map v D) deriving Eq
   instance Ord v => Ord (Mono v) where
     compare (Mono f) (Mono g) =
       compare (M.toDescList f) (M.toDescList g)
   

   Überprüfen und begründen Sie, daß das eine korrekte Implementierung der lexikografischen Ordnung ist.

   Ist folgende Implementierung äquivalent?

       compare (M.toAscList g) (M.toAscList f)
   

2. zur Ordnung auf Polynomen:

   für Polynome in Variablen X > Y > Z: geben Sie möglichst lange $\gg$-Ketten an, die bei X³ + Y²Z beginnen

   • bzgl. der grad-lexikografische Ordnung auf Monomen
   • bzgl. der lexikografische Ordnung auf Monomen
3. bestimmen Sie nach dem Buchberger-Algorithmus eine Gröbner-Basis B für I = 〈X²Y - 1, XY² -1〉.
   • auf Papier
   • mit maxima (load(grobner);poly_buchberger(...);) oder fricas
   • mit Eigenbau-Implementierung (siehe Repo)
4. Benutzen Sie dieses B (oder B', siehe unten), um zu entscheiden, ob X⁵≡_IY².
   • auf Papier
   • mit maxima (poly_grobner_member) oder fricas
   • mit Eigenbau-Implementierung
5. Geben Sie Polynome c₁, c₂ mit X⁵ - Y² = c₁(X²Y - 1) + c₂(XY² - 1) an.

   Erweitern Sie den Buchberger-Algorithmus und das Reduktionsverfahren →_B, um diese Darstellung zu erhalten.

   (zum Vergleich: Euklid bestimmt gcd(a, b), erweiterter Euklid bestimmt c, d mit ac + bd = gcd(a, b).)

6. Für eine Gröbner-Basis B definieren wir
   B' = {b∈B | ¬∃c : b→_{B $\setminus$ {b}}c}

   (alle b, die nicht durch die jeweils anderen Basis-Elemente reduziert werden können)

   Bestimmen Sie B' für voriges Beispiel.

   Ergänzen Sie die Eigenbau-Implementierung.

   (Es gilt 〈B'〉 = 〈B〉. Jedes solche B' heißt reduziert. Die reduzierte Gröbner-Basis eines Polynom-Ideals ist im wesentlichen eindeutig.)

7. Arjen Cohen: Gröbner Bases, an Introduction (in: Some Tapas of Computer Algebra, Springer, 1999):

   it is very hard to provide a good explicit upper bound on [die Laufzeit des Buchberger-Algorithmus], bad examples are known.

   Finden Sie solche bad examples

   • selbst ausdenken
   • mit Suchmaschine
   • brute force
   und messen Sie den Ressourcenverbrauch (maxima, fricas, Eigenbau)

   Erklärung: brute force mit unserer Implementierung und Leancheck-Generatoren für Monome und Polynome. Vorsicht: Generatoren sollen keine Exponenten oder Koeffizienten 0 erzeugen. Hinweis: Anzahl der Variablen fixieren, z.B. data V = X | Y. Deswegen ist der Code polymorph im Variablentyp v.