Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in AU-4-1

Beantwortet: NP-Vollständigkeit

Sat, 22 Jan 2022 15:24:33 +0000

Hallo,

Warum es NP ist, ist vermutlich klar, oder? Der zweite Teil ist hier vermutlich das Problem.

Ein Beispiel:

Beantwortet: Tut 4 - A3

Thu, 11 Mar 2021 10:27:21 +0000

Hallo,

in dieser Aufgabe geht es darum, einen binären Vollsubtrahierer aufzustellen. Dabei bezeichnet E das Ergebnis-Bit, welches von den Eingaben a und b (die Subtrahenden) und ü, dem Übertrags-Bit, abhängt.

Wir füllen zunächst die Tabelle aus, bei der wir jeweils a-b-ü rechnen und das Ergebnis in E speichern - falls wir im negativen landen, speichern wir außerdem eine 1 im Übertragsbit. Das kommt so zustande, da wir quasi schriftlich subtrahieren. So erhält man dann folgende Tabelle:

Diese Tabelle deckt einfach nur alle möglichen Szenarien an Eingaben für a, b und ü ab. Jetzt betrachten wir die Zeile des Ergebnisbits E: Wir versuchen zu erkennen, über welche logische Verknüpfung wir dieses jeweils pro Zeile erzeugen können - und nehmen uns dabei das XOR Gatter zur Hilfe. Die Formel für E lautet also nicht wie von dir beschrieben a + b + ü, sondern a XOR b XOR ü

Zur Erinnerung: XOR ist das Gatter, was eine 1 zurückgibt, wenn eine der beiden Eingaben 1 ist, aber nicht beide. Schauen wir also beispielsweise mal Zeile 3 unserer Tabelle an: Wir vergleichen zunächst a und b in einem XOR miteinander, also 0 und 1 -> dieser XOR ist "wahr", liefert also eine 1 zurück. Die zurückerhaltene 1 vergleichen wir nun in einem zweiten XOR mit dem Übertragsbit ü, also der 0. Wir vergleichen also wieder 1 und 0 im XOR und erhalten eine 1 zurück, da die XOR-Bedingung erfüllt ist. So funktioniert das für alle Zeilen der Tabelle, probier es gerne als Übung mal für ein paar Zeilen aus :)

LG,

Martin (Tutor)

Beantwortet: BDD - Tut 4 (Aufgabe 2a)

Thu, 11 Mar 2021 10:12:59 +0000

Hallo,

um deine Frage zu beantworten, müssen wir uns nochmal anschauen, wie das BDD aus dem Baum entstanden ist:

Im dritten Schritt sieht man, dass wir bei Eingabe einer 1 in x zum rechten y gehen - dieses ist aufgrund seiner verschiedenen Nachfolgekonfigurationen nicht identisch mit dem linken y! Jedoch sehen wir, dass wir vom rechten y aus immer im rechten z landen werden, egal ob wir eine 0 oder eine 1 eingeben. Aufgrund dessen ist das rechte y überflüssig, wir können immer direkt von x ins rechte z gehen, wenn wir eine 1 einlesen.

Eine Kante (0 / 1) von x zum linken y zu zeichnen wäre nicht richtig, da das linke y andere Folgekonfigurationen hat. Deutlich wird das vielleicht an einem Beispiel:

Wir betrachten die Eingabefolge (1,0,1), mit der wir immer am Ende eine 1 erhalten sollten (siehe Ausgangsgraph). Wenn wir jetzt aber die Kante (0 / 1) von x zum linken y hinzufügen, wie von dir vorgeschlagen, erhalten wir für eben diese Eingabe eine 0.

Ich hoffe das hat es deutlich gemacht, bei Nachfragen melde dich gerne.

Beste Grüße,

Martin (Tutor)

Beantwortet: Inverter

Fri, 26 Jan 2018 12:42:07 +0000

Hallo,

also sind alle deine Variablen (in unserem Fall A, B und C) bereits in deiner Funktion negiert vorhanden, kannst du aufgrund der Eigenschaften von p-Mos und n-Mos (wie in der Antwort zuvor schon beschrieben) die Leitungen von A, B und C direkt verwenden und benötigst keinen Invertierer.

Das bedeutet du musst nur für Variablen die ohne Negation in der Funktion vorkommen einen Inverter einbauen. Also wenn die Funktion z.b. lauten würde:

f(A,B,C) = (nichtA oder nichtB) und C

Dann müsstest du C zunächst Invertieren und könntest dann erst die Leitung nutzen.

Schau dir hierzu vielleicht mal die Aufgabe CMO-AC c) an. Hier siehst du das wir in der Lösung für C zunächst einen Invertierer einbauen und erst danach die Leitung weiterverweden.

Hoffe es wurde jetzt ein wenig verständlicher :)

Beste Grüße,

Marius (Tutor)

Beantwortet: Tut 4/ A8

Fri, 26 Jan 2018 10:23:56 +0000

Hallo,

ich vermute, dass sich deine Frage auf den Aufgabenteil b) bezieht.

In der Aufgabe ist gefordert, den jeweiligen Zustand in welchem sich der Automat bei den Eingaben befindet mit den Flip Flops zu kodieren.

Hierbei wird die 1. Stelle der dreistelligen binären Zahl durch FF 2 kodiert. Die 2. Stelle durch FF 1 und die dritte Stelle durch FF 0.
Das RS-Flip Flop lässt sich durch eine 1 am Eingang s auf 1 stellen und durch eine 1 am Eingang r auf eine 0 stellen. Da im Eingang r in dieser Aufgabe immer die Negation des bei s eintreffenden Signals ankommt, wird ein Flip Flop auf null gesetzt wenn eine 0 den den Flip Flop erreicht und auf 1 gesetzt, wenn eine 1 den Flip Flop erreicht.
Der Automat stellt eine Sprache dar, in welcher ein Wort am Ende mindestens 4 Einsen enthalten muss um zur Sprache zu gehören. Mit einer der Eingabe 1, geht der Automat in den jeweils nächsten Zustand über. Die Eingabe gehört zur Sprache wenn die Flip Flops die Werte FF2=1 FF1= 0 FF0=0. Dementsprechend hat e3 den Wert 1 wenn FF2 den Wert 1 hat.

Mit diesem Wissen kann man nun das Schaltwerk ergänzen. Wie man sieht befindet sich vor jedem "Und" 4 Eingänge: E, die Eingabe; q0, Wert des FF 0; q1, Wert des FF1 und q2 Wert des FF2. Auch kann man sehen, dass für jedes "Und" verschiedene q negiert sind. Nun schaust du durch mit welcher Belegung die "Und"s den Wert 1 weitergeben:

Von oben nach unten:

1. Und: E = 1 q2 = 0 q1 = 0 q0 = 0
(Dieses "Und" gibt also den Wert 1 weiter, wenn die Eingabe 1 ist und der Automat sich im Zustand s000 befindet.
2. Und: E = 1 q2 = 0 q1 = 0 q0 = 1
3. Und: E = 1 q2 = 0 q1 = 1 q0 = 0
4. Und: E = 1 q2 = 0 q1 = 1 q0 =1
5. Und: E = 1 q2 = 1 q1= 0 q0 = 0

Jedes "Und" leitet also den Wert 1 weiter, wenn die Eingabe 1 ist und sich der Automat im jeweiligen Zustand befindet. Jetzt musst du nur noch diese "Und"s so mit den "Oder"s verbinden, dass der im Automat nächste Zustand mit den Flip Flops kodiert wird.

Beispiel:

1. Und: Wir bekommen die Eingabe E = 1 und befinden uns im Zustand s000. Damit wäre der Folgezustand s001. Deswegen verbinden wir dieses "Und" mit dem untersten "Oder". Damit die nachfolgende Flip Flop Belegung q2 = 0 q1 = 0 q0 = 1 ist und damit den Zustand s001 zeigt.

Usw.

Ich hoffe dies hat dir weitergeholfen.

Grüße

Michelle (Tutorin)

Beantwortet: Tut 4/ A5

Fri, 26 Jan 2018 08:43:00 +0000

Hallo,

dass ein Konverter nicht benötigt wird, liegt daran, dass auch die darzustellende Funktion eine negation vor jeder Variable hat und somit deren Komplement benutzt.

Auf die Lösung kommt man in dieser Aufgabe gut, wenn man sich zunächst fragt für welche Belegungen von A,B,C die Funktion die Werte 0 oder 1 annimmt.

Zur Erinnerung:

Liegt an einem p-Mos Bauteil eine 0 am Gatter an, so wird eine 1 weitergeleitet
Liegt an einem n-Mos Bauteil eine 1 an einem Gatter an, so wird eine 0 weitergeleitet

Für den oberen Teil (den p-Mos Teil) betrachtest du nun alle Belegungen für die die Funktion eine 1 ergibt. Das wäre: A oder B ist 0 und zusätzlich muss C 0 sein. Da zwischen A oder B eine "Oder"-Beziehung besteht, müssen sie paralell geschaltet werden, da für entweder eine an A anliegende 0 oder an B anliegende 0 eine 1 weitergeleitet werden soll. Zusätzlich muss C mit diesem Gebilde in Reihe geschaltet werden, da zwischen C und (A oder B) eine "Und"-Beziehung besteht.

Für den unteren Teil (den n-Mos Teil) betrachtest du nun alle Belegungen die für die Funktion zu einer 0 führen. Das wäre: A und B sind 1 oder C ist 1. Wir haben nun also zwei Möglichkeiten eine 0 zu erzeugen. Erstens C = 1 und Zweitens A =1 und B=1. Wegen dieser "Oder"-Beziehung muss C also parallel zu A und B geschaltet werden. Nun müssen wir uns noch fragen wie der n-Mos Teil der Schaltung mit A und B aussieht. Da zwischen ihnen hier eine "Und"- Beziehung herrscht (beide müssen 1 sein, damit f =0 ist), müssen sie in Reihe geschaltet werden.

Ich hoffe jetzt ist es verständlicher geworden.

Grüße

Michelle (Tutorin)

Beantwortet: Wie hoch ist der Aufwand um ein Erfüllbarkeitsproblem in KNF zu lösen?

Tue, 22 Sep 2015 09:34:25 +0000

Hallo,

die so genannten SAT-Probleme, bei denen eine allgemeine aussagenlogische Formel auf Erfüllbarkeit geprüft wird, sind NP-vollständig, also die schwierigsten Probleme aus NP. (Siehe Vorlesung)

Das Prüfen eines Problems in DNF auf Erfüllbarkeit stellt einen Spezialfall des SAT-Problems dar. Da es dabei ausreicht einen einzigen Konjunktionsterm zu finden, der wahr ist, ist der Aufwand linear.

Bei der KNF müssen alle Disjunktionsterme geprüft werden. Das Problem gehört zu der Problemklasse NP-vollständig und ist im Allgemeinen nur mit viel Rechenaufwand lösbar.

Für die Umwandlung von KNF in DNF gibt es mehrere Methoden. Eine aus Grundlagen der Informatik I bekannte Methode erfordert die Aufstellung einer Wahrheitstabelle. Die Wahrheitstabelle hat \(2^n\) Zeilen. Auch andere Methoden führen zum exponentionellen Aufwand.

Viele Grüße

Irina (Tutorin)