[Diskrete] Euklidischer Alg. mit Rückwärtseinsetzen

[Teq]

Ups okay das stimmt

[Nomar]

ich kenn das auch so:

Code: Alles auswählen

(von unten nach oben betrachten)
q    s    t

2 |  2 | -5
1 | -1 |  2
1 |  1 | -1
2 |  0 |  1

man fängt unten an mit s=0 und t=1, und füllt  die Tabelle nach folgender Formel:
s = t_alt
t = s_alt - q*t_alt


Meint ihr man kann das so beim Triesch verwenden?

Beispiel 3.13 im Steger ist eigentlich genau das. Die Verwendung von Information aus der offiziellen Literatur wird ja wohl erlaubt sein müssen.

[Fighter_MV]

Man muss das ganze aber erst vorwärts rechnen und erst dann kann ich rückwärts gehen um t und s auszurechnen richtig?

Noch ne Frage, s ist nicht der ggt oder?

Und noch die letzte Frage: Darf man in der Klausur die Tabelle als Lösungsweg benutzen?

Allerletze Frage:

von kb:

hehe, jo, da fehlt ne 0 ^^

@crazy
also 8 und -13

8 = -1*(-13) -5
-13 = 3*(-5) +2
-5 = -3*2 + 1
2 = 2*1

Im zweiten Schritt, wieso machst du da nicht

-13 = 2*(-5) - 3

Muss man immer den kürzesten Abstand wählen?

[Nomar]

Man muss das ganze aber erst vorwärts rechnen und erst dann kann ich rückwärts gehen um t und s auszurechnen richtig?

Ja.

Noch ne Frage, s ist nicht der ggt oder?

Nein. s ist eine Variable in der Gleichung ggt(a,b)=s*a+t*b. Du sollst s und t finden, so das die Gleichung gilt.

Und noch die letzte Frage: Darf man in der Klausur die Tabelle als Lösungsweg benutzen?

Tja, wenn das schon in der Offiziellen Vorlesungsvorlage[TM] so steht, können sie dir das wohl schlecht verbieten...

Allerletze Frage:

von kb:

hehe, jo, da fehlt ne 0 ^^

@crazy
also 8 und -13

8 = -1*(-13) -5
-13 = 3*(-5) +2
-5 = -3*2 + 1
2 = 2*1

Im zweiten Schritt, wieso machst du da nicht

-13 = 2*(-5) - 3

Muss man immer den kürzesten Abstand wählen?

Gute Frage. Sollte eigentlich beides erlaubt sein, das Ergebnis ist so oder so 2...

[kb]

@Fighter_MV

nein, man muss nicht immer den kürzesten Abstand wählen, aber so kommt man auf die minimale Anzahl von Rechenschritten =]

[padde]

Wie man den erweiterten Euklidischen Algorithmus bei Zahlen anwendet, verstehe ich soweit.

Auf Blatt 5 in Aufgabe 1 soll man das jedoch für Polynome benutzen. Hat da jemand einen Tipp, wie man das angeht?
ggT von Polynomen würde ich normalerweise anhand der Faktorisierung "ablesen", von daher hab ich keine Ahnung wie man das mit dem Eukl. Algorithmus macht..


padde

[kb]

da gibts schon n thread zu

--> http://www.infostudium.de/viewtopic.php?t=1375

[CrazyPumuckl]

Wenn jetzt in der Aufgabenstellung steht: Berechnen Sie den ggT der Form s*a+t*b mit 'Rückwärtseinsetzen', darf ich dann trotzdem die Methode von kb verwenden (das mit der q-s-t-Tabelle (find ich richtig gut die mehtode!)), d.h. das ist doch auch ne Art Rückwärtseinsetzen, oder was meint ihr?

[kb]

Meint ihr man kann das so beim Triesch verwenden?

Beispiel 3.13 im Steger ist eigentlich genau das. Die Verwendung von Information aus der offiziellen Literatur wird ja wohl erlaubt sein müssen.