1 00:00:04,560 --> 00:00:05,640 Das war's für heute. 2 00:00:05,640 --> 00:00:08,720 Bis zum nächsten Mal. 3 00:00:09,178 --> 00:00:15,178 KV-Diagramm und Terme. Vom KV-Diagramm zum Term und andersherum. 4 00:00:18,818 --> 00:00:26,098 Das Carnot-Feitsch-Diagramm, kurz KV-Diagramm, ist ein grafisches Optimierungsverfahren für 5 00:00:26,098 --> 00:00:35,218 bullshit Terme, das sich insbesondere zur manuellen Optimierung für drei oder vier Variabeln eignet. 6 00:00:35,712 --> 00:00:40,352 Bei weniger Variabeln kriegt man es in der Regel auch mit Buccia Algebra direkt hin und 7 00:00:40,352 --> 00:00:46,172 bei mehr als vier Variabeln wird es manuell schon wieder eng, aufgrund der räumlichen 8 00:00:46,172 --> 00:00:50,712 Nachbarschaftsverhältnisse, die man sich als Mensch nur schwer vorstellen kann. 9 00:00:52,112 --> 00:00:59,552 Die grundsätzliche Idee ist die, dass in einer Tabellenform, also grafisch, Terme 10 00:00:59,582 --> 00:01:02,542 getragen werden und 11 00:01:03,312 --> 00:01:08,892 diese können entfallen, wenn sich die Variablenbelegung nur in dieser einen Variablen unterscheidet. 12 00:01:09,092 --> 00:01:13,872 Und das sieht man zumindest bei drei oder vier Variablen sehr viel einfacher, 13 00:01:14,112 --> 00:01:20,652 als man das per Buccia-Algebra ausrechnen kann. 14 00:01:20,852 --> 00:01:27,072 Natürlich ist das möglich per Buccia-Algebra, aber das K-V-Diagramm ist da schon einfacher. 15 00:01:28,432 --> 00:01:31,752 Wie wird ein K-V-Diagramm jetzt konstruiert? 16 00:01:33,228 --> 00:01:38,908 Systematisch. Es gibt hier mehrere Varianten. Das sieht man direkt am ersten 17 00:01:38,908 --> 00:01:43,628 Fall, wenn man nur eine Variable hat, hat man entsprechend zwei Felder, weil immer 18 00:01:43,628 --> 00:01:47,888 die Variable selbst und die Negation, also x1 nicht, die für gewöhnlich dann 19 00:01:48,588 --> 00:01:54,508 nicht hingeschrieben wird, notiert werden. Jetzt könnten Sie auch das Feld 20 00:01:54,508 --> 00:01:59,348 hier mit x1 belegen und da, wo jetzt x1 dran steht, für x1 nicht 21 00:01:59,348 --> 00:02:00,888 resolvieren. Das hat dann 22 00:02:01,072 --> 00:02:10,152 eine andere Aufteilung zufolge. Grundsätzlich erhält man das nächst komplexere KV-Diagramm 23 00:02:10,152 --> 00:02:16,352 immer durch Umklappen an den Horizontalen und dann Umklappen an den Vertikalen. Das soll 24 00:02:16,352 --> 00:02:21,932 heißen, wir gehen mal vom KV-Diagramm für eine Variable aus, dann wird das einmal gespiegelt 25 00:02:21,932 --> 00:02:30,092 bei einer x-Achse sozusagen, erhält man das hier, klappt das vertikal um, dann hat man 26 00:02:30,288 --> 00:02:36,228 die Variante für 3 Variablen, dann klappt man wieder horizontal um, da hat man das für 27 00:02:36,228 --> 00:02:44,408 4 und so weiter. Die beiden gängigsten Varianten sind die für 3 und 4 Variablen, meistens hat 28 00:02:44,408 --> 00:02:49,528 man Übungsprobleme vorliegen, die auf 4 Variablen bezogen sind. 29 00:02:53,086 --> 00:02:59,906 Das KV-Diagramm ist eigentlich sehr intuitiv und leicht umzusetzen, solange man sich bei 30 00:02:59,906 --> 00:03:02,366 drei oder vier Variablen bewegt. 31 00:03:02,686 --> 00:03:09,186 Das einzige Problem und auch das, was dafür sorgt, dass es ab vier Variablen, bei mehr 32 00:03:09,186 --> 00:03:16,506 als vier Variablen schwieriger wird, sind die Nachbarschaften. 33 00:03:16,506 --> 00:03:22,046 Benachbarte Elemente in einer Tabelle sind benachbart nach wie vor, allerdings, da 34 00:03:22,416 --> 00:03:28,936 man es hier mit räumlichen Strukturen bezüglich der Nachbarschaften zu tun hat, 35 00:03:29,856 --> 00:03:32,556 ist es relativ schnell schwer vorstellbar. 36 00:03:33,356 --> 00:03:38,136 Was relativ häufig vorkommt, sind die sogenannten Randnachbarschaften. 37 00:03:39,476 --> 00:03:46,256 Wenn alle vier Ecken belegt sind, dann kann man die auch zu einem Viererblock zusammenfassen, 38 00:03:46,256 --> 00:03:50,856 genauso wie die Eckfelder hier mal mit Grün markiert. 39 00:03:51,256 --> 00:03:51,956 Also dieses... 40 00:03:51,984 --> 00:03:56,824 grüne Feld ist mit dem grünen Feld hier benachbart oder die grauen beiden grauen 41 00:03:56,824 --> 00:04:04,624 Felder ebenfalls. Es kann helfen sich das als sogenannter Buhlscher Würfel vorzustellen. 42 00:04:05,264 --> 00:04:10,124 Diese grauen Striche deuten die Nachbarschaften an. Das heißt, wenn sie 43 00:04:10,124 --> 00:04:16,584 hier ein Würfel haben, dann sind die grauen Flächen jeweils für 44 00:04:16,584 --> 00:04:20,644 Nachbarschaften stehend. Und deswegen wird auch klar, warum hier diese 45 00:04:20,644 --> 00:04:21,204 Flächen... 46 00:04:21,472 --> 00:04:44,492 zueinander benachbart sind. Wenn Sie sich hier den Schnitt durch den Würfel vorstellen und das 2D-mäßig aufklappen, dann hat der braune Knoten hier, die beiden, den grünen und den türkisen zum Nachbarn, den grünen sehen Sie direkt, aber der türkise ist aufgrund des Schneidevorgangs jetzt auf der anderen Seite. 47 00:04:44,892 --> 00:04:50,252 Aber wenn Sie den wieder zusammenkleben sozusagen und einen Würfel haben, dann liegt Braun und Türkis zusammen. 48 00:04:50,656 --> 00:04:57,716 Deswegen haben Sie diese Randnachbarschaften. Also das ist nicht so leicht mit der Vorstellung, 49 00:04:57,876 --> 00:05:06,996 deswegen hat auch das KV-Diagramm gewisse Grenzen. Schauen wir uns das erste Beispiel an. 50 00:05:07,956 --> 00:05:14,296 Wie kommt man vom Term zum KV-Diagramm, vom KV-Diagramm zum Term und wie kriegen wir die Minimierung hin? 51 00:05:14,296 --> 00:05:17,596 Ausgehend von der distruktiven Normalform. 52 00:05:18,272 --> 00:05:26,772 Erhält jeder unverknüpfte Teilterm einen Eintrag mit 1 in irgendeiner Zelle. 53 00:05:27,512 --> 00:05:31,652 Das heißt, man klappert systematisch die Variablen ab. 54 00:05:32,072 --> 00:05:33,852 Ich empfehle, wie folgt, vorzugehen. 55 00:05:34,052 --> 00:05:40,832 Man geht systematisch bezüglich der Felder, ich nenne das Reduktionsverfahren vor, 56 00:05:40,832 --> 00:05:43,032 soll heißen X1. 57 00:05:44,584 --> 00:05:50,264 Taucht in den beiden Spalten hier auf. Die Spalte und die Spalte. Das heißt, man kann 58 00:05:50,264 --> 00:05:55,124 über die vier Zellen hier ein Finger draufhalten oder darüber bewegen. 59 00:05:56,244 --> 00:06:03,004 X2 nicht. X2 nicht ist in dieser Zeile. Das heißt, aus den vier Feldern werden 60 00:06:03,004 --> 00:06:06,864 die beiden hier schon mal gestrichen und man kreist jetzt nur noch um die 61 00:06:06,864 --> 00:06:10,864 beiden Kandidatenfelder. Man schränkt die Menge der möglichen Felder also 62 00:06:10,864 --> 00:06:11,724 excessiver ein. 63 00:06:12,208 --> 00:06:20,548 Jetzt haben wir hier noch x_3 nicht. x_3 ist hier. x_3 nicht ist in dem Bereich. Das heißt, es bleibt nur die Zelle übrig. 64 00:06:24,688 --> 00:06:28,308 Erste Einschränkung. Aus acht Zellen wurden die vier hier. 65 00:06:29,328 --> 00:06:37,448 Zweite Einschränkung. Aus den Vieren wurden die zwei Felder. Und aus den zwei Feldern durch die letzte Einschränkung ist dann unser Ziel übrig geblieben. 66 00:06:38,768 --> 00:06:41,428 Hier ist also die eins für den linken Teilterm. 67 00:06:42,224 --> 00:06:52,084 Der rechte Teilterm, der Klamann-Term, gleiches Verfahren. x1 sind die Felder und x2 nicht, 68 00:06:52,144 --> 00:06:59,184 auch wieder die untere Zeile entfällt, und x3 bleibt nur diese Zelle übrig, 69 00:06:59,484 --> 00:07:07,824 die kriegt nur eins spendiert und so weiter. Sollten wir die Situation haben, 70 00:07:07,824 --> 00:07:09,464 dass wir den Term... 71 00:07:09,648 --> 00:07:15,268 für den die eins steht oder diesen hier rekonstruieren müssen, gehen sie einfach rückwärts vor. 72 00:07:15,788 --> 00:07:17,408 Nehmen wir uns mal den Term her. 73 00:07:18,408 --> 00:07:19,408 Da lesen sie 74 00:07:19,408 --> 00:07:25,208 für jede Variable den Term ab, der da eben in der Zeile bzw. Spalte steht. 75 00:07:25,288 --> 00:07:27,028 Hier ist es x1 76 00:07:27,028 --> 00:07:32,088 und x2 nicht und x3. Fertig. 77 00:07:33,448 --> 00:07:36,048 Gut, wie geht es jetzt weiter? 78 00:07:36,592 --> 00:07:43,192 Was die Optimierung angeht. Man trägt die Terme ja zunächst ein, um sie dann zu vereinfachen. Das ist ja der ganze 79 00:07:43,192 --> 00:07:45,352 Sinn des Carnot-Falch-Diagramms. 80 00:07:47,192 --> 00:07:57,912 Immer maximal große Blöcke bilden, wobei Blöcke nur in Größen einer Zweierpotenz erlaubt sind. Sprich 2, 4, 8, 16, 32, 64er Blöcke. 81 00:07:59,372 --> 00:08:04,052 Und immer maximal große Blöcke bilden, sonst kriegen sie nicht zwangsläufig ein minimales Ergebnis. 82 00:08:04,692 --> 00:08:06,132 Dabei die Ränder beachten. 83 00:08:06,704 --> 00:08:20,864 Gut, hier sind nur zwei Einsen vorhanden. Da bildet sich der zweier Block einfach und entfällt eine Variable entfällt, wenn sie sowohl in negierter als auch in nicht-negierter Form vorkommt. 84 00:08:21,564 --> 00:08:30,664 Gucken wir uns das an. X1 kommt in beiden Einsfeldern vor, muss notiert werden. 85 00:08:32,404 --> 00:08:36,424 X2 haben wir hier in der unteren Zeile. 86 00:08:36,864 --> 00:08:41,204 In der für uns relevanten Zahl steht durchgängig X2 nicht. 87 00:08:41,664 --> 00:08:43,424 Wird als X2 nicht notiert. 88 00:08:43,904 --> 00:08:49,804 Die 1 ist X3, die Nachbarschafts 1 ist X3 nicht. 89 00:08:50,184 --> 00:08:56,564 Das heißt wir haben X3 und X3 nicht. Die Variable kommt in negierter und in nicht negierter Form vor. 90 00:08:56,884 --> 00:08:57,904 Fliegt also raus. 91 00:08:58,644 --> 00:09:00,324 Sprich man kann den Term 92 00:09:01,244 --> 00:09:02,504 vereinfachen zu diesem. 93 00:09:03,224 --> 00:09:05,164 Der ist so übersichtlich, das kriegen wir 94 00:09:05,600 --> 00:09:09,360 auch mit Butcher Algebra durch scharfes Hinschauen noch hin. 95 00:09:09,680 --> 00:09:11,160 Wie würde man da vorgehen? 96 00:09:11,600 --> 00:09:16,280 Wir würden x1 und x2 nicht aus dem Term rausschreiben 97 00:09:16,280 --> 00:09:19,220 und aus dem Term auch, sprich ausklammern 98 00:09:19,220 --> 00:09:20,580 und dann bleibt 99 00:09:20,580 --> 00:09:21,580 hier übrig 100 00:09:21,580 --> 00:09:24,340 x3 nicht und x3 101 00:09:24,340 --> 00:09:25,960 und die 102 00:09:25,960 --> 00:09:32,220 Unverknüpfung von einer Variable mit seiner Negation ist immer 0, kann also entfallen. 103 00:09:35,866 --> 00:09:38,966 Hier haben wir das zweite Beispiel. 104 00:09:42,186 --> 00:09:51,746 Es werden immer maximal große Einsmengen gebildet und es sind nur Zweierpotenzen erlaubt 105 00:09:51,746 --> 00:09:58,326 als Elemente, sprich zwei Elemente, vier Elemente, acht, 16, 32, 64 und so weiter. 106 00:09:58,326 --> 00:10:03,926 Das heißt, sie können jetzt nicht hier so einen sechser Block bilden. 107 00:10:04,464 --> 00:10:07,164 Weil es keine Zweierpotenz ist. 108 00:10:07,744 --> 00:10:12,764 Gut, schauen wir uns die Minimierungsoption hier mal an. 109 00:10:12,984 --> 00:10:15,404 Fangen wir mit dem großen Block an. 110 00:10:15,524 --> 00:10:18,184 Immer möglichst große Blocke bilden. 111 00:10:18,504 --> 00:10:19,304 Das wurde hier gemacht. 112 00:10:19,664 --> 00:10:24,184 4 Einsen, 2 hoch 2 ist 4, also eine Zweierpotenz wurden erfasst. 113 00:10:24,804 --> 00:10:26,964 Und jetzt schaut man sich an, welche 114 00:10:27,232 --> 00:10:32,992 Variablen wie vorkommen. Und taucht eine Variable sowohl negiert als auch nicht 115 00:10:32,992 --> 00:10:39,812 negiert vor, dann fliegt sie raus. x1 ist hier aufgetragen. Wir haben in dem 1er 116 00:10:39,812 --> 00:10:50,552 Block sowohl x1 als auch x1 nicht. Deswegen entfällt x1. x2 steht in dem 117 00:10:50,552 --> 00:10:52,892 Bereich, also die beiden Zeilen. 118 00:10:53,248 --> 00:10:59,868 Alle Einsen des Blockes sind mit x2 versehen, muss also da bleiben. Okay, da haben wir notiert. 119 00:11:00,688 --> 00:11:03,728 x3 ist in den beiden Spalten vorrätig. 120 00:11:04,388 --> 00:11:07,928 In beiden Spalten, wo unsere Einsen stehen, haben wir nur x3. 121 00:11:09,528 --> 00:11:15,368 Nicht auch x3 nicht, also bleibt x3 stehen. x4 steht in den beiden Zeilen hier. 122 00:11:18,808 --> 00:11:19,228 Eine 123 00:11:19,228 --> 00:11:21,668 Reihe von Einsen wird mit x4 belegt. 124 00:11:26,048 --> 00:11:32,768 Die Variable kommt also sowohl in negierter als auch in nicht negierter Form vor und entfällt deswegen. 125 00:11:33,248 --> 00:11:39,408 Das heißt, die Minimierung des Blocks hier ergibt sich zu x2 und x3. 126 00:11:39,848 --> 00:11:43,428 Okay, schauen wir uns diesen hier an. 127 00:11:43,868 --> 00:11:49,308 Zweier Block x1, x1 nicht, entfällt, taucht nicht auf. 128 00:11:50,108 --> 00:11:52,928 Dann haben wir x2. 129 00:11:52,928 --> 00:11:52,948 Dann haben wir x2. 130 00:11:52,948 --> 00:11:52,988 Dann haben wir x5. 131 00:11:53,088 --> 00:11:53,208 Dann haben wir x10. 132 00:11:53,232 --> 00:12:07,612 Taucht nur in der Form x2 nicht auf. Steht da. Okay. x3 haben wir in der Spalte und in der Spalte. 133 00:12:07,912 --> 00:12:17,812 Beide Einsen tauchen nur in der x3 nicht Form auf. Haben wir notiert. x4 ist in der Zeile und in der. 134 00:12:17,812 --> 00:12:20,672 Das heißt die beiden zahlen. 135 00:12:21,424 --> 00:12:26,604 Für uns ist ja die oberste relevant, taucht nur mit x4 nicht auf, alles klar. 136 00:12:27,184 --> 00:12:35,424 Also x2 nicht und x3 nicht und x4 nicht. Dieser Block, der linke mit zwei 1s versehene. 137 00:12:36,924 --> 00:12:43,604 x1 taucht nur in der Spalte x1 nicht auf, ist erhalten. 138 00:12:44,644 --> 00:12:50,704 x2 taucht hier als x2 auf und hier als x2 nicht entfällt, also alles klar. 139 00:12:52,064 --> 00:13:06,024 x3 taucht nur hier auf, in der Spalte, als x3 nicht. Gut. x4 nicht und x4 nicht, also nur als x4 nicht. Auch gut. 140 00:13:07,444 --> 00:13:17,464 Trickreich ist dann hier wieder die Randnachbarschaft. Erstmal muss man sie als solche erkennen und dann aufpassen, dass man die richtigen Variablen erwischt. 141 00:13:17,464 --> 00:13:20,104 Schauen wir uns das an. x1 nicht. 142 00:13:20,672 --> 00:13:30,592 Und rechter Rand auch x1 nicht, deswegen x1 nicht notieren. x2 taucht hier auf. 143 00:13:31,432 --> 00:13:38,772 Der hier hat x2 nicht, der hier hat auch x2 nicht, also notieren. x3, der rechte Rand 144 00:13:38,772 --> 00:13:47,552 hat x3, der linke Rand hat x3 nicht, entfällt also. x4, der 145 00:13:48,880 --> 00:13:58,860 rechte rand hat x4 und die gleiche zeile auch x4, wir notieren x4. alles klar. was 146 00:13:58,860 --> 00:14:04,140 hier nicht eingetragen ist, ist der zweier block, der hier noch übrig bleibt. 147 00:14:06,460 --> 00:14:12,200 wir müssen ja die ganze eins menge erfassen. was passiert da? x1 bleibt 148 00:14:12,200 --> 00:14:18,260 halten, also x1 und x2 und 149 00:14:18,480 --> 00:14:21,280 x3 nicht, x4 entfällt.