Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
301 Aufrufe
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
in HU-4-1 von uqdrx uqdrx Eins-Komma-Null-Anwärter(in) (4.3k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

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)

 

von udebm udebm Tutor(in) (105k Punkte)  
0 0
Max,

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