Robert Sedgewick: Algorithmen

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


41. Die schnelle Fourier-Transformation



Übungen

  1. Wie würden Sie den einfachen Algorithmus des Berechnens-Multiplizierens-Interpolierens verbessern, um zwei Polynome p(x) und q(x) mit bekannten Wurzeln p0, p1, ..., pN-1 und q0, q1, ..., qN-1 miteinander zu multiplizieren?
  2. Geben Sie eine Menge von N reellen Zahlen an, in denen ein Polynom vom Grad N unter Benutzung von wesentlich weniger als N2 Operationen berechnet werden kann.
  3. Geben Sie eine Menge von N reellen Zahlen an, mit deren Hilfe ein Polynom vom Grad N unter Benutzung von wesentlich weniger als N2 Operationen interpoliert werden kann.
  4. Welchen Wert hat wNM für M > N?
  5. Lohnt es sich, lichte Polynome unter Benutzung der schnellen Fourier-Transformation zu multiplizieren?
  6. Die Implementation der schnellen Fourier-Transformation enthält drei Aufrufe von eval, ebenso wie die in Kapitel 36 angegebene Prozedur für die Multiplikation von Polynomen drei Aufrufe von mult enthält. Warum ist die Implementation der schnellen Fourier-Transformation effizienter?
  7. Geben Sie ein Verfahren zur Multiplikation von zwei komplexen Zahlen unter Benutzung von weniger als vier Multiplikationen ganzer Zahlen an.
  8. Wieviel Speicherplatz würde für die schnelle Fourier-Transformation benötigt, wenn wir das Problem der Speicherverwaltung nicht mit Hilfe des perfekten Mischens umgehen würden?
  9. Warum kann eine Methode von der Art des perfekten Mischens nicht verwendet werden, um die Probleme mit dynamisch deklarierten Feldern bei der Prozedur zur Polynommultiplikation aus Kapitel 36 zu vermeiden?
  10. Erstellen Sie ein effizientes Programm zur Multiplikation eines Polynoms vom Grad N mit einem Polynom vom Grad M (nicht notwendigerweise Zweierpotenzen).


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