Transformationen

Gelegentlich ist es vorteil­hafter, ein Problem über einen Umweg zu lösen, als es auf direktem Wege zu lösen.

Weihnachtsstern basteln

Bild 1 zeigt den untauglichen Versuch, einen Stern auf direktem Wege auszu­schneiden.

Der indirekte Weg besteht darin, das Papier zunächst zu falten. Dann wird eine Ecke in das gefaltete Papier geschnitten. Zum Schluss wird das Papier wieder auseinander­gefaltet. Das Ergebnis ist ein perfekt regelmäßiger Stern (Bild 2).

Bild 2: Indirekte Lösung

Der indirekte Weg besteht darin, dass die ursprüng­liche Aufgabe trans­formiert wird. Es entsteht eine neue, gänzlich anders geartete Aufgabe, die leichter zu lösen ist. Zum Schluss wird eine Rück­trans­formation vorgenommen, um aus der Lösung des trans­formierten Problems die Lösung des ursprüng­lichen Problems zu gewinnen. Bild 3 zeigt schematisch diese Vorgehens­weise.

Rechnen mit Logarithmen

Als es noch keine Taschen­rechner gab, wurde in der Schule das Rechnen mit Logarithmen gelehrt.

Hierbei werden zwei Zahlen miteinander multi­pliziert, indem zunächst ihre Logarithmen aus einer Logarithmen­tafel heraus­gesucht werden (Trans­formation). Die Logarithmen werden addiert (Verfahren B). Zu diesem Ergebnis wird nun umgekehrt die zugehörige Zahl, also der inverse Logarithmus, aus der Logarithmen­tafel heraus­gesucht (Rück­trans­formation). Diese Zahl ist das Produkt der Zahlen. Die Rechnung basiert auf der Beziehung

log(a·b) = log(a) + log(b)

Der Umweg über die Logarithmen­tafel lohnt sich dann, wenn der Aufwand für das Heraussuchen der Logarithmen, die anschließende Addition sowie das Heraussuchen des inversen Logarithmus schneller geht als die direkte Multi­plikation. Wirklich effizient ist das Rechnen mit Logarithmen nur, wenn längere Rechnungen mit mehreren Multi­plikationen und insbesondere mit Potenzen und Wurzeln auszuführen sind.

Montgomery-Multiplikation

Ein ähnliches Beispiel aus dem Bereich der ganzen Zahlen ist die Montgomery-Multi­plikation. Das zu lösende Problem besteht in der Multi­plikation zweier ganzer Zahlen a und b modulo einer Zahl n:

c  =  a · b   mod n

Zum Beispiel gilt 3 · 5 mod 7 = 1, denn 3 · 5 = 15 ergibt bei ganzzahliger Division durch 7 den Rest 1.

Die direkte Berechnung erfordert eine Division durch n; diese Operation ist aufwendig, insbesondere bei sehr großen Zahlen, die typischer­weise in der Kryptografie verwendet werden.

Bei der Montgomery-Multi­plikation werden die beteiligten Zahlen mit einer Trans­formation h so trans­formiert, dass anstelle der Division durch n eine Division durch eine Zweierpotenz m möglich ist. Eine Division durch eine Zweierpotenz lässt sich bei binärer Zahlen­darstellung durch eine wesentlich weniger aufwendige Schiebe­operation realisieren.

Auch hier gilt, dass sich die Trans­formation nur lohnt, wenn längere Rechnungen mit mehreren Multi­plikationen und mit Potenzen auszuführen sind.

Polynommultiplikation

Die Polynom­multiplikation lässt sich mithilfe der Schnellen Fourier­transformation beschleunigen. Statt zwei Polynome vom Grad n auf direktem Wege in Zeit Θ(n²) zu multi­plizieren, werden die Polynome zunächst an 2n jeweils gleichen Stützstellen ausgewertet, dann werden die jeweils 2n Funktions­werte miteinander multi­pliziert, und zum Schluss wird aus diesen 2n Werten durch Inter­polation das Ergebnis­polynom berechnet.

Durch Anwendung der Schnellen Fourier­transformation benötigen Auswertung und Inter­polation jeweils Zeit O(n log(n)). Die Multi­plikation der Funktions­werte benötigt Zeit O(n). Insgesamt ergibt sich für die Polynom­multiplikation auf diesem indirekten Wege somit eine Zeit­komplexität von O(n log(n)).

Reduktion

Eine weitere wichtige Anwendung der Trans­formation ist die Reduktion. Wenn es möglich ist, den Umweg in Bild 3 zu gehen, so lässt sich Problem A auf Problem B reduzieren.

Dies ist dann interessant, wenn beispiels­weise kein direktes Verfahren zur Lösung von Problem A bekannt ist. Wenn sich aber Problem A auf Problem B reduzieren lässt und für Problem B ein Lösungs­verfahren bekannt ist, ergibt sich somit ein indirektes Verfahren zur Lösung von Problem A.

Durch Reduktion eines Problems auf ein anderes Problem lassen sich auch oft obere und untere Schranken für die Komplexität der Probleme gewinnen.

Obere Schranken

Hat beispiels­weise Problem B polynomielle Komplexität, d.h. T(n) ∈ O(n^k), und lässt sich Problem A auf Problem B polynomiell reduzieren (d.h. Trans­formation und Rück­trans­formation haben ebenfalls polynomielle Komplexität), so hat Problem A ebenfalls polynomielle Komplexität.

Aus einer oberen Schranke von Problem B lässt sich also unter diesen Bedingungen eine obere Schranke für Problem A gewinnen.

Untere Schranken

Kennt man dagegen eine untere Schranke für Problem A, etwa Ω(f(n)), so muss auch der Umweg über ein Problem B in Ω(f(n)) liegen. Denn ginge der Umweg schneller, so könnte man ihn beschreiten – damit wäre aber Ω(f(n)) keine untere Schranke für Problem A mehr.

Ein Beispiel für diese Vorgehens­weise ist die Bestimmung der unteren Schranke für die Berechnung der konvexen Hülle von n Punkten. Es lässt sich nämlich das Sortier­problem (Problem A) auf das Problem der Berechnung der konvexen Hülle (Problem B) reduzieren. Das Sortier­problem hat eine untere Schranke von Ω(n log(n)). Somit ist Ω(n log(n)) auch eine untere Schranke für den Umweg über Problem B. Trans­formation und Rück­trans­formation liegen in O(n), sind also nicht verantwort­lich für die Komplexität des Umwegs. Also muss Problem B selber, also das Problem der Berechnung der konvexen Hülle, eine Komplexität von Ω(n log(n)) haben.