Skip to main content


Zutaten: Zucker, Kakaomasse (50%), Milchzucker, Weizenmehl, Vollmilchpulver, Magermilchpulver, Butterreinfett, Sahnepulver, Butter (1,4%)
Kann Spuren von Analysis und Geometrie enthalten.

IV_11_titel_zauberlehrling

Lila ist Goethes Zauberlehrling

Lila hat geträumt, dass sie beim Programmieren des euklidischen Algorithmus aus der Schleife mit der Abfrage niemals herauskommt. Was soll sie tun? Das Programm rechnet und rechnet und hört nie auf. Sie hat das Gefühl, dass sie die Geister, die sie rief, niemals loswerden kann. Sie kommen, verrichten Unheil, vermehren sich und sind nicht zu stoppen. Kann ein Programm eine Seele haben? Kann eine Maschine ein Bewusstsein haben? Beim Frühstück mit ihrer Freundin Maya bekommt sie keinen Bissen runter.

Der Zauberlehrling-Traum vom euklidischen Algorithmus

Maya Hi Lila, was ist denn passiert?

Lila Ich habe geträumt, beim Euklidischen Algorithmus nicht aus der Schleife herauszukommen. Es war so schrecklich…

Maya Hm. Wollen wir den Algorithmus nochmal durchgehen?

Lila Ja, gut. Also, ich habe zwei Zahlen m und n. Ich teile m durch n und berechne den Rest. Ist der Rest Null, dann bin ich fertig, n ist der größte gemeinsame Teiler. Ist der Rest nicht Null, muss ich m durch n ersetzen und n durch r. Dann fange ich wieder von vorn an.

IV_11_flowchart_arnold_02-04
Flowchart zum euklidischen Algorithmus nach Donald Knuth.

Maya Richtig. Es gibt viele Fehlerquellen darin, gut, dass wir das besprechen. Du könntest zum Beispiel den Rest r so berechnen:

r\;=\;m\;-\;[\frac{m}{n}]\;\cdot\;n.

Die eckige Klammer steht dann für den ganzen Anteil einer reellen Zahl k: [k], das kann man mathematisch so schreiben:

[k]\;=\;n,\; \mathrm{ falls}\; n\; \le\; k\; <\; n+1,\; n\; \in\; \mathbf{N},\; k\; \in\; \mathbf{R},

also wenn k zwischen den ganzen Zahlen n und n+1 liegt, dann soll n der ganze Anteil sein.

Lila Gut. Verstehe.

Maya Wenn wir m und n positiv wählen, dann wird r immer kleiner. r ist nichtnegativ aufgrund seiner Konstruktion. Also ist die Folge der r’s monoton fallend. Der euklidische Algorithmus startet mit natürlichen Zahlen, r ist natürlich oder 0 und wird nach endlich vielen Schritte Null.

Lila Okay.

Ein Negativbeispiel

Maya Wenn Du nun ein Programm schreibst und m versehentlich nicht natürlich wählst, sagen wir mal:

m \;=\;\pi,

n\;=\;3.

Dann kriegen wir für den ersten Rest:

r\;=\;m\;-\;[\frac{m}{n}]\;\cdot\;n

\;=\;\pi\; -\; [\frac{\pi}{3}]\;\cdot\; 3

\;=\;\pi\;-\;1 \cdot 3

\;=\;\pi\;-\;3.

Lila Gut. Lass mich mal weiter rechnen. Dann setzen wir

m\;=\;3

n\;=\;\pi\;-\;3

und für r erhalten wir:

r\;=\;m\;-\;[\frac{m}{n}]\;\cdot\;n

\;=\;3\;-\; [\frac{3}{3\;-\;\pi}]\;\cdot\;(\pi\;-\;3)

\;=\;3 -21(\pi \;-\;3)

\;=\;66\;-\;21\pi .

Hmm?

Maya Ja, so geht es immer weiter, für das nächste r kriegst Du eine Gleichung

r\;=\;m\;-\;[\frac{m}{n}]\;\cdot\;n

\;=\;k_1 \pi \;+\;k_2

mit ganzen Koeffizienten k_1 und k_2.

Lila Und dann? Ach ja, π ist transzendent, es löst keine algebraische Gleichung! Also wird r niemals Null! Ja, das war mein Traum!

Maya Richtig, r wird immer kleiner, aber niemals Null. Du rechnest und rechnest und rechnest….

Die Rettung

Lila Lass mal den Scherz. Es kann wohl nicht nur im Traum passieren, dass man aus einer Schleife nicht herauskommt.

Maya Ja, genau, Goethes Zauberlehrling! Es ist ein Klischee für fehlendes Bewusstsein für Maschinen und fehlerhaftes Programmieren. Doch man kann ernsthaft was gegen solche und andere Fehler tun. Zuerst denkst Du, kein Mensch wird je für π und 3 den größten gemeinsamen Teiler suchen, aber dann kommt jemand, um Dein Programm zu testen, und der gibt als erstes π und 3 ein….

Lila Na gut, dem kann ich ja vorbeugen, ich lasse nur natürliche Zahlen zu und teste das vor dem Eingang, als Fehlermeldung können wir ja den Zauberlehrling benutzen, haha! Jetzt muß ich mal Max fragen, ob das schon mal jemand in Deutschland gemacht hat und warum Goethe so ein schlechter Programmierer war!

***

Übungsaufgaben

  1. Welche Dinge müssen beim Ausführen des Algorithmus noch getestet werden?
  2. Kann man den Rest auch anders berechnen?

Lösungen

    • Bei jeder Division muss getestet werden, ob der Nenner Null ist.
    • Sind die beiden Zweige nach der Entscheidung richtig programmiert, syntaktisch und inhaltlich?
    • Ist der Rest eine natürliche Zahl oder Null?
    • Ist das Ergebnis eine natürliche Zahl?
    • Ist das Ergebnis wirklich Teiler der Ausgangszahlen m und n?
  1. Ja, in einigen Umgeben ist die Division modulo n als Befehl vorgesehen. Dann erhält man den Rest sofort, muss aber kontrollieren, ob die Eingangsgrößen m und n natürliche Zahlen größer Null sind.