Allgemeine Fragen

Question

Hallo,

 

woran erkenne ich denn ob ein Aufwand linear O(n^2), exponentiel etc ist?

 

Was heisst denn genau in Polynomialzeit reduzierbar? Was ist Polynomialzeit ?

 

Wie erkenne ich denn z.B. bzw. woher weiß ich denn, dass eine Umwandlung von DNF in KNF max. exponentieller Aufwand sein muss (Tut 4 A1 b)) ? Wie wird denn sowas gerechnet bzw. wie kommt man den zu so einer Schlussfolgerung?

 

LG

Answer 1

Hallo,

also, der Reihe nach zu deinen Fragen:

1) Die Frage ist erstmal recht allgemein und es sei dir gesagt, dass O(n^2) KEIN linearer Aufwand ist, sondern quadratischer. Linear wäre O(n). Leider gibt es kein eindeutiges "Rezept", um den Aufwand zu erkennen. Daher mal zwei Beispiele, aus denen sich das Erschließen des Aufwands eventuell ergibt:

a) Angenommen, du hast ein Programm, bestehend aus einer Schleife. Diese Schleife wird n-mal durchlaufen, n ist dabei beispielsweise eine Eingabe. Der Berechnungsaufwand steigt also linear mit n an, der Aufwand wäre also O(n). 

b) Du möchtest eine Wahrheitstabelle mit Binärvariablen aufstellen. Du hast zunächst zwei Variablen, daher musst du 2^2=4 Kombinationen betrachten. Bei drei Variablen sind es bereits 2^3=8, bei vier Variablen 2^4=16... Der Aufwand (sprich: die Anzahl der Kombinationen) steigt mit jeder Variable um den Faktor 2 an, ist also 2^n für n Variablen. Der Aufwand ist also O(2^n), also exponentiell.

Ich weiß, dass das keine allgemeinen Regeln oder Ähnliches sind, aber eventuell können dir die Beispiele helfen, den Zusammenhang zwischen der Anwendung und der dahinterstehenden Komplexität zu verstehen.

2) Polynome sind alle Funktionen der Form ax^n + bx^(n-1) + ... + ..x^0, also beispielsweise quadratische oder kubische Funktionen aus der Schule. "Polynomialzeit reduzierbar" heißt nun, dass ein Problem in einem Aufwand, der dem Grad eines solchen Polynoms entspricht, umgewandelt werden kann. Am einfachsten ist, sich andere Fälle wie beispielsweise Exponentialzeit als Gegenbeispiel vorzustellen. Der Polynomialzeit kommt besondere Bedeutung zu, weil sie für uns das "noch gut berechenbare" darstellt. Bei bspw. exponentiellem Aufwand wächst die Berechnungsdauer einfach zu schnell zu stark an.

Also: Wenn ein Problem in Polynomialzeit auf ein anderes reduziert werden kann (was sich beispielsweise lohnt, weil wir für dieses andere Problem schon ein Lösungsverfahren haben), dann heißt es "polynomialzeit-reduzierbar".

3) Die Antwort auf die Frage nach einer allg. Lösung ist dieselbe wie in 1).

Zum Beispiel: In KNF sehen Terme ja bspw. so aus: (a ODER b) UND (c ODER d). Will man das jetzt in DNF umwandeln, also mit einem ODER zwischen den Klauseln, so muss man ja die Terme (a UND c), (a UND d), (b UND c) und (b UND d) betrachten. Jetzt war das hier bei zwei Klauseln mit je zwei Variablen noch sehr schön übersichtlich. Hat man aber längere Terme, z.B. (x1 ODER y1) UND (x2 ODER y2) UND (x3 ODER y3), dann wird die Umwandlung schon deutlich länger. Auch hier ist der Aufwand exponentiell.

So, lange Rede kurzer Sinn: Es gibt hier kein Patentrezept, daher Unterlagen anschauen, verschiedene Aufgaben machen und ein Gefühl dafür bekommen. Ich hoffe einfach mal, dass meine obigen Beispiele ein bisschen dieses Gefühl getroffen haben.

Viele Grüße

Max (Tutor)

 

Comments

Max,

Vielen lieben Dank für deine Mühe. Hat dich bestimmt etwas gedauert, um das niederzuschreiben. Geholfen hat es mir sehr!:)