Computeralgebra < Sonstiges < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:31 Mo 15.05.2006 | | Autor: | Ilcoron |
Hallo,
ich muss nächste Woche ein Referat in der Schule über Computeralgebra halten. Dabei muss ich mich sowohl auf Geschichtliches, wie auch auf Mathematisches beziehen. Der geschichtiliche Teil stellt kein Problem dar, der mathematische ist hingegen nciht gerade leicht. In den Quellen, die mein lehrer mir gegeben hat, sind mehrere Beispiele von Aufgaben enthalten, die ein Computer löst. Vor allem steht dort auch wie er das macht. Es sind drei Beispiele:
a) Faktorisieren von Polynomen
b) Gröbner-Basen, der Buchberger-Algorithmus (Dies lasse ich komplett weg, da ich noch nie etwas davon gehört habe)
c) Unbestimmte Integrale (Dies erscheint mir sehr kompliziert, und wird deshalb ebenso weggestrichen)
Ich zitiere nun aus dem Quellenmaterial:
Die Idee, modulare Betrachtungen zur Lösung von Problemen über dem Bereich [mm] \IZ [/mm] der ganzen Zahlen zu nutzen, wird besonders wirksam bei der Faktorisierung von Polynomen aus [mm] \IZ[x] [/mm] (in zunächst einer Unbekannten x) in irreduzible Bestandteile. Das klassische Verfahren von Kronecker (vergleiche [Mignotte 1991]) scheitert an zu großem Rechenaufwand und auch an der nicht effektiv gelösten Faktorisierung ganzer Zahlen. Polynomfaktorisierung dagegen ist weitestgehend, d. h. im Rahmen von üblicherweise auftretenden Anforderungen, durchführbar. Hier wieder einige wenige Beispiele, berechnet in MAPLE (der Befehl expand bewirkt, daß die vorgegebene Produktdarstellung vom Rechner nicht gespeichert wird!):
[Anm.: Es folgen mehrere Berechnungen mit MAPLE, die nur Veranschaulichen, wie Faktorisieren mit dem PC aussieht. Ich halte es nicht für nötig die hier aufzuführen.]
Welche Algorithmen laufen nun tatsächlich ab? Sei f ein primitives Polynom
aus [mm] \IZ[x] [/mm] (d. h. der größte gemeinsame Teiler der Koeffizienten ist 1).
[mm] q=p^{k} [/mm] , k > 0 bezeichne die k-te Potenz einer (meist ungeraden) Primzahl p, so daß [mm] \IZ_{q} [/mm] = [mm] \IZ/(q) [/mm] ein Körper ist.
Der Übergang von f [mm] \in \IZ[x] [/mm] zu [mm] \bruch{}{f} [/mm] = f (mod q) bereitet keine Schwierigkeiten. [Anm. des Fragenverfassers: HAHA]
Die Zerlegung von [mm] \bruch{}{f} [/mm] in über [mm] \IZ_{q} [/mm] irreduzible Faktoren gelingt dann, je nach Verfahren, in einem oder mehreren Schritten:
1. Herstellen der quadratfreien Zerlegung: mehrfach auftretende Faktoren
werden hier bereits berechnet;
2. Zerlegung nach verschiedenen Graden: Zerlegung eines quadratfreien Polynoms in ein Produkt, wobei der i-te Faktor nur aus irreduziblen Faktoren i-ten Grades zusammengesetzt ist; sind keine irreduziblen Faktoren etwa vom Grade k vorhanden, so wird dies erkannt. Hat der i-te Faktor Grad i, so ist er bereits irreduzibel.
3. Zerlegung nach gleichen Graden: Zerlegung der Faktoren von 2. in über [mm] \IZ_{q} [/mm] irreduzible Faktoren.
In einem nachfolgenden Schritt 4 sind aus den Faktoren von [mm] \bruch{}{f}, [/mm] berechnet nach 2.und 3., diejenigen von f zu gewinnen. Zu bedenken ist hier, dass irreduzible Faktoren von f zwar in Faktoren von [mm] \bruch{}{f} [/mm] übergehen, diese aber über [mm] \IZ_{q} [/mm] nicht mehr irreduzibel sein müssen. Die Zerlegung über [mm] \IZ_{q} [/mm] ist also feiner.
Ist q selbst Primzahl, hinreichend groß, so stimmen die Zerlegungen von f und
[mm] \bruch{}{f} [/mm] überein. Dies ist neben der Nutzung modularer Methoden ein wesentlicher
Punkt. Eine Strategie A besteht darin, solche q zu bestimmen. Man erhält
sie durch gewisse Abschätzungen, das Rechnen in [mm] \IZ_{q} [/mm] gestaltet sich durch das
große q jedoch nachteilig.
Strategie B geht von einer kleinen Primzahl p aus. Auf der Grundlage von
Hensels Lemma gelingt dann das sogenannte "Hensel lifting":
Zu [mm] \bruch{}{f}=\bruch{}{f1}*\bruch{}{f2} \in \IZ_{p}[x] [/mm] wird [mm] \vec{\vec{f}}=\vec{\vec{f1}}*\vec{\vec{f2}} \in \IZ_{p^{2}}[x] [/mm] [Anm.: Die holprige Darstellung tut mir leid, aber ich wusste nciht wie ich f quer oder f mit 2 Strichen drüber anders darstellen sollte.]
konstruiert. Rat man das "Hensellifting" mehrfach durchgeführt, so werden
die Faktoren von f, wenn vorhanden, tatsächlich gefunden.
Varianten bestehen zum Beispiel in folgendem Vorgehen:
f wird bereits in [mm] \IZ[x] [/mm] quadratfrei gemacht. q wird danach, eventuell im Rahmen
eines probabilistisch arbeitendem Verfahrens, so gewählt, daß auch [mm] \bruch{}{f}
[/mm]
quadratfrei bleibt. So kann man dann gleich mit Schritt 2 fortfahren.
Schritte im Hensellifting werden ersetzt durch den sogenannten LLL-Algorithmus
[Lenstra, Lenstra, Lovacs 1982].
Die Ausdehnung obiger Verfahren auf Polynome mit Koeffizienten aus algebraischen
Zahlbereichen ist ebenso wie die Ausdehnung auf den multivariaten
Fall befriedigend gelungen.
Grundlegende Ideen bzw. das Aufstellen der Algorithmen für die geschilderten
Schritte stammen von Berlekamp, Zassenhaus und Cantor - Zassenhaus
und zwar [Berlekamp 1967] bzw. [Berlekamp 1970] für Schritt 2 und Schritt 3
zusammengefaßt, [Zassenhaus 1969]für Schritt 2, [Cantor - Zassenhaus 1981]
für Schritt 3.
Für den 4. Schritt sind Hensel [Hensel 1918] mit seinen grundlegenden Arbeiten
und Zassenhaus [Zassenhaus 1970] als Pioniere zu erwähnen. Letzterer
hat als erster das "Hensellifting" zur Faktorisierung von Polynomen eingesetzt.
Die Wurzeln der Algorithmen liegen zum Teil aber schon bei Gauß, Legendre,
Galois u. a. Einen sehr guten Überblick vermittelt [v. z. Gathen, Gerhard
1999]; der erstgenannte Autor ist selbst neben zahlreichen weiteren, z.B. Erich
Kaltofen, mit mehreren Arbeiten an der Entwicklung und Verbesserung von
Verfahren zur Faktorisierung von Polynomen beteiligt.
Es tut mir wirklich leid, dass ich euch mit so einer Ladung Text überfallen muss. Allerdings verstehe ich nicht übermäßig viel. Die Körpertheorie kann ich mir überhaupt nicht vorstellen. Wir haben zwar Vektorräume gemacht aber mir ist nciht ganz klar wie das zusammenhängt.
Ich wäre euch so dankbar wenn ihr euch vielleicht mal die Zeit nehmt und mir das ganze System vielleicht mal an einem Beispiel erklärt.
Ich hoffe ich werde es schaffen, sonst wird mein Referat eher dürftig.
Euer Ilcoron
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:44 Mo 15.05.2006 | | Autor: | goeba |
Hi,
ich finde, Du solltest noch mal mit Deinem Lehrer Rücksprache halten. Es könnte ja evtl. sein, dass er sich diese Quellen gar nicht so genau angeschaut hat. Denn: Was die ganze Körpertheorie betrifft, so hast Du keine Chance, das in einem Referat für die Schule verständlich darzustellen.
Zu der Art, wie die Algorithmen funktionieren, kann ich selbst nicht viel sagen, vielleicht weiß jemand anderes, ob es da evtl. ein einfaches Beispiel gibt, das man in der Schule bringen könnte.
Ich würde als Lehrer (und ich bin Lehrer und würde meine, ich verstehe also ein wenig davon ...) viel eher folgendes erwarten:
- Von den Dingen, die Ihr schon gemacht habt, mal zeigen, wie man das mit einem CAS macht. Das wäre sicherlich
- Nullstellenberechnung (was ja bei Polynomen aufs gleiche wie die Faktorisierung hinausläuft)
- Differentiation und Integration. Du wolltest das mit den unbestimmten Integralen rauslassen, aber das würde ich nicht!
- evtl. lineare Gleichungssysteme, auch mit Parametern
Das käme jetzt natürlich auch drauf an, ob Ihr vielleicht sowiso einen TR mit CAS habt, dann wäre das natürlich alles ein alter Hut für Euch!
Vom Matheunterricht her ist ja das bedenkenswerte: Praktisch alles, an dem man per Hand stundenlang rumrechnen muss, geht mit einem CAS auf Knopfdruck.
Du könntest auch z.B. mal eine Extremwertaufgabe (eine richtig fiese) vorstellen, bei der dann "nur noch" die Schwierigkeit darin besteht, die Funktion und die Nebenbedingungen zu finden. Die Rechnung erledigt dann der Rechner.
Es sollte am Ende klar sein: Ein Matheunterricht, der die ganze Zeit ein CAS einsetzt, ist eigentlich schwerer als einer ohne. "Standardaufgaben" gibt es nicht mehr- das wäre sinnlos. Nur noch der Ansatz zählt, und den zu finden ist normalerweise ein (zumindest etwas) kreativer Vorgang.
Also, das war jetzt mehr eine pädagogische Antwort als eine mathematische, aber ich wüsste nicht, wie Du das mit den Gröbnerbasen sinnvoll in einem Referat in der 12. Klasse vorstellen sollst.
Viele Grüße,
Andreas
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 14:54 Di 16.05.2006 | | Autor: | Ilcoron |
Hallo
danke, dass du dir die Mühe gemacht hast :)
Ja wir haben die ganze Zeit schon mit einem CAS in der Schule gerechnet. Mein mathematischer Background ist leider auch nicht mehr aktuell. Ich bin schon in der 13. Klasse und habe die schriftlichen Prüfungen schon hinter mir. Wir müssen diese Referate anstatt der letzten Klassenarbeit halten. Bei diesen Referaten geht es auch nur teilweise um die mathematischen Probleme vielmehr um die Mathematische Geschichte und Entwicklung. Die Überschrift unter der die Referate laufen lautet "6000 Jahre Algebra und Mathematik". Wir haben in der Frühzeit angefangen und uns dann immer weiter vorgearbeitet und ich bin der letzte mit meinem Thema.
Ich denke das wesentliche an meinem Referat sollte sein, wie die Verwendung des Computers die Mathematik verändert hat. Z.B. dass es nun immer wichtiger wird effizientere Algorithmen zu schreiben und sich über einen ausgefeilten Symbolismus Gedanken zu machen, damit man dem Computer mitteilen kann was er tun soll.
Bei diesen Ausführungen wäre es sehr gut wenn ich ein Beispiel zur Vorgehensweise der CAS geben könnte. In meinem Quelltext sind die drei genannten Beispiele aufgeführt, sie sind jedoch alle über die Körpertheorie gelöst (in Wikipedia verstehe ich diese Körpertheorie auch nciht).
In meinem Quelltext ist als weiteres Beispiel der Euklidische Algorithmus genannt. Dieser kann mittels CAS nicht in herkömmlicher Weise bearbeitet werden, sondern musste angepasst werden. Vielleicht könnte ich in meinem Referat auf beide Methoden eingehen. Bei Wikipedia steht sowol etwas über den Euklidischen Algorithmus wie über seine Bearbeitung mittels eines Computers.
In meinem Quellenmaterial steht jedoch, dass dabei Probleme auftreten können, wenn man ihn auf Polynome anwendet. Bei rationalen Koeffizienten können die Teilergebnisse teilweise sehr komplex werden (die Koeffizienten werden wesentlich größer).
AUf http://de.wikipedia.org/wiki/Euklidischer_Algorithmus ist alles ganz gut erklärt soweit ich sehe. Glaubt ihr das ist ein gutes Beispiel oder habt ihr noch anregungen ich wäre sehr dankbar für alle Tips.
Ilcoron
P.S. Falls man das Anfangsbeispiel doch noch verständlcih nutzen könnte wäre es auch nciht schlecht.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:10 Di 16.05.2006 | | Autor: | goeba |
Hi,
der Euklidische Algorithmus ist auf jeden Fall ein gutes Beispiel. Den kann man sowohl vom eigentlichen Algorithmus als auch von der Anwendung im PC gut verstehen.
Symbolische Integration und Differentiation sind - das habe ich nur gehört, ich habe es nicht selbst durchgearbeitet - wohl auch ganz gut zu erklären, da die verwendeten Methoden sehr nahe an dem sind, wie man es "per Hand" macht.
Ein Anspruchsvolles Thema!
Von der Körpertheorie würde ich, wie gesagt, die Finger lassen. Ich könnte mir denken, dass Du selbst es so weit verstehen könntest, dass Du ein geeignetes Beispiel dann auch verstehst, aber Du hast in dem Referat keine Chance, dass die anderen es verstehen.
Kannst Du programmieren? Ist vielleicht eine Schnapsidee, aber z.B. das Computeralgebrasystem Yacas ist sehr klein und openSource, da kann man mal anschauen, wie so was wirklich gemacht wird. Ist aber, wenn Du nicht einige Programmiererfahrung hast, sicher keine gute Idee.
Es wäre sicher nicht schlecht, wenn sich hier jemand, der Erfahrung mit den Algorithmen zur Computeralgebra hat, auch noch melden könnte ?!?
Viele Grüße,
Andreas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Di 23.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
