Euklid von Alexandria & Euklidischer Algorithmus

Letztmalig dran rumgefummelt: 09.01.08 07:04:20

	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. Problembeschreibung

	Über das Leben des griechischen Mathematikers Euklid ist wenig bekannt. Man nimmt an, dass er um das Jahr 365 v. Chr. geboren wurde und dass er seine Ausbildung an Platons Akademie in Athen erhalten hat. Man ist ziemlich sicher, dass er während der Regierungszeit von Ptolemaios I (möglicherweise auch während der von Ptolemaios II) in Alexandria bis etwa zum Jahre 300 v. Chr. gelebt und dort Mathematik gelehrt hat. Berühmt wurde Euklid durch 13 Lehrbücher, in denen das damalige Wissen zur Mathematik zusammengefasst ist. Die Elemente, wie diese Bücher genannt werden, sind die erfolgreichsten Mathematikbücher aller Zeiten. So wurden Übersetzungen dieser Bücher z. B. in England noch im 19. Jahrhundert als offizielle Schulbücher für die Geometrie benutzt. Über Euklid erzählt man sich viele Anekdoten: Ein Schüler fragte, als er den ersten Satz gelernt hatte: "Was kann ich verdienen, wenn ich diese Dinge lerne?" Da rief Euklid seinen Sklaven und sagte: "Gib ihm drei Obolen, denn der arme Mann muss Geld verdienen mit dem, was er lernt." Pharao Ptolemaios fragte einmal Euklid, ob es nicht für die Geometrie einen kürzeren Weg gebe, als die Lehre der Elemente. Er aber besaß den Mut zu antworten, dass es zur Geometrie keinen Königsweg gebe. Auch ein König muss sich wie jeder andere Mensch "auf den Hosenboden setzen", wenn er die Mathematik verstehen will.
	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich - Beispiel: M = {-11, -9, -5, -3, 2, 4, 13,21, 23} Antwort: JA - nämlich für die Teilmenge m = {-11, -9, -5, 2, 23}

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Für kleine Mengen M ist das Problem empirisch durch ausprobieren möglich! Für große Mengen existieren allerdings keine anderen Verfahren, als genau diese: ausprobieren jeden Elements mit jedem - das sind dann aber schon bei 10 Elementen 210 Möglichkeiten.

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-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 9. Januar 2008