Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Komplexität (disjunktive\konjunktive Normalform)
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Komplexität (disjunktive\konjunktive Normalform)
 
Autor Nachricht
jr. firefighter
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 07.12.2005
Beiträge: 5

BeitragVerfasst am: 07 Dez 2005 - 08:01:39    Titel: Komplexität (disjunktive\konjunktive Normalform)

Hallo

Ich sitze vor folgender Aufgabe:
Gegeben ist die konjunktive Normalform
(a v ¬b) ^ (¬c v d) ^ (e v f) ^ (g v ¬h).
Wie lautet die entsprechende disjunktive Normalform?

Das ging noch. Aber jetzt die Frage die mir seit Tagen kopfzerbrechen macht:
-------------------
Sei T die Zeit, die der bestmögliche Algorithmus für die Ausgabe der Lösung ben
ötigen würde. Sei N die Anzahl der Bits, die zur Beschreibung der gegebenen
konjunktiven Normalform nötig sind.
Frage: Wie komplex ist das allgemeine Problem einer solchen Umwandlung bezogen
auf T im Vergleich zu N? Vergiss nicht Deine Antwort zu begründen.
-------------------
Meine Antworten die ich mir denke
Das Problem ist 2^n
Ich habe (..) v (..) ...
16 Therme für DNF

Kann mir da wer weiterhelfen? Ich verzweifle bei dem ;(

Danke!!!!!
mfg
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 07 Dez 2005 - 13:52:40    Titel:

Zitat:
Sei T die Zeit, die der bestmögliche Algorithmus für die Ausgabe der Lösung benötigen würde.


Das ist eine komische Fragestellung. Es geht offenbar nicht um die Komplexität der Berechnung, sondern um die Komplexität der Ausgabe. Und das ganze auch noch im logarithmischen Kostenmaß. Nett. Und der Grund dafür ist wohl der Folgende. Wenn Die nach der Berechnungszeit fragen würden, so würde ein Algorithmus, der immer die (vorberechnete) DNF obiger Formel ausgibt, in O(1) laufen.

Die Frage ist hier, ob die DNF sich weiter vereinfachen lässt. Die Laufzeit des bestmöglichen Verfahrens zur Ausgabe ist exakt gleich der Bitlänge der kürzesten Lösung. Beweise, dass man keine kürzere angeben kann. Dann ist die Zeit gleich ihrer Länge.
jr. firefighter
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 07.12.2005
Beiträge: 5

BeitragVerfasst am: 07 Dez 2005 - 14:27:55    Titel:

Danke für deine Antwort!!!

Hui - mit den Beweisen hab ich so meine Probleme Smile
Wie genau könnte sowas ausschaun?

Danke im Voraus,
mfg
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 07 Dez 2005 - 14:38:26    Titel:

Die Antwort war eigentlich ein Scherz. Wir sollten uns womöglich erst mal bzgl. der Fragestellung mal unterhalten.

Gesucht ist offenbar eine untere Schranke für die KNF->DNF Berechnung. Ich kann schon mal vorab sagen: Die ist exponentiell in der Bitlänge. Der Beweis geht über Potenzmengen denk ich mal.

Zunächsteinmal ist unklar:

- Wollen die die Komplexität für das Beispiel oben oder die allgemeine Komplexität bei der KNF->DNF umwandlung

- Wenn allgemeine, dann in welchem Fall: Worst Case, Best Case usw.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Komplexität (disjunktive\konjunktive Normalform)
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum