– shelter.geister –

So, dann herzlich Willkommen!

Wir haben uns ja letztes Mal am Montag mit der Terminierung von Thermersetzungssystemen beschäftigt

und haben festgestellt, dass es nicht so einfach ist,

eine so genannte Reduktionsordnung zu finden für ein Thermersetzungssystem,

die uns garantiert, dass unser System terminiert.

Und wir müssen heute dann, wie so oft, einen kleinen Rückstritt durchführen zu einem Thema aus der Mathematik,

das Sie schon lange kennen, und zwar zum Thema Polynome.

Wir werden uns heute mit sogenannten Polynomordnungen beschäftigen.

Und wir werden sehen, wie wir aus unserem Thermersetzungssystem eine solche Polynomordnung herausholen können,

die uns eben dann genau das gibt, was wir wollen, einen Beweis, dass das Thermersetzungssystem terminiert.

Also jeder Term in dem Thermersetzungssystem zu einer Normalform evaluiert.

Und das ist sogar relativ allgemein.

Also wir haben ja letztes Mal am Ende zwei Ideen gesehen, wie man eventuell auf Reduktionsordnungen kommen könnte.

Die eine hat so gut wie nie funktioniert, und die andere Idee war in sehr eingeschränkten Fällen vielleicht auch nützlich, aber dennoch sehr eingeschränkt.

Und diese Polynomordnungen, die funktionieren in vielen Fällen.

Ich glaube, das Tafellicht kann ich noch einschalten.

Aber bevor wir die Polynomordnungen definieren können, müssen wir erstmal sagen, über welche mathematischen Dinge wir hier sprechen.

Wir geben Polynome, und die sind für uns so definiert.

Das Recall.

Wir beschäftigen uns insbesondere mit Polynomen über den natürlichen Zahlen. In der Schulmathematik macht man das meistens ja über den reellen Zahlen.

Uns genügen einfach die natürlichen Zahlen.

Was es weiterhin heißt, ist, dass wir sowohl die koeffizienten aus den natürlichen Zahlen wählen, als auch die Auswertung über den natürlichen Zahlen geschieht.

Diese Polynome bezeichnen wir in dieser Schreibweise n x1 bis xn.

Das ist jetzt ein n-stelliges Polynom, das hat n Variablen x1 bis xn und Koeffizienten über den natürlichen Zahlen.

Das ist definiert als die Menge aller formalen Summen.

Jetzt muss man hier ein bisschen mit Indizes handwerken, das ist immer ein bisschen unübersichtlich.

I1 bis I n aus n. Ich hoffe, man kann das noch lesen.

Für jede Kombination von I1 bis I n aus n haben wir einen Koeffizienten a I1 bis I n.

Der ist auch aus den natürlichen Zahlen.

Und eben die Variablen x1 hoch I1 bis xn hoch I n.

Wie gesagt, die Einschränkungen sind hier, dass die a I1 bis I n natürliche Zahlen sind.

Und zusätzlich, was wir auch noch haben wollen, ist, dass a I1 bis I n gleich 0 fast immer gilt.

Was heißt das mathematisch?

Über alle Kombinationen I1 bis I n aus n.

Das sind die I1 hier.

Das ist eine Zahl.

Das sind n verschiedene I's.

Und da gibt es eben sehr viele Kombinationen davon.

Und für jede Kombination haben wir ein so ein a.

Und die I's sind einfach die Exponenten von unseren Variablen.

Also wenn man das jetzt auf ein Beispielpolynom übersetzt, also sagen wir mal, ja, das sehen wir eigentlich gleich,

aber vielleicht kann ich das gleich mal hinschreiben.

Schreiben wir es doch gleich einfach drunter.

1 bis n.

Je nachdem, ich sage halt hier gerade die Polynome, die die n Variablen haben, haben n xr.

Also zum Beispiel, ich schreibe mal ein Beispiel hin.

3x²y plus 2xy²z.

Das wäre ein Beispiel für so ein Polynom.

Und das ist jetzt aus nxyz.