TU Wien:Grundzüge der Informatik VU (Schauer)/Erklärung der Übungen WS09

Mögliche Aufgaben

Fertig

• Übung 1: Informationsgehalt berechnen, Redundanz berechnen, Bit die nötig sind berechnen
• Übung 2: Schaltungen lösen, Äq/Antivalenz, kommutativ
• Übung 3: Wahrheitstabelle erstellen, Dualität, Wie viele unterschiedliche Schaltfunktionen mit n Eingängen sind?, Schaltung vollständig realisierbar?
• Übung 5: J/K Schaltungen lösen
• Übung 7: Syntax

Noch nicht fertig

• Übung 3 FEHLT: (Wie viele unterschiedliche Schaltfunktionen mit n Eingängen ist das duale Gegenstück komplementä)
• Übung 4
• Übung 6

Allgemein

• Was ist NAND? eine AND Verknüpfung negiert also 0001 => 1110

A	B	Y = A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

• Was ist NOR? eine OR Verknüpfung negiert also 0111 => 1000

A	B	Y = A ∨ B	Y =A ⊽ B
0	0	0	1
0	1	1	0
1	0	1	0
1	1	1	0

• Was ist XOR? Exklusive OR also nur true wenn eins der beiden richtig ist, nicht wenn beide richtig sind

A	B	Y = A ⊻ B
0	0	0
0	1	1
1	0	1
1	1	0

• Was ist ein OR:

A	B	Y = A ∨ B
0	0	0
0	1	1
1	0	1
1	1	1

• Was ist ein AND:

A	B	Y = A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

• Zustände:
• abc
• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111

Übung 1

• Anzahl Zeichen: n = 2^l
• Wahrscheinlichkeit, dass Zeichen auftritt p = 1/n
• Wortlänge l = ld(n) Bit - Wieviel Bit verwendet werden
• Informationsgehalt h(p) = ld(1/p) = ld(n) <- ist auch Wortlänge, also wieviel Bit braucht man?
• Mittlerer Informationsgehalt H = Σ pi ld 1/pi [bit] - Der Informationsgehalt ist der Informationsgehalt über alle verwendeten Zeichen
• Mittlere Wortlänge L = Σ pi li [bit] - Die mittlere Wortlänge sind die Bits die man benötigt um die Zahl zu speichern, da man keine halben Bits speichern kann
• Redundanz R = L - H [bit] Ist das was man sich eigentlich einsparen könnte, aber benötigt wird, da man keine halben Bits zur Verfügung hat

Aufgabe: Wie gross ist der Informationsgehalt einer zufällig aus einem Stapel von 52 Bridgekarten gezogenen Spielkarte?

• Es gibt 52 unterschiedliche Elemente = n = 2^l
• Informationsgehalt h(p) = ld(1/p) = ld(n) = ld(52) = ln(52)/ln(2) = log10(52) / log10(2) = logn(52)/logn(52) = 5.70 Bit
• Wolframalpha

Aufgabe: Wie gross ist der Informationsgehalt einer 7-stelligen Telefonnummer?

• 1234567 : von 0 bis 9999999 = 10^7 Möglichkeiten = n
• p = 1/10^7
• Informationsgehalt h(p) = ld(1/p) = ld(1/ (1/10^7)) = ld(10^7) = Wolfram = 23.25

• Alternativ: 7 * ld(10) = 23.25

Aufgabe: Wie gross ist der Informationsgehalt eines Datums, das aus Tag (1..31), Monat (1..12) und Jahr (1905..2004) besteht?

• n1 = (31-1 +1) = 31 => p1 = 1/31
• n2 = (12 -1 +1) = 12 => p2 = 1/12
• n3 = (2004 - 1905 +1) = 100 => p3 = 1/100
• h(p) = ld(1/p1) + ld(1/p2) + ld(1/p3) = ld(1/(p1*p2*p3)) = ld(n1) + ld(n2) + ld(n3) = ld(n1*n2*n3) = 15.18

Aufgabe: Wie gross ist die Redundanz, wenn eine 9-stellige ganze Dezimalzahl mit/ohne Vorzeichen in einem binären Code der Länge 32 bit dargestellt wird?

• 9-stellige Zahl => 10^9 Möglichkeiten
• und 1 bit für Vorzeichen reserviert (im letzten Schritt L-H wird noch -1 abgezogen, sonst nicht)
• n = 2*10^9, p = 1/(2*10^9)
• L = l = 32 Bit
• R = L - H = 32 - (h(1/p) - 1)= 32 - ld(10^9) -1= 1.10 Bit
• -> Alle Antwortmöglichkeiten im Taschenrechner oder bei Wolframalpha eingeben und testen ob es übereinstimmt

Aufgabe: Auf wieviele Dezimalziffern genau können ganze Zahlen mit Vorzeichen in einem binären Code der Länge 24 bit dargestellt werden?

• Verfügbare Bits = 24 - 1 Bit = 23 (eins wird wegen dem Vorzeichen abgezogen sonst nicht)
• Möglichkeiten = 2^23 = 8388608 = 7 Ziffern
• Allerdings kann nur von 0 bis 8388607 dargestellt werden, d.h. die erste Ziffer kann nur bis 8 (eigentlich 7) dargestellt werden -> es muss eine Ziffer abgezogen werden. Innerhalb 6 Ziffern können alle Zahlen dargestellt werrden
• 7 - 1 = 6

Übung 2

• *,& ist ein und
• +,| ist ein oder
• ! ist ein nicht

Aufgabe: Gegeben sei folgende Schaltfunktion: y = -a * b - Erstellen Sie die Wahrheitstabelle und wählen Sie die korrekte Antwort!

• a und b anschreiben 00, 01, 10, 11 und dann y lösen
• true = 1
• false = 0

Aufgabe: Welche der folgenden Schaltfunktionen entsprechen der Äquivalenz/Antivalenz von a und b?

Antivalenz:

• Antivalenz von a und b siehe Übung 3: a <!=> b
• a,b 00, 01, 10, 11 => 0 1 1 0
• Auf alle Schaltunten ausprobieren

• Äquivalenz von a und b siehe Übung 3: a <==> b
• a,b 00, 01, 10, 11 => 1 0 0 1
• Auf alle Schaltunten ausprobieren

Aufgabe: Aussagen überprüfen

• Komplementär: wenn man a und b hat dann ist GENAU (nur 1) 1 true.
• Kommutativ: Mathe: a ring b = b ring a
• Tauologie: Alles wahr
• Kontradiktion: Alles falsch
• Antivalenz/Äquivalzen siehe oben
• Implikation a => b
• Äquivalenz a <=> b
• Antivalenz a <!=> b

Richtig:

• Die Antivalenz ist kommutativ. (a <!=> b und b <!=> a ist das selbe)
• Die Äquivalenz ist kommutativ.
• Die NOR-Funktion und die OR-Funktion sind komplementär. (Richtig da eine Funktion negiert das komplement darstellt)

Falsch:

• Die NAND-Funktion und die NOR-Funktion sind komplementär.
• Die Implikation ist kommutativ. (a => b und b => a ist was anderes)
• Die AND-Funktion und die OR-Funktion sind komplementär.
• Die OR-Funktion und die NOR-Funktion sind komplementär.
• SONST einfach oben die Schaltfunktionen der Gatter anschauen und überprüfen ob sie Komplementär sind (immer genau 1 a oder b 1)

Übung 3

Aufgabe: Wahrheitstabelle einer Schaltfunktion erstellen

Beispiel: y = (-a * -b) + -(-a + -b)

• Lsg: Alle Kombinationen von a und b anschreiben und y damit lösen

Aufgabe: Welche der folgenden Schaltfunktionen realisieren die Äquivalenz/Antivalenz von a und b?

• Äquivalenz ist <==>
• Antivalenz ist <!=>

• a <==> b <- a ist das selbe wie b
• a <!=> b <- a ist nicht das selbe wie b

• a b <==>
• 0 0 1
• 0 1 0
• 1 0 0
• 1 1 1

• a b <!=>
• 0 0 0
• 0 1 1
• 1 0 1
• 1 1 0

-> Für alle gegebenen Funktionen die Wahrheitstabelle anschreiben und mit Antivalenz/Äquivalenz vergleichen

Aufgabe: Wie lautet die Ergebnisspalte der Wahrheitstabelle einer Schaltfunktion, die zu DUAL ist

• Bsp: Wie lautet die Ergebnisspalte der Wahrheitstabelle einer Schaltfunktion, die zu y = (-a & -b) | -(-a & -b) dual ist?

• Laut Informatik forum:
• Dual ist das Gegenteil vom gespiegelten - in Formeln: f(a,b) = !g(!a,!b)
• f = 00011100 --> f gespiegelt: 00111000 und dann invertiert ist g
• g =11000111
• 00011100 und 11000111 sind dual

• y lösen:
• ab y
• 00 1
• 01 0
• 10 0
• 11 1

• -> 1001 spiegeln 1001
• -> invertieren 0110 -> ist zu y dual

Aufgabe: Welche der folgenden Schaltfunktionen realisieren die Antivalenz von a und b?

Antivalenz ist <!=>

a <==> b <- a ist das selbe wie b a <!=> b <- a ist nicht das selbe wie b

• a b
• 0 0
• 0 1
• 1 0
• 1 1

Aufgabe: Wie lautet die Ergebnisspalte der Wahrheitstabelle einer Schaltfunktion, die zu dual ist?

y=(NOTa AND NOTB) OR (A AND B) Die Wahrheitstabelle dieser Schaltfunktion sieht so aus:

• a b y
• 0 0 1
• 0 1 0
• 1 0 0
• 1 1 1

Um die Ergebnisspalte der dualen Funktion zu erhalten, muss man einfach die Ergebnisspalte umkehren. Das heisst die duale Funktion zu 1001 hat die Ergebnisspalte 0110

Aufgabe: Wie viele unterschiedliche Schaltfunktionen mit n Eingängen gibt es?

• Lsg: 2^(2^n) = 256

Aufgabe: Wie viele unterschiedliche Schaltfunktionen mit n Eingängen sind kommutativ

• Lsg: 2^(n+1)

Übung 3 Aufgabe 5:

Frage: Wie viele unterschiedliche Schaltfunktionen mit drei Eingängen sind kommutativ? Geben Sie die Anzahl ohne Leerschläge ein! Antwort: 16 Schaltfunktionen

Erklärung: x = 3 (Eingänge) => 2^( 2^(x-1) ) = 2^4 = 16 Die Erklärung stimmt nicht. Die Formel für kommutative Funktionen ist 2^(n+1).

Bei kommutativen Funktionen muss man die Eingänge tauschen können , ohne dass sich an der Wahrheitstafel etwas ändert, das ist der Fall wenn die Eingänge alle 0 sind, alle 1 sind (klarerweise), aber auch wenn bei drei Eingängen die Belegung mit 001, 100 und 010 entweder immer 0 oder immer 1 ergibt bzw. wenn 110, 011 und 101 entweder immer 0 oder immer 1 ergeben. Also in (n+1) Fällen. (Weil zB bei fünf Eingängen ein einziger Eingang 1 sein kann, oder zwei, drei, vier oder fünf und zusätzlich alle null sein können.)

Die Zahl der möglichen kommutativen Funktionen ist daher 2^(n+1). Bei drei Eingängen ist das eben auch 16.

https://web.archive.org/web/*/www.informatik-forum.at/archive/index.php/t-50783.html

Aufgabe: Wie viele unterschiedliche Schaltfunktionen mit zwei Eingängen sind zu sich selbst dual?

• Lsg: 2^(2^(n-1))

Aufgabe: Wie viele unterschiedliche Schaltfunktionen mit n Eingängen ist das duale Gegenstück komplementär <TODO>

• Bei wievielen unterschiedlichen Schaltfunktionen ist das duale Gegenstück komplementär?
• Bei wie vielen unterschiedliche Schaltfunktionen mit drei Eingängen ist das duale Gegenstück gleichzeitig komplementär?

• Lsg: 2^(2^(n-1)) ... stimmt auch für 3 Eingänge (d.h. da kommt 16 raus - TR verwenden!! ;) )

Aufgabe: Wie lautet die Ergebnisspalte der Wahrheitstabelle einer Schaltfunktion, die zu y = komplementär ist?

• y = (!a & b) | !(!a | b)
• Komplementär: wenn man a und b hat dann ist GENAU (nur 1) 1 true.
• -> !y als Ergänzung

Aufgabe: Aussagen prüfen Komplimentär/ist Schaltung mit NAND/NOR/AND/NOR vollständig realisierbar

• Komplementär: wenn man a und b hat dann ist GENAU (nur 1) 1 true.
• Kommutativ: Mathe: a ring b = b ring a
• Tauologie: Alles wahr
• Kontradiktion: Alles falsch
• Antivalenz/Äquivalzen siehe oben
• Implikation a => b
• Äquivalenz a <=> b
• Antivalenz a <!=> b

RICHTIG:

• Jede Schaltfunktion lässt sich unter ausschliesslicher Verwendung von NAND-Gattern realisieren.
• Jede Schaltfunktion lässt sich unter ausschliesslicher Verwendung von NOR-Gattern realisieren.
• Zu jeder Schaltfunktion gibt es ein komplementäres Gegenstück.
• NAND und NOR sind zueinander dual.
• Tautologie und Kontradiktion sind zueinander dual.
• Äquivalenz und Antivalenz sind zueinander dual.

FALSCH:

• Schaltfunktionen, die zueinander dual sind, können nicht gleichzeitig komplementär sein.
• Jede Schaltfunktion lässt sich unter ausschliesslicher Verwendung von AND/OR realisieren.
• Schaltfunktionen, die zu sich selbst dual sind, sind auch immer kommutativ
• NAND und NOR sind zueinander komplementär.
• Schaltfunktionen, die zueinander dual sind, können nicht gleichzeitig komplementär sein.
• Schaltfunktionen, die zu sich selbst dual sind, sind auch immer

kommutativ.

Aufgabe: Komplement bilden

• Eine Zahl negativ machen: 2er Kompliment
• Vorgehensweise: Zahl invertieren -> 1er Kompliment
• 2er Kompliment: 1 dazu addieren

Übung 4

Grundlagen

• De'Morgansches Gesetz
• !(a & b) = !a | !b - nicht (a und b) = (nicht a) oder (nicht b)
• !(a|b) = !a & !b - nicht (a oder b) = (nicht a) und (nicht b)
• Folgerung:
• a & b = !(!a | !b)
• a | b = !(!a & !b)

• Vorgehensweise
• Schaltfunktion herausschreiben: das macht man in dem man von rechts anfangt das ist y = irgendwas
• dann sieht man das ein NOT kommt (der kreis) d.h. es ist was mit y = ! irgendwas
• Wenn man weiter nach links geht kommt ein Oder: d.h. es hat die Form y = !( irgendwas | irgendwas )
• Wenn man beiden Abzweigungen nach links weitergeht stösst man auf zwei NOT, d.h. hat es die Form y = !( ! irgendwas | ! irgendwas )
• Jetzt kommen wieder zwei oder d.h. y = !( ! (irgendwas | irgendwas) | ! (irgendwas | irgendwas) )
• die irgendwas enden bei den Eingängen d.h. y = !( ! (a | b) | ! (b | d) )

• Ziel ist es die Schaltfunktion so ähnlich Form zu bringen wie die Schaltfunktion die gegeben ist, so das man sieht welche Eingänge man negieren kann
• Das macht man mit dem De'Morganschem Gesetz
• Man kann 4 Eingänge negieren (b tritt doppelt auf, das spaltet man in b1 und b2)

Übung 5

Flip Flops

RS-FlipFlop

Das Reset-Set FlipFlop hat zwei Eingänge: Set und Reset

• Set=0 und Reset=0 => darf nicht passieren -> undefinierter Zustand -> race condition
• Set=1 und Reset=0 => Wert wird auf 1 gesetzt (Set)
• Set=0 und Reset=1 => Wert wird auf 0 gesetzt (Reset)
• Set=1 und Reset=1 => Zustand bleibt gespeichert (Store, Speichern)

S	R	Q
0	0	unverändert
1	0	1 (gesetzt)
0	1	0 (zurückgesetzt)
1	1	Q=Q=1 (wird nicht gespeichert; potenzielle Race condition)

JK-FlipFlop

Das Jump/Kill FlipFlop hat zwei Eingänge: Jump und Kill

• Jump=0 und Kill=0 => Zustand bleibt gespeichert (Store)
• Jump=1 und Kill=0 => Wert wird auf 1 gesetzt (Jump)
• Jump=0 und Kill=1 => Wert wird auf 0 gesetzt (Kill, Reset)
• Jump=1 und Kill=1 => Wert wird invertiert (Toggle)

während des Taktes		nach Taktflanke
J	K	Q
0	0	unverändert
0	1	0 (Flipflop zurückgesetzt)
1	0	1 (Flipflop gesetzt)
1	1	Zustand wechselt (toggle)

T-FlipFlop

Das Toogle-Flipflop invertiert den letzten Zustand wenn eine 1 anliegt, sonst bleibt er erhalten

• Toggle = 1 => Zustand wird invertiert (Toggle)
• Toggle = 0 => Zustand bleibt erhalten (Store)

D-FlipFlop

Das Data-Flipflop speichert den letzten Zustand wenn es auf

• Data = 1 => Zustand bleibt erhalten (Data)
• Data = 0 => Zustand wird gelöscht (Reset)

Vorgehen zum Lösen einer FlipFlop Schaltung

Kochrezept:

• Man zeichnet sich alle Zustände abc von 0-7 auf
• Man geht jeden Zustand einzeln durch:
• Man nimmt an in den Flipflops ist der aktuelle Zustand gespeichert
• Man nimmt schaut welcher Zustand an den J/K Eingängen liegt
• Man schaut in der Tabelle nach was passiert wenn J/K so gesetzt ist und schreibt sich in eine Tabelle daneben den folgezustand
• Man zeichnet das Zustandsdiagramm
• Man löst damit die Fragen

Übung 6

• (x+1)*(x-1) Infix Darstellung, so wie wir's in Mathe kennen

• *+x1-x1 Prefix: Operator steht vor Operanden --> Klammern sind daher

unwichtig

• x1+x1-* postfix: Es werden erst die nötigen Operanden angegeben und

anschließend ein Operator, welcher sich die zuvor angegebenen Operanden holt, die er benötigt.

• Preorder: jedes Element wird beim 1.Mal markiert

• Postorder: der letzte buchstabe ist die wurzel, und dann jenachdem ob der

buchstäbe größer ist als die wurzel nach rechts weiter oder wenn kleiner dann links weiter

• leveorder: erste buchstabe ist wurzel, dann jede höhenstufe von links nach

rechts!

• Schema zur vorgehensweise:
• Preorder: parent - left - right
• In order: left - parent - rigth
• Post order: left - right - parent
• siehe hier: [1]

Baum traversieren von preorder zu Levelorder

In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim preorder-Traversieren werden sie in der Reihenfolge

fbadceg

besucht. Wie lautet die Levelorder-Reihenfolge?

Lösung: fbgadce

Eine gute Simulation zur Traversierung von Bäumen gibts hier [2]

Baum traversieren von postorder zu Levelorder

In einem binären Sortierbaum sind die Schlüssel steigend sortiert. Beim postorder-Traversieren werden sie in der Reihenfolge

abdfec

besucht. Wie lautet die Levelorder-Reihenfolge?

Lösung: cbeadf

Hinweis: Das letzte Element der Postorder Traversierung muss bei der Rekonstruktion als Wurzelelement der Levelorder angenommen werden.

Traversierungsarten

• Preordertraversierung: Jedes Element wird beim 1. Mal markiert
• Postordertraversierung: Jene Elemente werden markiert, wenn sie zum letzten Mal erreicht werden.
• Inordertraversierung: Jedes Element wird beim 2. Besuch markiert oder sofort, wenn es nur einmal erreicht werden kann.
• Levelordertraversierung: Die Abfolge der zu markierenden Elemente beginnt bei der Wurzel und geht die gesamte Höhenstufe von links nach rechts entlang. Ist kein Element mehr in dieser Höhenstufe, so springt man zur unteren Höhenstufe zum ganz linken Element.

Sortierbaum:

                   d
                                        Wenn ein Element kleiner ist, als bei der aktuellen
                                        Stelle, so folgt man dem linken Ast, ansonsten
          b                 e           dem Rechten.
  a                c

Aufgabe: Eigenschaften von Bäume bestimmen

• Binär-Baum: Anzahl Knoten n = 2^(h+1) -1
• Binär-Baum: Höhe h = ld(n+1) -1
• Ordnung: höchste Anzahl der Abzweigungen von einem Knoten
• Binäre Bäume haben Ordnung 2

Aufgabe: Aussagen über arithmetische Schreibweise prüfen

Richtig:

• [x] Die infix-Schreibweise endet immer mit einer Variablen oder Konstanten.
• [x] Bei der prefix-, der infix- und der postfix-Darstellung ist die Reihenfolge der Variablen und Konstanten immer die selbe.
• [x] Bei der prefix-, der infix- und der postfix-Darstellung ist die Reihenfolge der Variablen und Konstanten immer dieselbe
• [x] Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Knoten.
• [x] Die infix-Schreibweise beginnt immer mit einer Variablen oder Konstanten.

Falsch:

• [] Die prefix-Schreibweise endet immer mit einem Operator.
• [] Ein als Baum dargestellter arithmetischer Ausdruck hat immer eine ungerade Anzahl von Blättern.
• [] Die prefix- und die postfix-Schreibweise können unterschiedlich lang sein.

Aufgabe: Welche der folgenden Aussagen über das Traversieren von binären Suchbäumen sind richtig, wenn die Schlüsselwerte in den Knoten steigend sortiert angeordnet sind?

Richtig:

• [x] Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der levelorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.
• [x] Die inorder-Reihenfolge entspricht immer der Sortierreihenfolge.
• [x] Die inorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.
• [x] Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der postorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.
• [x] Die inorder-Reihenfolge entspricht immer der Sortierreihenfolge.
• [x] Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der postorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.
• [x] Die inorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.

Falsch:

• [] Die postorder-Reihenfolge endet immer mit dem größten Schlüssel.
• [] Die levelorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.
• [] Ein binärer Sortierbaum hat immer eine ungerade Anzahl von Knoten.
• [] Die preorder- und die postorder-Reihenfolgen können unterschiedlich lang sein.
• [] Die levelorder-Reihenfolge endet immer mit dem grössten Schlüssel.
• [] Die postorder-Reihenfolge endet immer mit dem kleinsten Schlüssel.
• [] Die preorder-Reihenfolge beginnt immer mit dem kleinsten Schlüssel.
• [] Wenn die Schlüsselwerte paarweise disjunkt sind, lässt sich der Sortierbaum aus der inorder-Reihenfolge seiner Schlüssel eindeutig rekonstruieren.

Übung 7

Grundlagen

• [Code] = optional
• (Bindung) = Klammern
• {Code} = iteration -> kann mehrfach vorkommen
• x|y = Alternative entweder x oder y
• y=x. = Definition
• x y = Sequenz
• "x" = Terminal (Als Konstante)
• x = Nonterminal (als Variable)

Aufgabe: Das folgende Syntaxdiagramm definiert einen Code 1

[3]

• Aufgabe: Code = 0 oder 1 und dann kann noch ein Code kommen
• -> Jeder beliebige Binärcode kann damit dargestellt werden
• -> Jede Zahl ist richtig

Aufgabe: Das folgende Syntaxdiagramm definiert einen Code 2

• Aufgabe: Code = "0" [Code] "1" | "1" [Code] "0"
• -> Code muss mit 0 beginnen und mit 1 enden oder umgekehrt
• -> Code muss in der mitte 01 oder 10 haben
• -> Damit aussagen treffen
• -> Code ist übrigens nicht symmetrisch
• 1010 ist richtig und 0101 ist richtig
• Möglich wären z.B auch 1100 oder 0011

Aufgabe: Das folgende Syntaxdiagramm definiert einen Code 3

• Aufgabe: Code = [Code] ("0" | "1") [Code]
• d.h. man hat immer 0 oder 1 und kann beleibig 0 oder 1 dranhängen
• -> es können beliebige Codes generiert werden
• -> das Komplement ist wieder syntaktisch richtig
• Ziffernsummen können bleibig sein
• Anzahl von irgendwelchen Elementen können bliebig sein
• ...

Aufgabe: Gegeben ist folgender Syntax: tree = "0" | "(" "1" tree "1" ")"

• Aufgabe: Gegeben ist folgender Syntax: tree = "0" | "(" "1" tree "1" ")"
• d.h. es muss immer entweder eine 0 rauskommen oder ein (1<tree>1) ausdruck
• d.h. es ist möglich: 0, (101), (1(101)1) oder (1(1(1(101)1)1)1) usw.
• was anderes ist nicht möglich
• -> easy

Aufgabe: Gegeben ist folgender Syntax: tree = "(" digit | tree ")" digit = "0" | "1"

• Aufgabe: Gegeben ist folgender Syntax: tree = "(" digit | tree ")" digit = "0" | "1"
• d.h. es schaut so aus das eine Klammer kommt und dann kommt eine Ziffer oder wieder ein Tree mit Ziffern
• d.h. es sind möglich: (0), (1), ((0)), ((1)), (((0))), ...
• was anderes ist nicht möglich
• -> easy -> Immer symmetrisch, jeder tree beginnt und endet mit einer Klammer, es gibt nur eine Ziffer, ...

Aufgabe: Gegeben ist folgender Syntax: list = "0" | "1" | "0" list "1" | "1" list "0"

• Aufgabe: list = "0" | "1" | "0" list "1" | "1" list "0"
• Welche Strings entsprechend list?
• 1001 -> nicht, da es weder 0 ist noch 1 noch 0 [irgendwas] 1 noch 1 [irgendwas] 0
• 101 -> nicht, da es weder 0 ist noch 1 noch 0 [irgendwas] 1 noch 1 [irgendwas] 0
• 10110 -> schon, da 1 list 0 das äußerste ist dann bleibt 011 in der Mitte übrig, das ist wieder 0 list 1 da bleibt 1 in der Mitte -> passt
• 001 -> schon, da 0 list 1 das äußerste ist und 0 übrig bleibt -> passt

• Ähnliche Aufgabe:
• Frage ob List eine ungerade Anzahl Ziffern hat: Ja, da entweder 0 oder 1 oder irgendwas in der Mitte und aussen ziffern -> ungerade
• 0 und 1en sind nicht gerade
• Nicht symmetrisch aufgebaut
• Es existiert nicht immer mind. eine Null

Stuff

Aufgaben die zu klären sind

• Eingänge negieren? Übung 4
• https://web.archive.org/web/*/www.informatik-forum.at/attachment.php?attachmentid=9636&d=1169035288

Links

• Informatik Forum Tests
• Informatik Forum - #84
• [4]
• Datei:TU Wien-Grundzüge der Informatik VU (Schauer) - Grundzüge der Informatik.pdf

Todo für Test

• ALle Pdfs (Skriptum) ausdrucken

Lg. Simon