Nichttrivialer Algorithmus

Neue Frage »

Euklid-300 Auf diesen Beitrag antworten »
Nichttrivialer Algorithmus
Meine Frage:
Hallo Zusammen,
Der euklidische Algorithmus ist der älteste nicht triviale Algorithmus.
Ich habe mich gefragt, was das bedeutet. '
Kennt jemand eine Definition von "nicht trivialen Algorithmus.


Meine Ideen:
Ein Algorithmus heisst nicht trivial, falls gilt ...
g4lois Auf diesen Beitrag antworten »

Zitat:
... is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day

Das Zitat stammt von D. Knuth und wird bei Gelegenheit immer mal wieder herangezogen. Ich fürchte, es wird keine befriedigende Antwort auf deine Frage geben, weil Trivialität in diesem Zusammenhang eine relative Eigenschaft ist.

Die Floskel "Der Beweis ist trivial" ruft bei jedem Mathematiker eine gewisse Vorstellung (jedoch keine strikte Definition) hervor. Es wird mit "offensichtlich", "leicht erkennbar" oder "direkt ableitbar" assoziiert.

Und genauso sehe ich es in diesem Fall auch: Man könnte die ggT-Bestimmung mittels Faktorisierung als trivial bezeichnen. Euklids Algorithmus zeichnet sich ja gerade dadurch aus, dass er nur auf Subtraktionsschritten beruht, genauer auf der Beziehung . Dies ist nicht überaus schwer nachvollziehbar, aber eben auch nicht "trivial".
 
 
Elvis Auf diesen Beitrag antworten »

Der euklidische Algorithmus ist nichttrivial, weil er von einer multiplikativen Eigenschaft ausgeht, nämlich der Teilbarkeit zweier Elemente a und b, und den ggT(a,b) durch einen additiven Algorithmus berechnet. Es ist an sich schon höchst erstaunlich, dass vor über 2000 Jahren jemand so gut rechnen konnte. Ein ebenso großes Wunder ist der erweiterte euklidische Algorithmus, der den ggT(a,b)=xa+yb als Kombination von a und b darstellt (Lemma von Bezout). Weniger trivial ist kaum möglich, man muss nur bedenken, wie schwer es auch für Mathematikstudenten heute ist, diese Algorithmen in beliebigen euklidischen Ringen lediglich zu verstehen und anzuwenden, höchstens einer von 1.000.000 Studienanfängern wäre in der Lage, diesen Algorithmus zu erfinden. Ein Algorithmus heißt trivial, wenn ihn jeder 10. Anfänger sofort nach einer Erklärung versteht und jeder 1000. Mathematikstudent ihn erfinden könnte.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »