Klausurtrainer Informatik I

• Die schwächste Vorbedingung eines Programms rückwärts berechnen (Zuweisungs- und Sequenzregel).
• Nachweisen, dass ein Prädikat Schleifeninvariante ist — als sauberer handschriftlicher Aufschrieb.
• Die Regeln auf Zuweisungen, Sequenzen und Schleifen sicher anwenden.

1. Hoare-Tripel

• P und Q sind Prädikate (Bedingungen über Variablen), z. B. x > 0 oder y == 2·x.
• Die schwächste Vorbedingung wp(S, Q) ist die größte Menge von Startzuständen, von denen aus Q nach S garantiert gilt.

2. Die Regeln des Hoare-Kalküls (komplett)

3. Die Sequenzregel als „wp-Kette“

Bei mehreren Anweisungen startet man bei der letzten Anweisung und arbeitet sich nach oben vor. Jede Zwischenbedingung ist gleichzeitig Nachbedingung der darüberliegenden Anweisung:

   { P }
S1: x = x - y
   { Q1 }
S2: y = y + x
   { Q2 }
S3: x = y - 1
   { Q3 ≡ x > 0 }

Gerechnet wird: Q2 = wp(S3, Q3), dann Q1 = wp(S2, Q2), dann P = wp(S1, Q1).

4. Schleifeninvariante — die komplette Beweismethode

Für while B: S wählt man ein Prädikat I und zeigt drei Eigenschaften:

1. Anfangsgültigkeit: { I } gilt vor dem ersten Schleifendurchlauf.
2. Erhaltung: { I ∧ B } S { I } — nach jedem Rumpf-Durchlauf gilt I wieder.
3. Abschluss: I ∧ ¬B ⇒ Q — nach der Schleife folgt die Nachbedingung.

In Teilaufgabe b) wird nur Eigenschaft 2 verlangt. Der Aufschrieb ist immer gleich: Annahme I ∧ B, die neuen Werte der Variablen bestimmen (mit Strich: p', q'), dann die Gleichungen nachrechnen.

Die wp-Berechnung ist eine rückwärts laufende Kette: Jede Anweisung übersetzt die Nachbedingung in ihre Vorbedingung, die zur Nachbedingung der darüberliegenden Anweisung wird.

Ableserichtung: ganz unten starten (Nachbedingung { x > 0 }), jede Zuweisung rückwärts „durchschieben“, oben ist die Vorbedingung erreicht.

Invariante als Schleifen-Flussdiagramm

Teil a) — Schwächste Vorbedingung (6 Punkte)

Strategie: Von unten nach oben. Nachbedingung Q ≡ { x > 0 }. Für die letzte Zuweisung x = y - 1 die Zuweisungsregel anwenden, dann für y = y + x, dann für x = x - y.

Ziel:  { x > 0 }

S3:  x = y - 1
     wp:  x := y - 1  einsetzen
     ⇒  { y - 1 > 0 }   ≡   { y > 1 }

S2:  y = y + x
     wp:  y := y + x  einsetzen
     ⇒  { (y + x) > 1 }

S1:  x = x - y
     wp:  x := x - y  einsetzen
     ⇒  { y + (x - y) > 1 }   ≡   { x > 1 }

Antwort:  Schwächste Vorbedingung  P ≡ { x > 1 }

Teil b) — Schleifeninvariante (6 Punkte)

Zu zeigen: Wenn I ≡ (p == q*a ∧ q ≤ b) gilt und die Schleifenbedingung q < b erfüllt ist, dann gilt I auch nach einem Rumpf-Durchlauf. Wir schreiben die neuen Werte mit Strich: p' = p + a und q' = q + 1.

I:  p == q·a  ∧  q ≤ b

Annahme:  I ∧ (q < b)  gilt vor dem Rumpf.

1) p = p + a  ⇒  p' = p + a
   Mit p == q·a folgt:
   p' = q·a + a = (q + 1)·a = q'·a          ✓

2) q = q + 1  ⇒  q' = q + 1
   Aus q < b  und  q, b ∈ int folgt:
   q ≤ b - 1  ⇒  q' = q + 1 ≤ b             ✓

Nach dem Rumpf gilt also wieder
   p' == q'·a  ∧  q' ≤ b   =  I            ∎
   Damit ist I eine Schleifeninvariante.

• Für eine Funktion mit Parameter k das Ergebnis des Aufrufs k = 3 bestimmen (exakt ausrechnen!).
• Die Anzahl der Operationen als Summe aufstellen und schließen.
• Eine möglichst kleine Komplexitätsklasse in Abhängigkeit von k angeben — und in Abhängigkeit von n = 2^k.

1. Was bedeutet Komplexität?

Die Laufzeitkomplexität beschreibt, wie die Anzahl der Operationen wächst, wenn die Eingabe größer wird. Üblich ist die O-Notation (obere Schranke): Konstante Faktoren und kleinere Terme werden vernachlässigt, es zählt nur die Wachstumsordnung.

• O(1) — konstant: die Operationsanzahl hängt nicht von der Eingabe ab.
• O(log n) — logarithmisch: die Eingabe wird pro Schritt halbiert/verdoppelt.
• O(n) — linear.
• O(n log n) — quasi-linear (typisch für gutes Sortieren).
• O(n²) — quadratisch (verschachtelte Schleifen).
• O(2^n) — exponentiell (sehr schnell wachsend).

2. Die Summenformeln, die du können musst

Gauß (arithmetisch):     Σ_{i=1}^{n} i   = n·(n+1)/2      ∈ O(n²)
Geometrisch:             Σ_{i=0}^{k} 2^i = 2^{k+1} - 1    ∈ O(2^k)
Ungerade Zahlen:         Σ_{i=1}^{n} (2i-1) = n²          ∈ O(n²)

Die erste taucht bei f2 auf (m wird nur um 1 kleiner), die zweite bei f3 (m halbiert sich).

3. Logarithmus-Kurzinfo (wegen n = 2^k)

n = 2^k bedeutet k = log₂(n). Deshalb sind diese Umrechnungen in der Aufgabe überall im Spiel:

• 2^k = n — die Schleife über k ist linear in k, aber logarithmisch in n.
• 2^{2k} = (2^k)² = n².
• Beispiele: k=3 → n=8, k=5 → n=32, k=10 → n=1024.

4. Analyse-Methodik für Schleifen

1. Fest verschachtelt: for i in range(n): for j in range(m): mit festem m → n · m Durchläufe (f1).
2. m sinkt um 1: while m > 0: for j in range(m); m = m - 1 → Summe n + (n-1) + … + 1 = n(n+1)/2 (f2).
3. m halbiert sich: while m > 0: for j in range(m); m = m // 2 → n + n/2 + … + 1 = 2n - 1 (f3) — die geometrische Reihe.

5. Ergebnis für k = 3

Das Ergebnis ist schlicht count nach allen Schleifen. Für k = 3 ist n = 2³ = 8. Am sichersten: die Summe aufstellen und n = 8 einsetzen (nicht abzählen!).

Die beiden f3-Kurven (durchgezogen) und die f1/f2-Kurven (gestrichelt): Schon ab k = 3 ist der Unterschied klar — f1 und f2 wachsen quadratisch, f3 nur linear.

Trace-Tabellen für k = 3 (n = 8)

f1:  m = 8, beide Schleifen 8-mal   →  8 · 8          = 64
f2:  m = 8,7,…,1                    →  8+7+6+5+4+3+2+1  = 36
f3:  m = 8,4,2,1                    →  8+4+2+1        = 15

a) f1 — fest verschachtelt (6 Punkte)

f1:  m = n bleibt konstant.
     Innere Schleife:  n  Durchläufe (jeweils m = n Schritte)
     Äußere Schleife:  n  Durchläufe

     Operationen:  T(k) = n · n = n² = (2^k)² = 2^{2k}

     k = 3:  n = 8,  T = 8² = 64

     Klasse:  O(n²)  bzw.  O(2^{2k})

b) f2 — m sinkt um 1 (6 Punkte)

f2:  m durchläuft n, n-1, …, 1
     Operationen:  T(k) = n + (n-1) + … + 1
                         = n·(n+1)/2        (Gauß)

     k = 3:  n = 8,  T = 8·9/2 = 36

     Klasse:  O(n²)  bzw.  O(2^{2k})

c) f3 — m halbiert sich (6 Punkte)

f3:  m durchläuft n, n/2, n/4, …, 1
     Operationen:  T(k) = n + n/2 + n/4 + … + 1
                         = Σ_{i=0}^{k} 2^i
                         = 2^{k+1} - 1      (geometrische Reihe)
                         = 2·2^k - 1 = 2n - 1

     k = 3:  n = 8,  T = 15

     Klasse:  O(n)  bzw.  O(2^k)

• Einen vorgegebenen Baum (Knoten mit Attributen) verschachtelt als XML schreiben.
• Element-Tags und Attribute korrekt verwenden; „self-closing“ Elemente ohne Kinder.
• Die Regeln wohlgeformten XMLs anwenden (ein Wurzel-Element, korrekt schließende Tags).
• Fehler in fremdem XML-Code finden.

1. Was ist XML?

XML ist ein Textformat, das Daten hierarchisch (baumartig) speichert. Die Bausteine:

• Element mit Start- und End-Tag: <kreis> … </kreis>. Ein Element ohne Inhalt: <haus/> (self-closing).
• Attribut am Start-Tag, Wert in Anführungszeichen: <kreis name="A-Kreis">.
• Text-Inhalt optional: <strasse>Hauptstr.</strasse>.
• Verschachtelung: Elemente enthalten Elemente (Kinder) — daraus entsteht der Baum.

2. Regeln für wohlgeformtes XML

1. Genau ein Wurzelelement — alles andere liegt darin.
2. Jedes geöffnete Tag wird geschlossen — und zwar umgekehrt zur Öffnungsreihenfolge (Stack-Prinzip, LIFO).
3. Attributwerte stehen in Anführungszeichen (einfach oder doppelt).
4. Tags sind case-sensitiv: <Ort> und </ort> passen nicht zusammen.
5. Elemente dürfen sich nicht überkreuzen: <a><b></a></b> ist verboten.

3. Baum → XML übersetzen (die Methode)

1. Wurzel identifizieren → wird das äußerste Element.
2. Jede Kante nach unten wird ein Kind-Element; jede Beschriftung am Knoten wird ein Attribut (hier: name, nummer).
3. Knoten ohne Kinder (die Blätter) als self-closing schreiben: <haus nummer="1"/>.
4. In jeder Ebene einrücken und gegenprüfen: hat jedes Element genau einen Eltern-Knoten? Das Zählen der Elemente pro Ebene ist die beste Selbstkontrolle.

• Eine Sprachbedingung verstehen und daraus die Sprachmenge (hier: alle Wörter ≤ 3 Zeichen) systematisch aufschreiben.
• Einen regulären Ausdruck konstruieren, der genau die Sprache beschreibt.
• Die Kleenesche Hülle, Alternation und optionale Teile sicher einsetzen.
• Aus einem regulären Ausdruck die beschriebene Sprache ablesen können.

1. Grundbegriffe

• Alphabet Σ: Menge erlaubter Zeichen, hier {a, b}.
• Wort: endliche Folge von Zeichen; das leere Wort ε hat Länge 0.
• Sprache L: Menge von Wörtern über Σ.
• Länge eines Wortes |w|: Anzahl der Zeichen, z. B. |aba| = 3, |ε| = 0.

2. Operatoren regulärer Ausdrücke — die komplette Tabelle

3. Sprachmengen systematisch aufzählen

Vorgehen bei „alle Wörter bis Länge n“:

1. Nach Länge sortieren: erst Länge 0 (nur ε), dann Länge 1, 2, 3, …
2. Innerhalb einer Länge alle Kombinationen über {a, b} hinschreiben. Bei Länge 2: aa, ab, ba, bb; bei Länge 3: aaa, aab, aba, abb, baa, bab, bba, bbb (2³ = 8 Stück).
3. Jedes Wort gegen die Sprachbedingung prüfen — durchstreichen, was nicht passt.

4. Die Bedingung dieser Aufgabe genau lesen

„Wenn in dem Wort ein b vorkommt, muss auf das erste b ein a (unmittelbar) folgen.“ — Nur das erste b ist eingeschränkt! Nach diesem ersten ba darf alles folgen (auch weitere b's). Typische Fehlinterpretation: „auf jedes b folgt ein a“ — das ist eine andere (strengere) Sprache.

Alle Wörter bis Länge 3 als Baum

Ausgefüllte Kreise: in der Sprache. Graue, durchgestrichene Kreise: verletzen die Bedingung (das erste b hat kein unmittelbar folgendes a).

Der reguläre Ausdruck als endlicher Automat

Von q0 aus beliebig viele a's. Beim ersten b geht es nach q1, das verlangte a führt nach q2 — von dort ist alles erlaubt. Genau die Sprache a*(ba(a|b)*)?.

Teil a) — alle Wörter ≤ 3 Zeichen (4 Punkte)

Länge 0:  ε

Länge 1:  a        (b ✗ — auf das erste b folgt kein a)

Länge 2:  aa, ba   (ab ✗ — erstes b am Wortende; bb ✗)

Länge 3:  aaa, aba, baa, bab
          (aab ✗ — erstes b am Ende;
           abb ✗, bba ✗, bbb ✗ — erstes b nicht von a gefolgt)

⇒  L_≤3 = { ε, a, aa, ba, aaa, aba, baa, bab }
   Das sind 8 Wörter.

Teil b) — der reguläre Ausdruck (6 Punkte)

Fall 1: keine b's:           a*
Fall 2: es gibt ein erstes b: a*  ba  (a|b)*

⇒  r = a* (ba (a|b)*)?
   (äquivalent:  a* | a*ba(a|b)*)

• Die Sprache einer Grammatik verstehen: alle ableitbaren Wörter mit Längengrenze angeben.
• Ableitungen mit Pfeilen aufschreiben können (S ⇒ aSb ⇒ …).
• Eine Funktion check_word schreiben, die genau die Wörter der Grammatik erkennt — rekursiv oder mit Zählung.

1. Formale Definition

In der Klausur: G = ({a, b, c}, {S}, S, {S → aSb, S → c}). Eine Variable S, drei Terminale, zwei Produktionen.

2. Ableiten — die Notation

Ein Wort ist in L(G), wenn man es vom Startsymbol aus durch Anwenden der Regeln erzeugen kann. Ein Ableitungsschritt ersetzt eine Variable durch die rechte Seite einer Produktion (geschrieben ⇒):

S ⇒ aSb ⇒ aaSbb ⇒ aacbb

Die dritte Produktionsanwendung ersetzt S durch c — damit sind alle Variablen verschwunden, das Wort aacbb ist fertig. ε wird genau dann abgeleitet, wenn eine Produktion S → ε existiert — hier nicht!

3. Die Struktur erkennen

Die Regel S → aSb „wickelt“ bei jeder Anwendung ein a links und ein b rechts um die noch offene Variable: S ⇒ aSb ⇒ aaSbb ⇒ …. Irgendwann wird S → c angewendet. Also:

4. Wörter mit Längengrenze finden

Man zählt, wie oft S → aSb angewendet wurde (das ist das n): Die Wortlänge ist 2n + 1. Für Länge ≤ 5 heißt das: n = 0 (Länge 1), n = 1 (Länge 3), n = 2 (Länge 5). Mehr gibt es nicht — jede weitere Anwendung addiert 2 Zeichen.

5. Erkennung als Funktion

check_word(s) muss genau die Wörter a^n c b^n akzeptieren. Zwei klassische Ansätze:

• Rekursiv (passt zur Grammatik): s == "c" ist der Basisfall; sonst muss s mit a beginnen, mit b enden und der innere Teil muss wieder gültig sein.
• Zählend: Es darf genau ein c geben; links davon nur a's, rechts nur b's, und die Anzahlen müssen gleich sein.

Der Ableitungsbaum für aacbb: innere Knoten sind die Variable S, die Blätter sind die Terminale. Die „Schalen“ a … b liegen von außen nach innen — das zeigt die Struktur a^n c b^n.

Teil a) — Wörter ≤ 5 Zeichen (3 Punkte)

n = 0:  c                          (Länge 1)
n = 1:  a c b                      (Länge 3)
n = 2:  a a c b b                  (Länge 5)

⇒  L(G)_≤5 = { c, acb, aacbb }
   Das sind 3 Wörter.

Teil b) — check_word (12 Punkte)

def check_word(s: str) -> bool:
    if s == "c":
        return True
    if len(s) < 3:
        return False
    if s[0] != 'a' or s[-1] != 'b':
        return False
    return check_word(s[1:-1])

def check_word(s: str) -> bool:
    if s.count('c') != 1:
        return False
    i = s.index('c')
    return s[:i] == 'a' * i and s[i + 1:] == 'b' * i

• Den Rekursionstyp einer Funktion begründet erkennen (hier: Endrekursion).
• Rekursion in eine äquivalente Schleife umwandeln — mit korrekter Reihenfolge der Updates.
• Hilfsfunktionen cond, fa, fb entwerfen, sodass die Funktion eine gewünschte Summe/Produkt berechnet.

1. Rekursionstypen

• Lineare Rekursion: genau ein rekursiver Aufruf, aber danach wird noch weiter gerechnet, z. B. return a + f(a - 1). Jeder offene Aufruf bleibt auf dem Aufruf-Stack, bis seine Kinder fertig sind.
• Baum-/Kaskadenrekursion: mehrere rekursive Aufrufe (z. B. Fibonacci: f(n-1) + f(n-2)).
• Endrekursion (Tail Recursion): der rekursive Aufruf ist die allerletzte Aktion; nach der Rückkehr wird nichts mehr berechnet. Das Muster: return f(neu_a, neu_b).

2. Warum ist Endrekursion besonders?

Bei Endrekursion passiert nach dem rekursiven Aufruf nichts mehr: Das Ergebnis des Kind-Aufrufs wird direkt zurückgegeben. Deshalb braucht man den Stack-Frame des Eltern-Aufrufs nicht mehr — ideale Compiler können die Rekursion in eine Schleife umwandeln (Tail-Call-Optimization). Die Funktion läuft mit konstantem Zusatzspeicher O(1), während lineare Rekursion O(n) Stack verbraucht.

3. Das allgemeine Schema dieser Aufgabe

def f(a: int, b: int) -> int:
    if cond(a):
        return b
    else:
        return f(fa(a), fb(a, b))

• cond(a) — Abbruchtest (Basisfall).
• fa(a) — neue Version von a („Schritt zum Ende hin“).
• fb(a, b) — neuer Akkumulator b, berechnet aus altem a und b.

Das ist das klassische Akkumulator-Muster: b sammelt das Zwischenergebnis, a schrumpft Richtung Basisfall. Genau dieses Schema muss man in Teil c) mit passenden Funktionen „füttern“.

4. Rekursion → Schleife

Endrekursion lässt sich mechanisch in eine Schleife übersetzen: Solange der Abbruchtest nicht erfüllt ist, werden die Parameter aktualisiert; danach b zurückgeben.

def f_loop(a: int, b: int) -> int:
    while not cond(a):
        b = fb(a, b)   # erst b mit ALTEM a berechnen!
        a = fa(a)      # dann a aktualisieren
    return b

5. Hilfsfunktionen entwerfen — die Methode

1. Basisfall bestimmen: Bei welchem a soll f einfach b zurückgeben? (Für s(n) = Σ i ist das a == 0.)
2. fa bestimmen: Wie kommt man Schritt für Schritt zum Basisfall? (a - 1.)
3. fb bestimmen: Die Rekursionsformel aus der Aufgabe umformen: s(a) = s(a-1) + a → der neue Akkumulator ist b + a.
4. Probe rechnen: Aufrufkette für ein Beispiel aufschreiben (siehe Musterlösung).

Teil a) — Rekursionstyp (3 Punkte)

f ist ENDREKURSIV (tail recursion).

Begründung: Im else-Zweig ist der rekursive Aufruf
f(fa(a), fb(a, b)) die ALLERLETZTE Aktion — sein
Ergebnis wird direkt zurückgegeben (return f(...)).
Nach dem Aufruf findet KEINE weitere Berechnung statt.

Teil b) — Schleifen-Version (4 Punkte)

def f_loop(a: int, b: int) -> int:
    while not cond(a):
        b = fb(a, b)
        a = fa(a)
    return b

Teil c) — Hilfsfunktionen für die Summe (9 Punkte)

cond(a) = (a == 0)          # Basisfall: Summe bis 0 ist 0
fa(a)   = a - 1             # n → n-1, Schritt Richtung Basisfall
fb(a, b) = b + a            # akkumuliere: bisherige Summe + a

Probe:  f(4, 0)
  f(4, 0) → cond(4)? nein → f(3, 0+4)
  f(3, 4) → cond(3)? nein → f(2, 4+3)
  f(2, 7) → cond(2)? nein → f(1, 7+2)
  f(1, 9) → cond(1)? nein → f(0, 9+1)
  f(0, 10) → cond(0)? ja   → 10
  s(4) = 0 + 1 + 2 + 3 + 4 = 10 ✓

• Eine Klasse mit Konstruktor, String-Repräsentation und Operator-Überladung schreiben.
• Verstehen, was z = x + y und print(z) hinter den Kulissen aufrufen.
• Die wichtigsten „dunder“-Methoden und ihre Operatoren kennen.

1. Klasse, Objekt, Attribut, Methode

• Klasse: Bauplan (hier StringNumber).
• Objekt/Instanz: konkretes Exemplar, erzeugt mit StringNumber("abcd").
• Attribut: Datenspeicher des Objekts, angelegt mit self.val = ….
• Methode: Funktion der Klasse; der erste Parameter ist immer self (das Objekt selbst).

2. Die drei „dunder“-Methoden dieser Aufgabe

3. Weitere dunder-Methoden (für Übungen und Verständnis)

4. Die Anforderungen der Aufgabe in Code übersetzt

1. „Konstruktor bekommt den String als Parameter und speichert ihn als Attribut“ → __init__(self, val) mit self.val = str(val) (sicherer Typ-Umbau).
2. „String-Repräsentation: String + in Klammern die Länge“ → __str__ mit f"{self.val} ({len(self.val)})".
3. „Addition zweier gespeicherter Zahlen“ → __add__: verketten und eine neue StringNumber zurückgeben.

5. f-Strings kurz erklärt

f"{self.val} ({len(self.val)})" setzt die Werte in geschweiften Klammern ein. Alles außerhalb der Klammern bleibt Text — hier ein Leerzeichen und zwei runde Klammern. Ergebnis für "abcd": abcd (4).