Übungen Informatik I, Gruppe 4 Robert S. Plaul Marc Christiansen 1

H1 (Ordnungsrelation)

Voraussetzungen: Die Relation | ⊆ IN × IN sei definiert durch:

a|b :⇔ ∃q ∈ IN : b = a · q

Behauptung: | ist eine Ordnung, also reflexiv, transitiv und antisymmetrisch. Beweis:

• Reflexivität Behauptung: Für alle a ∈ IN gilt a|a. ⇔ Für alle a ∈ IN gibt es ein q ∈ IN, so daß gilt: a = a · q Beweis: Setze q = 1. Es gilt: a = a · 1 ⇔ a = a. Die Relation ist also reflexiv.

• Transitivität Behauptung: Für alle a, b ∈ IN gilt: Aus a|b und b|c folgt a|c. Beweis: Seien a, b, c ∈ IN.

(a|b ∧ b|c) ⇔ (∃q ∈ IN : a · q = b) ∧ (∃r ∈ IN : b · r = c) (1)
⇔ ∃q, r ∈ IN : (a · q = b) ∧ (b · r = c)  (2)
⇔ ∃q, r ∈ IN : c = a · q · r  (3)
⇔ ∃p ∈ N : a · p = c  (4)
⇔ a|c  (5)

Anmerkung zu (3)⇔(4): ∀q, r ∈ IN : ∃p ∈ IN : p = q · r (Def. von (IN, ·))

• Antisymmetrie Behauptung: Für alle a, b ∈ IN gilt: Aus a|b und b|a folgt a = b. Beweis: Seien a, b ∈ IN.

(a|b ∧ b|a) ⇒ (∃q ∈ IN : b = a · q) ∧ (∃r ∈ IN : q = b · r)
⇒ ∃q, r ∈ IN : (b = a · q) ∧ (a = b · r)
⇒ ∃q, r ∈ IN : b = b · r · q
⇒ ∃q, r ∈ IN : r · q = 1
⇒ q = r = 1, q, r ∈ IN
⇒ a = b

| ist also eine Ordnung.

H2 (Assoziativität)

1. • Sei M eine Menge. Seien R, S, Q ∈ 2^{M×M}. Behauptung:R ∪ (S ∪ Q) = (R ∪ S) ∪ Q Beweis: Sei < x, y >∈ R ∪ (S ∪ Q)

⇔ (< x, y >∈ R) ∨ (< x, y >∈ (S ∪ Q))
⇔ (< x, y >∈ R) ∨ (< x, y >∈ S) ∨ (< x, y >∈ Q)
⇔ ((< x, y >∈ (R ∪ S)) ∨ (< x, y >∈ Q)
⇔ < x, y >∈ (R ∪ S) ∪ Q

∪ ist also assoziativ auf den homogenen Relationen auf M.

• Sei M eine Menge. Seien R, S, Q ∈ 2^{M×M}. Behauptung:R ∩ (S ∩ Q) = (R ∩ S) ∩ Q Beweis: Sei < x, y >∈ R ∩ (S ∩ Q)

⇔ (< x, y >∈ R) ∧ (< x, y >∈ (S ∩ Q))
⇔ (< x, y >∈ R) ∧ (< x, y >∈ S) ∧ (< x, y >∈ Q)
⇔ ((< x, y >∈ (R ∩ S)) ∧ (< x, y >∈ Q)
⇔ < x, y >∈ (R ∩ S) ∩ Q

∩ ist also assoziativ auf den homogenen Relationen auf M.

• Sei M eine Menge. Seien R, S, Q ∈ 2^{M×M}. Behauptung: Die Operation \ ist assoziativ. Beweis: Sei < x, y >∈ M × M. Sei R = Q = {< x, y >}. Sei S = ∅

R \ (S \ Q) = R \ ∅ = R  (6)
(R \ S) \ Q = (R \ ∅) \ Q = R \ Q = ∅  (7)

Da (6) und (7) ungleich sind, ist \ nicht assoziativ.

2. Sei M eine Menge. Seien R, S, Q ∈ 2^{M×M}. Behauptung: (R · S) · Q = R · (S · Q). Beweis: Sei < x, y >∈ (R · S) · Q.

⇔ ∃z ∈ M : (< x, z >∈ R · S)∧ < z, y >∈ Q
⇔ ∃z, w ∈ M : ((< x, w >∈ R) ∧ (< w, z >∈ S))∧ < z, y >∈ Q
⇔ ∃z, w ∈ M : (< x, w >∈ R) ∧ ((< w, z >∈ S) ∧ (< z, y >∈ Q))
⇔ ∃w ∈ M : (< x, w >∈ R) ∧ (< w, y >∈ S · Q)
⇔ < x, y >∈ R · (S · Q)

Die Operation Produkt ist also auf 2^{M×M} assoziativ.

H3 (Binomialkoeffizienten)

• \binom{n}{m} mit n, m ∈ IN ist definiert als die Anzahl der m–elementigen Teilmengen einer n–elementigen Menge.

Begründung für \binom{n}{0} = \binom{n}{n} = 1 Es gibt nur eine 0–elementige Teilmenge der n–elementigen Menge, nämlich ∅. Es gibt nur eine n–elementige Teilmenge der n–elementigen Menge, nämlich die Menge selbst. Dies gilt für alle n ∈ IN.

Begründung für \binom{n}{m} = 0 für 0 ≤ n < m Es gibt keine Teilmenge, die mehr Elemente als ihre Obermenge enthält.

Begründung für \binom{n}{m} = \binom{n−1}{m−1} + \binom{n−1}{m} für n, m ≥ 1 Sei N eine Menge mit n Elementen, sei M eine Menge mit m Elementen. Betrachtet man ein beliebiges x ∈ N, so gibt es bei der Auswahl der Teilmenge M zwei Möglichkeiten: Entweder das x ist in der Auswahl enthalten oder nicht. Im ersten Fall sinkt die Anzahl n der Elemente, die für die Auswahl in Frage kommen sowie die Anzahl m der Elemente, die für die Teilmenge ausgewählt werden müssen jeweils um 1 (d.h. \binom{n−1}{m−1}). Im zweiten Fall verringert sich nur die Anzahl n um eins, da ja trotzdem m Elemente aus der Menge N entnommen werden müssen (d.h. \binom{n−1}{m}).

• Behauptung: Für alle n ≥ 0 gilt:

∑_{i=0}^{n} \binom{n}{i} = 2^{n}

Beweis durch vollständige Induktion: Induktionanfang: Setze n = 0. Es gilt:

∑_{I=0}^{0} \binom{0}{i} = 1 = 2^{0}

Induktionsvoraussetzung: Sei n ∈ IN. Es gelte:

∑_{i=0}^{n} \binom{n}{i} = 2^{n}

Übungen Informatik I, Gruppe 4 Robert S. Plaul Marc Christiansen 4

Induktionsschritt:

∑_{i=0}^{n+1} \binom{n + 1}{i} = ∑_{i=0}^{n} \binom{n + 1}{i} + \binom{n + 1}{n + 1}
= \binom{n + 1}{0} + ∑_{i=1}^{n} \binom{n + 1}{i} + \binom{n + 1}{n + 1}
= 1 + ∑_{i=1}^{n} (\binom{n}{i − 1} + \binom{n}{i}) + 1
= 2 + ∑_{i=1}^{n} \binom{n}{i − 1} + ∑_{i=1}^{n} \binom{n}{i}
= 1 + ∑_{i=1}^{n} \binom{n}{i − 1} + \binom{n}{0} + ∑_{i=1}^{n} \binom{n}{i}
= 1 + ∑_{i=1}^{n} \binom{n}{i − 1} + ∑_{i=0}^{n} \binom{n}{i}
= \binom{n}{n} + ∑_{i=0}^{n−1} \binom{n}{i} + ∑_{i=0}^{n} \binom{n}{i}
= ∑_{i=0}^{n} \binom{n}{i} + ∑_{i=0}^{n} \binom{n}{i}
= Σ_{i=0}^{n}\binom{n}{i} · 2
=^{I.V.} 2^{n} · 2

q.e.d.

H4 (Potenzmenge)

Sei (M, ≤) eine geordnete Menge und seien x, y ∈ M. Ist x < y, so heißt x Vorgänger von y. Gilt darüber hinaus für jedes z ∈ M : x ≤ z ≤ y ⇒ (x = z oder y = z), so heiße x direkter Vorgänger von y. P_{fin}(IN) sei die Menge aller endlichen Teilmengen von IN.

1. Behauptung: (P_{fin}(IN), ⊆) ist noethersch.

Beweis: (P_{fin}(IN), ⊆) ist eine geordnete Menge, da P_{fin}(IN) ∋ {1} ≠ ∅. Sei f : P_{fin}(IN) → IN, X → |X|. Seien M, N ∈ P_{fin}(IN) mit M ⊂ N. Dann folgt f(M) < f(N). Da (IN, ≤) noethersch, ist nach O7(1.) auch (P_{fin}(IN), ⊆) noethersch.

q.e.d.

2. Behauptung: Eine Menge X ∈ P_{fin}(IN) hat |X| direkte Vorgänger. Begründung: Sei X ∈ P_{fin}(IN). Wir unterscheiden zwei Fälle: X ≠ ∅ und X = ∅. Fall 1: X ≠ ∅. Ein Y ∈ P_{fin}(IN) ist direkter Vorgänger von X genau dann, wenn es ein x ∈ X gibt, so daß Y = X\{x}. Dies läßt sich wie folgt begründen: Y direkter Vorgänger von X heißt: Y ist Vorgänger von X (also Y ⊂ X) und für alle Z ∈ P_{fin}(IN) gilt: (Y ⊆ Z ⊆ X) ⇒ (Y = Z oder X = Z). Wenn Y ⊂ X ist und mindestens zwei Elemente x_{1}, x_{2} ∈ X nicht enthält, dann gilt für Z = X\{x_{1}} : Y ⊆ Z ⊆ X, aber X ≠ Z und Y ≠ Z, also ist Y kein direkter Vorgänger von X. Fall 2: X = ∅. Dann ist |X| = 0.

Also sind die direkten Vorgänger von X alle (|X| − 1)–elementigen Teilmengen von X. Dies sind gerade |X| Stück, also hat X ∈ P_{fin}(IN) genau |X| direkte Vorgänger.

3. Behauptung: X ∈ P_{fin}(IN) hat insgesamt 2^{|X|} − 1 Vorgänger. Beweis: Seien X, Y ∈ P_{fin}(IN). Y ist Vorgänger von X, wenn gilt: Y ⊂ X. Also ist die Anzahl der Vorgänger von X die Anzahl aller echten Teilmengen von X. Nach Aufgabe H3 ist die Gesamtzahl der Teilmengen einer n–elementigen Menge gerade 2^{n}. Da diese Zahl auch die Menge selbst beinhaltet, muß noch 1 davon abgezogen werden, um die Anzahl der echten Teilmengen zu erhalten. X enthält |X| Elemente. Damit ist die Gesamtzahl an Vorgängern 2^{|X|} − 1.

q.e.d.

H5 (Konkatenation)

Sei A ein Alphabet. Behauptung: <> ist rechtsneutral bezüglich conc, also es gilt:

∀w ∈ A^{∗} : conc(w, <>) = w

Beweis durch strukturelle Induktion: Seien w ∈ A^{∗}, a ∈ A. Induktionsanfang: conc(<>, <>) =<> (nach Def. von conc) Induktionsvoraussetzung: Es gelte:

conc(w, <>) = w

Induktionsschritt:

conc(prefix_{a}(w), <>) = prefix_{a}(conc(w, <>))
= prefix_{a}(w) (nach I.V.)

q.e.d.

H6 (Twist)

Sei A ein Alphabet und BK die Menge der Binärbäume mit Knotenmarkierungen aus A.

1. Sei twist : BK → BK folgendermaßen definiert:

twist(a) := a für alle a ∈ A  (8)
twist(mk_{a}(l, r)) := mk_{a}(twist(r), twist(l))  (9)
für alle a ∈ A, l, r ∈ BK

2. Behauptung: Für alle b ∈ BK gilt: twist(twist(b)) = b. Beweis: Seien b, c ∈ BK, a ∈ A. Induktionsanfang: twist(twist(a)) = twist(a) = a (nach (8)) Induktionsvoraussetzung: Es gelte: twist(twist(b)) = b. Induktionsschritt:

twist(twist(mk_{a}(b, c)) = twist(mk_{a}(twist(c), twist(b))) (nach (9))
= mk_{a}(twist(twist(b)), twist(twist(c))) (nach (9))
= mk_{a}(b, c)

q.e.d.

Übungen Informatik I, Gruppe 4 Robert S. Plaul Marc Christiansen 7

3. Sei istInnererKnoten : BK × A → IB folgendermaßen definiert:

istInnererKnoten(b, a) = tt :⇔ b = a für alle a, b ∈ A
istInnererKnoten(mk_{c}(l, r), a) = tt :⇔ (c = a)

∨(istInnererKnoten(l, a) = tt ∧ l ∉ A) ∨(istInnererKnoten(r, a) = tt ∧ r ∉ A) für alle l, r ∈ BK, a, c ∈ A

4. Behauptung: Es gilt für alle b ∈ BK, a ∈ A:

istInnererKnoten(b, a) = tt ⇒ istElemK(b, a) = tt Beweis: Seien a, c ∈ A, b ∈ BK. Induktionsanfang: Es gilt:

istInnererKnoten(c, a) = tt ⇔ c = a
⇒ istElemK(c, a) = tt

Induktionsvoraussetzung:

istInnererKnoten(b, a) = tt ⇒ istElemK(b, a) = tt

Induktionsschritt: Es gelte:

istInnererKnoten(mk_{c}(l, r), a) = tt

⇒ (c = a) ∨ ((istInnererKnoten(l, a) = tt) ∧ (l ∉ A))
∨ ((istInnererKnoten(r, a) = tt) ∧ (r ∉ A))
⇒ (c = a) ∨ (istInnererKnoten(l, a) = tt) ∨ (istInnererKnoten(r, a) = tt)
⇒ istElemK(mk_{c}(l, r), a) = tt

q.e.d.

H7 (Textersetzungssystem: Palindrome)

Sei A := {a, b} und seien $ und £ zwei Symbole. Sei T ein Textersetzungssystem über dem Alphabet B := {a, b, $, £, S}, wobei S ∈ A^{∗} als Hilfszeichen dient, und mit der Regelmenge

ℜ := \{ \begin{matrix}(1) & $£ & → & ε, \\ (2) & $a£ & → & ε, \\ (3) & $b£ & → & ε, \\ (4) & $aSa£ & → & $S£, \\ (5) & $bSb£ & → & $S£ \end{matrix} \} .

T erfüllt die Eigenschaft

w ∈ A^{∗} ist ein Palindrom ⇔ $w£ ⇒^{∗} ε und ε ist Normalform zu T.

Das Textersetzungssystem funktioniert folgendermaßen: Die leere Zeichenkette und die beiden Zeichenketten der Länge eins (”a“ und ”b“) sind Palindrome; deshalb bilden die Regeln (1)–(3) die Zeichenketten $£, $a£ und $b£ auf ε ab. Sei w ∈ T^{∗} im folgenden ein Palindrom mit |w| > 1. Dann existiert ein v ∈ T^{∗} mit w = ava oder w = bvb, wobei v wieder ein Palindrom ist. Die Regeln (4) und (5) liefern nun zu jedem w das zugehörige v. Ist |w| gerade, so liefert wiederholtes Anwenden der Regeln (4) und (5) die Zeichenreihe $£, welche mit Regel (1) in ε überführt wird. Ist |w| ungerade, so bleibt nach wiederholtem Anwenden von (4) und (5) entweder die Zeichenreihe $a£ oder $b£ übrig, die mit der Regel (2) bzw. (3) in ε überführt wird. Ist w kein Palindrom, dann terminiert die Berechnungsrelation mit einer Zeichenreihe der Form $avb£ oder $bva£, wobei v ∈ A^{∗} ist. Beispielrechnung für abba:

$abba£ ⟶^{(4)} $bb£ ⟶^{(5)} $£ ⟶^{(1)} ε.

Da abba ein Palindrom ist, wird $abba£ in ε überführt.

H8 (Grammatik)

Seien T := {a, b}, N := {W } und S := W. Sei P := {W → ε | abW | baW | W ab | W ba | aW b | bW a} und sei G = (N, T, P, S) eine Grammatik. Sei L := {w ∈ T^{∗} : |w|_{a} = |w|_{b}}. Behauptung: Dann gilt L(G) = L. Beweis durch Induktion über |w|: Induktionsanfang: Sei w ∈ T^{∗} mit |w| = 0. Dann ist w = ε und es gilt: ε ∈ L und ε ∈ L(G). Induktionsschritt: Sei w ∈ T^{∗} mit |w| ≥ 1. ”⇒“: Es gelte w ∈ L. Dann existiert ein v ∈ T^{∗} mit w = abv oder w = bav oder w = vab oder w = vba oder w = avb oder w = bva. O.B.d.A. sei im folgenden w = abv oder w = vab oder w = avb. Da w ∈ L ist, gilt auch v ∈ L und nach Induktionsvoraussetzung (|v| < |w|) folgt v ∈ L(G), d. h. W ⇒^{∗} v. Also W ⇒ abW ⇒^{∗} abv = w oder W ⇒ W ab ⇒^{∗} vab = w oder W ⇒ aW b ⇒^{∗} avb = w, d. h. w ∈ L(G). ”⇐“: Es gelte w ∈ L(G). Dann gilt W ⇒^{∗} w, also W ⇒ abW ⇒^{∗} w oder W ⇒ baW ⇒^{∗} w oder W ⇒ W ab ⇒^{∗} w oder W ⇒ W ba ⇒^{∗} w oder

W ⇒ aW b ⇒^{∗} w oder W ⇒ bW a ⇒^{∗} w.

O.B.d.A gelte W ⇒ abW ⇒^{∗} w oder W ⇒ W ab ⇒^{∗} w oder W ⇒ aW b ⇒^{∗} w. Dann existiert v ∈ T^{∗} mit w = abv oder w = vab oder w = avb und W ⇒^{∗} v. Damit ist v ∈ L(G) und |v| < |w|. Nach Induktionsvoraussetzung folgt v ∈ L. Damit ist w = abv ∈ L oder w = vab ∈ L oder w = avb ∈ L.

Übungen Informatik I, Gr. 4 K. Wittek, R.-S. Plaul, M. Christiansen 10

H9 (Signatur der Zeichenreihen)

Seien A := {a, b}, Σ_{A^{∗}} wie in 3.3.2 definiert. Sei x eine Variable der Sorte string, y eine Variable der Sorte char und X := {x, y}. Sei ferner t := postfix(y, lead(prefix(a, x))). Die Variablensubstitutionen σ_{1}, σ_{2}, σ_{3} : X → T_{Σ_{A^{∗}}}(X) seien wie folgt definiert:

\begin{aligned}σ_{1}(x) & := & prefix(a, prefix(y, prefix(a, empty))) & σ_{1}(y) & := & a \\ σ_{2}(x) & := & prefix(y, x) & σ_{2}(y) & := & b \\ σ_{3}(x) & := & prefix(b, prefix(a, empty)) & σ_{3}(y) & := & a \end{aligned}

Dann gilt:

tσ_{1} = postfix(a, lead(prefix(a, prefix(a, prefix(y, prefix(a, empty))))))
tσ_{2} = postfix(b, lead(prefix(a, prefix(y, x))))
tσ_{3} = postfix(a, lead(prefix(a, prefix(b, prefix(a, empty)))))

Sei B die ”Standard“-Algebra der Zeichenreihen zur Signatur Σ_{A^{∗}} mit char^{B} = {a, b}, string^{B} = A^{∗} und σ : X → char^{B} ∪ string^{B} eine Belegung mit σ(x) = abba und σ(y) = b. Dann gilt:

I[t]_{σ}^{B} = postfix(b, lead(prefix(a, abba)))
= postfix(b, lead(aabba))
= postfix(b, aabb)
= aabbb
I[tσ_{1}]_{σ}^{B} = postfix(a, lead(prefix(a, prefix(a, prefix(b, prefix(a, empty))))))
= postfix(a, lead(prefix(a, prefix(a, prefix(b, a)))))
= postfix(a, lead(prefix(a, prefix(a, ba))))
= postfix(a, lead(prefix(a, aba)))
= postfix(a, lead(aaba))
= postfix(a, aab))
= aaba
I[tσ_{2}]_{σ}^{B} = postfix(b, lead(prefix(a, prefixb, abba))))
= postfix(b, lead(prefix(a, babba)))
= postfix(b, lead(ababba))
= postfix(b, ababb)
= ababbb

I[tσ_{3}]_{σ}^{B} = postfix(a, lead(prefix(a, prefix(b, prefix(a, empty)))))
= postfix(a, lead(prefix(a, prefix(b, a))))
= postfix(a, lead(prefix(a, ba)))
= postfix(a, lead(aba))
= postfix(a, ab)
= aba.

H10 (Termersetzungssystem)

Sei die Signatur Σ = {{nat}, {null : nat}, {succ, pred, f : nat → nat}} gegeben und sei T = (Σ, X, R), wobei R aus folgenden Regeln besteht:

f(null) → succ(null), f(succ(x)) → succ(f(pred(f(x)))), pred(succ(x)) → x.

Der Term succ(succ(… (succ(null) …)), in dem genau n-mal das Funktionssymbol succ vorkommt, wird im folgenden durch succ^{n}(null) abgekürzt.

1. Es gilt:

f(succ^{0}(null)) = f(null)
= succ(null)
f(succ^{1}(null)) = succ(f(pred(f(null))))
= succ(f(pred(succ(null))))
= succ(f(null))
= succ(succ(null))
= succ^{2}(null)
f(succ^{2}(null)) = f(succ(succ(null)))
= succ(f(pred(f(succ(null)))))
= succ(f(pred(succ(succ(null)))))
= succ(f(succ(null)))
= succ(succ(succ(null)))
= succ^{3}(null)
f(succ^{3}(null) = f(succ(succ(succ(null))))

= succ(f(pred(f(succ(succ(null))))))
= succ(f(pred(succ(succ(succ(null))))))
= succ(f(succ(succ(null))))
= succ(succ(succ(succ(null))))
= succ^{4}(null)

Offenbar entspricht die Funktion f der Funktion succ. Also gilt für alle n ∈ IN: f(succ^{n}(null)) = succ^{n+1}(null).

2. Behauptung: Für alle Grundterme t ∈ T_{Σ} der Form succ^{n}(null) existiert eine Normalform t′ ∈ T_{Σ} der Form succ^{m}(null) mit f(t) ⇒^{∗} t′. Beweis durch strukturelle Induktion: Induktionsanfang: Setze n = 0. Es gilt:

f(succ^{0}(null)) = succ(null) = succ^{1}(null)

succ^{0}(null) ist Grundterm und succ^{1}(null) ist Normalform von T Σ,

und es gilt: succ^{0}(null) ⇒^{∗} succ^{1}(null).

Induktionsschritt: n → n + 1. Es gilt:

f(succ^{n+1}(null)) = f(succ(succ^{n}(null)))
= succ(f(pred(f(succ^{n}(null)))))
= succ(f(pred(succ^{n+1}(null))))
= succ(f(succ^{n}(null)))
= succ(succ^{n+1}(null))
= succ^{n+2}(null)

succ^{n+1}(null) ist Grundterm und succ^{n+2} ist Normalform von T Σ, und

es gilt: succ^{n+1}(null) ⇒^{∗} succ^{n+2}(null).

q.e.d..

Übungen Informatik I, Gr. 4 R.-S. Plaul, K. Wittek, M. Christiansen 13

H11 (Markov-Algorithmen

1. Ein Markov-Algorithmus zur Verdoppelung einer natürlichen Zahl, die in Dezimaldarstellung über dem Alphabet A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} gefolgt von dem Symbol $ gegeben ist, hat folgende Regeln:

\begin{aligned}0$ & → & $0 & (1) \\ 1$ & → & $2 & (2) \\ 2$ & → & $4 & (3) \\ 3$ & → & $6 & (4) \\ 4$ & → & $8 & (5) \\ 5$ & → & £0 & (6) \\ 6$ & → & £2 & (7) \\ 7$ & → & £4 & (8) \\ 8$ & → & £6 & (9) \\ 9$ & → & £8 & (10) \\ $ & → & ε & (11) \end{aligned}  \begin{aligned}0£ & → & $1 & (12) \\ 1£ & → & $3 & (13) \\ 2£ & → & $5 & (14) \\ 3£ & → & $7 & (15) \\ 4£ & → & $9 & (16) \\ 5£ & → & £1 & (17) \\ 6£ & → & £3 & (18) \\ 7£ & → & £5 & (19) \\ 8£ & → & £7 & (20) \\ 9£ & → & £9 & (21) \\ £ & → & 1 & (22) \end{aligned}

Das £ dient zur Notierung eines Übertrages, mit den Regeln (11) und (22) wird ein links stehendes $ entfernt.

Die Anwendung des Algorithmus’ auf 71279 liefert:

71279$ →^{(10)} 7127£8
→^{(19)} 712£58
→^{(14)} 71$558
→^{(2)} 7$2558
→^{(8)} £42558
→^{(22)} 142558

2. Um eine in Binärdarstellung über dem Alphabet {∅, L} gegebene natürliche Zahl in Dezimaldarstellung über dem Alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} zu überführen, eignet sich folgender Regelsatz:

\begin{aligned}0$ & → & $0 & (1) \\ 1$ & → & $2 & (2) \\ 2$ & → & $4 & (3) \\ 3$ & → & $6 & (4) \\ 4$ & → & $8 & (5) \\ 5$ & → & £0 & (6) \\ 6$ & → & £2 & (7) \\ 7$ & → & £4 & (8) \\ 8$ & → & £6 & (9) \\ 9$ & → & £8 & (10) \\ $ & → & ε & (11) \end{aligned}  \begin{aligned}0£ & → & $1 & (12) \\ 1£ & → & $3 & (13) \\ 2£ & → & $5 & (14) \\ 3£ & → & $7 & (15) \\ 4£ & → & $9 & (16) \\ 5£ & → & £1 & (17) \\ 6£ & → & £3 & (18) \\ 7£ & → & £5 & (19) \\ 8£ & → & £7 & (20) \\ 9£ & → & £9 & (21) \\ £ & → & 1 & (22) \end{aligned}

\begin{aligned}0/ & → & 1 & (23) \\ 1/ & → & 2 & (24) \\ 2/ & → & 3 & (25) \\ 3/ & → & 4 & (26) \\ 4/ & → & 5 & (27) \\ 5/ & → & 6 & (28) \\ 6/ & → & 7 & (29) \\ 7/ & → & 8 & (30) \\ 8/ & → & 9 & (31) \\ 9/ & → & /0 & (32) \\ / & → & 1 & (33) \end{aligned}  \begin{aligned}%L & → & $/% & (34) \\ %∅ & → & $% & (35) \\ % & → & ε & (36) \\ L & → & 0%L & (37) \\ ∅ & → & 0%∅ & (38) \end{aligned}

Der erste Block, (1)-(22), verdoppelt die Dezimalzahl. Der Block von (23)-(33) addiert 1 zur Dezimalzahl. Die Regel (34) arbeitet ein L ab, indem sie dafür sorgt, daß die Dezimalzahl erst verdoppelt und dann um eins erhöht wird. Die Regel (35) arbeitet eine ∅ ab, indem sie dafür sorgt, daß die Dezimalzahl verdoppelt wird. Die Regel (36) entfernt das %-Zeichen am Ende der Umwandlung. Die letzten beiden Regeln fügen zu Beginn 0% vor der Binärzahl an.

Übungen Informatik I, Gr. 4 R.-S. Plaul, K. Wittek, M. Christiansen 15 Für L∅L∅L ergeben sich folgende Rechenschritte:

\begin{aligned}L∅L∅L & →^{(37)} & 0%L∅L∅L \\ & →^{(34)} & 0$/%∅L∅L \\ & →^{(1)} & $0/%∅L∅L \\ & →^{(11)} & 0/%∅L∅L \\ & →^{(23)} & 1%∅L∅L \\ & →^{(35)} & 1$%L∅L \\ & →^{(2)} & $2%L∅L \\ & →^{(11)} & 2%L∅L \\ & →^{(34)} & 2$/%∅L \\ & →^{(3)} & $4/%∅L \\ & →^{(11)} & 4/%∅L \end{aligned}  \begin{matrix}→^{(27)} & 5%∅L \\ →^{(35)} & 5$%L \\ →^{(6)} & £0%L \\ →^{(22)} & 10%L \\ →^{(34)} & 10$/% \\ →^{(1)} & 1$0/% \\ →^{(2)} & $20/% \\ →^{(11)} & 20/% \\ →^{(23)} & 21% \\ →^{(36)} & 21 \end{matrix}

H12 (Das ML-System)

1. Bildschirmausgabe:

- use "/home/inf1057/isperfect.ml";
[opening /home/inf1057/isperfect.ml]
val devides = fn : int * int -> bool
val isp = fn : int * int * int -> bool
val isperfect = fn : int -> bool
val it = () : unit
- isperfect(0);
val it = true : bool
- isperfect(1);
val it = false : bool
- isperfect(2);
val it = false : bool
- isperfect(3);
val it = false : bool
- isperfect(4);
val it = false : bool
- isperfect(5);
val it = false : bool
- isperfect(6);
val it = true : bool
- isperfect(7);
val it = false : bool
- isperfect(8);
val it = false : bool
- isperfect(9);
val it = false : bool
- isperfect(10);
val it = false : bool
- isperfect(11);
val it = false : bool
- isperfect(12);
val it = false : bool
- isperfect(13);
val it = false : bool
- isperfect(14);
val it = false : bool
- isperfect(15);

val it = false : bool
- isperfect(16);
val it = false : bool
- isperfect(17);
val it = false : bool
- isperfect(18);
val it = false : bool
- isperfect(19);
val it = false : bool
- isperfect(20);
val it = false : bool

2. Bildschirmausgabe:

- use "/home/inf1057/isqrt.ml";
[opening /home/inf1057/isqrt.ml]
val isqrt = fn : int -> int
val it = () : unit
- isqrt(4534);
val it = 67 : int
- isqrt(73546);
val it = 271 : int
- isqrt(494345);
val it = 703 : int

3. Die Folge der Fibonacci-Zahlen wird durch folgende Gleichungen definiert:

fibonacci(0) := fibonacci(1) := 1  (1)
fibonacci(n) := fibonacci(n − 2) + fibonacci(n − 1) (2)

Bildschirmausgabe:

- use "/home/inf1057/fibonacci.ml";
[opening /home/inf1057/fibonacci.ml]
val fibonacci = fn : int -> int
val it = () : unit
- fibonacci(30);
val it = 1346269 : int

Es ist nicht sinnvoll für große n die n-te Fibonaccizahl mit fibonacci(n) zu berechnen, denn durch den rekursiven Aufbau von fibonacci steigt die Berechnungsdauer mit wachsendem n stark an.

4. Bildschirmausgabe

- use "/home/inf1057/reverse.ml";
[opening /home/inf1057/reverse.ml]
val epsilon = "" : string
val ist_leer = fn : string -> bool
val kopf = fn : string -> string
val rest = fn : string -> string
val reverse = fn : string -> string
val it = () : unit
- reverse("Quarktasche");
val it = "ehcsatkrauQ" : string
- reverse("abbbaaaaba");
val it = "abaaaabbba" : string
- reverse("reliefpfeiler");
val it = "reliefpfeiler" : string

Mit der folgenden Rechenvorschrift is palindrom kann man testen, ob eine Zeichenreihe ein Palindrom ist:

fun is_palindrom(wort:string):bool=
    wort=reverse(wort);

Beispiele fuer Palindromüberprüfung:

- is_palindrom("abba");
val it = true : bool
- is_palindrom("asNUBJny");
val it = false : bool
- is_palindrom("reliefpfeiler");
val it = true : bool

H13 (Termersetzungssystem)

Sei A := {a, b} ein Alphabet. Für alle x, y ∈ A, v, w ∈ A^{∗} sei die Funktion ist gleich : A^{∗} × A^{∗} ⟶ 𝔹 sei induktiv definiert durch:

ist gleich(ε, ε) := tt,  (1)
ist gleich(ε, x&w) := ff,  (2)
ist gleich(x&v, ε) := ff,  (3)
ist gleich(x&v, y&w) := (x = y) ∧ ist gleich(v, w)  (4)

1. Behauptung: Für alle v, w ∈ A^{∗} gilt:

ist gleich(v, w) = tt ⇔ (v = w)

Beweis durch strukturelle Induktion: Seien v, w ∈ A^{∗} und x ∈ A. Induktionsanfang: v = ε: Fallunterscheidung:

(a) w = ε: Dann gilt: ist gleich(v, w) = tt nach Definition, und es ist v = w.

(b) w ≠ ε: Dann gilt: ist gleich(v, x&w) = ff nach Definition, und es ist v ≠ x&w.

Induktionsschritt: v ≠ ε: Fallunterscheidung:

(a) w = ε: Dann gilt: ist gleich(x&v, w) = ff nach Definition, und es ist x&v ≠ w.

(b) w ≠ ε: Dann existieren ein y ∈ A, u ∈ A^{∗} mit w = y&u, und es gilt: ist gleich(x&v, w&u) = (x = y) ∧ ist gleich(v, u). Fallunterscheidung:

i. x = y: Dann gilt: ist gleich(x&v, y&u) = ist gleich(v, u) und:

ist gleich(v, u) = tt
⇔ v = u
⇔ x&v = y&u  da x = y

ii. x ≠ y: Dann ist: ist gleich(x&v, y&u) = ff und x&v ≠ y&u, da x ≠ y.

2. Sei für alle v, w ∈ A^{∗} v ≃ w :⟺ ist gleich(v, w) = tt.

Behauptung: ≃ ist Äquivalenzrelation. Beweis: zu zeigen: Reflexivität, Symmetrie, Transitivität

(a) Reflexivität: Sei v ∈ A^{∗}. Dann ist ist gleich(v, v) = tt, da v = v ist.

(b) Symmetrie: Seien v, w ∈ A^{∗}, und es gelte v ≃ w. v ≃ w ⇔ ist gleich(v, w) = tt ⇔ v = w ⇔ w = v ⇔ ist gleich(w, v) = tt ⇔ w ≃ v.

(c) Transitivität: Seien u, v, w ∈ A^{∗}, und es gelte u ≃ v ∧ v ≃ w. Es gilt u ≃ v ⇔ u = v und v ≃ w ⇔ v = w. Also gilt u = w, also auch u ≃ w.

Jedes Element von A^{∗} bildet seine eigene Äquivalenzklasse, da für je zwei Wörter v, w ∈ A^{∗} mit v ≠ w gilt: ist gleich(v, w) = ff und damit v ≄ w.

3. Behauptung: Die Wörter aaba und aabb aus A^{∗} liegen in verschiedenen Äquivalenzklassen. Beweis:

ist gleich(aaba, aabb) =^{(4)} (a = a) ∧ ist gleich(aba, abb)
=^{(4)} (a = a) ∧ (a = a) ∧ ist gleich(ba, bb)
=^{(4)} (a = a) ∧ (b = a) ∧ ist gleich(a, b)
= ff  da b ≠ a

4. Gegeben seien die Signatur

Σ := ({string, char, bool}, {a, b : char, empty : string, true, false : bool},
{ist gleich : string, string → bool, isEq : char, char → bool,
and : bool, bool → bool, pre : char, string → string}),

die Variablenmenge

X := {x, y : char, v, w : string, c : bool}

und die Regelmenge

ℜ := \{ \begin{matrix}(1) & and(false, c) → false \\ (2) & and(true, c) → c \\ (3) & isEq(x, x) → true \\ (4) & isEq(a, b) → false \\ (5) & isEq(b, a) → false \\ (6) & ist gleich(empty, empty) → true \\ (7) & ist gleich(empty, pre(x, w)) → false \\ (8) & ist gleich(pre(x, v), empty) → false \\ (9) & ist gleich(pre(x, v), pre(y, w)) → and(isEq(x, y), ist gleich(v, w)) \end{matrix} \} .

Dann läßt sich mit dem Termersetzungssystem T := (Σ, X, ℜ) die Funktion ist gleich berechnen, und für die Aussage aus Teil 3 ergibt sich folgendes:

ist gleich(pre(a, pre(a, pre(b, pre(a, empty)))), pre(a, pre(a, pre(b, pre(b, empty)))))

⇒^{(9)} and(isEq(a, a), ist gleich(pre(a, pre(b, pre(a, empty))), pre(a, pre(b, pre(b, empty)))))
⇒^{(3)} and(true, ist gleich(pre(a, pre(b, pre(a, empty))), pre(a, pre(b, pre(b, empty)))))
⇒^{(2)} ist gleich(pre(a, pre(b, pre(a, empty))), pre(a, pre(b, pre(b, empty))))
⇒^{(9)} and(isEq(a, a), ist gleich(pre(b, pre(a, empty)), pre(b, pre(b, empty))))
⇒^{(3)} and(true, ist gleich(pre(b, pre(a, empty)), pre(b, pre(b, empty))))
⇒^{(2)} ist gleich(pre(b, pre(a, empty)), pre(b, pre(b, empty)))
⇒^{(9)} and(isEq(b, a), ist gleich(pre(a, empty), pre(b, empty)))
⇒^{(5)} and(false, ist gleich(pre(a, empty), pre(b, empty)))
⇒^{(1)} false

H14 (Einfache ML-Rechenvorschriften

1. Die Rechenvorschriften nand und nor können wie folgt implementiert werden:

fun nand(a,b:bool):bool=
    not(a andalso b);
fun nor(a,b:bool):bool=
    not(a orelse b);

2. Die ML-Rechenvorschriften und, oder, nicht, pfeil und doppelpfeil, die die logischen Operatoren ∧, ∨, ¬, →, ↔ auf der Menge 𝔹 implementieren, können unter Verwendung der Rechenvorschriften nand und nor wie folgt definiert werden:

use "nandnor.ml";
fun und(a,b:bool):bool=
    nand(nand(a,b),nand(a,b));
fun oder(a,b:bool):bool=
    nand(nor(a,b),nor(a,b));
fun nicht(a:bool):bool=
    nand(a,a);
fun pfeil(a,b:bool):bool=
    nand(a,nand(b,b));
fun doppelpfeil(a,b:bool):bool=
    nand(nor(nand(nand(a,b),nand(a,b)),
             nand(nand(nand(a,a),nand(b,b)),nand(nand(a,a),nand(b,b)))),
         nor(nand(nand(a,b),nand(a,b)),
             nand(nand(nand(a,a),nand(b,b)),nand(nand(a,a),nand(b,b)))));

3. Um den Wert der Aussage

((E_{L} ∨ S_{W}) ∧ (¬S_{W} → ¬E_{L})) → S_{W} (∗)

in Abhängigkeit von den booleschen Werten E_{L} (“Erwin lügt”) und S_{W} (“Susanne sagt die Wahrheit”) mit Hilfe der Rechenvorschriften aus Teil 2 zu bestimmen, dient folgende Rechenvorschrift:

use "logik.ml";
fun aussage(el,sw:bool):bool=
    pfeil(und(oder(el,sw),pfeil(nicht(sw),nicht(el))),sw);

Mit Hilfe der unten definierten Rechenvorschrift wird überprüft, ob die Aussage (*) zutrifft. Dies geschieht, indem der Wahrheitsgehalt der Aussage für jede Kombination von Werten für E_{L} und S_{W} bestimmt wird und die vier Ergebnisse und-verknüpft werden.

fun test_aussage():bool=
    und(und(und(aussage(true,true),aussage(false,true)),
    aussage(true,false)),aussage(false,false));

Die Überprüfung liefert das Ergebnis, daß die Aussage (*) zutrifft.

4. Die folgende ML-Rechenvorschrift automat.ml gibt Menge und Art des Wechselgeldes aus:

fun groschen(betrag:int):int=
    if betrag<10 then 0
    else 1+groschen(betrag-10);
fun fuffzig(betrag:int):int=
    if betrag<50 then 0
    else 1+fuffzig(betrag-50);
fun maak(betrag:int):int=
    if betrag<100 then 0
    else 1+maak(betrag-100);
fun zweemaak(betrag:int):int=
    if betrag<200 then 0
    else 1+zweemaak(betrag-200);
fun heiermann(betrag:int):int=
    betrag div 500;
fun groschentext(betrag:int):string=
    makestring(groschen(betrag))^" Groschen.";

fun fuffzigtext(betrag:int):string=
    makestring(fuffzig(betrag))^"*50Pf und "^groschentext(betrag mod 50);
fun maaktext(betrag:int):string=
    makestring(maak(betrag))^"*1DM, "^fuffzigtext(betrag mod 100);
fun zweemaaktext(betrag:int):string=
    makestring(zweemaak(betrag))^"*2DM, "^maaktext(betrag mod 200);
fun heiermanntext(betrag:int):string=
    "Es kommt raus: "^makestring(heiermann(betrag))^"*5DM, "
      ^zweemaaktext(betrag mod 500);
fun zurueck(betrag:int):string=
    heiermanntext(betrag);

Bildschirmausgabe beim Aufruf von zurueck mit dem Betrag 13,80 DM (entspricht betrag=1380):

- zurueck(1380);
val it = "Es kommt raus: 2*5DM, 1*2DM, 1*1DM, 1*50Pf und 3 Groschen."
 : string

H15 (Test auf Teilbarkeit)

Sei A ein Alphabet. Die Funktion ist teilwort : A^{∗} × kA^{∗} ⟶ 𝔹 ist definiert durch:

ist teilwort(v, w) = tt :⇔ ∃u_{1}, u_{2} ∈ A^{∗} : u_{1}vu_{2} = w.

1. Seien x, y, z ∈ A, v, w ∈ A^{∗}. Eine induktive Definition für ist teilwort lautet:

(1) ist teilwort(ε, w) := tt (ε ist Teilwort von jedem Wort)
(2) ist teilwort(x&v, ε) := ff (außer ε (siehe 1) ist kein Wort Teilwort von ε)
(3) ist teilwort(x&v, y&ε) := (x&v = y&ε)
(4) ist teilwort(x&v, y&w&z) := ist teilwort(x&v, w&z) ∨ ist teilwort(x&v, y&w)

Mit (3) wird der Fall abgefangen, daß das zweite Argument aus einem Zeichen besteht. Dies wird benötigt, da in (4) das zweite Argument aus mindestens zwei Zeichen bestehen muß. Denn x&v ist Teilwort von y&w&z, wenn es Teilwort von y&w oder von w&z ist. Die Alternative zu (3) und (4) ist die Verwendung von zwei Fällen ist teilwort(x&v, y&w) := ist teilwort(x&v, w) und ist teilwort(x&v, w&y) := ist teilwort(x&v, w), wobei nicht klar ist, welchen Fall man zu betrachten hat.

2. Ein Implementierung der Funktion ist teilwort als ML-Rechenvorschrift lautet:

fun ist_teilwort(v,w:string)=
  v="" orelse v=w orelse w<>""
  andalso (ist_teilwort(v,substring(w,1,size(w)-1))
           orelse ist_teilwort(v,substring(w,0,size(w)-1)));

H16 (ML-Rechenvorschriften)

1. Die Berechnung der Anzahl der Jahre, die die Kugeln des Weihnachtsmannes ausreichen führt letztendlich auf die Berechnung des Binomialkoeffizienten zurück. Es gibt \binom{24}{11} Möglichkeiten. Eine ML-

Rechenvorschrift, die \binom{n}{k} berechnet, lautet folgendermaßen:

fun binomi(n,k:int):int=
    if (k=n) orelse (k=0) then 1
    else if (k>n) then 0
    else binomi(n-1,k-1)+binomi(n-1,k);

Die Ausgabe lautet:

- binomi(24,11);
val it = 2496144 : int

Die Kugeln reichen also für die nächsten 2496144 Jahre.

2. Bildschirmausgabe:

fun ist_praefix(v,w:string):bool=
    if v="" then true
    else if w="" then false
    else (substring(v,0,1)=substring(w,0,1))
      andalso ist_praefix(substring(v,1,size v -1), substring(w,1,size w-1));
- ist_praefix("info","informatik");
val it = true : bool
- ist_praefix("form","informatik");
val it = false : bool
- ist_praefix("birne","apfelschorle");
val it = false : bool
- ist_praefix("Urin","Urinstinkt");
val it = true : bool
- ist_praefix("Methoxydimethylmethamphetamin","Desoxyribonukleinsäure");
val it = false : bool

3. Die Funktionen linkswort und ist teilwort können wie folgt definiert werden:

fun linkswort(v,w:string):string=
    if ist_praefix(v,w) then ""
    else substring(w,0,1)^linkswort(v, substring(w,1,size w -1));
fun ist_teilwort(v,w:string)=
  v="" orelse v=w orelse w<>""
  andalso (ist_teilwort(v,substring(w,1,size(w)-1))
           orelse ist_teilwort(v,substring(w,0,size(w)-1)));

Bildschirmausgabe beim Programmlauf mit den gegebenen Parametern:

- linkswort("aaba","aabbbaabaaabaa");
val it = "aabbb" : string
- linkswort("aaba","aabbbabaaabba");
! Uncaught exception:
! Substring
- linkswort("tasche","Quarktasche");
val it = "Quark" : string
- ist_teilwort("aaba","aabbaabaaab");
val it = true : bool
- ist_teilwort("aaba","aabbabaabba");
val it = false : bool
- ist_teilwort("tasche","Quarktasche");
val it = true : bool

H17 (Termersetzungssemantik)

Sei mult : ℕ × ℕ → ℕ definiert durch:

mult(x, y); = \{ \begin{matrix}0 & : & x = 0 \\ y + mult(x − 1, y) & : & x > 0 \end{matrix}

1. Behauptung: Für alle x, y, z ∈ ℕ gilt: mult(x+y, z) = mult(x, z)+ mult(y, z). Beweis: Durch vollständige Induktion über x. Seien y, z ∈ ℕ. Induktionsanfang: Setze x = 0: Dann gilt:

mult(x+y, z) = mult(y, z) = 0+mult(y, z) =^{Def.} mult(x, z)+mult(y, z)

Induktionsschritt: Sei x ∈ ℕ. Es gilt:

mult(x + 1 + y, z) =^{Def.} z + mult(x + y, z)
=^{IV} z + mult(x, z) + mult(y, z)
=^{Def.} mult(x + 1, z) + mult(y, z)

q.e.d.

2. Wir betrachten die Rechenvorschriften

fun dup(x : int) : int = 2*x;
fun mult(x, y : int) : int =
    if x = 0 then 0
           else if x mod 2 = 0 then mult(x div 2, dup(y))
                              else y+mult((x-1) div 2, dup(y));

Behauptung: Für alle y, k ∈ ℕ benötigt die Auswertung von mult(x,y) mit x = 2^{k} genau k + 2 Aufrufe von mult und k + 1 Aufrufe von dup. Beweis: Durch vollständige Induktion. Sei y ∈ ℕ. Induktionsanfang: Setze k = 0. Dann ist x := 2^{k} = 1 und es gilt:

mult(x, y)

=

             if 1=0 then 0
             else if 1 mod 2 = 0 then mult(1 div 2, dup(y))
                  else y+mult((1-1) div 2, dup(y))

          = y+mult(0, dup(y))

=

             y+(if 0=0 then 0
                else if 0 mod 2 = 0 then mult(0 div 2, dup(dup(y)))
                     else dup(y)+mult((0-1) div 2, dup(dup(y))))

          = y+0
          = y

Es werden also k + 2 Aufrufe von mult und k + 1 Aufrufe von dup benötigt. Induktionsschritt: Sei k ∈ ℕ und x := 2^{k}. Damit ist 2x = 2^{k+1}. Dann gilt:

mult(2 ∗ x, y)

=

                if 2*x=0 then 0
                else if 2*x mod 2 = 0 then mult(2*x div 2, dup(y))
                    else y+mult((2*x-1) div 2, dup(y))

             = mult(x, dup(y))

Die Auswertung von mult(2*x, y) benötigt jeweils einen Aufruf mehr von mult und dup als die Auswertung von mult(x, y), also k + 3 Aufrufe von mult und k + 2 Aufrufe von dup. q.e.d.

3. Als Termfolge für die Auswertung von mult(8, 3) ergibt sich bei callby-value:

                   d_{0} : mult(8, 3)
                   d_{1} : mult(4, 6)
                   d_{2} : mult(2, 12)
                   d_{3} : mult(1, 24)
                   d_{4} : 24+mult(0, 48)
                   d_{5} : 24+0

d_{6} : 24

und bei call-by-name:

                   d_{0} : mult(8, 3)
                   d_{1} : mult(4, 6)
                   d_{2} : mult(2, 12)
                   d_{3} : mult(1, 24)
                   d_{4} : 24+mult(0, 48)
                   d_{5} : 24+0

d_{6} : 24

Da mult linear-rekursiv ist, tritt bei jedem Rekursionsschritt nur ein Aufruf von mult auf. Deshalb sind call-by-value und call-by-name Parameterübergabe gleich, und es werden auch bei call-by-name Parameterübergabe k+2 Aufrufe von mult und k+1 Aufrufe von dup benötigt, um mult(x,y) mit x = 2^{k} auszuwerten.

H18 (Subtraktion eines Präfixes)

Sei A ein Alphabet. Die partielle Funktion minus präfix : A^{∗} × A^{∗} → A^{∗} ist induktiv definiert durch:

minus präfix(ε, w) = w
minus präfix(x&v, x&w) = minus präfix(v, w)
ist präfix(v, w) = ff ⇒ minus präfix(v, w) undefiniert.

Dabei sind v, w ∈ A^{∗} und x ∈ A.

1. Behauptung: Für alle v, w ∈ A^{∗} gilt:

ist präfix(v, w) = tt ⟹ conc(v, minus präfix(v, w)) = w,

wobei conc wie im Beispiel 3.1.4 der Vorlesung definiert ist. Beweis: Durch strukturelle Induktion über v. Sei w ∈ A^{∗} und x ∈ A. Induktionsanfang: Setze v = ε. Dann ist ist präfix(v, w) = tt und conc(v, minus präfix(v, w)) = conc(v, w) = w. Induktionsschritt: Sei v ∈ A^{∗}. Dann ist ist präfix(x&v, x&w) = ist präfix(v, w). Fall 1: ist präfix(v, w) = tt: Dann gilt nach Induktionsvoraussetzung conc(v, minus präfix(v, w)) = w. Also

conc(x&v, minus präfix(x&v, x&w)) =^{Def.} conc(x&v, minus präfix(v, w))
= x&conc(v, minus präfix(v, w))
= x&w

Fall 2: ist präfix(v, w) = ff: Dann ist minus präfix(x&v, x&w) = minus präfix(v, w) undefiniert. q.e.d.

2. Die Funktion minus präfix läßt sich folgendermaßen als ML-Rechenvorschrift implementieren:

fun minus_praefix(v,w : string) : string =
 if ist_praefix(v,w) then
  if v="" then w
   else minus_praefix(substring(v,1,size(v)-1),substring(w,1,size(w)-1));

minus_praefix ist repetitiv-rekursiv, da in jedem Zweig höchstens ein Aufruf von minus_praefix vorkommt, und dieser nicht als Argument einer anderen Operation dient.

H19 (ML-Rechenvorschriften)

1. Eine ML-Rechenvorschrift, die überprüft, ob eine Textersetzungsregel l → r auf das Wort w anwendbar ist, läßt sich wie folgt implementieren:

fun Regel_anwendbar(l, r, w: string): bool=
    ist_teilwort(l, w);

2. Eine Implementierung einer ML-Rechenvorschrift mit den Eigenschaften

• Wende die Textersetzungsregel l → r auf das Wort w soweit links wie möglich an und liefere das entstehende Wort.

• Ist die Regel auf das Wort w nicht anwendbar, so gib w zurück.

lautet:

fun Regel_anwenden(l, r, w: string): string=
    if Regel_anwendbar(l, r, w) then
         linkswort(l, w)^r^minus_praefix(linkswort(l,w)^l, w)
    else w;

3. Einige Anwendungen der in 1. und 2. beschriebenen Rechenvorschriften:

- Regel_anwendbar("Haus", "Heim", "Mein Haus, suesses Haus");
val it = true : bool
- Regel_anwenden("Haus", "Heim", "Mein Haus, suesses Haus");
val it = "Mein Heim, suesses Haus" : string
- Regel_anwendbar("Eden", "Paradies", "Die Zahl des Tieres ist 666");
val it = false : bool
- Regel_anwenden("Eden", "Paradies", "Die Zahl des Tieres ist 666");
val it = "Die Zahl des Tieres ist 666" : string
- Regel_anwenden("||", "", "|||||||||");
val it = "|||||||" : string

H20 (Fixpunkt eines Funktionals)

Gegeben sei die folgende ML-Rechenvorschrift:

fun f(x: int): int =
   if x<=0 then 1
           else 2*f(f(x-1));

1. Das Funktional τ_{f} : (ℤ → ℤ) → (ℤ → ℤ) läßt sich wie folgt berechnen:

        τ_{f}[g](n) = [[if x<=0 then 1 else 2*f(f(x-1))]][g](n)

= \{ \begin{matrix}[[1]][g](n) & : [[x<=0]][g](n) = tt \\ [[2*f(f(x-1))]][g](n) & : [[x<=0]][g](n) = ff \\ undef & : [[x<=0]][g](n) = undef \end{matrix}

= \{ \begin{matrix}1 & : n ≤ 0 \\ 2 ∗ [[f(f(x-1))]][g](n) & : n > 0 \end{matrix}
= \{ \begin{matrix}1 & : n ≤ 0 \\ 2 ∗ g(g([[x-1]][g](n))) & : n > 0 \end{matrix}
= \{ \begin{matrix}1 & : n ≤ 0 \\ 2 ∗ g(g(n − 1)) & : n > 0 \end{matrix}

2. Die Fixpunkte von τ_{f} sind:

g : ℤ → ℤ; x → \{ \begin{matrix}1 & : x ≤ 0 \\ undef & : x > 0 \end{matrix}

h : ℤ → ℤ; x → \{ \begin{matrix}1 & : x ≤ 0 \\ 0 & : x = 3m + 1, m ∈ ℕ \\ 2 & : x = 3m + 2, m ∈ ℕ \\ 4 & : x = 3m + 3, m ∈ ℕ \end{matrix}

Bezüglich der Funktionsordnung gilt: g < h, da g für positive Argumente im Gegensatz zu h undefiniert ist. Damit ist g der kleinste Fixpunkt von τ_{f}.

H21 (Semantik einer Rechenvorschrift)

Wir betrachten die Rechenvorschrift

fun S(n: int): int =
if n = 0 then 1
       else S(S(n-1)-1)+1;

1. Das Funktional τ_{S} : (ℤ → ℤ) → (ℤ → ℤ) läßt sich wie folgt berechnen:

   τ_{S}[f](x) = [[if n=0 then 1 else S(S(n-1)-1)+1]][f](x)

= \{ \begin{matrix}[[1]][f](x) & : [[n=0]][f](x) = tt \\ [[S(S(n-1)-1)+1]][f](x) & : [[n=0]][f](x) = ff \\ undef & : [[n=0]][f](x) = undef \end{matrix}

= \{ \begin{matrix}1 & : x = 0 \\ [[S(S(n-1)-1)]][f](x) + 1 & : x ≠ 0 \end{matrix}
= \{ \begin{matrix}1 & : x = 0 \\ f(f(x − 1) − 1) + 1 & : x ≠ 0 \end{matrix}

2. Die Nachfolgerfunktion succ : ℤ → ℤ sei durch

succ(n) = n + 1

erklärt. Behauptung: succ ist ein Fixpunkt von τ_{S}. Beweis: durch Fallunterscheidung: Fall 1: n = 0 τ_{S}[succ](0) = 1 = succ(0) Fall 2: n ≠ 0

τ_{S}[succ](n) = succ(succ(n − 1) − 1) + 1
= succ(n − 1) + 1
= n + 1
= succ(n)

Für alle n ∈ ℤ gilt also τ_{S}[succ](n) = succ(n), damit ist succ Fixpunkt von τ_{S}. succ ist nicht die denotationelle Semantik von τ_{S}, da S für negative Argument nicht terminiert (also undefiniert ist), succ jedoch auf ganz ℤ definiert ist.

3. Behauptung: Die Funktion f : ℤ → ℤ; n → \{ \begin{matrix}n + 1 & : n ≥ 0 \\ undef & : n < 0 \end{matrix} ist

die denotationelle Semantik von τ_{S}. Beweis: zz.: f ist Fixpunkt von τ_{S} Fallunterscheidung: n = 0 : τ_{S}[f](0) = 1 = f(0) n < 0 :

τ_{S}[f](n) = f(f(n − 1) − 1) + 1
= f(undef) + 1
= undef
= f(n)

n > 0 :

τ_{S}[f](n) = f(f(n − 1) − 1) + 1
= f(n − 1) + 1
= n + 1
= f(n)

f ist also Fixpunkt von τ_{S}. zz.: f ist kleinster Fixpunkt Sei g ein weiterer Fixpunkt von τ_{S}. Wir zeigen:

(∗) f(n) ≠ undef ⟹ f(n) = g(n) für alle n ∈ ℤ,

da dieses äquivalent zu f ≤ g ist. Wir unterscheiden 2 Fälle. Sei n < 0. Dann ist f(n) = undef und (∗) gilt. Sei nun n ≥ 0. Dann ist zu zeigen: f(n) = g(n). Dazu führen wir eine Induktion über n durch: Induktionsanfang: n = 0 : g(0) = τ_{S}[g](0) = 1 = f(0) Induktionsschritt: n > 0 : Es gelte f(n) = g(n).

g(n + 1) = τ_{S}[g](n + 1)
= g(g(n) − 1) + 1
= g(f(n) − 1) + 1
= g(n) + 1
= f(n) + 1
= f(n + 1)

Also ist f der kleinste Fixpunkt von τ_{S} und damit dessen denotationelle Semantik.

H22 (Terminierungsbeweis)

Wir betrachten folgende ML-Rechenvorschrift f:

fun f(m: int, n: int): int =
  if (m <= 0 orelse n <= 0) then 1
                           else if odd(m) then f(m+1, n-1)
                                          else f(n, m div 2);

Dabei sei odd eine Operation, die genau dann true liefert, wenn m eine ungerade Zahl ist. Behauptung: f terminiert. Beweis: +, - sind total, div mit zweitem Argument ungleich 0 ist definiert, also sind alle Operationen definiert. Gegeben sei die Terminierungsfunktion

δ : ℤ × ℤ → ℕ; δ(m, n) := \{ \begin{matrix}m + 2n : & m > 0, n > 0 \\ 1 : & sonst \end{matrix}

Seien m, n ∈ ℤ, m > 0. Für m ungerade und n > 1 ist dann δ(m + 1, n − 1) = m + 2n − 1 < m + 2n = δ(m, n), für m ungerade und n = 1 ist δ(m, 0) = 1 < m + 2 = δ(m, 1). Für m gerade und n > 0: δ(n, m div 2) = n + m < m + 2n = δ(m, n). Also terminiert f.

H23 (Pattern Matching von rechts)

Sei A der Zeichenvorrat von ML. Für s, p ∈ A^{∗} sei M_{s,p} := {i ∈ ℕ : s_{i} … s_{i+|p|−1} = p}, wobei die Teilwortbildung auf Zeichenreihen wie in der Vorlesung (Beispiel 5.1.8) definiert ist. Wir betrachten die Funktion

rpm : A^{∗} × A^{+} → ℕ; rpm(s, p) := \{ \begin{matrix}max M_{s,p} : & M_{s,p} ≠ 0 \\ 0 : & sonst, \end{matrix}

die den größten Index i ∈ {1, …, |s|} mit s_{i} … s_{i+|p|−1} = p liefert, falls p eine Teilzeichenreihe von s ist, und sonst 0. Sei rp : A^{∗} × A^{∗} → 𝔹 definiert durch rp(s, p) = tt :⇔ s_{|s|−|p|+1} … s_{|s|} = p. Eine rekursive Definition von rpm lautet:

rpm(s, p) := \{ \begin{matrix}0 : & s = ε \\ |s| − |p| + 1 : & rp(s, t) = tt \\ rpm(lead(s), p) : & rp(s, p) = ff \end{matrix}

Eine Implementierung der Funktionen rpm und rp als ML-Rechenvorschriften lautet:

fun rp(s: string, p: string): bool =
  if size(p)<=size(s) then substring(s, size(s)-size(p), size(p))=p
                      else false;
fun rpm(s: string, p: string): int =
  if s="" then 0
          else if rp(s, p) then size(s)-size(p)+1
                          else rpm(lead(s), p);

Hierbei ist lead eine Rechenvorschrift mit der Semantik von lead.

H24 (Markov-Algorithmen: Regelanwendbarkeit)

1. type Regel=string*string*bool;
fun regel_anwendbar(regel: Regel, wort: string): bool=
Regel_anwendbar(#1(regel), #2(regel), wort);
fun regel_anwenden(regel: Regel, wort: string): string=
if regel_anwendbar(regel, wort) then
  Regel_anwenden(#1(regel), #2(regel), wort)
else
  wort;

2. Nach dem Eleminieren der Aufrufe von Regel anwendbar bzw. Regel anwenden durch Expandieren und Komprimieren ergeben sich

die Rechenvorschriften regel anwendbar2 und regel anwenden2:
fun regel_anwendbar2(regel: Regel, wort: string): bool=
ist_teilwort(#1(regel), wort);
fun regel_anwenden2(regel: Regel, wort: string): string=
let val l= #1(regel);
    val r= #2(regel)
in
  if regel_anwendbar2(regel, wort) then
    linkswort(l, wort)^r^minus_praefix(linkswort(l, wort)^l,wort)
  else
    wort
end;
3. fun regel_anwendbar3(regel: Regel, wort: string): bool=
let val l= #1(regel)
in
  if l="" orelse l=wort then
    true
  else
    if wort="" then
      false
    else

      regel_anwendbar3(regel, substring(wort, 1, size(wort)-1))
       orelse regel_anwendbar3(regel, substring(wort, 0, size(wort)-1))
end;
4. fun eine_regel_anwendbar(rl: Regel list, wort: string): bool=
if null(rl) then
  false
else
  if regel_anwendbar3(hd(rl), wort) then
    true
  else
    eine_regel_anwendbar(tl(rl), wort);

H25 (Fibonacci-Zahlen)

1. (a) Eine ML-Rechenvorschrift, die die Funktion F_{1} : ℕ → ℕ × ℕ, definiert durch F_{1}(n) := (fibonacci(n), fibonaci(n + 1)), implementiert, lautet:

fun F1(n: int): int*int=
if n=0 then
(1, 1)
else if n=1 then
(1, fibonacci(n-1)+fibonacci(n))
else
let val f_n_1=fibonacci(n-1);
    val f_n_2=fibonacci(n-2)
in
  (f_n_2+f_n_1, 2*f_n_1+f_n_2)
end;

(b) Eine ML-Rechenvorschrift, die die Funktion F_{2} : ℕ × ℕ × ℕ → ℕ mit F_{2}(n, a, b) := a ∗ fibonacci(n) + b ∗ fibonacci(n + 1) implementiert, lautet:

fun F2(n, a, b: int): int=
if n=0 then
a+b
else if n=1 then
a+b*(fibonacci(n-1)+fibonacci(n))
else
let val f_n_1=fibonacci(n-1);
    val f_n_2=fibonacci(n-2)
in
  a*(f_n_2+f_n_1)+b*(2*f_n_1+f_n_2)
end;

f_n_1 und f_n_2 dienen dazu, die mehrfache Berechnung derselben Finonacci-Zahl zu vermeiden, denn wegen fibonacci(n) = fibonacci(n − 1) + fibonacci(n − 2) für n > 1 ist fibonacci(n − 1) + fibonacci(n) = 2 ∗ fibonacci(n − 1) + fibonacci(n − 2).

Außer den Regeln aus O31 wurde ausgenutzt, daß ein ML-Programmstück der Form if b1 orelse b2 then t1 else t2 gleichbedeutend ist mit if b1 then t1 else if b2 then t1 else t2 und daß die Bedingung n + 1 = 0 für n ∈ ℕ nie erfüllt ist.

2. Die erste Komponente von F_{1}(n) liefert direkt den Wert von fibonacci(n). Unter Verwendung von F_{2} läßt sich fibonacci als fibonacci(n) = F_{2}(n, 1, 0) berechnen.

H1 (Polynomauswertung)

Die beiden Polynome p_{1}(x) = 5x^{4} + 6x^{3} + 28x^{2} + 9x + 15 und p_{2}(x) = 7x^{4} + 3x^{2} + 5 sollen von einem Modula-2-Programm an der einzugebenen Stelle x ausgewertet werden. Das fogende Programm macht sich bei der Berechnung den einfachen Aufbau der Polynome zunutze: Ist z.B. a := x^{3} schon berechnet worden, kann man bei der Berechnung von x^{4} auf das existierende ”Zwischenergebnis“ a zurückgreifen und braucht nicht x∗x∗x∗x berechnen.

MODULE polynom;
FROM InOut IMPORT WriteString, WriteLn, ReadCard;
VAR x,a,b   : CARDINAL;
BEGIN
  WriteString('Gib x ein: ');
  ReadCard(x);
  (*)
  WriteString('Die Lösung lautet: ');
  WriteCard(a);
  WriteLn;
END polynom.

Für (*) setzen wir ein:

a:=15;
b:=b;
a:=a+9*b;
b:=b*x;
a:=a+28*b;
b:=b*x;
a:=a+5*b;

für p_{1}, sowie

a:=5;
b:=x*x;
a:=a+3*b;
b:=b*b;
a:=a+7*b;

für p_{2}.

Übungen Informatik II  Robert S. Plaul  42

H2 (Was ist das?)

1. Das Programm wasistdas berechnet die Anzahl der Münzen pro Sorte, die ein Münzautomat bei einem gegebenen Betrag auswirft.

2. Für a, b, c, d, e, f, g empfehle ich folgende Ersetzung:

bisher  nachher
a  einwurf
b  fuenfmarkstuecke
c  zweimarkstuecke
d  markstuecke
e  fuenfzigpfennig
f  groschen
g  rest

H4 (Hexadezimaldarstellung)

MODULE Hex;
FROM InOut IMPORT ReadInt, WriteInt, WriteString, WriteLn, WriteHex;
VAR n: INTEGER;
BEGIN
WriteString('Bitte eine Zahl von 0 bis 255 ein.');
WriteLn;
ReadInt(n);
IF (n<0) OR (n>255) THEN
WriteString('Die Zahl ist nicht im Bereich 0-255');
WriteLn;
ELSE
WriteString("0x");
WriteHex(n DIV 16,1);
WriteHex(n MOD 16,1);
WriteLn;
END;
END Hex.

H5 (Programmentwicklung)

1. Ein der Zuweisung y := F_{2}(n, a, b) gleichwertiges WHILE-Programm ist:

(n,a,b):=(n,a,b);
WHILE n#0 DO
  (n,a,b):=(n-1,b,a+b);
END;
y:=a+b;

2. Sequentialisierung der in dem WHILE-Programm aus Teil 1 enthaltenen kollateralen Zuweisungen liefert folgenden Programmteil:

n:=n;
a:=a;
b:=b;
WHILE n#0 DO
  n:=n-1;

hilfe:=a;
a:=b;
b:=hilfe+b;
END;
y:=a+b;

3. Das komplette Programm fibonacci lautet:

MODULE Fibo;
FROM InOut IMPORT ReadCard, WriteCard, WriteString, WriteLn;
VAR a, b, n, hilfe: CARDINAL;
BEGIN
WriteString('Bitte geben Sie einen Wert fuer n ein.');
WriteLn;
ReadCard(n);
a:=1;
b:=0;
WHILE n#0 DO
  n:=n-1;
  hilfe:=a;
  a:=b;
  b:=hilfe+b;
END;
WriteString('Ergebnis: ');
WriteCard(a+b, 1);
WriteLn;
END Fibo.

H7 (Partielle Korrektheit)

Sei π ein while-Programm. Ferner seien ϕ, ψ_{1} und ψ_{2} Formeln. Aus der Definition der partiellen Korrektheit folgt unmittelbar die nachstehende Regel:

{ϕ}π{ψ_{1}}, {ϕ}π{ψ_{2}} ⟹ {ϕ}π{ψ_{1} ∧ ψ_{2}}

Behauptung: Das Programm x:=7 ist nicht partiell korrekt bezüglich der Vorbedingung TRUE und der Nachbdingung x:=8. Beweis: Sei π =x:=7, ϕ =TRUE, ψ_{1} =x=8 und ψ_{2} =x=7. Also nach gilt obiger Regel:

    {TRUE}x:=7{x=8}, {TRUE}x:=7{x=7} ⟹ {TRUE}x:=7{x=8 ∧ x=7}

Da x=8∧x=7 nicht gelten kann, folgt, daß die rechte Seite der Implikation falsch ist. Also folgt, daß x:=7 nicht partiell korrekt ist bezüglich Vorbedingung TRUE und Nachbedingung x=8, da x:=7 bezüglich der Nachbedingung x=7 offensichtlich korrekt ist und mindestens bezüglich einer der Nachbedingungen nicht partiell korrekt sein muß.

H8 (Bewachte Anweisung)

Sei x eine Programmvariable der Sorte CARDINAL. Bezeichne π das folgende Programmstück:

x:=x-1; IF x=7 THEN x:=x+1 ELSE x:=8 END

1. Sei y eine weitere Programmvariable der Sorte CARDINAL. Wir betrachten die Speicherzustände σ_{1} = (x ↦ 8) und und σ_{2} = (x ↦ 38, y ↦ 5).

Die von ⟨π, σ_{1}⟩ und ⟨π, σ_{2}⟩ erreichbaren Speicherzustände sind:

       ⟨π, σ_{1}⟩ ⇒^{a),f)} ⟨IF x=7 THEN x:=x+1 ELSE x:=8 END, σ_{1}[x ← 7]⟩

⇒^{c)} ⟨x:=x+1, σ_{1}[x ← 7]⟩
⇒^{a)} σ_{1}[x ← 7][x ← 8]
= (x ↦ 8)
= σ_{1}

und

  ⟨π, σ_{2}⟩ ⇒^{a),f)} ⟨IF x=7 THEN x:=x+1 ELSE x:=8 END, σ_{2}[x ← 37]⟩

⇒^{c)} ⟨x:=8, σ_{2}[x ← 37]⟩
⇒^{a)} σ_{2}[x ← 37][x ← 8]
= (x ↦ 8, y ↦ 5)

2. Für den Beweis per Hoare-Kalkül, daß das Programmstück π bezüglich der Vorbedingung x>=1 und der Nachbedingung x=8 partiell korrekt ist, siehe nächste Seite.

Bezüglich Vorbedingung TRUE und Nachbedingung x=8 ist das Programmstück nicht partiell korrekt, das sich die falsche Aussage {x-1>=-1}x:=x-1{x>=0} herleiten läßt:

      \frac{\overline{TRUE → x>=0}\frac{_{\overline{x>=0→x-1>=-1}\overline{\{x-1>=-1\}x:=x-1\{x>=0\}}}}{\{x>=0\}x:=x-1\{x>=0\}}}{\{TRUE\}x:=x-1\{x>=0\}}

H9 (Programmverifikation)

Es seien a und x Programmvariablen der Sorte CARDINAL. Behauptung: Das Programmstück

x := a;
WHILE x >= 2 DO
  x := x - 2
END

ist partiell korrekt bezüglich der Vorbedingung ∃k : a = 2∗k und der Nachbedingung x=0. Beweis: Siehe übernächste Seite.

H12 (Matrixmultiplikation)

1. n×n-Matrizen über ℤ können folgendermaßen mit Modula-2 Feldtypen implementiert werden:

TYPE index=[1..n];
TYPE matrix= ARRAY index,index OF INTEGER;

2. Das Programm lautet:

MODULE mat_mult;
FROM InOut IMPORT WriteInt, WriteCard, WriteString, WriteLn, Write,
                  ReadCard, ReadInt;
CONST n=30;
TYPE index=[1..n];
     matrix=ARRAY index,index OF INTEGER;
VAR A,B,C: matrix;
    dim: CARDINAL;
PROCEDURE WriteMatrix(A: matrix; dim: index);
VAR i,j: index;
BEGIN
  FOR i:=1 TO dim DO
    FOR j:=1 TO dim DO
      WriteInt(A[i,j], 5);
    END;
    WriteLn;
  END
END WriteMatrix;
PROCEDURE read_matrix(VAR A: matrix; dim: index);
VAR i,j: index;
BEGIN
  FOR i:=1 TO dim DO
    FOR j:=1 TO dim DO
      Write('[');
      WriteCard(i, 2); Write(';'); WriteCard(j, 2);
      WriteString(']='); WriteLn;
      ReadInt(A[i,j]);
    END
  END
END read_matrix;

PROCEDURE mult_matrix(A, B: matrix; VAR C: matrix; dim: index);
VAR i,j,k: index;
BEGIN
FOR i:=1 TO dim DO
  FOR j:=1 TO dim DO
    C[i,j]:=0;
    FOR k:=1 TO dim DO
      C[i,j]:=C[i,j]+A[i,k]*B[k,j];
    END
  END
END
END mult_matrix;
BEGIN
WriteString('Bitte Groesse der Matrix eingeben (1-30):'); WriteLn;
ReadCard(dim);
WHILE (dim<1) OR (dim>30) DO
  WriteString('Groesse muss im Bereich 1-30 liegen!'); WriteLn;
  ReadCard(dim);
END
WriteString('Matrix A eingeben:'); WriteLn;
read_matrix(A, dim);
WriteString('Matrix B eingeben:'); WriteLn;
read_matrix(B, dim);
mult_matrix(A, B, C, dim);
WriteString('Das Produkt der Matrizen'); WriteLn;
WriteMatrix(A, dim);
WriteString('und'); WriteLn;
WriteMatrix(B, dim);
WriteString('ist'); WriteLn;
WriteMatrix(C, dim);
WriteLn;
END mat_mult.

3. Mit den geschachtelten FOR-Schleifen in den Prozeduren WriteMatrix und read matrix wird die übergebene Matrix zeilenweise und innerhalb einer Zeile spaltenweise aus- bzw. eingegeben. Die beiden äußeren FOR-Schleifen in der Prozedur mult mat dienen zur zeilenweisen Bearbeitung der Ergebnismatrix C. Die innere Schleife berechnet für jedes i, j (A ∗ B)_{ij}, indem sie zu C[i,j] das Produkt A[i,k]*B[k,j] für k von 1 bis dim addiert, nachdem C[i,j] auf 0 gesetzt wurde.

4. Für die äußere FOR-Schleife in WriteMatrix und read matrix lautet die Invariante: ”∀1 ≤ x ≤ i ∀1 ≤ y ≤ dim : (A)_{xy} ist bearbeitet”. Für die innere FOR-Schleife lautet die Invariante: ”∀1 ≤ x ≤ i ∀1 ≤ y ≤ dim : (A)_{xy} ist bearbeitet ∧ ∀1 ≤ y ≤ j : (A)_{iy} ist bearbeitet”.

Für die beiden äußeren FOR-Schleifen in mult mat gelten die gleichen Invarianten mit ’C’ an Stelle von ’A’. Für die innerste FOR-Schleife ist die Invariante: ”Invariante der mittleren FOR-Schleife ∧ C[i,j]= ∑_{l=1}^{k−1} l”.

H13 (Binomialkoeffizienten)

Aus \{0 ≤ n ≤ 100, 0 ≤ m ≤ n\}π′; res := f[n, m]\{res = \binom{n}{m}\} wird mit der Re-

gel der sequentiellen Komposition \{0 ≤ n ≤ 100, 0 ≤ m ≤ n\}π′\{f[n, m] = \binom{n}{m}\}

und \{f[n, m] = \binom{n}{m}\}res := f[n, m]\{res = \binom{n}{m}\}. Letzteres ist ein Zuweisungs-Axiom. Für die Entwicklung von π′ führen wir eine weiter Programmvariable a vom Typ CARDINAL ein. Als Nachbedingung wählen wir

ψ : ∀0 ≤ x ≤ a ∀ max(0, x−(n−m) ≤ y ≤ min(x, m) : f[x, y] = \binom{x}{y}∧a = n.

Aus ψ folgt f[n, m] = \binom{n}{m}. Der erste Teil von ψ ist die Invariante I der Schleife, der zweite Teil die verneinte Fortsetzungsbedingung der Schleife. I beschreibt, daß bis Zeile a alle benötigten Binomialkoeffizienten berechnet wurden. Die Einschränkungen von y wurden verwendet, da kein Binomialkoeffizient \binom{x}{y} mit y > m benötigt wird und dieser erst ab y = x − (n − m) berechnet werden muß, falls diese größer als Null ist. Mit diesem Ansatz ergibt sich für π′ folgende Form:

a:=0;
f[0,0]:=1;
WHILE a#n DO

π′′;

  a:=a+1;
END

Nun muß π′′ entwickelt werden, so daß die Spezifikation

\{I∧a#n\}π′′\{∀0 ≤ x ≤ a+1 ∀ max(0, x−(n−m) ≤ y ≤ min(x, m) : f[x, y] = \binom{x}{y}\}

erfüllt ist. Dazu setzten wir unter Verwendung einer weiteren Programmvariablen b vom Typ CARDINAL an:

∀0 ≤ x ≤ a ∀ max(0, x − (n − m) ≤ y ≤ min(x, m) : f[x, y] = \binom{x}{y}
∧ ∀ max(0, a + 1 − (n − m) ≤ y ≤ b : f[a + 1, y] = \binom{a + 1}{y}
∧ b ≤ min(a + 1, m)
∧ b = min(a + 1, m)

Die zweite Zeile bedeutet, daß die Binomialkoeffizienten \binom{a+1}{y} bis y = b berechnet sind. Die ersten drei Zeilen bilden die Invariante I’ und aus dem gesamten Ausdruck folgt die Nachbedingung von π′′. Damit ergibt sich π′′ zu:

b:=max(0, a+1-(n-m));
IF b=0 THEN
  f[a+1,0]:=1;
ELSE
  f[a+1,b]:=f[a,b-1]+f[a,b];
END;
WHILE b#min(a+1,m) DO
  IF b+1=a+1 THEN
    f[a+1,b+1]:=1;
  ELSE
    f[a+1,b+1]:=f[a,b]+f[a,b+1];
  END;
  b:=b+1;
END

Die zweiseitige bewachten Anweisungen ergeben sich aus \binom{n}{0} = \binom{n}{n} = 1 für

n ≥ 0 und \binom{n}{m} = \binom{n−1}{m−1} + \binom{n−1}{m} für n > m ≥ 1.

Als Gesamtprogramm haben wir damit:

MODULE binomi;
FROM InOut IMPORT WriteString, WriteCard, WriteLn, ReadCard;
VAR a, b, n, m, b_max, res: CARDINAL;
f: ARRAY [0..100],[0..100] OF CARDINAL;
BEGIN
WriteString('Binomialkoeffizient n \choose m'); WriteLn;
n:=101;
WHILE n>100 DO
WriteString('Bitte geben Sie n ein (0-100)'); WriteLn;
ReadCard(n);
END;
m:=n+1;
WHILE m>n DO
WriteString('Bitte geben Sie m ein (0-'); WriteCard(n, 1);
WriteString(')'); WriteLn;
ReadCard(m);
END;
a:=0;
f[0,0]:=1;
WHILE a#n DO
IF a+1>n-m THEN
  b:=a+1-(n-m);
ELSE
  b:=0;
END;
IF b=0 THEN
  f[a+1,0]:=1;
ELSE
  f[a+1,b]:=f[a,b-1]+f[a,b];
END;
IF a+1>m THEN
  b_max:=m;
ELSE
  b_max:=a+1;
END;
WHILE b#b_max DO
  IF a+1=b+1 THEN
    f[a+1,b+1]:=1;
  ELSE

        f[a+1,b+1]:=f[a,b]+f[a,b+1];
      END;
      b:=b+1;
    END;
    a:=a+1;
  END;
  res:=f[n,m];
  WriteCard(res,1); WriteLn;
END binomi.

Der Ausdruck b:=max(0, a+1-(n-m)) wurde durch das Programmstück

IF a+1>n-m THEN
  b:=a+1-(n-m);
ELSE
  b:=0;
END;

ersetzt, wobei a+1>n-m verwendet wurde, da a+1-(n-m) zu einem Laufzeitfehler führte, falls der Ausdruck negativ wurde. Und an Stelle von WHILE b#min(a+1,m) DO wird das Programmstück

IF a+1>m THEN
  b_max:=m;
ELSE
  b_max:=a+1;
END;
WHILE b#b_max DO

verwendet.

H14 (Modula-2-Programme)

1. denethor{inf2031} mat_mult
Bitte Groesse der Matrix eingeben (1-30):
3
Matrix A eingeben:
[ 1; 1]=
2
[ 1; 2]=
3
[ 1; 3]=
4
[ 2; 1]=
3
[ 2; 2]=
4
[ 2; 3]=
5
[ 3; 1]=
1
[ 3; 2]=
2
[ 3; 3]=
3
Matrix B eingeben:
[ 1; 1]=
6
[ 1; 2]=
7
[ 1; 3]=
8
[ 2; 1]=
7
[ 2; 2]=
6
[ 2; 3]=
5
[ 3; 1]=
6
[ 3; 2]=

7
[ 3; 3]=
8
Das Produkt der Matrizen
    2    3    4
    3    4    5
    1    2    3
und
    6    7    8
    7    6    5
    6    7    8
ist
   57   60   63
   76   80   84
   38   40   42
2. >> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
40
Bitte geben Sie m ein (0-40)
10
847660528
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
40
Bitte geben Sie m ein (0-40)
11
2311801440
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
40
Bitte geben Sie m ein (0-40)
12
1291886184
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)

Bitte geben Sie m ein (0-40)
28
1291886184
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
40
Bitte geben Sie m ein (0-40)
29
2311801440
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
40
Bitte geben Sie m ein (0-40)
30
847660528
>> binomi
Binomialkoeffizient n \choose m
Bitte geben Sie n ein (0-100)
100
Bitte geben Sie m ein (0-100)
50
3355989352

Aus den Ergebnissen kann man eine Bestätigung von \binom{n}{m} = \binom{n}{n−m} für 1 ≤ m < n ablesen.

H15 (Modula-2 Typdefinition)

TYPE Term= RECORD
  arg1, arg2: CASE Zahl: BOOLEAN OF
      TRUE:  z_arg: CARDINAL;
      FALSE: t_arg. POINTER TO Term;
    END;
  op: ('+', '-', '*');
END;

Zahl gibt an, ob es sich bei dem jeweiligen Argument um eine Zahl handelt. Wenn nicht, zeigt das Argument auf einen weiteren Term, so daß sich eine Baumstruktur ergibt.

H16 (Maximumssuche)

Außer den Variablen aus der Aufgabe werden noch verwendet

i,k:  [1..N], j,l:  [1..M], m,res:  CARDINAL.

Wir machen einen Ansatz mit zwei Pseudooperationen M1 und M2, die wie folgt definiert sind:

M1(k, l) := Max_{l≤j≤M}a[i, j]
M2(k, l) := Max_{k≤i≤N}(M1(i, l))

Es ist also res :=