Der euklidische Algorithmus
Weitz / HAW Hamburg
https://www.youtube.com/watch?v=yLeMl2dHw1g

Transkript (automatisch erstellt)

0:02 Da benutzt man nämlich dann denklidischen Algorithmus und das macht man genauso, wie wir das eben grafisch gemacht haben. Stellen
0:11 sich vor, z.B. das muss jetzt man muss gar nicht mit der größeren von beiden anfangen, ist aber sieht ein bisschen einfacher aus. Das war unsere schwarze
0:19 Strecke in dem Bild und dies wäre die kürzere rote Strecke gewesen und wir möchten jetzt ein gemeinsames Maß dafür finden. Dann sind wir ja so vorgegangen,
0:28 wir haben die große Strecke genommen und haben geguckt, wie oft die kleinere Strecke in die große Strecke reinpasst und haben geguckt, ob ein Rest übrig
0:35 bleibt. Das war der erste Schritt. Ja, da gibt es zwei Möglichkeiten, das zu machen. Ich schreib das erstmal hin. Wir fangen an mit den, nee, machen wir es
0:43 mal in schwarz. Wir fangen also an mit diesen beiden Zahlen. 1020 und 768. Dieses abtragen, was ich hier oben in dem Bild gemacht habe, ich gehe noch mal
0:55 zurück. Hier ist unsere schwarze Strecke. Hier ist die rote Strecke. Das ist das, was ich ganz am Anfang gesagt habe. Ich kann
1:02 das so mir vorstellen, dass ich die rote Strecke so lange abziehe, subtrahiere, bis es nicht mehr geht. Oder ich kann mir das so vorstellen,
1:11 dass ich eine Division mit Rest mache. Das ist egal. Das läuft auch dasselbe hinaus, je nachdem, was mir lieber ist, was ich besser im Kopf kann, was für
1:18 mein Programm gerade passt. Wir können ja wirklich mal äh beide Wege hier gehen, zumindest im ersten Schritt, damit man sieht, dass das keinen
1:26 Unterschied ausmacht. Also, die eine Möglichkeit wäre, dass ich von der 1020 die 768 abziehe.
1:40 10 - 8= 2, ein Übertrag, 11 - 6= 5 äh ein Übertrag und dann haben wir 9 - 7= 2, dann kommt hier 252 raus. Von dieser Zahl kann ich nicht noch mal 768
1:53 abziehen, also wäre hier das Reststück, das war das grüne Stück, 252. Oder ich hätte jetzt tatsächlich rechnen können, da würde ich eine schriftliche
2:01 Division machen und würde sagen 1020 ge 768 ist rechen rechen 1 rest 252 kommt natürlich dasselbe raus, das sehe ich ja hier, ne? Hier steht 1 x 768 252. So und
2:16 jetzt haben wir hier, um in dem Bild von vorhin zu bleiben, unser rotes Stück und hier haben wir unser grünes Stück. Und jetzt haben wir
2:23 ja genauso weitergemacht. Wir haben jetzt das grüne Stück versucht in das rote Stück reinzulegen, um zu gucken, ob das geht. Ja, und da können wir jetzt
2:30 auch wieder entweder ein paar mal subtrahieren oder wir können einfach eine Division durchführen. Also, worum es uns jetzt geht, sind die Zahlen 768
2:39 und 252. Und eine Möglichkeit ist, dass wir hier eine Nebenrechnung machen und sagen, wir ziehen mal die 252 ab. Dann haben wir 8
2:48 - 2= 6, 6 - 5= 1, 7 - 2= 5. Da sollte doch die 252 noch mal reinpassen. 6 - 2= 4, 11 - 5= 6, 1 ab 2 264. Das da geht immer noch die 252 rein. 4 - 2= 2. 6 -
3:05 5= 1 12. Jetzt geht's nicht mehr. Jetzt habe ich also gesehen, dass ich dreimal diese Strecke abtragen konnte, dann bleibt hier 12 übrig.
3:15 Oder ich hätte das Ganze auch wieder mit Division machen müssen. Ich mache eine ganz ordentliche schriftliche Division. 768 dur 25
3:24 Rest 12. Das habe ich ja hier auch gesehen, dass ich einmal zweimal dreimal die 252 hier rausziehen kann, ne? Also, sie sehen, das Prinzip läuft immer so,
3:34 äh, ich fange an mit den beiden Zahlen, die mich interessieren, mache eine Division und bekomme einen Rest raus. Wenn ich
3:42 keinen Rest rausbekomme, dann bin ich fertig. Wenn ich nämlich keinen Rest rausbekomme, bin ich an der Stelle angelangt, wo in unserem geometrischen
3:49 Beispiel ich unten diese orangen Stücke hatte, die ohne Rest reinpassten. Aber solange ich noch einen Rest rausbekomme, muss ich weitermachen. Und
3:57 das mache ich, indem ich die kleinere von den beiden Zahlen und den Rest habe und genauso weitermache wie eben. Ich habe wieder zwei Zahlen
4:06 und versuche die eine in die andere reinzukriegen. Also wieder Division mit Rest. Wenn es einen Rest gibt, bin ich noch nicht fertig, mache ich das gleiche
4:13 wieder weiter. Das mache ich jetzt auch. Ich habe wieder zwei Zahlen rausbekommen, 252 und 12,
4:21 mit denen ich weitermache. Und da werde ich jetzt nicht immer 12 abziehen, bis der Arzt kommt, sondern das rechnen wir jetzt mal ähm im Kopf
4:29 aus. Das ist 20 mal 21 mal müsste das hier reinpassen, würde ich sagen. Stimmt das? Äh und äh
4:41 dann habe ich, was habe ich den jetzt gerechnet? Äh 240. Das stimmt, ne? Geht auf. Ja, also hier habe ich jetzt Rest null. Mache ich noch mal deutlich. Das
4:52 geht jetzt auf. Ja. Was ist denn jetzt unser oranges Stück? Was ist das Stück, was in die anderen reinpasst?
5:02 Ja, da hinten. Ja, die 21. 12 die 12, weil ich habe ja, das war ja das
5:15 Stück, von dem ich guckte, ob es in die 252 reinpasst ohne Rest und es passte ohne Rest hier rein. Wie oft ist eigentlich gar nicht so wichtig, aber
5:23 dieses Stück passte 21 mal in die 252 rein, ne? Also äh und das ist auch unsere Lösung. Die 12 ist der größte gemeinsame Teiler.
5:34 Wenn Sie dieses Verfahren also später anwenden, das ist manchmal so ein Punkt der Verwirrung. Welches ist denn jetzt eigentlich die Zahl, die als Ergebnis
5:39 rauskommt? Man kann sich relativ leicht merken, dass man das so lange macht, bis hier ein Rest null rauskommt, aber man kommt gerne hier mal durcheinander und
5:46 fragt sich, welches ist denn jetzt die Zahl, die eigentlich rauskommen sollte? Ich glaube, am einfachsten ist es äh indem man sich das merkt, äh, dass so,
5:54 dass man sagt, der der letzte Rest hier, das ist das, was rauskommt. Also, der letzte Rest bei den ganzen Resten untereinander, der nicht null ist, ist
6:02 das Ergebnis. Dann kommen sie gar nicht in die Verlegenheit, äh vielleicht diese beiden Zahlen durcheinander zu bringen. Das hier haben wir jetzt ausgerechnet,
6:11 ist der größte gemeinsame Teiler von 1020 und 768. Warum das wirklich der größte gemeinsame Teiler ist, habe ich glaube ich an der
6:23 Skizze Ihnen klar gemacht. Ich will da jetzt auch nicht noch einen weiteren formalen Beweis für führen. Ich würde sagen, entweder haben Sie das in der
6:30 Skizze mitverfolgt oder sie glauben jetzt einfach, dass das Verfahren funktioniert. Eine Sache, über die wir vielleicht noch mal reden können, ist
6:38 ich habe sie ja vorhin so ein bisschen absichtlich verwirrt mit der Wurzel aus 2 und habe gesagt, wer sagt mir denn, dass das Verfahren immer funktioniert?
6:46 Also, wer garantiert mir denn das nicht der Falleintritt, über den wir vorhin kurz gesprochen haben, dass ich immer weitermache und niemals in diese schöne
6:55 Situation komme, dass ich so ein passendes Stück finde, sondern es wird immer kleiner und kleiner und kleiner. Irgendwann ist mein Zirkel zu groß, aber
7:01 es es hört nicht auf. Wieso passiert das hier nicht? Der Unterschied ist ja bei dem Beispiel mit den beiden Strecken, was ich ihnen gesagt habe, wo das nicht
7:09 klappen wird, war die eine Strecke Wurzel 2 und die andere Strecke war 1. Also das waren keine ganzen Zahlen. Hier rechnen wir nur mit ganzen Zahlen. Jetzt
7:19 schauen Sie sich mal diesen Algorithmus an, der hier abläuft. Wir gucken uns gleich noch mal ein weiteres Beispiel an und fragen sich mal, das ist eine Frage,
7:26 die Sie sich gar nicht unbedingt als Mathematiker stellen sollten, stellen Sie sich mal die als Informatiker. Wenn das Ihr Algorithmus ist und Ihr Chef
7:34 fragt, sie funktioniert denn das auch, kann das nicht passieren, dass da irgendwie mal eine Endlosschleife auftritt? Das ist eine wichtige Frage,
7:40 die man sich bei jedem Algorithmus stellen sollte. Hört der auch garantiert immer auf? Könnten Sie mir begründen, warum dieser Algorithmus immer aufhört?
7:47 Kann man den das ansehen? Diese Zahlen hier werden immer kleiner. Ne, das liegt ja in der Natur der Sache. Das ist das, was wir uns ganz am Anfang überlegt
7:55 haben. Die Reste, die bei irgendwas rauskommen, sind immer kleiner als der Divisor. Wenn ich hier durch 768 teile, dann muss der Rest auf jeden Fall
8:03 kleiner als 768 sein. Und dann habe ich eine Zahl, die kleiner als 768 ist. durch die teile ich, der Rest muss wieder kleiner als diese Zahl sein.
8:12 Jetzt teile ich durch diese Zahl, der Rest muss wieder kleiner als die sein. Das heißt, die Zahlen, die hier am rechten Rand stehen, die Reste, von
8:19 denen ist garantiert immer jede Zahl kleiner als die da drüber. Ich habe also hier eine Abfolge von Zahlen, von denen jede Zahl immer kleiner als die da
8:28 drüber ist. Weil das aber alles ganze Zahlen sind, muss irgendwann Schluss sein. Ja, es können nicht solche Dinge passieren wie 2 1 einbel
8:39 1 das kann nicht passieren, weil hier immer nur ganze Zahlen auftauchen. Also spätestens bei 0 ist Schluss, dann ist
8:47 das Verfahren zu Ende und damit ist klar, dass das immer funktionieren wird. Ja, also wir haben jetzt einen Algorithmus, von dem wir uns überzeugt
8:53 haben. Der rechnet uns den größten gemeinsamen Teiler aus und der funktioniert garantiert immer. Wunderbar. Wir müssen vielleicht nur
9:01 noch ein bisschen üben, falls Sie noch nie gesehen haben. Darum gucken wir uns noch mal ein Beispiel an.
9:10 Wir wollen ausrechnen den größten gemeinsamen Teiler von 99 und 5390.
9:18 Und das Verfahren geht jetzt genau wie eben. Sie fangen an mit den beiden Zahlen und dividieren die durcheinander.
9:28 Ich mache das jetzt vielleicht mal einen kleinen Tick schneller und nicht mit den ganzen Nebenrechnung, soweit ich das im Kopf hinbekomme. Sie passen auf, dass
9:33 ich mich nicht verrechne. 99 durch 5390, da kann man glaube ich sehen, zweimal geht das nicht, weil das ja über schon über 10 000 ist. Also ist es einmal. Na,
9:42 sollte ich vielleicht doch lieber eine Nebenrechnung machen. 9 10 - 9= 1 9 3 6 1 Rest 3619 ist noch nicht so toll, aber sie sehen
9:59 zumindest, was wir uns eben überlegt haben. Natürlich ist der Rest kleiner als das hier, sonst habe ich beim Dividieren was falsch gemacht. So, jetzt
10:06 nehme ich diese beiden Zahlen. 5390 ge 3619. Einmal passt das da sicherlich rein. Zweimal wird's nicht reinpassen, weil 2
10:17 3000 ja schon 6000 ist. Also machen wir Vorsicht wieder eine kleine Nebenrechnung. Die schmiere ich mal einfach hier drunter. 0 - 9 1 ein
10:25 Übertrag 8 - 1 7 13 - 6 71 1 Stimmt das? Das habe ich da auch. Also steht hier 1 Rest 1771.
10:38 Jetzt kommen die beiden Zahlen hier dran. 3619 geteilt durch 1771. Das wird wohl zweimal reinpassen, ne? 2
10:48 x 17 ist 34. Ja, ich würde mal sagen, da könnte mal von ausgehen, dass das zweimal passt. Mist. Ähm 3619
10:57 2 x 1= 2 x 7= 14 1 15 1 3 sowas 9 - 2= 7 11 - 4 7 ein über 7 2 rest 77. Das ist 23, Rest 0. Und an der Stelle sind wir wieder
11:28 fertig. Und denken Sie dran, merken, gucken Sie einfach in die letzte Spalte. Die letzte Zahl, die hier rausgekommen ist,
11:35 ist das Ergebnis. Also der größte gemeinsame Teiler dieser beiden Zahlen ist 77. Und ich glaube, spätestens an der Stelle
11:44 mit so großen Zahlen wird klar, dass das ein ziemlich geniales Verfahren ist. Äh wenn Sie stattdessen überlegen, dass sie mit irgendeiner Probiermethode versucht
11:53 hätten, das hier rauszufinden, hätten sie ganz schön viel Arbeit gehabt. Und tatsächlich, das werden wir nicht machen. Man kann sich äh man kann
12:01 Überlegung anstellen zum Laufzeitverhalten dieses Algorithmus, also wie schnell der im schlimmsten Fall ist und der ist tatsächlich erstaunlich
12:08 gut. Sowas machen wir vielleicht im vierten Semester mal in der theoretischen Informatik. Da geht's um solche Fragen, wie gut sind Algorithmen
12:15 in Bezug auf ihre Geschwindigkeitseffizienz und obwohl dieses Verfahren tausende von Jahren alt ist, ist das unglaublich
12:21 schnell, weil es halt sehr schnell die Zahlen klein bekommt und darum im Allgemeinen nur sehr wenige Schritte durchlaufen muss.
12:41 Ja. gleich Fragezeichen.
12:50 Also hier ist noch mal die ganze Rechnung mit Ergebnis. Äh, wenn Sie äh Lust haben, sich damit noch ein bisschen näher zu beschäftigen, dann können Sie
12:58 ja mal spaßeshalber sich überlegen, äh was, also das ist ja eh hier zum Schluss hat man das Gefühl gehabt, ist so ein bisschen langsamer geworden. Also, das
13:05 hat nicht mehr so große Sprünge gemacht und man kann sich mal überlegen, das ist jetzt auch nicht so schwer, äh was denn das Schlimmste ist, was einem passieren
13:13 kann. Also was für Zahlen muss man gerade erwischen, dass das Verfahren sozusagen möglichst langsam abläuft? Manchmal hat man Glück und das macht
13:21 ganz ganz große Sprünge. Idealerweise haben sie irgendwann bei zwei großen Zahlen nur einen ganz ganz kleinen Rest. Dann sind sie eventuell sehr schnell
13:28 durch. Aber es kann ihn halt auch passieren, dass sie gerade die Zahlen so dumm gewählt haben, dass immer so es ganz ganz langsam nur vorwärts geht.
13:37 Vielleicht denken Sie mal drüber nach, was das für Zahlen sein müssten.