buchberger-Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:51 So 07.11.2010 | | Autor: | binchen |
hallo,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
ich bin in der 12 Klasse Gymnasium und muss bis dienstag meine Seminararbeit abgeben, die über Algorithmen, insbesondere aber übre String-Matching und Gröbnerbasen geht. ich bin nun schon fast fertig, bis auf dei beschreibung des Buchberger-Algorithmus. den verstehe ich nicht ganz und nun ist meine frage, ob ihm mir i-jemand kurz in Worten unkompliziert beschreiben könnte. Das würde mir wirklich sehr helfen.
lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:16 So 07.11.2010 | | Autor: | felixf |
Moin!
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> ich bin in der 12 Klasse Gymnasium und muss bis dienstag
> meine Seminararbeit abgeben, die über Algorithmen,
> insbesondere aber übre String-Matching und Gröbnerbasen
> geht. ich bin nun schon fast fertig, bis auf dei
> beschreibung des Buchberger-Algorithmus. den verstehe ich
> nicht ganz und nun ist meine frage, ob ihm mir i-jemand
> kurz in Worten unkompliziert beschreiben könnte. Das
> würde mir wirklich sehr helfen.
Eigentlich ist es ganz einfach: du berechnest alle $S$-Polynome von je zwei Basiselementen und reduzierst diese, und alle Reste ungleich 0 nimmst du mit zur Basis hinzu. Dies machst du solange, bis alle zu 0 reduzieren. Nach dem Buchberger-Kriterium hast du dann eine Groebner-Basis.
Dazu muss man natuerlich beachten: kam bereits 0 raus, braucht man das $S$-Polynom nicht nochmal zu berechnen und zu reduzieren. Das braucht man nur mit "neuen" $S$-Polynomen, also bei Paaren von Basiselementen, von denen mind. eins noch nicht in einem $S$-Polynom vorkam was man schon berechnet hat.
Sagen wir mal, du hast ein Ideal gegeben mit zwei Erzeugern [mm] $f_1, f_2$.
[/mm]
Zuerst rechnest du [mm] $S(f_1, f_2)$ [/mm] aus und reduzierst das. Es kommt sagen wir mal etwas [mm] $\neq [/mm] 0$ heraus, nennen wir es [mm] $f_3$.
[/mm]
Jetzt arbeitest du mit der Basis [mm] $f_1, f_2, f_3$ [/mm] weiter. [mm] $S(f_1, f_2)$ [/mm] hast du schon berechnet, aber noch nicht [mm] $S(f_1, f_3)$ [/mm] und [mm] $S(f_2, f_3)$. [/mm] Diese beiden berechnest du und reduzierst du.
Sagen wir mal, bei [mm] $S(f_1, f_3)$ [/mm] kommt nach dem Reduzieren 0 heraus, bei [mm] $S(f_2, f_3)$ [/mm] aber nicht. Nennen wir das Ergebnis [mm] $f_4$.
[/mm]
Dann machst du mit [mm] $f_1, f_2, f_3, f_4$ [/mm] weiter.
[mm] $S(f_1, f_2)$, $S(f_1, f_3)$, $S(f_2, f_3)$ [/mm] hattest du schon, also musst du [mm] $S(f_1, f_4), S(f_2, f_4), S(f_3, f_4)$ [/mm] berechnen und reduzieren.
Nehmen wir mal an, dass die alle reduziert 0 ergeben. Dann ist [mm] $f_1, f_2, f_3, f_4$ [/mm] eine Groebnerbasis des Ideals und der Algorithmus terminiert.
Ich hoffe das macht es ein wenig klarer...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 So 07.11.2010 | | Autor: | binchen |
boah genial!
ich habs kapiert... vielen vielen dank :D
glg Binchen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:30 So 07.11.2010 | | Autor: | felixf |
Moin,
> boah genial!
> ich habs kapiert... vielen vielen dank :D
freut mich zu hoeren :)
Hast da aber schon ein etwas komplizierteres Thema, zumindest falls du auch nachvollziehen sollst was man mit dem Algorithmus eigentlich will 
LG Felix
|
|
|
|
deine hilfe hat mich echt weitergebracht! 