Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


36. Arithmetik



Trotz ständiger Veränderungen beruht die Existenzberechtigung vieler Computersysteme darauf, daß sie in der Lage sind, schnelle und genaue numerische Berechnungen zu realisieren. Computer haben Fähigkeiten, arithmetische Operationen mit ganzen Zahlen und mit Gleitkommazahlen auszuführen; zum Beispiel können in Pascal Zahlen vom Typ integer oder real sein, wobei alle normalen Rechenoperationen für beide Typen definiert sind. Das Verfahren, das für Rechenoperationen wirklich angewandt wird, ist Teil der Maschinenarchitektur und nicht Gegenstand unserer Betrachtungen (obwohl ein schneller neuer Algorithmus, beispielsweise für die Multiplikation von zwei aus 32-Bit-Zahlen, tatsächlich von enormer Bedeutung sein könnte). Stattdessen wollen wir einige der Algorithmen erörtern, die eine Rolle spielen, wenn die Operationen mit komplizierteren mathematischen Objekten ausgeführt werden müssen.

Im vorliegenden Kapitel wollen wir Pascal-Implementationen von Algorithmen für die Addition und Multiplikation von Polynomen, langen ganzen Zahlen und Matrizen betrachten. Elementare Algorithmen für diese Probleme sind wohlbekannt und sehr einfach, doch es lohnt sich, darüber nachzudenken, wie grundlegende Datenstrukturen für spezielle Situationen anzuwenden sind. Unser Schwerpunkt liegt weniger als sonst bei Anwendungen; stattdessen betrachten wir den Gesamtkomplex der Berechnungen für grundlegende arithmetische Probleme, da die Arithmetik ein ausgezeichnetes Beispiel dafür darstellt, wie die richtige Anwendung algorithmischen Denkens zur Entwicklung raffinierter Verfahren führen kann, die (asymptotisch) wesentlich effizienter sind als elementare Verfahren. Solche Untersuchungen sind auch wegen ihres historischen Hintergrunds von Interesse: Algorithmen für die Ausführung elementarer Rechenoperationen wie Addition, Multiplikation und Division haben eine sehr lange Geschichte, die bis auf die Ursprünge algorithmischer Untersuchungen in den Arbeiten des arabischen Mathematikers al-Khowarizmi zurückgeht, wobei die Wurzeln sogar noch weiter bis zu den Griechen und Babyloniern zurück reichen.

Wir werden sehen, daß die Multiplikation von Polynomen und Matrizen klassische Beispiele für die Leistungsfähigkeit der Methode »Teile und Herrsche« darstellen. Leider sind die sich ergebenden Algorithmen (mit der wichtigen Ausnahme des Verfahrens, das in Kapitel 41 betrachtet wird) kaum praktisch anwendbar; elementare Methoden, die grundlegende Datenstrukturen benutzen, sind mit Sicherheit am besten, außer für ungewöhnlich umfangreiche Probleme.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]