Eukldischer Algorithmus |
| 03.12.2017, 11:59 | luk100 | Auf diesen Beitrag antworten » |
| Eukldischer Algorithmus im Anhang findet ihr zwei Fotos vom Skript. Ich kann nicht völlig verstehen, wie man mit den Weg, den größten gemeinsamen Teiler finden kann (Bemerkung 2.10 Algorithmus 2.11). Ich finde die Bemerkung ist überhaupt nicht klar wie man die q's findet und wie man am Ende den ggT findet. Kann jemand bitte erklären wie es genau läuft? Und wie ist dieser Weg einfacher oder sozusagen wertvoller als der andere Weg ohne Matrizen? Ein paar Beispiele wären sehr hilfreich. Oder falls jemand weißt, wo ich eine gute Erklärung finden kann, würde ich mich freuen, wenn ihr mir es schicken könntet. Ich habe schon 1 Stunde verschwendet durch das Internet nachzuschlagen aber leider habe ich keine bessere Erklärung oder Beispiele gefunden. Danke im Voraus. [attach]45917[/attach] [attach]45915[/attach] |
||
| 03.12.2017, 13:01 | Elvis | Auf diesen Beitrag antworten » |
Die q's kommen aus der ganzzahligen Division mit Rest, so wie man sie in der Grundschule lernt : Rest In den Gleichungen mit Matrizen, Vektoren und der iterierten Anwendung von steht nichts anderes als die Gleichungen des (erweiterten) euklidischen Algorithmus, deshalb ist die Bemerkung "recht offensichtlich". Der Vorteil der Matrizenschreibweise besteht, wie im Skript gesagt wird, darin, dass man die Darstellung des ggT als Linearkombination von a und b "schmerzfrei" geschenkt bekommt. Der "schmerzhafte" Weg ist die Berechnung der Linearkombination durch Rückwärtsrechnen durch alle Zeilen des euklidischen Agorithmus. |
||
| 03.12.2017, 14:08 | luk100 | Auf diesen Beitrag antworten » |
Hallo Elvis, ja das ist schon klar aber wie kann man die q's genau dann finden? Wir müssen trotzdem die q's finden bevor wir mit dem Matrizenweg anfangen. Aber das ist jetzt die Frage...wenn wir schon wissen was die q's sind, dann was bringt überhaupt diesen Weg zu machen? Wenn wir wissen was das vor letztem q (wenn das letzte q ist null) ist, dann ist das der ggT. |
||
| 03.12.2017, 14:22 | Elvis | Auf diesen Beitrag antworten » |
a=5, b=2 5:2=2 Rest 1 2:2=1 Rest 0 5=2*2+1 2=1*2+0 ggT(5,2)=1 schreibe in Matrizen um und berechne damit die Linearkombination von 1 vergleiche den Aufwand mit dem Aufwand für das andere Verfahren mache 5 kompliziertere Rechnungen, stoppe die Zeit, teile deine Ergebnisse mit - was ist schneller ? Hau rein, sei fleißig, dann lernst du mehr als wenn du andere rechnen lässt. Wenn du Informatiker werden willst, berechne den Rechenaufwand für die unterschiedlichen Verfahren. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
