Horner-Schema
Das Horner-Schema ist ein effizienter Algorithmus zum Berechnen von Polynomen mit komplexen Koeffizienten. Die Idee des Horner-Schemas beruht darauf, dass man ein Polynom f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n in der Form f(x) = a_0 + x(a_1 + x(a_2 + … + x(a_{n-1} + xa_n)…))) schreiben kann. Durch die Klammersetzung wird f(x) zu einer Multiplikation reduziert, was die Berechnung erheblich beschleunigt.
Das Horner-Schema ist besonders nützlich, wenn man den Wert eines Polynoms für einen bestimmten Wert von x berechnen möchte. In diesem Fall muss man nur die Koeffizienten des Polynoms in umgekehrter Reihenfolge eingeben und dann x einsetzen. Die Berechnung des Polynoms für einen bestimmten Wert von x wird so zu einer Multiplikation und einer Addition reduziert.
Übungen mit lösungen zur Horner Schema
Das Horner-Schema ist ein effizienter Weg, um eine Polynomfunktion an einem gegebenen Punkt auszuwerten. Die Idee des Horner-Schemas ist, das Polynom in einer speziellen Form zu schreiben, so dass die Anzahl der Multiplikationen und Divisionen reduziert wird.
Beispiel: Wir möchten f(x) = x4 + 2x3 + 3x2 + 4x + 5 an x = 2 auswerten.
Die Standard-Methode zur Auswertung eines Polynoms an einem gegebenen Punkt würde folgendermaßen funktionieren:
f(2) = 24 + 23 + 3(2)2 + 4(2) + 5
f(2) = 16 + 8 + 12 + 8 + 5
f(2) = 41
Das Horner-Schema funktioniert so:
f(x) = x4 + 2x3 + 3x2 + 4x + 5
f(2) = (24 + 2) + (23 + 3) + (22 + 4) + (2 + 5)
f(2) = 16 + 8 + 12 + 8 + 5
f(2) = 41
Das Horner-Schema hat die Multiplikationen und Divisionen reduziert und ist somit effizienter.
Aufgaben zur Horner Schema
Das Horner-Schema ist ein Algorithmus zur effizienten Berechnung von Polynomen. Es wird named nach dem deutschen Mathematiker Wilhelm Horner, der es 1819 publiziert hat.
Das Horner-Schema funktioniert wie folgt: Gegeben ist ein Polynom P(x) = a0 + a1x + a2x2 + … + anxn mit den Koeffizienten a0, a1, …, an. Die Berechnung des Polynoms an einem Punkt x = x0 wird durch folgende Formel durchgeführt:
P(x0) = a0 + x0(a1 + x0(a2 + … + x0an))
Das Horner-Schema ist ein sogenannter Divide-and-Conquer-Algorithmus: Die Berechnung wird in kleinere Teilaufgaben zerlegt, die dann nacheinander gelöst werden. In diesem Fall wird das Polynom in kleinere Teilpolynome zerlegt, die dann nacheinander berechnet werden.
Das Horner-Schema ist ein sehr effizienter Algorithmus, da es die Anzahl der Multiplikationen und Additionen reduziert. So benötigt das Horner-Schema nur n multiplikationen und n-1 additionen um ein Polynom der Größe n zu berechnen. Im Vergleich dazu benötigt das naiv-Algorithmus (a0 + a1x0 + a2x02 + … + anx0n) n2 multiplikationen und n-1 additionen.
Das Horner-Schema ist also ein sehr effizienter Algorithmus und kann bei der Berechnung von Polynomen eingesetzt werden.
