Grundlagen der Informatik II - info2.aifb.kit.eduinfo2.aifb.kit.edu/secure/Tutoriumsfolien/Tutorium4-Druck.pdf · 2 Grundlagen der Informatik II – Tutorium 4 Institut für Angewandte

KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft

Institut für Angewandte Informatik und Formale Beschreibungsverfahren – Professor Dr. Hartmut Schmeck

www.kit.edu

Grundlagen der Informatik II Tutorium 4

Miniaufgabe

* bevor es losgeht * Welche dieser Aussagen sind korrekt?

a) 𝑃 = 𝑁𝑃 b) 𝑃 ≠ 𝑁𝑃

c) 𝑃 ⊆ 𝑁𝑃 d) 𝐴 ≤𝑝𝑜𝑙 𝐵 ⇔ 𝐵 ≤𝑝𝑜𝑙 𝐴

?

Ob 𝑃 = 𝑁𝑃, ist ein offenes

Problem. d) ist Quatsch, weil ≤𝑝𝑜𝑙

eine ordnende Relation ist.

In der Arithmetik gilt ja auch nicht

𝑥 ≤ 𝑦 ⇔ 𝑦 ≤ 𝑥

Institut für Angewandte Informatik und Formale Beschreibungsverfahren 2 Grundlagen der Informatik II – Tutorium 4

L. König, F. Pfeiffer-Bohnen, M. Wünsche und M. Braun

Grundlagen der Informatik II – Tutorium 4


Bonusklausur

Montag, 15.01.2018, 19:30 Uhr

Inhalte der Übungsblätter 1-4 (bis Kapitel 6)

Anmeldung: bis 07.01.2018 über https://portal.wiwi.kit.edu/ys/1741/signup

3 Aufgaben. Für jede komplett richtig gelöste Aufgabe wird ein Verrechnungspunkt

in der Klausur gutgeschrieben.

Saalübung

1. Übung fand am 11.12.2017 statt

2. Übung findet am 22.01.2018 statt

Selbsttest über nuKIT

Fragen zu Kapitel 1-6 sind bereits freigeschaltet

Zugang über nuKIT-App oder Web: http://nukit.scc.kit.edu/nukit

Aufgabenpool

Die Diskussionsforen werden auch während der Weihnachtsferien betreut

Vorab…

https://portal.wiwi.kit.edu/ys/1741/signup


http://nukit.scc.kit.edu/nukit






Bonusklausur

Montag, 15.01.2018, 19:30 Uhr

Inhalte der Übungsblätter 1-4 (bis Kapitel 6)

Anmeldung: bis 07.01.2018 über https://portal.wiwi.kit.edu/ys/1741/signup

3 Aufgaben. Für jede komplett richtig gelöste Aufgabe wird ein Verrechnungspunkt

in der Klausur gutgeschrieben.

Saalübung

1. Übung fand am 11.12.2017 statt

2. Übung findet am 22.01.2018 statt

Selbsttest über nuKIT

Fragen zu Kapitel 1-6 sind bereits freigeschaltet

Zugang über nuKIT-App oder Web: http://nukit.scc.kit.edu/nukit

Aufgabenpool

Die Diskussionsforen werden auch während der Weihnachtsferien betreut

Vorab…

Nutzen Sie das Lehrbuch

zur Klausurvorbereitung!

(Denn wir nutzen es ja auch beim

Stellen der Klausuraufgaben )

www.dasinfobuch.de





http://dasinfobuch.de/





Weitere Aufgaben zu den Themen dieses Tutoriums

Aus dem Aufgabenpool bzw. Übungsbuch: Kapitel 10-Band I: Berechenbarkeits- und Komplexitätstheorie (12 Aufgaben).

Kapitel 2-Band II: CMOS (10 Aufgaben)

Kapitel 3-Band II: Binary Decision Diagram (7 Aufgaben).

Kapitel 1-Band II: Schaltnetze und Schaltwerke (7 Aufgaben).

Im Lehrbuch: Kapitel 6: Berechenbarkeitstheorie

Kapitel 7: Komplexitätstheorie

Auf Übungsblatt 4 (4 erkenntnisreiche Aufgaben)

Aufgaben, die mit „für zuhause“ markiert sind: HU-4-1 bis HU-4-4

Bei Fragen oder Kommentaren zu allen Aufgaben

nutzen Sie das Q/A-Forum oder

fragen Sie Ihren Tutor.

Für die Fleißigen…

Klick





Einführungsaufgabe: Komplexität

Wie verhalten sich die Mengen 𝑃, 𝑁𝑃, 𝑁𝑃-vollständig und 𝑁𝑃-schwer

zueinander? Geben Sie ein Beispiel für ein 𝑁𝑃-vollständiges Problem an.

Lösung:

℘(E*)

𝐿0 (semi-entsch.)

𝑷

𝑵𝑷

𝑵𝑷-v.

𝑵𝑷-

schwer

entsch.

Beispiele für 𝑁𝑃-vollständige

Probleme (nichtdeterministisch

polynomiell lösbar):

• 𝑆𝐴𝑇 (Gibt es eine erfüllende

Belegung für eine Formel?)

• 𝐶𝐿𝐼𝑄𝑈𝐸 (Gibt es einen

vollständig verbundenen

Teilgraph der Größe 𝑘?)

In 𝑃 liegen

die „gerade

so noch

praktisch

lösbaren“

Probleme





Aufgabe 1: Komplexität

Bekanntermaßen ist das 𝑆𝐴𝑇-Problem 𝑁𝑃-vollständig. In dieser allgemeinen

Variante liegen die aussagenlogischen Formeln in beliebiger Form vor.

a) Wie hoch ist der Aufwand, wenn man die Formelstruktur in der Art einschränkt,

dass die Formeln in disjunktiver Normalform (DNF) vorliegen („DNF-SAT“)?

Hinweis: Betrachten Sie hierzu ein Beispiel in DNF.

Lösung:

Beispiel in DNF:

Der Aufwand ist linear, da nur ein einziger wahrer Konjunktionsterm impliziert,

dass die ganze Formel wahr ist. Man sucht also nur die erste Klausel in der

keine Variable sowohl negiert als auch nicht negiert auftaucht. Diese Klausel

kann man erfüllen und damit auch die ganze Formel (hier gleich die erste).

𝑥1 ∧ 𝑥2 ∨ 𝑥3 ∧ 𝑥′5 ∧ 𝑥1 ∧ 𝑥5 ∨ 𝑥′3 ∨ 𝑥′3 ∧ 𝑥5 ∧ 𝑥1

Klausel Literal





Aufgabe 1: Komplexität

b) Wenn die DNF-Variante leichter ist, warum wird dann die KNF-Variante nicht

genauso leicht, indem man einfach KNF-Formeln in DNF umwandelt, um das

SAT-Problem zu lösen?

Lösung:

Die Umwandlung in DNF kann exponentiellen Aufwand haben.

Beispiel:

KNF: 𝑥1 ∨ 𝑦1 ∧ 𝑥2 ∨ 𝑦2 ∧ 𝑥3 ∨ 𝑦3

DNF: 𝑥1 ∧ 𝑥2 ∧ 𝑥3 ∨ 𝑥1 ∧ 𝑥2 ∧ 𝑦3 ∨ 𝑥1 ∧ 𝑦2 ∧ 𝑥3 ∨ 𝑥1 ∧ 𝑦2 ∧ 𝑦3 ∨ ⋯

𝑦1 ∧ 𝑥2 ∧ 𝑥3 ∨ 𝑦1 ∧ 𝑥2 ∧ 𝑦3 ∨ 𝑦1 ∧ 𝑦2 ∧ 𝑥3 ∨ 𝑦1 ∧ 𝑦2 ∧ 𝑦3


L. König, F. Pfeiffer-Bohnen, M. Wünsche und M. Braun Institut für Angewandte Informatik und Formale Beschreibungsverfahren 8 Grundlagen der Informatik II – Tutorium 4


Wenn ein Problem 𝐴 𝑁𝑃-vollständig ist, dann gilt für ein

beliebiges 𝑁𝑃-schweres Problem 𝐵:

𝐴 ≤ 𝑝𝑜𝑙 𝐵

□ WAHR

□ FALSCH

Entspannender, aber wichtiger Relax-Hintergrund:

Auf ein 𝑁𝑃-schweres Problem lässt sich (nach Definition) jedes Problem aus 𝑁𝑃 in

Polynomialzeit reduzieren. Da 𝑁𝑃-vollständige Probleme eine Teilmenge von 𝑁𝑃 bilden,

gilt das insbesondere für das Problem 𝐴.

Multiple-Choice-Relax-Aufgabe




Wenn ein Problem 𝐴 𝑁𝑃-vollständig ist, dann gilt für ein

beliebiges 𝑁𝑃-schweres Problem 𝐵:

𝐴 ≤ 𝑝𝑜𝑙 𝐵

□ WAHR

□ FALSCH


Auf ein 𝑁𝑃-schweres Problem lässt sich (nach Definition) jedes Problem aus 𝑁𝑃 in

Polynomialzeit reduzieren. Da 𝑁𝑃-vollständige Probleme eine Teilmenge von 𝑁𝑃 bilden,

gilt das insbesondere für das Problem 𝐴.


X




Relax-Tipp zum Begriff „Reduktion“

X

Eine Reduktion „A≤B“ beschreibt keine schnellere Lösung

für A. Sie ist nur ein weiterer Lösungsweg für A über B.

Demnach meint der Begriff „Reduktion“ von A auf B, dass es

nicht „wesentlich“ schwieriger sein kann, A zu lösen als B.

Daher auch der „≤“-Operator, der meint: „A ist leichter oder

gleich schwer zu lösen wie B (im Wesentlichen)“.

Dann gilt auch umgekehrt: Wenn ich weiß, dass

es keinen Weg von Stuttgart nach Karlsruhe gibt,

dann können nicht alle Städte in Deutschland

durch Straßen miteinander verbunden sein.

So könnte man die Frage A, ob es

einen Weg von Stuttgart nach

Karlsruhe gibt, auf die Frage B

reduzieren, ob alle Städte in

Deutschland durch Straßen

miteinander verbunden sind.

!





Einführungsaufgabe: BDD

Welchen Vorteil haben reduzierte Funktionsgraphen (z.B. Binary Decision

Diagram) gegenüber anderen Darstellungsformen für Boolesche Funktionen wie

beispielweise Wahrheitstabelle, KNF/DNF?

Lösung:

Der Platzbedarf ist häufig wesentlich geringer (im schlimmsten Fall

jedoch bei allen Varianten exponentiell).

Das Berechnen eines Funktionswertes dauert höchstens 𝑛 Schritte bei

𝑛 Eingangsvariablen.





a) Erzeugen Sie das BDD (Binary Decision Diagram) zu der durch folgenden

Baum gegebenen Funktion 𝑓 ∶ 𝔹3 → 𝔹:

Aufgabe 3: Binary Decision Diagram





a) Erzeugen Sie das BDD (Binary Decision Diagram) zu der durch folgenden

Baum gegebenen Funktion 𝑓 ∶ 𝔹3 → 𝔹:


Das BDD ist der

vollständig

reduzierte

Funktionsgraph.

Lösung:

Skript ID-8850

http://xwizard.de:8080/Wizz?lang=ger&hide=.i2&template=ID-8850#Output





b) Lesen Sie aus dem berechneten BDD einen Booleschen Ausdruck in

disjunktiver Normalform (DNF) ab.

1. 𝑥′𝑦′𝑧′

2. 𝑥′𝑦 𝑧

3. 𝑥 𝑧


𝑓 𝑥, 𝑦, 𝑧 = 𝑥′𝑦′𝑧′ + 𝑥′𝑦𝑧 + 𝑥𝑧




Ein Binary-Decision-Diagram hat immer minimale

Knotenanzahl bezogen auf die Boolesche Funktion, die es

darstellt.

□ WAHR

□ FALSCH


Je nach Variablenreihenfolge kann die Knotenanzahl auch für die gleiche Boolesche

Funktion unterschiedlich groß sein. Jedoch ist ein BDD bei vorgegebener

Variablenreihenfolge eindeutig.





Ein Binary-Decision-Diagram hat immer minimale

Knotenanzahl bezogen auf die Boolesche Funktion, die es

darstellt.

□ WAHR

□ FALSCH


Je nach Variablenreihenfolge kann die Knotenanzahl auch für die gleiche Boolesche

Funktion unterschiedlich groß sein. Jedoch ist ein BDD bei vorgegebener

Variablenreihenfolge eindeutig.


X





Einführungsaufgabe: CMOS

Welche elektronischen Bauelemente sind hier dargestellt?

Lösung: n-MOSFET p-MOSFET

Welche Bedeutung haben die Anschlüsse G, D und S?

Lösung:

G (Gate): Schaltungseingang, bestimmt ob Weg von S nach D durchlässig

S (Source): Verbindung in Richtung 𝐺𝑁𝐷

D (Drain): Verbindung in Richtung 𝑉𝐷𝐷





Aufgabe 5: CMOS

Zeichnen Sie eine CMOS-Schaltung für die Boolesche Funktion 𝑓: 𝔹3 → 𝔹

mit: 𝑓 𝐴, 𝐵, 𝐶 = (¬𝐴 ∨ ¬𝐵) ∧ ¬𝐶

GND

VDD

A

B

C

𝑓 𝐴, 𝐵, 𝐶

1. PMOS: ¬𝐴 ∨ ¬𝐵

2. PMOS: ∧ ¬𝐶

3. NMOS: ¬𝐴 ∨ ¬𝐵

4. NMOS: ∧ ¬𝐶

Was würde passieren,

wenn gleichzeitig

𝑉𝐷𝐷 eine 1 und 𝐺𝑁𝐷

eine 0 an den

Ausgang leitet?





Einführungsaufgabe: Schaltnetze

Beschreiben Sie, welche Funktionen die folgenden Schaltungen realisieren.

Lösung:

& a

b 2k+1

a

b 1 a

b & a

b 1

a

b

Welches

wichtige Gatter

fehlt hier noch?

XOR NAND AND NOR OR





Aufgabe 6: Schaltnetz

Entwickeln Sie einen Vollsubtrahierer, der aus drei Booleschen Eingangsvariablen

𝑎, 𝑏, ü ein Differenz-Bit 𝐸 und ein Übertrags-Bit Ü berechnet. Verwenden Sie für

Ihren Vollsubtrahierer nur die Elemente OR, AND, NOT, NAND, NOR und XOR.

Hinweis: Stellen Sie 𝐸 und Ü zuerst in der Wahrheitstabelle dar, lesen Sie dann

die Boolesche Funktion ab und leiten Sie daraus das Schaltnetz ab.

Lösung:

𝑎 𝑏 ü 𝐸 Ü

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

𝐸(𝑎, 𝑏, ü) = 𝑎 ⊕ 𝑏 ⊕ ü

Ü 𝑎, 𝑏, ü = 𝑎′𝑏′ü + 𝑎′𝑏ü′ + 𝑎′𝑏ü + 𝑎𝑏ü

= 𝑎′ 𝑏′ü + 𝑏ü′ + 𝑏ü

= 𝑎′(𝑏 ⊕ ü) + 𝑏ü





Aufgabe 6: Schaltnetz

𝐸 𝑎, 𝑏, ü = 𝑎 ⊕ 𝑏 ⊕ ü Ü 𝑎, 𝑏, ü = 𝑎′(𝑏 ⊕ ü) + 𝑏ü

Skript ID-8861





Schaltnetze unterscheiden sich von Schaltwerken dadurch,

dass Schaltwerke rückführende Leitungen besitzen

(können), Schaltnetze aber nicht.

□ WAHR

□ FALSCH



Was soll man dazu

noch mehr sagen...




Schaltnetze unterscheiden sich von Schaltwerken dadurch,

dass Schaltwerke rückführende Leitungen besitzen

(können), Schaltnetze aber nicht.

□ WAHR

□ FALSCH



X

Was soll man dazu

noch mehr sagen...





a) Welche Sprache 𝐿(𝐴) wird durch den endlichen

Automaten 𝐴 erkannt mit:

𝐴 = 0, 1 , 𝑠000, 𝑠001, 𝑠010, 𝑠011, 𝑠100 , 𝛿, 𝑠000, 𝑠100 ,

𝛿:

Lösung:

𝐿(𝐴) = {𝑤1111 | 𝑤 ∈ {0,1}∗}

d.h. die Sprache, die der Automat 𝐴 erkennt, besteht aus

Wörtern, die auf 1111 enden.

Aufgabe 8: Schaltwerke

Skript ID-9064






b) Ergänzen Sie das unten abgebildete Schaltwerk so, dass eine 1 am

Ausgang 𝑒3 genau dann anliegt, wenn die bisher über 𝐸 erfolgte Eingabe 𝑤

Element der Sprache 𝐿(𝐴) ist.


Hinweise:

• das Schaltwerk erhält

pro Takt 𝑇 über 𝐸 ein

Zeichen einer fort-

laufenden Eingabe 𝑤

• jeder Zustand von 𝐴

wird durch eine Kom-

bination von

Zuständen der drei

Flipflops kodiert z.B.

𝑠100:

FF0 => 0

FF1 => 0

FF2 => 1





Lösung:


1

0

0

0

1

0

1

1

0 1

0

0 0

0

1

0

0

0

Skript ID-9085





Jedes Schaltwerk ist die Realisierung eines endlichen

Automaten.

□ WAHR

□ FALSCH


Endliche Automaten und Schaltwerke sind gegenseitig

aufeinander abbildbar.


Frohe

Weihnachten

und einen guten

Rutsch ins

Neues Jahr!




Jedes Schaltwerk ist die Realisierung eines endlichen

Automaten.

□ WAHR

□ FALSCH


Endliche Automaten und Schaltwerke sind gegenseitig

aufeinander abbildbar.


Frohe

Weihnachten

und einen guten

Rutsch ins

Neues Jahr!

X

Documents

Grundlagen der Informatik II - info2.aifb.kit.eduinfo2.aifb.kit.edu/secure/Tutoriumsfolien/Tutorium4-Druck.pdf · 2 Grundlagen der Informatik II – Tutorium 4 Institut für Angewandte