Euklid von Alexandria & Euklidischer Algorithmus

Letztmalig dran rumgefummelt: 06.09.26 20:37:55

	Die Suche nach dem größten gemeinsame Teiler sowie auch die, nach dem kleinsten gemeinsamen Vielfachen sind zwei eng benachbarte Verfahren. In der englischsprachigen internationalen Literatur wird der mit gcd (greatest common divisor) und das mit lcm (least common multiple) bezeichnet.
	1. Euklid von Alexandria 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Praktische Elementaralgorithmen Euklid von Alexandria begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Wissen für Fortgeschrittene der Informatik Wissen für Fortgeschrittene der Informatik Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 146/147 (2007) Seite 47 ff.

1. Euklid von Alexandria

Euklid von Alexandria (ca. 350 v. Chr. – 270 v. Chr.), kurz Euklid (altgriechisch Εὐκλείδης Eukleídēs, latinisiert Euclῑdēs), war ein griechischer Mathematiker, der im 3. Jahrhundert v. Chr. in Alexandria gelebt hat. Er gilt als „Vater der Geometrie“ und ist Namensgeber für die euklidische Geometrie zur anschaulichen Darstellung des zwei- und dreidimensionalen Raums. Über das Leben Euklids ist fast nichts bekannt. Aus einer Notiz bei Pappos hat man geschlossen, dass er im ägyptischen Alexandria wirkte. Die Lebensdaten sind unbekannt. Die Annahme, dass er um 300 v. Chr. gelebt hat, beruht auf einem Verzeichnis von Mathematikern bei Proklos. Andere Indizien lassen vermuten, dass Euklid etwas älter als Archimedes (ca. 285–212 v. Chr.) war. Aus einer Stelle bei Proklos hat man auch geschlossen, dass er um das Jahr 360 v. Chr. in Athen geboren wurde, dort seine Ausbildung an der Platonischen Akademie erhielt und dann zur Zeit Ptolemaios I. (ca. 367–283 v. Chr.) in Alexandria wirkte. Er sollte nicht mit Euklid von Megara verwechselt werden, wie das bis in die frühe Neuzeit häufig geschah, was dazu führte, dass der Name des Euklid von Megara auch auf den Titeln der Ausgaben der Elemente erschien. In diesem Zusammenhang gibt es unter Historikern Diskussionen, inwieweit Euklid von Alexandria die ihm zugeschriebenen Werke überhaupt selbst verfasst hat. Der Mathematikhistoriker Jean Itard formulierte hierzu im Jahr 1961 drei Hypothesen: Euklid war eine Einzelperson, die alle die Werke zusammenfügte, die man ihm heute zuschreibt. Euklid war eine Einzelperson, die das Oberhaupt einer Schule war, deren Schüler auch nach seinem Tode noch unter seinem Namen publizierten. Euklid war eine Gruppe von alexandrinischen Mathematikern, die unter dem Namen Euklid von Megara veröffentlichten. Die zweite Hypothese wurde von Itard favorisiert.

2. Euklid'scher Algorithmus - größter gemeinsamer Teiler - ggt

	Mit dem euklidischen Algorithmus1 kann der größte gemeinsame Teiler (ggT) zweier Zahlen berechnet werden. In seinen Elementen hat Euklid diesen Algorithmus ungefähr so formuliert: Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst. Hm, das ist recht schwierig zu verstehen. Euklid betrachtet die beiden Zahlen, von denen der größte gemeinsame Teiler ermittelt werden soll, als Strecken (AB und CD). Er zieht wiederholt die kleinere der beiden Strecken von der größeren ab. Er wiederholt dies solange, bis die beiden Strecken gleich lang sind - genauer: er wiederholt dies solange, solange die beiden Strecken nicht gleich lang sind (... CD aber AB nicht misst...). Nicht unerwähnt sollte bleiben, dass wenn die beiden Zahlen schon einmal keine Primzahl sein darf und beide überhaupt irgendwelche gemeinsamen ganzzahligen Teiler haben müssen.
	Beispiel: ggT von 24 und 40 AB: 40, CD: 24, AB größer als CD → 40 - 24 = 16 AB: 16, CD: 24, CD größer als AB → 24 - 16 = 8 AB: 16, CD: 8, AB größer als CD → 16 - 8 = 8 AB: 8, CD: 8, AB gleich CD → Ende → ggT ist 8
	Wir versuchen, den Algorithmus in eine verständlichere und genauere Sprache zu überführen, ohne bereits eine Programmiersprache zu verwenden. Wir benutzen sogenannten Pseudocode: Angenommen, die beiden Zahlen, von denen wir den ggT berechnen wollen, sind a und b: solange a ungleich b ist, wiederhole   wenn a größer ist als b, dann:     ziehe b von a ab und weise das Ergebnis a zu   andernfalls:     ziehe a von b ab und weise das Ergebnis b zu   wenn a gleich b ist, dann:     a (oder auch b) ist der gesuchte ggT Wichtig ist, dass das Einrücken hier eine Bedeutung hat (eine Semantik). In Zeile 1 formulieren wir, dass sich etwas wiederholen soll, solange eine bestimmte Bedingung gilt. Das, was sich wiederholen soll, ist in den Zeilen 2 bis 5 formuliert. Zeile 1 formuliert eine Schleife und in den Zeilen 2-5 befindet sich der Schleifeninhalt. Die Zeilen 2-5 formulieren ein eigenes Konstrukt, nämlich eine Auswahl zwischen Alternativen, abhängig von einer Bedingung. Die Bedingung ist, ob a größer ist als b. Wenn das der Fall ist, dann wird die Alternative ziehe b von a ab und weise das Ergebnis a zu ausgeführt (In der Programmierung werden das später als a = a - b schreiben - das sieht für uns jetzt noch sehr "falsch" aus). Ist jedoch a nicht größer als b, dann wird die Alternative ziehe a von b ab und weise das Ergebnis b zu (b = b - a) ausgeführt. Ein solches Konstrukt wird Selektion (oder auch bedingte Alternative) genannt. Nachdem entweder Zeile 3 oder Zeile 5 ausgeführt wurde (es wird genau eins von beiden ausgeführt), wird erneut in Zeile 1 geprüft, ob a ungleich b ist. Wenn ja, wird die Selektion wiederholt. Wenn nicht, dann ist die Schleife beendet und Zeile 6 wird ausgeführt. Die in Zeile 6 formulierte Bedingung wenn a gleich b ist, ist eigentlich unnötig.

3. Lösungsalgorithmus

	Nimm die vorgegebene Zahl - fülle sie auf vier Stellen auf. Ergibt sich Gleichheit in allen vier möglichen Stellen, so verabschieden wir uns von der Zahl - sie ist keine Zahl innerhalb des Definitionsbereiches - was wir selbstverständlich softwartechnisch exakt wegfangen, wobei wir Oma und/oder Katze nutzen! Wir erhalten in jedem Fall der verbleibenden Restmenge vier Stellen (ungleich in mindest einer Position) und bilden daraus die jeweils kleinste und größte ziffernfolge als Zahl. Von der jeweils größeren subtrahieren wir die jeweils kleinere und verfahren damit, bis wir entweder 6174 oder eine Tiefe von 7 erreicht haben (was im Worst-Case gleichzeitig eintritt).

4. Programmvorschläge

	Hannes Uhlig hat unser Vorschläge konsequent aufgegriffen und einschließlich der Problematik Oma und Katze ein Programm des Kaprekar-Algorithmus notiert, in welchem schon einige Kerngedanken eines sauberen - eben noch nicht objektorientierten Programmieirstils zusammenlaufen.

5. Zusammenfassung

6. Weiterführende Literatur

7. Links zum Thema

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Damen-Problem das Cliquenproblem das Dominoproblem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Wortproblem das Hamiltonproblem das K-Farben-Problem das Flaggenproblem das Halteproblem das Königsberger Brückenproblem das Philosophenproblem das Teilsummensummenproblem das Post'sche Korrespondenz-Problem das Rucksackprolem (Knapsackproblem) das Rundreiseproblem - aber: beachte die Mächtigkeit! das Springerproblem die Türme von Hanoi - mit hoher Anzahl von Scheiben wird das Problem praktisch nicht lösbar - 64 ist bereits enorm hoch das Knotenüberdeckungsproblem The Busy Beaver-Problem das Spannbaumproblem der Maze-Running-Algorithmus das Schachspiel Greedy Algorithm das Maximalflussproblem das Syntheseproblem   das k-Next-Neighbor-Problem   Schwarmintelligenz ... fehlererkennende Algorithmen -  ISBN-Nummer das Binärbaumproblem geometrischen Probleme Dijkstra-Algorithmus Fermat'sches Problem FERMAT's letzter Satz   ZIP-Algorithmus   Bresenham-Algorithmus   der Huffman-Code LZW-Kompression   Quadratsummen-Problem   die glücklichen & traurigen Zahlen   Smarandache-Wellin-Zahlen der austarierte Baum   Trunkierbare Primzahlen   FERMAT'scher Großer Satz   Eulerkreis   Lauflängen-Codierung   Zeichenkettenabgleich
	die Primzahlsuche die Primzahl-Faktorierung Miller-Rabin-Test   der Fluch des Pharao-Algorithmus die Chiffrierung ohne Schlüssel das Teilerproblem Die Sache mit dem Wüstenfit (gefällt mir zu gut) Die Magischen Quadrate - hier beschrieben von Stefan Hecker in einer Belegarbeit aus dem Schuljahr 2001/02 das Chinesische Kisten- oder chinas Postmen-Problem das Labyrinth das PASCAL'sche Dreieck SUDOKU
	einfache aber rechenintensive Spielereien mit Zahlen all den folgenden Problemstellungen ist gemein, dass sie extrem einfach zu beschreiben sind - einzelne Lösungen oder gar alle bzw. mindestens viele zu finden, ist jedoch u. U. extrem zeitkomplex - auch schnelle Computer können daran sehr lange tüffteln. - wer's nicht glaubt, probiert's aus, aber vorab die Randbedingungen gut durchlesen - teilweise gibt's extrem lange Wartezeiten und die Lösung erscheint evtl. in einer Woche, wenn überhaupt Selbst, wenn wir die mitunter große Laufzeit akzeptieren können, stoßen wir teilweise recht schnell an die Realisierbarkeit durch die verfügbaren Datentypen - eine Million ist hier ein eher kleiner Wert - dies zeigen uns sehr deutlich die Perfect Numbers die Primzahl-Zwillingssuche die Primzahl-Palindrome der Kaprekar Algorithmus die befreundeten Zahlen Pythagoräische Tripel die Schmidtzahlen das Autoquadratzahlenproblem Ulam-Spirale die Polynomzahlen Pascal-Zahlen die Goldbach-Vermutung das 153-Problem - Narziß-Zahlen   die Pólya-Vermutung Zahlensystem-Umechner ...als Startbare Datei Software zur Veranschaulichung der Zahlenumrechung das Palindrom-Spiegelsummen-Problem die Perfect Numbers die ABC-Vermutung

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 9. Januar 2008