Klausur 02.04.14 2d
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Symmetriediagramm → Nelson/Petrick-Verfahren - kleine Frage
Hallo zusammen,
Wenn man aus einem Symmetriediagramm die Nullblocküberdeckung ausliest erhält man ja die KMF.
Nun ist gewollt, dass man mittels des Nelson/Petrick die DMF ermittelt (könnte man die nicht einfacher durch Einsblocküberdeckung auslesen?)
Bei dem Nelson Verfahren geht es ja darum durch Distr. und Abs. die konjunktive in die disjunktive Form zu bringen und dann durch Überdeckungstabelle und Petrick-Ausdruck die kostenminimale Auswahl daraus zu finden.
Frage: Muss ich das Nelson-Verfahren auf die KMF aus dem SD anwenden oder auf die KNF?
und: wo liegt der Vorteil im N/P Verfahren im Vergleich zum SD?
Hoffe ich hab nichts durcheinander gebracht :rolleyes: ansonsten korrigiert mich bitte bin gespannt auf eine Antwort 
Du hast es perfekt beschrieben 
Für’s Archiv sei noch erwähnt: Keinen Konsensus anwenden! Es gibt Fälle, in denen dieser dazu führt, dass man Primimplikanten verliert.
Das Nelson-Verfahren akzeptiert eine vollständige Nullblocküberdeckung (alle 0er, keine Don’t Cares) in beliebiger konjunktiver Form. Das kann eine der KMFs sein oder die KNF oder irgendwas dazwischen. Letzteres bietet sich z. B. sehr an, wenn man ausgehend von einem SD arbeitet. Sieht man da etwa bereits Nullblöcker, deren Terme man schnell auslesen kann, spart man sich i) die einzelnen Maxterme, ii) den Schreibaufwand und iii) die Fehleranfälligkeit beim Nelson-Verfahren.
Dieses geschickte Auslesen kann auch anhand der Funktionstabelle geschehen, etwa wenn f(0101) = 0 und f(0001) = 0 (Variablenbenennung nach f(abcd)), dann kann man sofort den Term [m]a + c + ~d[/m] auslesen.
Nelson/Petrick heißt: Mit Nelson Primimplikanten finden und mit Petrick eine kostenminimale Auswahl/Überdeckung daraus.
Mit dem SD in einer moderaten Größe (<= 8x4) kann der Mensch sowohl Primimplikanten als auch eine kostenminimale Auswahl davon finden. Algorithmisch ist das nichts anderes als Quine/McCluskey + Petrick.
-
Im für den Menschen ausgerichteten Vergleich: Ich denke bei 4x4 ist das Hingucken beim SD schneller. Beim 8x4 wird’s tricky!
-
Im für den Computer ausgerichteten Vergleich: Nachdem man sich den graphischen Teil sparen kann, läuft das auf „Nelson+Petrick vs. Quine/McCluskey+Petrick“ hinaus. Auf die Schnelle fand ich hierzu auch keine brauchbaren Ergebnisse bei Google. Beide Verfahren sind exakt und damit nur in (minimal) exponentieller Laufzeit* ausführbar. Bei den Schaltungsgrößen, bei denen das noch Sinn ergibt, kann es auch sein, dass beide Verfahren ungefähr gleich schnell sind. Ich vermute, dass bei größeren Schaltungen exakte Verfahren hoffnungslos sind und man heuristische, nicht exakte Methoden anwenden muss.
*) Nach Verfahren nach Quine und McCluskey – Wikipedia ist „das zugrunde liegende Problem NP-vollständig“. Jeder Algorithmus zur Auswahl einer kostenminimalen Überdeckung kann also (sofern P != NP) nur in exponentieller Zeit ausgeführt werden. Unabhängig von P = NP laufen Petrick und Quine/McCluskey ganz sicher mindestens in exponentieller Zeit.