Algorithmus „Hornerschema“
1. Setze k ← n − 1 und z ← an.
2. Falls k < 0 gehe zu Schritt 6.
3. Setze z ← z · x0 + ak.
4. Setze k ← k − 1.
5. Gehe zu Schritt 2.
6. Gib z aus.
a) Beweisen Sie die partielle Korrektheit dieses Algorithmus für alle n ≥ 0. Hinweis: Verwenden Sie vollständige Induktion bezüglich n.
b) Zeigen Sie, dass der Algorithmus terminiert.
c) Vergleichen Sie die beiden Algorithmen zur Auswertung von p bezüglich der Anzahl der benötigten Multiplikationen!
