 n-stellige Schaltfunktion Kosten |
Dr.Java 
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
 |
|
| n-stellige Schaltfunktion Kosten |
     |
Hi. Ich arbeite mich inzwischen schon länger in die Technische Informatik ein, leider ist das Buch das ich benutze etwas dürr was seine Beweise betrifft. Deswegen würde ich hier auch grad ein paar Fragen stellen.
Meine Frage wäre zunächst der Beweis dafür ,das für p als vollständig disjunkte Normalform einer n-stelligen Schaltfunktion f,gilt,
L(p)<=n*2^(n+1) , wobei L die Kosten sind(boolesche).
Das Buch sagt dazu im wesentlichen folgendes , jeder Minterm m der vollständigen,disjunkten Normalform von f besteht aus genau n Literalen und n-1 logischen Und Zeichen .
Ebenso das L(m)<=2n-1 ist und p aus #Tr(f) Mintermen besteht. Tr meint hierbei den Träger von f.
Für die Anzahl der Logischen Oder in p gilt dann, #Tr(f)-1 ,falls #Tr(f)>= 2 ist und 0,falls #Tr(f) <= 1.
Wegen #Tr(f)<=# {0,1}^n=2^n soll dann das besagte folgen, L(p)<=n*2^(n+1).
Meine Frage ist nun wie man das daraus konkret schlussfolgern kann/sollte,denn ich werde da nicht schlau draus.
Vielen lieben Dank im voraus und lg
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
27.08.2016 19:25 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Ah, danke dir,für die ausführliche Lösung.
Ich habe nur noch ein paar Fragen dazu.
| Zitat: |
Original von eulerscheZahl
für 2^n Minterme macht das also: ![[latex]L(p) \leq (2n-1) \cdot 2^n = 2n\cdot2^n - 2^n = n\cdot 2^{n+1} - 2^n < n\cdot 2^{n+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(p) \leq (2n-1) \cdot 2^n = 2n\cdot2^n - 2^n = n\cdot 2^{n+1} - 2^n < n\cdot 2^{n+1}) .
|
Kann man das dann einfach so zusammenrechnen, und wie kommt man darauf das man das am Ende so umformen kann, ich meine ich keine die Regeln wegen dem <=,aber wieso grade so?
Und zum anderen, gibt es diese Regel eigentlich in verschiedenen Formen? Ich habe nämlich in einem anderen Buch das ganze in ähnlichen Zusammenhang gefunden und sie meinten es gelte für jede Boolesche Funktion ![[latex]L(f)\leq n\cdot 2^{n+1}-1[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(f)\leq n\cdot 2^{n+1}-1) ,wobei L(f) die minimalen Kosten sind.
Während das ursprüngliche Buch meint
Für jede n-stellige Schaltfunktion f gilt ![[latex]L(f)\leq n\cdot 2^{n+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(f)\leq n\cdot 2^{n+1}) ,wobei L(f) die minimalen Kosten sein sollen.
Wäre dann beides richtig,in verschiedenen Zusammenhängen?
Danke und lg
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Dr.Java: 28.08.2016 12:02.
|
|
|
28.08.2016 12:01 |
|
|
|
|
Ich hatte leider das ODER zwischen den einzelnen Mintermen vergessen. Habe es oben editiert.
Ich kriege auch die -1 von deinem zweiten Buch. Das macht eine großzügigere Abschätzung aber nicht falsch.
Und wie schon angedeutet, kann man die Grenze noch weiter nach unten setzen: Im Erwartungswert ist nur jede zweite Variable negiert. Und da jede mögliche Kombination verwendet wird, kann man hier auch mit dem Erwartungswert statt dem worst case rechnen.
![[latex]L(p) \leq (\underbrace{n-1}_{\text{UND in m}} + \underbrace{\frac{1}{2}n}_{\text{Negation}}) \cdot \underbrace{2^n}_{\text{Anzahl Minterme}} + \underbrace{2^n-1}_{\text{ODER}}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L(p) \leq (\underbrace{n-1}_{\text{UND in m}} + \underbrace{\frac{1}{2}n}_{\text{Negation}}) \cdot \underbrace{2^n}_{\text{Anzahl Minterme}} + \underbrace{2^n-1}_{\text{ODER}})
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
28.08.2016 14:28 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Ah danke dir ,so in etwa beweist es auch das Buch. Nur mit n in der Klammer, nicht mit 1/2 *n. Bedeutet das also im Endeffekt das es irrelevant ist ob du die Zahl der Oder .o.ä. weg lässt? Und was hat es in diesem Sinne mit dem Erwartungswert auf sich ,beziehst sich das nur auf den Vorfaktor von der Negation,beziehungsweise also auf die Warscheinlichkeit das es negiert ist?
lg
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
|
28.08.2016 20:37 |
|
|
|
|
Das ODER hatte ich nur vergessen, das gehört da schon hin.
Der Faktor 1/2 ist die Wahrscheinlichkeit, dass eine Variable negiert ist. Für alle Variablen sind es im Erwartungswert n/2 Negationen je Minterm (kannst du für das Beispiel mit 3 Variablen gerne nachzählen).
Insgesamt sind es n/2 * 2^n. Das ist ein exakter Wert für ein p mit maximaler Anzahl an Mintermen, keine Abschätzung.
Aber wenn du es ohne die 1/2 verstanden hast, will ich dich nicht unnötig verwirren. Das sollte nur eine Fußnote sein, dass man dads besser abschätzen kann.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
28.08.2016 20:54 |
|
|
Dr.Java
Foren As
Dabei seit: 21.03.2016
Beiträge: 99
|
|
Kann man denn trotz dem Oder auf ![[latex] n\cdot 2^{n+1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? n\cdot 2^{n+1}) kommen,durch umformen nehme ich an? Wegen dem Erwartungswert,okay, ich habe das jetzt noch nicht ganz raus,werd mir das vielleicht später nochmal in Ruhe anschauen.
Danke dir und lg
__________________
| Zitat: |
"Ich glaube, es gibt einen weltweiten Bedarf an vielleicht fünf Computern."
-Thomas Watson |
|
|
|
29.08.2016 12:55 |
|
|
|
