Campus Flensburg

Informatik in Flensburg studieren...

 

Neues Studienangebot

Web- und Softwaretechnologie

 

Wir bieten Ihnen ein praxis­orientiertes Informatik-Studium mit Schwerpunkt auf modernsten Webtechnologien.

Sehen Sie sich einmal den Studienplan an.

 

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Weitere Informatik-Studienangebote an der Fachhochschule Flensburg:

MedieninformatikMedieninformatik

Informations- und Kommunikationstechnik

Wirtschaftsinformatik

 

 

Transformation

 aufwärts

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

 

Weihnachts­stern basteln

Bild 1 zeigt den untauglichen Versuch, einen Stern auf direktem Wege auszuschneiden.

Direkte Lösung
Bild 1:  Direkte Lösung

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).

Papier falten Ecke einschneiden Auseinanderfalten
Bild 2:  Indirekte Lösung

Der indirekte Weg besteht darin, dass die ursprüngliche 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­transformation vorgenommen, um aus der Lösung des trans­formierten Problems die Lösung des ursprünglichen Problems zu gewinnen. Bild 3 zeigt schematisch diese Vorgehensweise.

Indirekte Lösung eines Problems durch Transformation
Bild 3:  Indirekte Lösung eines Problems durch Transformation

 

Rechnen mit Logarithmen

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

Hierbei werden zwei Zahlen miteinander multipliziert, indem zunächst ihre Logarithmen aus einer Logarithmen­tafel herausgesucht werden (Transformation). Die Logarithmen werden addiert (Verfahren B). Zu diesem Ergebnis wird nun umgekehrt die zugehörige Zahl, also der inverse Logarithmus, aus der Logarithmen­tafel herausgesucht (Rück­transformation). 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 Multiplikation. Wirklich effizient ist das Rechnen mit Logarithmen nur, wenn längere Rechnungen mit mehreren Multiplikationen und insbesondere mit Potenzen und Wurzeln auszuführen sind.

 

Polynom­multiplikation

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

Durch Anwendung der Schnellen Fourier­transformation benötigen Auswertung und Interpolation jeweils Zeit O(n log(n)). Die Multiplikation der Funktionswerte 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 Transformation 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 beispielsweise 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 beispielsweise Problem B polynomielle Komplexität, d.h. T(nElement O(nk), und lässt sich Problem A auf Problem B polynomiell reduzieren (d.h. Transformation und Rück­transformation 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 Vorgehensweise ist die Bestimmung der unteren Schranke für die Berechnung der konvexen Hülle von n Punkten. Es lässt sich nämlich das Sortierproblem (Problem A) auf das Problem der Berechnung der konvexen Hülle (Problem B) reduzieren. Das Sortierproblem hat eine untere Schranke von Ω(n log(n)). Somit ist Ω(n log(n)) auch eine untere Schranke für den Umweg über Problem B. Transformation und Rück­transformation liegen in O(n), sind also nicht verantwortlich 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.

 

 

Weiter mit:   up

 

homeH.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 15.01.2003   Updated: 29.03.2011
Valid HTML 4.01 Transitional