Robert Sedgewick: Algorithmen

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


41. Die schnelle Fourier-Transformation



Einer der am weitesten verbreiteten arithmetischen Algorithmen ist die schnelle Fourier-Transformation (fast fourier transform), eine effiziente Methode zur Ausführung einer häufig angewandten und grundlegenden mathematischen Berechnung. Die Fourier-Transformation ist von fundamentaler Bedeutung für die mathematische Analysis, sie ist Gegenstand Bände füllender Untersuchungen. Die Entdeckung eines effizienten Algorithmus für diese Berechnung war ein Meilenstein in der Geschichte der numerischen Verfahren.

Die Fourier-Transformation besitzt unzählige Anwendungen. Sie ist die Grundlage für viele wesentliche Operationen bei der Signalverarbeitung, wo ihre Benutzung sehr verbreitet ist. Außerdem liefert sie einen geeigneten Weg zur Erhöhung der Effizienz von Algorithmen für häufig auftretende arithmetische Probleme, wie wir sehen werden. Es würde über den Rahmen dieses Buches hinausgehen, die mathematischen Grundlagen für die Fourier-Transformation darzulegen oder eine Übersicht über ihre zahlreichen Anwendungen zu geben. Unser Ziel ist es, die Merkmale eines grundlegenden Algorithmus für die Fourier-Transformation im Zusammenhang mit einigen anderen von uns untersuchten Algorithmen zu betrachten.

Insbesondere beschreiben wir, wie der Algorithmus angewandt werden kann, um die benötigte Zeit für die in Kapitel 36 untersuchte Multiplikation von Polynomen beträchtlich zu reduzieren. Es werden nur einige wenige elementare Tatsachen aus der komplexen Analysis benötigt, um zu zeigen, wie die Fourier-Transformation für die Polynom-Multiplikation benutzt werden kann. Auch ist es möglich, den Algorithmus der schnellen Fourier-Transformation zu beurteilen, ohne die mathematischen Grundlagen vollständig zu verstehen. Dieser Algorithmus nutzt das »Teile und Herrsche«-Prinzip in ähnlicher Weise wie andere wichtige Algorithmen, mit denen wir uns beschäftigt haben.


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