Vorlesung 6

Question 1

Kontrollstrukturen

Answer 1

• Bisher: (weitestgehend) linearer Ablauf der Programme
• Jetzt: Beeinflussung des Programmflusses
• Kontrollstrukturen:
• Bedingte Anweisungen: wenn Anweisungen nur unter bestimmten Bedingungen
  ausgeführt werden sollen
• if, switch
• Schleifen: für wiederkehrende Anweisungen
• while, do, for
• Sprunganweisungen: Ausführung an anderer Stelle im Programm fortsetzen
• break, continue, goto, return

Question 2

Programmablaufplan

Answer 2

• Beschreibt die Abfolge von Anweisungen und Operationen in einem
  Programm.
• Auch bekannt als Flussdiagramm.

Question 3

Nassi-Shneiderman-Diagramm

Answer 3

• Stellt das Programm als hierarchische Lösung eines Problems dar, das in
  Teilprobleme zerlegt wird.
• Programme werden als Blöcke dargestellt und in Teilblöcke unterteilt.
• Auch bekannt als Struktogramm.
• Elemente:
  Anweisung Block
  Anweisung Unterblock
  Bedingung
  erfüllt?
  ja nein
  Verzweigter
  Block

Question 4

Mehrfachauswahl

Answer 4

● Ausführung von Befehlen in Abhängigkeit vom Ergebnis eines Ausdrucks.
● if: Anwendung, wenn nur wenige Alternativen oder wenn unterschiedliche
Bedingungen geprüft werden sollen
● switch: Anwendung, wenn viele Alternativen des gleichen Ausdrucks zu
unterschiedlichen Anweisungen führen sollen

Question 5

Syntax der switch-Anweisung

Answer 5

switch(Ausdruck)
{
case Konst1:
Anweisung1;
break;
case Konst2:
Anweisung2;
break;
…
default:
Default-Anweisung;
}

• Mit switch wird überprüft, ob der
  Wert eines Ausdrucks mit einer
  bestimmten Konstanten übereinstimmt
  und ggf. wird die hinter case stehende
  Anweisungsfolge ausgeführt.
• break beendet die switch-Anweisung
  (optional, sonst wird auch der nächste
  Abschnitt ausgeführt).
• Wenn der Wert mit keiner der
  Konstanten übereinstimmt, wird der
  default-Befehl ausgeführt (optional).

beispiel:

int c;
c = getchar();
switch(c) {
case ‘a’:
printf(“ein kleines a\n”);
break;
case ‘A’:
printf(“ein großes A\n”);
break;
case ‘b’:
case ‘B’:
printf(“ein kleines oder großes b\n”);
break;
default:
printf(“weder a noch b\n”);
}

Question 6

De Morgan’sche Gesetze

Answer 6

• ¬(A ʌ B) 㲗 ¬A ᴠ ¬B
• Beispiel:
• Es stimmt nicht, dass es regnet (A) und die Straße nass ist (B).
• Also regnet es entweder nicht (¬A) und/oder die Straße ist nicht nass (¬B).
• ¬(A ᴠ B) 㲗 ¬A ʌ ¬B
• Beispiel:
• Es stimmt nicht, dass es regnet (A) und/oder die Straße nass ist (B).
• Also regnet es nicht (¬A) und die Straße ist nicht nass (¬B).

Question 7

Boolesche Funktionen

Answer 7

● Definition: Eine n-stellige Boolesche Funktion ist eine Abbildung
f: {0, 1}n ➝ {0, 1}
● Beispiele:
– 1-stellige Boolesche Funktion: Negation (nicht)
* fnicht(0) = 1
* fnicht(1) = 0
– 2-stellige Boolesche Funktion: Konjunktion (und)
* fund(0, 0) = 0
* fund(0, 1) = 0
* fund(1, 0) = 0
* fund(1, 1) = 1
– Beachte Analogie zur Wahrheitstabelle

Question 8

Normalformen

Answer 8

• Jede n-stellige Funktion mit n ≥ 3 lässt sich als Kombination
  2-stelliger Funktionen darstellen.
• Disjunktive Normalform (DNF): Disjunktion von Konjunktionen (konjugierten
  Variablen in nichtnegierter oder negierter Form)
• Beispiel: (x ∧ ¬y ∧ z) ∨ (¬x ∧ y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ ¬z)
• Konjunktive Normalform (KNF): Konjunktion von Disjunktionen (disjugierten
  Variablen in nichtnegierter oder negierter Form)
• Beispiel: (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z¬) ∧ (x ∨ ¬y ∨ z)

Question 9

Erstellung DNF aus Wahrheitstabellen

Answer 9

man sucht die stellen bei denen die funktion f(x,y,z) 1 ergibt, und dreht alle variablen auf eins durch negation der nullen

x = 0 y = 0 z = 1 f(x,y,z) = 1
x = 0 y = 1 z = 0 f(x,y,z) = 1

f(x,y,z) = (¬x ʌ ¬y ʌ z) v (¬x ʌ y ʌ ¬z)

in den klammern UND operator, zwischen den klammern ODER operator

Question 10

Erstellung KNF aus Wahrheitstabellen

Answer 10

man such die stellen bei denen die funktion f(x,y,z) 0 ergibt, und dreht alle variablen auf 0 durch negation der einsen

x = 0 y = 0 z = 0 f(x,y,z) = 0
x = 0 y = 1 z = 1 f(x,y,z) = 0

f(x,y,z) = (x v y v z) ʌ (x v ¬y v ¬z)

in den klammern ODER operator, zwischen den klammern UND operator

Question 11

Algorithmen für DNF und KNF

Answer 11

DNF
Für eine gegebene n-stellige Funktion:
1. Erstelle Wahrheitstabelle.
2. Wähle alle Zeilen mit f(x1,…,xn) = 1.
3. Für jede Zeile bilde X1 ʌ … ʌ Xn
mit Xi := xi, wenn x0 = 1
mit Xi := ¬xi, wenn x0 = 0
4. Bilde Disjunktion (v) über die
gebildeten Terme.

KNF
Für eine gegebene n-stellige Funktion:
1. Erstelle Wahrheitstabelle.
2. Wähle alle Zeilen mit f(x1,…,xn) = 0.
3. Für jede Zeile bilde X1 v … v Xn
mit Xi := xi, wenn x0 = 0
mit Xi := ¬xi, wenn x0 = 1
4. Bilde Konjunktion (ʌ) über die
gebildeten Terme.

Question 12

Reduktion der Operatoren

Answer 12

• Alle Booleschen Funktionen lassen sich äquivalent nur mit den Operatoren
• AND, OR, NOT
• AND, NOT
• OR, NOT
• NOR
• NAND
  darstellen.
• Anwendung: Aufbau von Schaltkreisen mit möglichst wenig unterschiedlichen
  Bausteinen