www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Schul-Informatik Algorithmen" - buchberger-Algorithmus
buchberger-Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

buchberger-Algorithmus: Erklärung
Status: (Frage) beantwortet Status 
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

        
Bezug
buchberger-Algorithmus: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
buchberger-Algorithmus: Danke :-)
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:20 So 07.11.2010
Autor: binchen

boah genial!
ich habs kapiert... vielen vielen dank :D
glg Binchen

Bezug
                        
Bezug
buchberger-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                
Bezug
buchberger-Algorithmus: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:06 So 07.11.2010
Autor: binchen

jaa.. :D aber des wusste ich noch ned, als ich des thema genommen hab... ich versuch einfach so viel wie möglich zu verstehn :-) deine hilfe hat mich echt weitergebracht! :-)

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Schul-Informatik Algorithmen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]