Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
ich bin gerade dabei eine Klasse zu schreiben, mit der durch ein KV-Diagramm die boolsche Funktion vereinfacht wird.
Nun habe ich gelesen, das sich in der programmierung das Verfahren von Quine-McCluskey gut anwenden lässt.
Jetzt weiß ich aber nicht, ob ich mit diesem Verfahren auch das ganze Grafisch im KV-Diagramm anzeigen lassen kann?
Das Verfahren basiert ja auf Tabellen.
Ich würde gerne die zusammengefassten Blöcke anzeigen lassen, so wie man es am Papier macht, indem man nach der minterm Methode die "1" mit 2, 4, 8er Blöcken zusammenfasst. Einfach nur die zusammengefassten Blöcke in Farbe anzeigen lassen, mehr brauch ich nicht.
Zuerst einmal: Graphische Lösungsverfahren beruhen vor allem darauf, die Lösung am Ende zu sehen und abzulesen. Und nicht auf Berechnung. Du sitzt aber an einer Maschine, die vornehmlich rechnen kann. Sehen und Ablesen kann sie dagegen nicht so ohne weiteres.
Ich will es mal an einem anderen Beispiel klarmachen: Nimm ein xy-Koordinatensystem, und trage zwei beliebige Punkte ein. Und nun suche die eine lineare Funktion (f(x) = mx + n), die durch beide Punkte geht.
Das graphische Lösungsverfahren ist einfach: Lege ein Lineal an die zwei Punkte an an, ziehe eine Gerade durch, und lese m und n einfach ab.
Das graphische Lösungsverfahren am Rechner zu implementieren ist grober Unfug: Um die Gerade zu zeichnen müßtest die Gleichung bereits vorher lösen, schließlich brauchst du die Parameter ja zur Berechnung wo die Linie verlaufen soll.
Selbst wenn du die Linie ohne vorherige Berechnung eintragen kannst: Danach müßtest du Pixel zählen. Das wird ungenau, und mal ehrlich: Etwas Subtraktion und Division ist da doch deutlich schneller und einfacher.
Mit deinem KV-Diagramm ist es prinzipiell ähnlich: Das ist nur ein Verfahren, um eine bereits gegebene boolsche Gleichung zu vereinfachen. Da kommt zwar oft, aber auch nicht immer die einfachste Form heraus. Das KV-Diagramm erstellst du ja (normalerweise) aus einer Zustandstabelle, die die ursprüngliche Gleichung liefert.
Insofern ist es sehr sinnvoll, direkt ein rechnerisches Verfahren zu verwenden.
Aber gut, lassen wir mal die graphische Darstellung eines KV-Diagramms außer Acht. Das ist sowieso nur optischer Zucker. Wie würdest du denn ein KV-Diagramm in einem Programm modellieren?
Normalerweise würde ich von Arrays absehen, aber hier würde ich es tatsächlich mal mit einem zweidimensionalen Array versuchen (eine ImmutableList, die wiederum ImmutableLists enthält, würde wohl auch gehen).
Und jetzt überleg dir mal, wie du die Indizes einer boolschen Variable zuordnen willst, daß du
a) eine allgemeine Form, d.h. unterschiedlich große KV-Diagramme bekommst
b) dabei nicht durcheinander kommst.
Zeichne dir z.B. mal ein 2x2-KV-Diagramm auf ein Blatt Papier auf, stelle einen allgemeinen Algorythmus auf und spiele ihn dann mal an einem 2x4 und 4x4-Diagramm durch. Du wirst sehen: Das wird nicht einfach.
Und nehmen wir mal an, es gelingt dir. Dann mußt du das Diagramm immer noch auswerten. Jetzt hast du z.B. so etwas:
Jetzt überlege dir mal einen Algorythmus um an deinen Indizees entlangzukrauchen und rauszufinden, welche T mit welchen anderen benachbart sind. Das wird bestimmt schon irgendwie gehen, ist aber sackig kompliziert und aufwändig.
Und das um ein Verfahren zu implementieren, daß noch nichteinmal so ohne weiteres beliebig nach oben hin aufgeblasen werden kann, sondern recht bald an Grenzen stößt an denen es noch sinnvoll angewandt werden kann.
Da ich die Idee mit dem grafischen KV-Diagramm verworfen habe, bin ich jetzt zum Quine-McCluskey-Verfahren gewechselt.
Der Code funktioniert schon sehr gut, aber eine Frage habe ich noch zur Quineschen Tabelle i-ter Ordnung.
So wie ich das gelesen habe, hängt die Anzahl der Quineschen Tabellen von der Anzahl der Eingangsvariablen ab.
Beispiel:
Ich habe in meiner Wahrheitstabelle 4 Eingangsvariablen: A, B, C, D
Dann habe ich (i−1) Ordnungen, also sind das dann: 4 (Eingangsvariablen) - 1 = 3Quinesche Tabellen.
Bei 5 Eingangsvariablen wären es: 5 - 1 = 4Quinesche Tabellen.
...erstmal nachlesen was Quine-McCluskey ist...aha.
Ehrlich gesagt höre ich von dem Verfahren gerade zum ersten Mal (ich bin aber auch kein Informatiker). Es gibt aber auf Wikipedia ein schönes Beispiel dazu, an dem du deinen Plan durchexerzieren kannst. Und zumindest in diesem Fall ist es so, wie du sagst: Eine Tabelle weniger als Eingangsvariablen.
