Embed Size (px)
Citation preview
SXXX/UE-DMG(WINF)/1003/200/30
Ubungen DMG
Diskrete Mathematik und Graphentheorie
Wirtschaftsinformatik
Wintersemester
Cenker
Institut fur Statistik und Decision Support SystemsUniversitatsstraße 5/9, 1010 Wien
c©September 2003, CC: UEDMG.
Kompiliert: 2. September 2003
Zur Ubung
Sinn und Zweck dieser Sammlung ist es, den Studierenden begleitend zur Vorlesung eineMoglichkeit zu geben, ihr Wissen aus der Vorlesung zu uberprufen, anzuwenden undzu erweitern.
In dieser Sammlung sind auch Programmierbeispiele enthalten, die in Gruppen vonjeweils 1 bis 5 Studierenden gemeinsam gelost werden sollen. Die Losung wird dannvon diesen in geeigneter Form (Notebook, Code, Folien mit Erklarung, Beispiele etc.)prasentiert, erklart und abgegeben. Mindestens 50 % des Programmieraufwandes sinddie Dokumentation des Quellcodes!
Als Programmiersprachen kommen Java (http://java.sun.com ) oder MatLab/SciLabzur Anwendung; es ist sowohl objektorientiert als auch (relativ) unabhangig von derverwendeten Plattform.Borland bietet auf seiner Homepage http://www.borland.com etwa den JBuilder(Personal Edition) fur Java gegen Registrierung gratis an.SciLab (http://www-rocq.inria.fr/scilab ) ist ein PD MatLab–Klon (interakti-ves Lineare Algebra und Mathematik System, Syntax C++/Fortran/Mathematik, guteGrafik).Octave (http://www.octave.org ) ist ein weiterer PD MatLab–Klon, mit mehr Kom-patibilitat als SciLab jedoch einer etwas
”komplizierten“ Grafik (gnuPlot). Einige Bei-
spiele konnen mit MS Excel gerechnet werden (siehe Anmerkungen). Um mit endlichenAutomaten und Turing Maschinen zu arbeiten, kann auch KaraToJava(http://www.educeth.ch/informatik/karatojava ) der ETH-Zurich verwendetwerden (PD). Ausgewahlte Programme werden in der Ubung prasentiert, bzw. Beispielekonnen auch ins Internet gestellt werden.
Ubungsmodus: Der genaue Modus wird in der Vorbesprechung festgelegt. Bei der Prasenta-tion der Beispiele werden Sie au Grund von Vortrag, Richtigkeit der Ausfuhrung, Ausar-beitung und Beantwortung von Zwischenfragen bewertet. Die Ausarbeitung eines Pro-grammes ist Pflicht. Die Programme werden gegen Voranmeldung (auch fur Gruppen)vergeben.
Aktuellste Informationen im Internet: Aktuelle Informationen finden Sie immer auf denHomepages der UbungsleiterInnen. I. A. sollten Links vom PISWI auf diese Homepagesvorhanden sein.
Literatur: Grundsatzlich ist zu bemerken, dass die Wahl, welche Literatur beschafft/gelesenwird, davon abhangt, ob der Stil eines Autors Ihnen liegt oder nicht. Daher sollte vordem Kauf eines Buches dieses in der Institutsbibliothek oder der UB entlehnt, auszugs-weise gelesen oder durchgeschmokert werden!
• Schulbucher als Auffrischung
• Gerd Baron, Peter Kirschenhofer: Einfuhrung in die Mathematik fur Informatiker,Band 1 und 3. Springer Wien, 1989.
• John E. Hopecroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languagesand Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
• Josef Leydold: Mathematik fur OkonomenOldenburg 1998, ISBN 3-486-24524-4
• Richard Bronson: Schaum’s Outline of Matrix Operations. McGraw-Hill, 1988. ISBN0070079781.
• Seymour Lipschutz: Schaum’s Outline of Essential Computer Mathematics. McGraw-Hill, 1982.
Weiters stehen Ihnen die Lehrbuchsammlung der UB und die Fachbibliothek fur Mathe-matik, Statistik und Informatik zur Verfugung, sowie Skripten und OnLine-Lehr- undLernmaterial am Internet.
Inhaltsverzeichnis
1 Vollstandige Induktion 1
2 Komplexe Zahlen z ∈ C 6
3 Relationen und Ordnungen 13
4 Differenzengleichungen 17
5 Halbgruppen und Gruppen 27
6 Graphen 33
7 Endliche Automaten 42
LATEX
iii
1 Vollstandige Induktion
Die vollstandige Induktion in der Mathematik ist eine einfache Beweismethode, diesich aus den Peano-Axiomen fur die naturlichen Zahlen herleitet. Sie besteht aus dreiSchritten:
1. Induktionsbasis (-anfang): Die Aussage A(1) ist wahr (oder A(1) bis A(n − 1)sind wahr).
2. Induktionsvoraussetzung (-annahme): Die Aussage A(n) ist wahr.
3. Induktionsschritt: Zeige, dass aus A(n) auch A(n + 1) folgt, d. h., dass die Aus-sage A(n) fur alle n ∈ N gilt.
1.1 Beweise mittels vollstandiger Induktion!
a)∑n
i=1 i =n(n + 1)
2
b)∑n
i=1 i2 =n(n + 1)(2n + 1)
6
c)∑n
i=1 i3 = (n(n + 1)
2 )2
/
1.2 Beweise folgende Summenformeln mittels vollstandiger Induktion!
a)∑n
i=1(2i − 1) = n2
b)∑n
i=1(2i − 1)2 =n(2n − 1)(2n + 1)
3
c)∑n
i=1(2i)2 =
2n(n + 1)(2n + 1)3
/
Die obigen Summen sind sogenannte arithmetische Reihen k-ter Ordnung, d. h., diek-ten Differenzen aufeinander folgender Reihenglieder sind konstant. Die Summen-formeln konnen auch mit Hilfe eines sogenannten Differenzenschemas gefunden wer-den.
Fur eine arithmetische Reihe erster Ordnung gilt, dass aufeinander folgende Folgen-glieder einen konstanten Abstand d haben, also
n∑
k=1
a + (k − 1)d = a + (a + d) + (a + 2d) + · · · + (a + (n − 1)d) = na +n(n − 1)
2d
1
Fur eine arithmetische Reihe k-ter Ordnung lasst sich folgendes Differenzenschemaaufschreiben:
a1 a2 a3 a4 a5 · · ·∆1
1 ∆12 ∆1
3 ∆14 · · ·
∆21 ∆2
2 ∆23 · · ·
∆31 ∆3
2 · · ·. . . . . .
wobei∆1
j = aj+1 − aj und ∆kj = ∆k−1
j+1 − ∆k−1j .
Liegt eine arithmetische Reihe der Ordnung k vor, so ist ∆kj konstant fur alle j, d. h.,
∆k+1j = 0, fur alle j. Die Summe dieser Reihe ist dann
Sn =
(
n
1
)
a1 +
(
n
2
)
∆11 +
(
n
3
)
∆21 + · · · +
(
n
k + 1
)
∆k1 .
Beispiel:∑n
i=1 k5
1 32 243 1024 3125 7776 16807 32768 · · ·31 211 781 2101 4651 9031 15961 · · ·
180 570 1320 2550 4380 6930 · · ·390 750 1230 1830 2550 · · ·
360 480 600 720 · · ·120 120 120 · · ·
0 0 · · ·
D.h., die Summenformel lautet
n∑
i=1
k5 =
(
n
1
)
1 +
(
n
2
)
31 +
(
n
3
)
180 +
(
n
4
)
390 +
(
n
5
)
360 +
(
n
6
)
120
1.3 Finde und vereinfache die Summenformeln fur folgende Summen mit Hilfe eines Dif-ferenzenschemas!
a)∑n
k=1 k b)∑n
k=1 k2 c)∑n
k=1 k3 d)∑n
k=1 k4
/
2
1.4 Programm: Arithmetische Reihe. Schreibe ein Programm, das nach Angabe der er-sten Folgenglieder oder nach Angabe ihrer Definition uberpruft, ob eine arithmeti-sche Reihe der Ordnung k vorliegt. Es soll sodann die Ordnung der Folge und dieSummenformel ausgeben, bzw., die Summe fur eingegebene n berechnen. Uberprufedas Programm mit den Beispielen 1.1, 1.2 und 1.9, sowie mit folgenden Zahlenfolgen
1 4 9 16 25 36 49 66 88 111
15 21 33 51 75 105 141
1 8 27 64 125 226
16 36 64 100 144
/
1.5 Zeige, dass mit αi > 0, i = 1, . . . , n, fur n > 1 gilt:
(1 + α1)(1 + α2) · · · (1 + αn) > 1 + (α1 + α2 + · · · + αn)
/
1.6 Bernoulli Ungleichung: Zeige, dass fur h > −1 gilt: (1 + h)n ≥ (1 + nh) ∀n ∈ N /
1.7 Geometrische Reihe: Zeige, dass a + aq + aq2 + · · · + aqn = a1 − qn+1
1 − q , fur q 6= 1! /
1.8 Zeige:∑n
k=1k2k = 2 − n + 2
2n . /
1.9 Beweise folgende Summenformeln mittels vollstandiger Induktion!
a) 1 · 2 + 2 · 3 + · · · + (n − 1)n =(n − 1)n(n + 1)
3
b) 1 · 2 · 3 + 2 · 3 · 4 + · · · + (n − 2)(n − 1)n =(n − 2)(n − 1)n(n + 1)
4
c) 11 · 2 + 1
2 · 3 + 13 · 4 + · · · + 1
n(n + 1)= n
n + 1
d) n + (n + 1) + · · · + 2n = 32n(n + 1)
LOSUNG:n → n + 1: (n + 1) + (n + 2) + · · · + (2n + 1) + (2n + 2) = 3
2n(n + 1) − n +
(2n + 1) + (2n + 2).
/
3
1.10 Zeige, dass gilt:
a) 2n > n2 fur n > no
b) 2n > n3 fur n > no
Hinweis: fur n ≥ 10 ist (1 + 1n)3 < 2.
/
1.11 Sei a1 = 1, a2 = 1 und an+1 = an−1 + an, fur n > 2. Zeige, dass fur die so definiertenFibonacci-Zahlen folgende Summenformeln gelten!
a)∑n
i=1 ai = an+2 − 1
b)∑n
i=1 a2i = an · an+1
c)∑n
i=1 a2i−1 = a2n
d)∑n
i=1 a2i = a2n+1 − 1
Bemerkung: Siehe auch die vielen Internet-Seiten zu den Fibonacci-Zahlen! /
BEMERKUNG: Fib(n) = 1√5
(
(1 +√
52 )n − (1 −
√5
2 )n
)
.
1.12 Binomischer Lehrsatz. Zeige, dass∑n
k=0
(
n
k
)
an−kbk = (a + b)n fur alle a, b ∈ R und allen ∈ N.Hinweis: Die Binomialkoeffizienten
(
n
k
)
= n!k!(n − k)!
, n ≥ k ≥ 0, erfullen folgende
Rekurrenzrelation:(
n
k
)
+
(
n
k + 1
)
=
(
n + 1
k + 1
)
.
Zeige und verwende diese! /
1.13 Programm: Pascal’sches Dreieck. Verwende die Rekurrenzrelation(
n
k
)
+
(
n
k + 1
)
=
(
n + 1
k + 1
)
um eine Tabelle zu generieren, die als Eintrage die Binomialkoeffizienten(
n
k
)
enthalt,wobei n der Zeilenindex und k der Spaltenindex ist.Speichere diese Tabelle in einem moglichst effizienten Array. Implementiere ein Inter-face, das nach Eingabe von n und k den Koeffizienten
(
n
k
)
ausgibt, bzw., nach Eingabevon n alle zugehorigen Binomialkoeffizienten! Fange Fehleingaben ab! /
4
1.14 Zeige bzw. widerlege folgende Eigenschaften der Binomialkoeffizienten!
a)∑n
k=0
(
n
k
)
= 2n
b)∑[n
2]+1
k=0
(
n
2k
)
= 2n−1
c)∑[n
2]+1
k=1
(
n
2k−1
)
= 2n−1
d)∑n
k=0(−1)k(
n
k
)
= 0
e)∑n
k=1 k(−1)k+1(
n
k
)
= 0
f)∑n
k=0 k(
n
k
)
= n2n−1
g)∑m
k=0
(
n+k
n
)
=(
n+m+1n+1
)
h)∑r
k=0
(
m
k
)(
n
r−k
)
=(
n+m
r
)
i)∑n
k=01
k + 1
(
n
k
)
= 1n + 12n+1
j)∑B
k=0
(
A
C+k
)(
B
k
)
=(
A+B
C+B
)
, A,B,C ∈ N
k)∑n
k=0
(
A
n−k
)(
B
k
)
=(
A+B
n
)
, A,B ∈ N
l)∑n
k=0
(
m
n−k
)(
m
k
)
=(
2m
n
)
m)∑n
k=0
(
n
k
)2=
(
2n
n
)
n)∑m
k=0
(
n−1+k
k
)
=(
n+m
m
)
o)∑n
k=0
(
n−1+k
k
)
=(
2n
n
)
p)(
n
k
)
= nk
(
n−1k−1
)
q)(−n
k
)
(−x)k =(
n+k−1k
)
xk
/
1.15 Sei M die auf folgende Weise rekursiv definierte Menge:
a ∈ M
x ∈ M ∧ y ∈ M ⇒ xyb ∈ M
a) Gib alle Zeichenketten in M der Lange 7 an.
b) Zeige durch vollstandige Induktion, dass fur jedes w ∈ M gilt:
(Anzahl der Symbole a in w) = (Anzahl der Symbole b in w) + 1
/
5
2 Komplexe Zahlen z ∈ C
Ein Großteil der folgenden Beispiele wird nicht in den Ubungen gerechnet, da diesebereits laut Lehrplan in der Schule gerechnet werden sollten (2.1–2.6, 2.10–2.16, 2.24,2.25). Der Einschub uber Taylorreihen, die Sie spater auch in der Vorlesung kennenlernen werden, dient zur Erlauterung und (hoffentlich) zum Verstandnis der Euler-Formel und einige ihrer Anwendungen.
Exzerpiere aus Schulbuchern, Formelsammlungen etc. die wichtigsten Formeln furdas Rechnen mit komplexen Zahlen (Addition, Subtraktion, Multiplikation, Division,Polardarstellung, Wurzelziehen u.A.). Beachte, dass die komplexe Einheit
√−1 in der
Mathematik mit i bezeichnet wird, wahrend in der Elektrotechnik die Bezeichnung jublich ist!
2.1 Stelle folgende Zahlen in der komplexen Zahlenebene dar!
1 1 + i 6 − 3i 2i − 2 3 − i − i − 1 − i
/
2.2 Addiere z1 + z2 und subtrahiere z2 − z1!
a) z1 = 3 + 2i, z2 = 3 − 2i b) z1 = −1 − i, z2 = 2 − 2ic) z1 = 7i, z2 = 3 − i d) z1 = 4 + 2i, z2 = −i
/
2.3 Bilde das Produkt z1 · z2 mit den Zahlen aus Beispiel 2.2! /
2.4 Bilde die Quotienten z1z2
und z2z1
mit den Zahlen aus Beispiel 2.2! /
2.5 Berechne!
a) i5 + i7 + i2 + i12 + i27
b) i(−i) + (−i)2 + i4 − i5(−i)3
c) (3i − 3)2 + (i + 3i2)3
/
6
2.6 Berechne und vereinfache!
a)i(5 − 2i)2
2 + 5i b) 7 + 2i(7 − 2i)2 c) (1 + i)(3 − 3i)
d) 5 + 2i2 − 5i e)
(1 + 2i)2
3 + i f)(4 − i)2
3 + 2ig) 3 − 2i
(3 + 2i)2 h) 7 − 2i(14 − 4i)3 i) 7 + 3i
7 − 3i
/
Taylorreihen.Um komplizierte, jedoch n-mal stetig differenzierbare Funktionen f(x) durch einfa-chere Funktionen (etwa lineare oder quadratische oder etwa f(x + h) ≈ f(x) + hf ′(x))naherungsweise darzustellen, gibt es in der Mathematik unter anderem das Hilfsmit-tel der Taylorreihen. Eine solche Funktion f(x) kann dann durch eine Taylorreihe fol-gendermaßen dargestellt werden:
f(x) =n
∑
k=0
f (k)(x0)
k!(x − x0)
k + Rn(x)
wobei fur das Restglied Rn(x) gilt, dass
Rn(x) =f (n+1)(x0 + θ(x − x0))
(n + 1)!(x − x0)
n+1 θ ∈ (0, 1)
und
|Rn(x)| ≤ C · |x − x0|n+1
(n + 1)!, falls |f (n)ξ| ≤ C, ξ ∈ [x, x0], ∀n,
sodass Rn(x) umso kleiner ist, je naher x an x0 liegt, und je großer n ist.
Als Punkt x0, an dem die Taylorreihe entwickelt wird, wahlen wir einen, an dem dieAbleitungen f (k)(x0) einfach zu berechnen sind.
Eine Taylorreihe heißt auch MacLaurin-Reihe, falls x0 = 0.
Beispiel: f(x) = 11 − x ⇒ f ′(x) = 1
(1 − x)2
f ′′(x) = 2(1 − x)3
f ′′′(x) = 6(1 − x)4
Daher ist
f(x) = f(x0) + f ′(x0)(x − x0) + 12f ′′(x0)(x − x0)
2 + 16f ′′′(x0)(x − x0)
3 + · · ·= 1 + x + x2 + x3 + x4 + · · ·
bei Entwicklung an der Stelle x0 = 0.
7
Typische Taylorreihen sind:
ex = 1 + x + x2
2!+ x3
3!+ x4
4!+ · · ·
sin x = x − x3
3!+ x5
5!− x7
7!+ · · ·
cos x = 1 − x2
2!+ x4
4!− x6
6!+ · · ·
log(x + 1) = x − x2
2 + x3
3 − x4
4 + · · ·1
1 − x = 1 + x + x2 + x3 + · · ·
Betrachten wir nun die Taylorreihen fur ex, sin x und cos x, so lasst sich daraus folgern,dass fur x = iϕ gilt
eiϕ = cos ϕ + i sin ϕ
was sich durch einen einfachen Koeffizientenvergleich beweisen lasst!
2.7 Leite folgende Identitat her (i ist die komplexe Einheit):
eiϕ = cos ϕ + i sin ϕ
/
2.8 Zeige folgende Identitaten
cos ϕ =eiϕ + e−iϕ
2sin ϕ =
eiϕ − e−iϕ
2i
/
2.9 Taylorreihen: Entwickle folgende Funktionen in eine Taylorreihe um den Nullpunkt !
a) f(x) = 11 − x b) f(x) = (1 + x)α α ∈ R
c) f(x) = log(1 + x) d) f(x) = cosh x
e) f(x) = 11 − x2 f) f(x) = 1
1 + x2
g) f(x) = arctan x
Hinweis: sinh(x) = ex − e−x
2 , cosh(x) = ex + e−x
2 /
8
2.10 Taylorreihen: Berechne die Werte folgender Reihen:
a)∑∞
k=1(−1)k+1 1k
b)∑∞
k=1 e−λ λk
k!
Anleitung: Betrachte die Taylorreihen von log(1 + x) und ex ! /
Polardarstellung. Aus der Formel
eiϕ = cos ϕ + i sin ϕ
erhalten wir eine andere Darstellung fur komplexe Zahlen z = a + ib, die sogenanntePolardarstellung
z = (r, ϕ) = r(cos ϕ + i sin ϕ) .
mit
r =√
a2 + b2 tan ϕ =b
abzw. a = r cos ϕ b = r sin ϕ .
Es gelten folgende Rechenregeln
z1 · z2 = r1r2(cos(ϕ1 + ϕ2) + i sin(ϕ1 + ϕ2))
z1z2
= r1
r2
(cos(ϕ1 − ϕ2) + i sin(ϕ1 − ϕ2))
zn = rn(cos(nϕ) + i sin(nϕ)) (Satz von Moivre)
zk = n√
z = n√
r(cosϕ + k · 2π
n + i sinϕ + k · 2π
n ) k = 0, . . . , n − 1
2.11 Programm: Komplexe Zahlen. Schreibe ein Programm, das komplexe Zahlen in ihreverschiedenen Darstellungen umwandelt. Weiters soll es alle elementaren (binaren)Operationen zwischen zwei komplexen Zahlen durchfuhren konnen, wie auch Wur-zelziehen und Potenzieren. e und π sollen als Konstante in geeigneter Form enthaltensein. Es ist nicht notwendig, einen Parser zu schreiben! /
2.12 Stelle die folgenden komplexen Zahlen in Polarkoordinaten dar!
a) z = 2 − 2i
b) z = −i
c) z = 1 + i
d) z = −1 + i
/
9
2.13 Die Polarkoordinaten von z sind r = 2 und ϕ = 2π3 .
Berechne z in kartesischer Darstellung! /
2.14 Wandle folgende Zahlen in die kartesische Form um!
3(cos ϕ + i sin ϕ) ϕ = 30, 45, 90, 135, 270, 315
/
2.15 Wandle folgende Zahlen in die kartesische Form!
3(cos ϕ + i sin ϕ) ϕ =π
6,π
4,π
2,3π
4,3π
2,7π
4
/
2.16 Wandle die Zahlen aus Beispiel 2.2 in Polarkoordinaten um und fuhre dann die Mul-tiplikationen und Divisionen wie in den Beispielen 2.3 und 2.4 durch und wandle dieErgebnisse wieder in kartesische Koordinaten zuruck! /
2.17 Lose folgende quadratische Gleichungen in C!
a) x2 − 4x + 5 = 0 b) x2 + 4x + 5c) x2 − 6x + 10 d) x2 − 4x + 9e) 2x2 − 4x + 4 = 0 f) x2 − 12x + 45 = 0g) x2 − 4x + 19 = 0 h) 2x2 − 6x + 9 = 0i) x2 − 10x + 41 = 0 j) 25x2 + 10x + 1 = 0k) 9x2 − 24x + 17 = 0 l) 49x2 − 28x + 53 = 0m) x2 + 20x + 109 = 0 n) x2 + 16x + 65 = 0o) 25x2 − 10x + 13 = 0
/
2.18 Finde das algebraische Polynom vom kleinsten Grad, das folgende Losungen besitzt
a) ±i, ±2i b) 3 − i, 2 ± i, 1
/
10
2.19 Programm: Polynome. Schreibe ein Programm, das aus der Angabe von komplexenZahlen das zugehorige Polynom vom kleinsten Grad berechnet und ausgibt, das dieseZahlen als Losungen besitzt.
Teste das Programm unter anderem mit
a) 3 + i, ±i, 2 b) 3, 0, 2 ± 2i c) ±i, 1, 1 ± 2i
/
2.20 Berechne alle Losungen folgender Gleichungen!
a) 9x4 − 37x2 + 4 = 0
b) x4 − 4x2 + 4 = 0
c) x4 + 2x2 − 15 = 0
/
2.21 Programm: Nullstellen. Programmiere einen iterativen Algorithmus (Newton, Bisek-tion etc.), der eine reelle Losung x0 einer Gleichung n-ten Grades (anx
n + an−1xn−1 +
· · ·+a1x+a0 = 0) findet. Dividiere die Gleichung sodann durch den der Losung x0 ent-sprechenden Linearfaktor (Abspalten der Losung) und lose die Gleichung in C! Stellediese sodann graphisch dar!
a) x3 − 4x2 + 6x − 4 = 0 b) x3 + 5x2 + 11x + 7 = 0c) x4 + 8x3 + 21x2 + 20x = 0 d) x3 − 3x2 + 4x − 12 = 0e) x3 − x2 + 17x + 87 = 0 f) 2x3 − 8x2 + 11x − 5 = 0
/
2.22 Berechne folgende Wurzeln in C und zeichne sie in der komplexen Zahlenebene!
3√
1 3√−1
3√
i 3√−i
/
11
Bemerkung.Die Multiplikation mit einer komplexen Zahl z entspricht einer Drehung (|z| = 1) bzw.einer Drehstreckung (|z| > 1) oder Drehstauchung (|z| < 1).Die Multiplikation mit z = (1, ϕ) = cos ϕ + i sin ϕ entspricht einer Drehung um denWinkel ϕ.
Nimm beliebige 2-dimensionale Vektoren
(
xy
)
her, interpretiere sie als komplexe
Zahl x + iy und drehe diese durch Multiplikation mit der entsprechenden Zahl z ∈ C!
Bemerkung: statt mit z = (1, ϕ) = cos ϕ + i sin ϕ zu multiplizieren, kann der Vek-
tor auch mit der Matrix
(
cos ϕ − sin ϕsin ϕ cos ϕ
)
multipliziert werden (Drehung). Das ent-
spricht einer Darstellung einer komplexen Zahl als a+ib.=
(
a −bb a
)
(Drehstreckung).
2.23 Berechne folgende n-te Einheitswurzeln in C und zeichne sie in der komplexen Zahlen-ebene!
3√
14√
15√
16√
1
/
2.24 Berechne alle Losungen der Gleichung z6 = 64 in C! /
2.25 Berechne folgende Wurzeln !
a)√
6 − 8i b)√
7 − 6ic)
√5 − 3i d)
√−3 + 6i
/
2.26 Berechne folgende Wurzeln !
a) 3√
6 − 8i b) 3√
7 − 6ic) 3
√5 − 3i d) 3
√−3 + 6i
/
12
3 Relationen und Ordnungen
3.1 a) Gib die Potenzmengen zu A = a, b und zu B = −, ∗, + an!
b) Wieviele Elemente hat die Potenzmenge von C = a, b, c, d, e, f, g, h, i, j, k, l,m ?
/
3.2 Gegeben seien die Mengen A,B und C
A = a, b, c, d; B = 1, 2, 3, 4; C = (1, 2), (1, 3), (2, 4)
Gib folgende Produktmengen an:
a) A × C b) C × Ac) A × B d) A × A
/
3.3 Sei A das abgeschlossene Intervall [2, 3] ⊆ R, B = 4 und die Menge C das offeneIntervall ]1, 2[⊆ R. Stelle das kartesische Produkt (A∪B) x C in der reellen Zahlenebenegraphisch dar! /
3.4 Sei R = (x, y) ∈ R2|y = x2. Wie sieht die graphische Darstellung von R in der reellenZahlenebene aus? /
3.5 Welche der folgenden geordneten Paare genugen den entsprechenden (binaren) Rela-tionen auf N × N?
a) x ρ y ⇔ x = y + 1; (2, 2), (2, 3), (3, 3), (3, 2)
b) x ρ y ⇔ x teilt y; (2, 4), (2, 5), (2, 6)
c) x ρ y ⇔ x ist ungerade ; (2, 3), (3, 4), (4, 5), (5, 6)
d) x ρ y ⇔ x > y2; (1, 2), (2, 1), (5, 2), (6, 4), (4, 3)
/
13
3.6 Welche der folgenden geordneten Paare genugen den entsprechenden (binaren) Rela-tionen auf S × S?
a) S = Z; x ρ y ⇔ x = −y; (1,−1), (2, 2), (−3, 3), (−4,−4)
b) S = Q; x ρ y ⇔ x ≤ 1/y; (1, 2), (−3,−5), (−4, 1/2), (1/2, 1/3)
/
Eigenschaften von Relationen: Sei ρ eine binare Relation auf der Menge A
• reflexiv: aρa, ∀a ∈ A
• symmetrisch: aρb ⇔ bρa
• transitiv: (aρb ∧ bρc) ⇒ aρc
• antisymmetrisch: (aρb ∧ bρa) ⇔ a = b
Eine reflexive, symmetrische und transitive Relation auf einer Menge heißt Aquiva-lenzrelation, eine reflexive, transitive und antisymmetrische Relation heißt Halbord-nung, eine Halbordnung in der je zwei Elemente immer vergleichbar sind, d.h., ent-weder aρb oder bρa fur zwei Elemente a und b gilt, heißt Totalordnung dieser Menge.
3.7 Welche der folgenden (binaren) Relationen auf der entsprechenden Menge S sind re-flexiv, symmetrisch, antisymmetrisch, transitiv?
a) S = N; x ρ y ⇔ x + y ist gerade
b) S = N; x ρ y ⇔ x teilt y
c) S = N; x ρ y ⇔ x = y2
d) S = 0, 1; x ρ y ⇔ x = y2
e) S = Q; x ρ y ⇔ |x | ≤ | y |
f) S = Z; x ρ y ⇔ x − y ist ein ganzzahliges Vielfaches von 3
g) S = N; x ρ y ⇔ x ist ungerade
/
14
3.8 Finde eine Menge S und eine (binare) Relation ρ auf S, fur die gilt:
a) ρ ist reflexiv und symmetrisch, aber nicht transitiv
b) ρ ist reflexiv und transitiv, aber nicht symmetrisch
c) ρ ist nicht reflexiv und nicht symmetrisch, aber transitiv
d) ρ ist reflexiv, aber weder symmetrisch noch transitiv
/
3.9 Programm: Relationen. Schreibe ein Programm, das als Eingabe eine Relation R aufeiner endlichen Menge A von (alphanumerischen) Zeichen entgegen nimmt, wobeidie Elemente (x, y) ∈ R ⊆ A × A in einer Schleife einzeln eingegeben werden sollen!Das Programm soll sodann die Grundeigenschaften fur Relationen uberprufen, d. h.,es soll ermitteln, ob R reflexiv, symmetrisch, antisymmetrisch bzw. transitiv ist.Beim Vorliegen einer Aquivalenzrelation soll das Programm die Aquivalenzklassenausgeben, beim Vorliegen einer Totalordnung eine Anordnung von A, sodass fur aRb,a, b ∈ A, a stets vor b kommt. /
3.10 Betrachte die Relation”x teilt y“ auf der Menge 1, 2, 3, 6, 12, 18
a) Gib die geordneten Paare (x, y) dieser Relation an!
b) Welche Vorganger hat 6?
c) Welche unmittelbaren Vorganger hat 6?
d) Zeige, dass dies eine Partialordnung definiert!
e) Zeichne einen Graphen, der diese Partialordnung beschreibt!
/
3.11 Zeichne einen Graphen fur die Partialordnung”x teilt y“ auf der Menge
S = 2, 3, 5, 7, 21, 42, 105, 210!Gibt es Teilmengen von S die total geordnet sind? Wenn ja, welche? /
Bemerkung: Die Aquivalenzklassen K(a) = b | aρb der Aquivalenzrelation ρ auf Abilden eine Partition der Menge A.
3.12 Sei M = 1, 2, 3, 4 und P (M) ihre Potenzmenge. Betrachte die folgende Aquivalenz-relation R: (A,B) ∈ R ⇔ |A \ B| = |B \ A|, A,B ∈ P (M). Gib jene Aquivalenzklassebezuglich R an, in der das Element 1, 2 ∈ P (M) liegt! /
15
3.13 Beschreibe fur jede der folgenden Aquivalenzrelationen die entsprechenden Aquiva-lenzklassen!
a) S = N; x ρ y ⇔ x = y
b) S = 1, 2, 3; ρ = (1, 1), (2, 2), (3, 3), (1, 2), (2, 1)
/
3.14 Gegeben ist die Relation R = (1, 1), (2, 3), (3, 2) in A = 1, 2, 3, d. h., R ∈ A × A.Ist R eine Aquivalenzrelation ? /
3.15 Welche der Relationen aus Beispiel 3.7 ist eine Aquivalenzrelation?Beschreibe die dazugehorigen Aquivalenzklassen! /
3.16 Sei S = ab| a, b ∈ Z, b 6= 0 die Menge aller Bruche.
Zwei Bruche heißen genau dann aquivalent (ab∼ c
d), wenn ad = bc gilt.
a) Zeige, dass ∼ eine Aquivalenzrelation ist!
b) Wie sehen die Aquivalenzklassen aus? (z.B. [1/2])
/
3.17 Sei S = Z, x ist kongruent modulo 4 zu y (x ≡4 y), genau dann, wenn x − y einganzzahliges Vielfaches von 4 ist.
a) Zeige, dass ≡4 eine Aquivalenzrelation ist!
b) Wie sehen die Aquivalenzklassen aus?
/
3.18 Gib ein Beispiel einer dreistelligen Relation R ⊆ A1 × A2 × A3, bei der A1 eine Mengevon Namen, A2 eine Menge von Adressen und A3 eine Menge von Telefonnummernist! Stelle diese Relation in einer 3-dimensionalen Skizze perspektivisch dar! /
16
4 Differenzengleichungen
Betrachten wir noch einmal Summen arithmetischer Reihen Sn =∑n
i=1 ai der Ordnungk und das zugehorige Differenzenschema
a1 a2 a3 a4 a5 · · ·∆1
1 ∆12 ∆1
3 ∆14 · · ·
∆21 ∆2
2 ∆23 · · ·
∆31 ∆3
2 · · ·. . . . . .
wobei∆1
j = aj+1 − aj und ∆kj = ∆k−1
j+1 − ∆k−1j .
Liegt eine arithmetische Reihe der Ordnung k vor, so ist ∆kj konstant fur alle j, d. h.,
∆k+1j = 0, fur alle j. Die Summe dieser Reihe ist dann
Sn =
(
n
1
)
a1 +
(
n
2
)
∆11 +
(
n
3
)
∆21 + · · · +
(
n
k + 1
)
∆k1 .
Haben wir nun einen diskreten”Zeitparameter“ t, so definieren wir die k-te Differenz
als∆kyt = ∆(∆k−1yt) mit ∆yt = ∆1yt = yt+1 − yt .
Eine homogene lineare Differenzengleichung erster Ordnung mit konstanten Para-metern, d. h., eine Gleichung der Form
yt+1 + ayt = 0 , a ∈ R fix
hat folgende Losung:
yt = A(−a)t mit A = y0 (Startwert).
Ist a > 0, so ist die Losung oszillierend, ist |a| < 1 so konvergiert die Losung furt → ∞.
Die inhomogene lineare Differenzengleichung erster Ordnung mit konstanten Pa-rametern, d. h., eine Gleichung der Form
yt+1 + ayt = s a, s ∈ R fix
hat folgende Losung:
yt =
A(−a)t + sa + 1 a 6= −1
A + st a = −1
Fur die obigen Losungen ist es wichtig, dass in den Differenzengleichungen nur kon-stante Parameter a und s vorkommen, d. h., diese durfen nicht vom
”Zeitindex“ t
abhangen!
17
4.1 Lose folgende Differenzengleichungen durch Iteration, d. h., durch iteriertes Einset-zen!
a) yt+1 = yt + 1 y0 = 1b) yt+1 = 3yt y0 = 2
/
4.2 Lose folgende Differenzengleichungen und bestimme das Verhalten der Losungen(konvergent, oszillierend etc.)!
a) yt+1 = 2yt + 5 y0 = 1b) yt+1 = −1
4yt + 6 y0 = 2
c) yt+1 = yt + 5 y0 = 1/
4.3 Berechne die allgemeine Losung von ∆yt = yt + 3 und die spezielle Losung, fur diey3 = 2 gilt ! /
4.4 Seien folgende Differenzengleichungen und entsprechende Funktionen gegeben. Zei-ge jeweils, dass die Funktion eine Losung der Differenzengleichung ist (c0 beliebigeKonstante), bzw. berechne die Losung!
a) yt+1 − yt = 0 yt = 5b) yt+1 − yt = 0 yt = c0
c) yt+1 − yt = 1 yt = td) yt+1 − yt = 1 yt = t + c0
e) yt+1 − yt = 1 y0 = 1 bzw. y0 = 3
/
Die Losung einer homogenen linearen Differenzengleichung zweiter Ordnung mitkonstanten Parametern, d. h., einer Gleichung der Form
yt+2 + a1yt+1 + a2yt = 0 , a1, a2 ∈ R fix
erhalten wir durch Ersetzen von yt = Aβt. Wir erhalten dadurch die quadratischeGleichung
β2 + a1β + a2 = 0 mit Losungen β1,2 = −a1
2±
√
a21
4− a2 .
Je nach Vorzeichen der Diskriminantea2
14 − a2 unter der Wurzel ergeben sich folgende
Losungen der Differenzengleichung.
a214 − a2 > 0 β1 6= β2 ∈ R yt = A1β
t1 + A2β
t2
a214 − a2 = 0 β1 = β2 = β ∈ R yt = A1β
t + A2tβt
a214 − a2 < 0 β1,2 = a ± ib ∈ C yt = rt(A1 cos ϕt + A2 sin ϕt)
r =√
a2 + b2 =√
a2
sin ϕ =
√
1 − a21
4a2
cos ϕ = − a21
2√
a2
18
Die Losung der inhomogenen linearen Differenzengleichung zweiter Ordnung mitkonstanten Parametern
yt+2 + a1yt+1 + a2yt = s , a1, a2, s ∈ R fix
ist die Summe aus der Losung der homogenen Losung y(h)t wie oben und der speziel-
len Losung y(s)t , d. h.,
yt = y(h)t + y
(s)t
mit
y(s)t =
sa1 + 2 · t a 6= −2
s2 · t2 a = −2
Die k-ten Differenzen ∆kyt werden durch
∆kyt = ∆(∆k−1yt) mit ∆yt = ∆1yt = yt+1 − yt
definiert. Somit ist
∆2(yt) = ∆(yt+1 − yt) = ∆(yt+1)−∆(yt) = (yt+2 − yt+1)− (yt+1 − yt) = yt+2 − 2yt+1 + yt .
4.5 Berechne die allgemeine Losung von ∆2yt − 5∆yt + 4yt = 1 ! /
4.6 Lose folgende Differenzengleichungen und vergleiche die Schaubilder! Was passiertbei verschiedenen Anfangswerten, was bei verschiedener rechter Seite (Parameter s) ?
a) yt+2 − 3yt+1 + 2yt = 0 y0 = 1, y1 = 0b) yt+2 − 3yt+1 + 2yt = 1 y0 = 1, y1 = 1
/
4.7 Die Rauchgewohnheiten eines Rauchers haben zur Folge, dass seinem Blut eine Ta-gesdosis von 0.02 mg Nikotin zugefuhrt wird. 1 % des Nikotins wird innerhalb von 24Stunden abgebaut.
a) Wie kann der Nikotingehalt im Blut berechnet werden, wenn von einem Start-wert von x0 = 0 mg ausgegangen wird ?
b) Wie verhalt sich der Nikotingehalt im Blut uber langere Zeit ?
c) Wird der gesundheitsschadliche Wert von 1 mg je uberschritten ?
d) Gibt es einen Grenzwert, bei dem sich Nikotinzufuhr und -abbau die Waagehalten ?
e) Zeichne/Programmiere Schaubilder, wo einmal (n, xn) die Koordinaten sind,einmal (xn, xn+1) (Phasenraum)!
f) Wie verhalt sich der Nikotingehalt im Blut, wenn taglich 0.05 mg zugefuhrtwerden ?
/
19
4.8 Lose und zeichne Schaubilder (Phasenbilder (xn, xn+1)) von
a) xn+1 = −0.75xn + 7, x0 = 1
b) xn+1 = −23xn + 16, x0 = 2
c) xn+1 = −xn + 10, x0 = 2.5
Gibt es Fixpunkte in diesen Differenzengleichungen ? /
4.9 Eine Walpopulation wird auf 1120 Individuen geschatzt. Durch Geburten und naturli-che Sterberate ergibt sich ein jahrlicher Zuwachs von 15 %.
Stelle die zugehorige Differenzengleichung auf und lose sie! Zeichne ein Schaubild!Welchen Einfluss hat eine Fangquote von 120 bzw. 200 Tieren jahrlich auf die Gesamt-population ? Warum ? /
4.10 Programm: Attraktor von Nullstellen. Das Newton’sche Naherungsverfahren
xn+1 = xn − f(xn)
f ′(xn)
zum Finden von Nullstellen von algebraischen Gleichungen zeigt fur die Gleichung
x3 − 1 = 0
in der komplexen Zahlenebene ein interessantes Verhalten! Manche Startwerte x0 ∈ C
fuhren zur Losung 1, manche nicht. Zeichne ein Schaubild des Basins fur die Losung1, indem komplexe Startwerte, die zur Losung 1 fuhren, weiß eingezeichnet werden,alle anderen schwarz! Verfahre mit den anderen Nullstellen ebenso! Es ergibt sich einefraktale Struktur!Hinweis: Setze zuerst die Funktion in das Verfahren ein und berechne die Differen-zengleichung! /
4.11 Lose folgende Differenzengleichung! yt+2 − yt = 0 y0 = 1, y1 = 2 /
20
4.12 Programm: Iteriertes Funktionensystem. Betrachte das folgende iterierte Funktionen-system (IFS):
xn+1 = f(xn) = xn + k · xn · (1 − xn) 0 ≤ k ≤ 3, x0 ∈ (0, 1) fest.
a) Zeichne ein so genanntes Feigenbaum-Diagramm fur variables k, in dem diePunkte (Endwerte) (k, pN) in der xy-Bildebene eingezeichnet werden (es ge-nugt oft ein Maximum von N = 250 Iterationen)! Was kann uber die un-gefahren Werte k1 = 2.45, k2 = 2.544 bzw. k3 = 2.57 ausgesagt werden? –Diese Art von Verhalten wird auch oft als deterministisches Chaos bezeichnet(chaotisches Verhalten trotz einer gegebenen mathematischen Gleichung).
b) Zeichne ein Phasenbild desselben IFS, d. h., zeichne (xn, xn+1) fur verschiede-ne Startwerte und verschiedene k in ein Schaubild!
/
4.13 Programm: Henon Attraktor. Der Henon-Attraktor ergibt sich, wenn von einem Start-wert (x0, y0) aus die Punkte (xn, yn) gezeichnet werden, die dem Bildungsgesetz
xn+1 = yn − ax2n + 1
yn+1 = bxn
gehorchen, wobei a und b Konstante sind (etwa a = 1.4, b = 0.3). Schreibe ein Pro-gramm, das verschiedene Startwerte und verschiedene Konstanten zulasst und einSchaubild ausgibt!
Bemerkung: Wird in die Graphik hineingezoomt, sehen wir ein selbstahnliches Ver-halten, d. h., der Henon Attraktor besteht aus vielen kleinen
”Attraktionsmengen“.
/
Lineare Differenzengleichungen hoherer Ordnung
4.14 Lose folgende Differenzengleichungen!
a) yn − 3yn−1 + 2yn−2 = 0
b) 4yn − 4yn−1 + yn−2 = 2
c) yn − 2yn−1 + yn−2 = 3
d) yn − 5yn−1 + 6yn−2 = 0
e) yn − 5yn−1 + 6yn−2 = 2
f) yn − 3yn−1 + 2yn−2 = 1
g) yn + yn−1 − yn−2 − yn−3 = 0
/
21
4.15 Lose folgende Differenzengleichungen!
a) yn − 4yn−1 + 4yn−2 = 0, y0 = 1, y1 = 3
b) yn − 3yn−1 + 2yn−2 = 0, y0 = 2, y1 = 3
c) yn + yn−1 − yn−2 − yn−3 = 0, y0 = 2, y1 = −1, y2 = 3
d) yn + 2yn−1 + 2yn−2 = 0, y0 = 0, y1 = −1 )
/
4.16 Ein Vorrat verringert sich in jeder Periode um 10 %. Er wird am Ende jeder Periodeum den konstanten Betrag 200 erganzt. Der Vorrat hat einen Anfangswert von 1000Einheiten und soll verdoppelt werden. Wie lange dauert es, bis dieses Ziel zu 95 %erreicht ist ?
/
4.17 Lose folgende Differenzengleichungen!Vorsicht: Die Parameter sind hier nicht konstant, sondern veranderlich, d. h., sie hangenvom Index ab. Obige Losungsverfahren konnen dafur nicht angewendet werden!
a) yn − 3yn−1 + 2yn−2 = 4n
b) yn − 3yn−1 + 2yn−2 = 2n
c) yn − 4yn−1 + 4yn−2 = 3 · 2n + 5 · 4n − 1
d) yn − 2yn−1 + yn−2 = 2n − 2(n − 3), y0 = 0, y1 = 1
/
4.18 Programm: Rossler Attraktor. Das linke System von Differentialgleichungen definierteinen Rossler Attraktor, der durch das rechte System von Differenzengleichungen si-muliert werden kann, wobei der
”infinitesimal kleine Schritt“durch entsprechende
Werte der Schrittweite h 1 simuliert wird.
x′ = −y − zy′ = x + ayz′ = b + xz − cz
xn+1 = xn − h(yn + zn)yn+1 = yn + h(xn + ayn)zn+1 = zn + h(b + xnzn − czn)
wobei a, b, c Konstante sind (etwa a = b = 0.2, c = 8), h die Schrittweite ( 1). /
22
4.19 Programm: Schmetterlingseffekt, Lorenz-Attraktor (1993). Eine Wetterprognose istvon vielen Parametern wie der Jahreszeit, der Vegetation, dem Luftdruck, der Wind-richtung und Windgeschwindigkeit, dem Niederschlag, der Temperatur, der Bewolkung,der Feuchtigkeit, usw. abhangig. In den 60er-Jahren versuchte Edward N. Lorenz amMassachusetts Institute of Technology (MIT) meteorologische Prozesse mittels Syste-men von Differentialgleichungen zu beschreiben. Ein Modell fur die Erdatmospharebasierte auf einem Differentialgleichungssystem (links), simuliert durch Differenzen-gleichungen (rechts)
x′ = a · (y − x)y′ = bx − xz − yz′ = xy − cz
xn+1 = xn + h · a · (yn − xn)yn+1 = yn + h(bxn − xzn − yn)zn+1 = zn + h(xnyn − czn)
Als Lorenz eine zuvor getatigte Wetterprognose nachprufen wollte, gab er die Ein-gabeparameter nicht wie zuvor auf 6, sondern auf 3 Dezimalstellen genau an. Intui-tiv wurden die meisten meinen, dass dies das Ergebnis nicht signifikant verandert,da es bei einfachen Rechnungen (vergleiche etwa a = 8.120474, b = 2.134789, c =3.803876636 mit 8.120, 2.134 und 3.805060918, welches eine durchwegs zu vernachlassi-gende Abweichung von 0.001184282 liefert) in den meisten Fallen auch keine Rol-le spielt. Lorenz erzielte jedoch zwei vollig unterschiedliche Ergebnisse und schlossdaraus, dass kleine Veranderungen oder Abweichungen von Parametern zu großenVeranderungen fuhren konnen. Eine kleine Ursache kann eine große Wirkung ha-ben (abhangig von den Anfangsbedingungen). Das Wetter ist ein chaotisches Systemund daher schwer zu prognostizieren. Die genaue Berechenbarkeit der Welt und dielangerfristige Prognostizierbarkeit von Vorgangen haben offensichtlich ihre Grenzen.Ahnlich wie bei den Benard-Zellen kann es in Luftschichten zu Fluktuationen kom-men, die sich verstarken. Diese sind nicht vorhersehbar und daher sind Wetterprogno-sen eine außerst unsichere Angelegenheit. Beim Attraktor des Differentialgleichungs-systems zeigt sich, dass ein sich bewegender Punkt entweder auf dem linken oderdem rechten Teil kreist und dass es spontane Ubergange gibt, die nicht vorhersehbarsind.
Da der Attraktor einem Schmetterling ahnelt, wird der Effekt, dass kleine Ursachengroße Wirkungen haben konnen, auch Schmetterlingseffekt genannt und es haben sichetwas ubertriebene Beschreibungen wie jene, dass der Flugelschlag eines Schmetter-lings in Asien ein Gewitter in Wien auslosen kann, entwickelt. /
4.20 Programm: Mandelbrot und Julia. Apfelmannchen und Julia-Mengen entstehen, wennfur komplexe Zahlen die Vorschrift
zn+1 = z2n + c, zn, c ∈ C
iteriert wird.Sei z = a + ib und c = x + iy so ergibt sich
zn+1 = (a2 − b2 + x) + i(2ab + y).
23
Apfelmannchen (Mandelbrot-Mengen) erhalten wir dadurch, dass wir das Verhaltenbeim variablen Startwert c ∈ C einen Punkt in einer bestimmten Farbe codieren, jenachdem, ob |zn|
– gegen 0 konvergiert,
– gegen ∞ geht,
– zwischen verschiedenen Werten oszilliert,
– keinem bestimmten Muster folgt.
Bei Julia-Mengen hingegen wird z0 variabel und c als konstant angesehen. z0 wirdeingefarbt, wenn |zn| konvergiert. Als Konstante nimm etwa c = i, oder c = −0.4+0.7i,c = −0.7 + 0.3i, c = −1.77 + 0.01i .
Versuche auch die Formel zn+1 = z4n + c, zn, c ∈ C! /
4.21 Programm: Biomorphe. Formen wir die”Mandelbrot-Iteration“ leicht um
zn+1 = sin(z2n) + c, zn, c,∈ C,
so erhalten wir Biomorphe (C. A. Pickover).
Weitere interessante Attraktoren (Galaxien) ergeben sich, wenn wir
zn+1 = u · zn(1 − zn)
iterieren, etwa fur u = −0.7 + 0.8i. /
4.22 Programm: Bevolkerungswachstum.
bn+1 = bn + n(gn − sn), b0 = 1000
Hierbei ist b die Bevolkerung, g die Geburten im Jahr n und s die Sterbefalle im Jahrn, die sich aus den Prozentsatzen der Geburtenziffer gz und der Sterbeziffer sz be-rechnen. Etwa gz = 1 %, sz = 0.85 %. Experimentiere mit verschiedenen Prozent- bzw.Promillesatzen! Lose und zeichne ein Schaubild! /
4.23 Programm: Epidemien. Infektionskrankheiten, Epidemien. Erstellen wir ein einfachesModell fur Masern (ohne Impfungen zu berucksichtigen). Jede Person, die Masernnoch nicht hatte, kann andere innerhalb der Inkubationszeit (eine Woche) anstecken,nach einer weiteren Woche klingt die Krankheit ab und die Person kann weder ange-steckt werden noch anstecken, da sie immun ist. Setzen wir die Zeiteinheit daher aufeine Woche. Sei In die Zahl der Infizierten zum Zeitpunkt n, Sn die Zahl der Suszepti-blen, d. h., jener Personen, die angesteckt werden konnen.
24
Wir nehmen an, dass jede infizierte Person eine festen Prozentsatz p ansteckt, weiters,dass jede Zeiteinheit G Neugeborene zum Pool der Suszeptiblen hinzu kommen.
Unser Modell sieht dann folgendermaßen aus:
In+1 = pSnIn Sn+1 = Sn − pSnIn + G
Schreibe ein Programm, das zulasst, dass alle Parameter geandert werden konnen,und das die Kurven von In und Sn in verschiedenen vergleichenden Diagrammenausgibt! Sei I0 = 20, S0 = 30000, und p = 0.00003. Experimentiere mit verschiedenenGeburtenzahlen (etwa G = 120 oder G = 360) und vergleiche! /
4.24 Programm: Wachstum. Schreibe ein Programm, das folgende Modelle betrachtet:
a) Exponentielles Wachstum: xn+1 = rxn mit Wachstumsrate r (etwa r = 0.1).Stelle die Große der Population xn dem Zuwachs gegenuber!
b) Verhulst-Pearl logistisches Wachstum: xn+1 = xn + rn(1− nk). Stelle die Große
der Population xn dem Zuwachs gegenuber!
c) Lotka-Volterra Modelle (Rauber-Beute Modelle): Eine Population von Raubernrn steht ihrer Beute bn gegenuber. Die Beute-Population hat eine naturlicheWachstumsrate von bw, wahrend eine fixer Prozentsatz bs den Raubern zumOpfer fallt (Tod durch Altersschwache gibt es nicht). Die Rauber ihrerseitshaben eine Zuwachsrate rw, die von der Anzahl der Beutetiere abhangt, undeine Sterberate von rs. Als Rauber-Beute Modell ergibt sich
bn+1 = bn + (bw · bn − bs · bn · rn)rn+1 = rn + (rw · bn · rn − rs · rn)
Schreibe ein Programm, das dieses Modell implementiert und das auch beruck-sichtigt, dass eine Population aussterben kann!
Sinnvolle Startwerte und Parameter konnten sein
a) b0 = 100, r0 = 10, bw = 0.003, bs = 0.0003, rw = 0.00001, rs = 0.0005
b) b0 = 100, r0 = 15, bw = 0.015, bs = 0.000333, rw = 0.0001, rs = 0.001
c) b0 = 10, r0 = 15, bw = 0.005, bs = 0.000333, rw = 0.0001, rs = 0.001
Stelle die beiden Populationen jeweils in einem gemeinsamen Schaubild dar!
/
25
4.25 Programm: Turme von Hanoi. Die Sage berichtet, dass in einem buddhistischen Tem-pel bei Hanoi die Mitglieder eines Monchsordens seit Urzeiten damit beschaftigt seien,eine muhsame, aber fur die Welt als Ganzes sehr wichtige Arbeit zu verrichten: Dortstehen drei Pfosten, auf denen 64 zylindrische Scheiben von jeweils verschiedenemDurchmesser, der Große nach geordnet, liegen. Anfangs liegen alle Scheiben auf demersten Pfosten. Diese sollen auf den dritten Pfosten einzeln umgelegt werden. Dabeikann der zweite Pfosten als Zwischenablage verwendet werden, aber es darf nur im-mer eine kleinere auf einer großeren Scheibe zu liegen kommen.
Wenn diese Arbeit einst vollendet sein wird, ist der Zweck des Weltalls erreicht: DieMenschheit wird vom Zwang der ewigen Wiedergeburt erlost und darf ins Nirvanaeingehen.
Das Problem sieht sehr kompliziert aus, vor allem was die dabei notige Buchhaltungbetrifft. Wir wollen die Monche bei ihrem sehr lobenswerten Werk durch eine Com-putersimulation unterstutzen. Nach langerer Uberlegung zeigt sich, dass es nutzlichist, einige Hilfsbegriffe einzufuhren:
– Ein Turm ist ein Stapel von Scheiben; dabei liegt immer eine kleinere Scheibe aufeiner großeren.
– Die Hohe eines Turmes ist die Anzahl der Scheiben. Sie kann auch 0 sein.
– der Durchmesser eines Turmes sei gleich dem Durchmesser seiner untersten Schei-be – oder 0 fur einen leeren Turm.
– Ein Turm ist entweder leer, oder er besteht aus einer Scheibe und einem daraufstehenden Turm kleineren Durchmessers und um 1 kleinerer Hohe.
Aus dieser rekursiven Beschreibung der Situation konnen wir nun den Ansatz einerrekursiven Losung fur den Transport eines Turmes gewinnen:
– Fur einen leeren Turm ist nichts zu tun.
– Um einen nicht-leeren Turm von einem Pfosten A auf einen Pfosten E zu verla-gern, bringen wir den auf der untersten Scheibe stehenden kleineren Turm (aufdie gleiche Weise) auf den dritten Pfosten Z, legen die verbliebene Scheibe vonA nach Z um, und holen dann den kleineren Turm (auf die gleiche Weise) vomHilfspfosten Z nach E.
Sei A(n) der Aufwand, einen Turm der Hohe n zu bewegen, und c1, c2 irgendwelcheKonstanten. Dann berechnet sich der Aufwand wie folgt:
A(n) = 2A(n − 1) + c1 fur n > 0, A(0) = c2
Lose diese Differenzengleichung ! Wie lange arbeiten die Monche an ihrer Aufgabe,wenn sie fur das Umlegen eines Steines etwa 10 Sekunden benotigen ? /
26
5 Halbgruppen und Gruppen
Gruppeneigenschaften fur (G, ):
(G1) Abgeschlossenheit: a b ∈ G ∀a, b ∈ G
(G2) Assoziativitat: (a b) c = a (b c) ∀a, b, c ∈ G
(G3) Neutrales Element, Einselement: ∃! e ∈ G : a e = e a ∀a ∈ G
(G4) Inverses Element: ∀a ∈ G ∃ a−1 ∈ G : a a−1 = a−1 a = e
(G5) Kommutativitat: a b = b a ∀a, b ∈ G
Gilt fur ein (G, ) (G1), so heißt (G, ) Gruppoid, gilt zusatzlich (G2), so heißt (G, )Halbgruppe, gilt zusatzlich (G3), so heißt (G, ) Monoid, gilt zusatzlich (G4), so heißt(G, ) Gruppe, gilt zusatzlich (G5), so heißt (G, ) abelsche oder kommutative Gruppe.
Die mathematische Struktur der Gruppe ist ein wesentlicher Konstrukt in der Mathe-matik. Weiß man von einem
”Objekt“, dass es eine Gruppe ist, so konnen die verschie-
densten Eigenschaften aus den Gruppeneigenschaften abgeleitet werden. Wir konnensogar einfache und bekannte Beispiele als Modell hernehmen, denn es gilt der
Satz von Cayley: Jede Gruppe ist zu einer Permutationsgruppe isomorph.
Bemerkung: Ein Isomorphismus ϕ : H → G ist ein bijektiver Homomorphismus. IstG = H so heißt ein Isomorphismus Automorphismus.
Ein Homomorphismus ϕ : G → H hat definitionsgemaß folgende Eigenschaft:
ϕ(x) + ϕ(y) = ϕ(x + y) .
Der Kern eines Homomorphismus ϕ : G → H ist Kerϕ = x ∈ G |ϕ(x) = ε ∈ HPermutationen sind bijektive Abbildungen auf einer Menge. Notiert werden die Ele-mente der Einfachheit halber als Zahlen, die der Position der Elemente in einer geord-neten Menge (n-Tupel) entsprechen. Einfache Darstellungen einer Permutation sindentweder Zyklen (etwa (1234)) oder Transpositionen ((1234) = (12)(23)(34)).
Die Symmetrische Gruppe Sn entspricht der Menge aller Permutationen von n Ele-menten, die Altanierende Gruppe An entspricht der Menge aller geraden Permutatio-nen einer Menge von n Elementen. Eine Permutation heißt gerade, wenn sie durcheine gerade Anzahl von Transpositionen dargestellt werden kann.
Untergruppen mussen das neutrale Element ε und zu jedem Element a auch a−1 ent-halten.
27
Beispiel: Sei M = 1, 2, 3, so ist SM die symmetrische Gruppe S3 und besteht ausallen bijektiven Abbildungen auf der Menge M und hat demzufolge 3! = 6 Elemente:
ε =
(
123
123
)
= () p1 =
(
123
132
)
= (23) p2 =
(
123
321
)
= (12)
p3 =
(
123
213
)
= (12) p4 =
(
123
231
)
= (23)(31) p5 =
(
123
312
)
= (12)(23)
Die Gruppentafel istS3 ε p1 p2 p3 p4 p5
ε ε p1 p2 p3 p4 p5
p1 p1 ε p2 p3 p4 p5
p2 p2 p4 ε p5 p1 p3
p3 p3 p5 p4 ε p2 p1
p4 p4 p2 p3 p1 p5 εp5 p5 p3 p1 p2 ε p4
Die Untergruppen dieser Gruppe S3 sind:
ε ε, p1 ε, p2 ε, p3 A3 = ε, p4, p5 S3
2
Es gilt der
Satz von Lagrange: Die Ordnung einer Untergruppe ist stets Teiler der Ordnung derGruppe.
Beispiel: Klein’sche Vierergruppe
V4 = ε, (12)(34), (13)(24), (14)(23) .
Es gilt: ε ⊆ V4 ⊆ A4 ⊆ S4.
Es mag verwundern, dass die Existenz dieser Untergruppen der S4 dafur”verant-
wortlich“ ist, dass eine Gleichung vierten Grades per Formel auflosbar ist. Eine solche
”Faktorisierung“gibt es fur
”hohere“ Gruppen Sn, n > 4, nicht, und daher auch keine
expliziten Losungsformeln fur Gleichungen vom Grad 5 und hoher (Galoistheorie). 2
Beispiel: Weitere”wichtige“ Gruppen in der Mathematik sind die Matizengruppen:
Gl(n) = n × n − MatrizenA | det A 6= 0 General linear groupAB 6= BA, B−1AB 6= A aber B−1AB ∼ A
Sl(n) = n × n − MatrizenA | det A = 1 Special linear groupO(n) = n × n − MatrizenA | 〈Ax,Ay〉 = x, y〉, x, y ∈ Rn Orthogonal groupSO(n) = A ∈ O(n) | det A = 1 Special orthogonal g.
SO(2) Drehmatrizen in R2
U(n) = n × n − MatrizenU | 〈Ux, Uy〉 = 〈x, y〉, x, y ∈ Cn Unitary group
〈x, y〉 = 〈y, x〉 =∑
i xi, yi, xi, yi ∈ C
SU(n) = U ∈ U(n) | detU = 1 Special unitary group
2
28
5.1 Welche der folgenden Strukturen ist Gruppoid, Halbgruppe, Monoid oder Gruppe?
a) (N, +) b) (N0, +) c) (Q, +)d) (Q, ·) e) (R, +) f) (R+, +)g) (R, ·) h) (R+, ·) i) (Z, ·)
/
5.2 Welche der folgenden Strukturen (S, ) ist Halbgruppe, Monoid oder Gruppe?
a) S = N, x y := min(x, y)
b) S = R, x y := (x + y)2
c) S = 1,−1, i,−i, x y := komplexe Multiplikation (d. h. i2 = −1)
d) S = 1, 2, 4, x y := x ·6 y (siehe Definition in Beispiel 5.7)
/
5.3 Ein Ausdruck der Form anxn + an−1x
n−1 + · · · + a0 mit ak ∈ R, k = 0, . . . , n und n ∈ N
heißt”Polynom in x mit reellen Koeffizienten“. ak heißen Koeffizienten von xk fur alle
k. Falls k die großte ganze Zahl ist fur die ak 6= 0, dann heißt das Polynom vom”Grad
k“. Falls kein solches existiert ist der Grad 0. Die Menge aller Polynome in x uber R
bezeichnen wir mit R[x]. Wir konnen in R[x] auf nahe liegende Art die Operationen‘+’ und ‘·’ definieren.
a) Ist (R[x], +) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
b) Ist (R[x], ·) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
c) Bestimme das Inverse von 7x4 − 2x3 + 4 in (R[x], +)!
/
5.4 Stelle die Verknupfungstafel fur die Permutationsgruppe G ⊆ S4 mit der Generator-menge (2, 4, 3, 1) auf!
Gib das Einselement von G sowie das Inverse von (2, 4, 3, 1) an!Die Notation (a1, . . . , a4) bedeutet π(1) = a1, . . . , π(4) = a4.Hinweis: G hat 3 Elemente! /
29
5.5 Stelle die Verknupfungstafel fur die alternierende Gruppe A3 von Permutationen von3 Elementen auf!Hinweis: Suche aus den in S3 enthaltenen Permutationen die geraden heraus! /
5.6 Sei Z5 = 0, 1, 2, 3, 4. Definiere die”Addition modulo 5“ (+5) auf Z5 durch x +5 y = r,
wobei r der Rest der Division von x+y durch 5 ist (Bsp.: 1+5 2 = 3, 3+5 4 = 2) und die
”Multiplikation modulo 5“ (·5) auf Z5 durch x ·5 y = r, wobei r der Rest der Division
von x · y durch 5 ist (Bsp.: 2 ·5 3 = 1, 3 ·5 4 = 2). Eine andere gebrauchliche Darstellungist x ≡ r(5) oder x ≡ r mod 5 (sprich:
”x kongruent r modulo 5“).
a) Ist (Z5, +5) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
b) Ist (Z5, ·5) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
c) Vervollstandige folgende Tabellen!
+5 0 1 2 3 4
01 323 24
·5 0 1 2 3 4
012 13 24
d) Bestimme alle Inversen zu den Elementen in (Z5, +5)!
e) Welche Elemente von (Z5, ·5) haben Inverse?
/
5.7 Sei Z6 = 0, 1, 2, 3, 4, 5. Definiere die”Addition modulo 6“ (+6) auf Z6 durch x +6 y =
r, wobei r der Rest der Division von x + y durch 6 ist und die”Multiplikation modulo
6“ (·6) auf Z6 durch x ·6 y = r, wobei r der Rest der Division von x · y durch 6 ist.
a) Ist (Z6, +6) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
b) Ist (Z6, ·6) Gruppoid, Halbgruppe, Monoid, Gruppe, kommutativ?
c) Stelle die Gruppenverknupfungstafeln auf !
d) Bestimme alle Inversen zu den Elementen in (Z6, +6)!
e) Welche Elemente von (Z6, ·6) haben Inverse?
/
30
5.8 Eine Teilmenge A ⊆ Ω einer gegebenen endlichen Menge Ω = ω1, . . . , ωn lasst sichdurch eine binare Zeichenkette (0-1-Folge) bA = b1 · · · bn darstellen,
wobei bi =
1 ωi ∈ A0 ωi /∈ A
.
a) Beschreibe fur Mengen A,B ∈ P (Ω), welche Operationen fur binare Zeichen-ketten den Mengenoperationen A ∪ B, A ∩ B und Ac entsprechen, d. h., wiedie Zeichenketten bA∪B , bA∩B und bAc aus bA und bB gebildet werden!
b) Begrunde, warum (P (Ω),∪) und (P (Ω),∩) Halbgruppen sind! Gib das jewei-lige neutrale Element und dessen Darstellung als binare Zeichenkette an!
c) Welche Operation auf binaren Zeichenketten entspricht der Mengenoperationder symmetrischen Differenz A∆B = (A \ B) ∪ (B \ A) ?
d) Die Hamming-Distanz zwischen den Mengen A,B ∈ P (Ω) ist als die Anzahlder Elemente |A∆B| in der symmetrischen Differenz definiert. Gib an, wie ausbA und bB die Hamming-Distanz zwischen A und B ermittelt werden kann!
/
5.9 Programm: Permutationen.
a) Schreibe ein Programm, das alle moglichen Permutationen einer gegebenenZeichenkette ausgibt! Hinweis: Rekursiv!
b) Schreibe ein Programm, das alle Binarstrings der Lange n generiert!
c) Schreibe ein Programm, das Addition (Multiplikation) modulo n in einer Ver-knupfungstafel ausgibt und die Gruppeneigenschaften testet!
/
5.10 Programm: Gruppeneigenschaften (umfangreich).
a) Schreibe ein Programm, das die Verknupfungstafel eines beliebigen Gruppo-ids als quadratische Matrix (Tabelle) akzeptiert, diese ausgibt, und sodannuberpruft, ob eine Halbgruppe, ein Monoid, eine Gruppe oder eine Abel’scheGruppe (kommutative Gruppe) vorliegt und das Ergebnis ausgibt!Anleitung: Die Eingabe erfolgt in einer Matrix, eingegeben werden Charakterbzw. Strings. Damit es nicht zu schwierig wird, kann vorausgesetzt werden,dass nur die Buchstaben a−z verwendet werden. Uberprufe sodann die Defi-nitionseigenschaften durch vollstandige Enumeration, d. h., alle Elemente wer-den durchnummeriert (wenn die Elemente in einer Matrix eingegeben wer-den, sind dies automatisch die Zeilen- und Spaltenindizes, die Verknupfun-gen werden in geschachtelten Schleifen zur Uberprufung der Eigenschafteneinzeln abgehandelt. Wenn etwa das Assoziativgesetz (a ∗ b) ∗ c = a ∗ (b ∗ c)uberpruft werden soll, gehe alle Tripel (a, b, c) einzeln durch.
31
b) Erweitere obiges Programm durch folgende Merkmale, wenn im speziellenFall sinnvoll:
– Ausgabe aller neutralen Elemente;
– Ausgabe des inversen Elementes bei Eingabe eines Elements;
– Losen der Gleichung a ∗ x = b nach Eingabe von a und b.
/
5.11 Finde alle Elemente der”Alternierenden Gruppe“ A4 aller geraden Permutationen von
1, 2, 3, 4 und zeige, dass A4 eine Untergruppe von S4 der Gruppe aller Permutatio-nen von 1, 2, 3, 4 ist! /
5.12 Schreibe die Elemente der alternierenden Gruppe A4 in lexikographischer Ordnung(nach dem Alphabet) auf! /
5.13 Programm: Symmetrische und alternierende Gruppen.
a) Schreibe ein Programm, das zu einem eingegebenen n ∈ N alle Elemente dersymmetrischen Gruppe Sn ausgibt!
b) Schreibe ein Programm, das zu einem eingegebenen n ∈ N alle Elemente deralternierenden Gruppe An ausgibt!Hinweis: Schreibe eine Routine, die eine Zyklenzerlegung einer gegebenenPermutation π durchfuhrt! Damit lasst sich leicht prufen, ob π ∈ An.
/
5.14 (N+, +) ist eine Halbgruppe. Sei G = Z+ die Menge der positiven ganzen Zahlen, dannist (G, ·) auch eine Halbgruppe. Zeige, dass die Funktion ϕ : N+ → G, definiert durchϕ(x) = 2x ein Homomorphismus ist! /
Ein Homomorphismus zwischen zwei Halbgruppen (G,⊕) und (H,) ist eine Abbil-dung
ϕ : (G,⊕) → (H,), a ∈ G 7→ ϕ(a) ∈ H
fur dieϕ(a ⊕ b) = ϕ(a) ϕ(b)
gilt. Ein bijektiver Homomorphismus heißt Isomorphismus. Ist G = H , so heißt einHomomorphismus auf G Automorphismus.
32
5.15 Seien folgende Abbildungen ϕ : (G,⊕) → (H,) gegeben.Welche sind Homomorphismen, welche Isomorphismen?
a) (G,⊕) = (N, +), (H,) = (2N, +), ϕ(x) = 2x
b) (G,⊕) = (N, +), (H,) = (2N, ·), ϕ(x) = 2x
c) (G,⊕) = (R, +), (H,) = (R, +), ϕ(x) = x2
d) (G,⊕) = (Z, +), (H,) = (Z, +), ϕ(x) = 2
e) (G,⊕) = (R, +), (H,) = (R, +), ϕ(x) = x + 1
f) (G,⊕) = (R, +), (H,) = (R, +), ϕ(x) = |x|
g) (G,⊕) = (Z × Z, +), (H,) = (Z, +), ϕ((x, y)) = x + 2y
h) (G,⊕) = (R[x], +), (H,) = (R, +)ϕ(anx
n + an−1xn−1 + · · · + a0) = an + an−1 + · · · + a0
/
5.16 Zeige, dass ϕ(x) = x ·3 1 ein Homomorphismus von (Z, +) nach (Z3, +3) ist!Bestimme den Kern! /
6 Graphen
Bevor wir in medias res gehen, eine Zusammenfassung der wichtigsten Definitionenund Notationen fur Graphen.
Graphen bestehen aus Knoten (vertex, vertices) und Kanten (edge(s)) und einer Funkti-on, die jeder Kante ein Paar von Knoten zuordnet. Ein Graph G kann daher durch dieMengen V (G) und E(G) und einer Funktion f gegeben sein. Kanten konnen gerichtetsein, (x, y) ist etwa die Kante von Knoten x nach Knoten y, oder ungerichtet, x, yist die (ungerichtete) Kante zwischen x und y. Im Folgenden werden wir aber die No-tation (x, y) fur ungerichtete, und < x, y > fur gerichtete Kanten verwenden, da sieeinfacher ist.
Ein gerichteter Graph besitzt nur gerichtete Kanten, ein ungerichteter nur ungerichte-te. Treten beide Arten von Kanten auf, so heißt der Graph gemischt.
Es kann in einem Graphen auch Schlingen und Mehrfachkanten geben. Ein schlichter(oder einfacher) Graph hat weder Schlingen noch Mehrfachkanten.
Ein vollstandiger Graph hat zwischen jedem seiner Knotenpaare eine Kante, d. h., bein Knoten hat er
(
n
2
)
Kanten und wird mit Cn bezeichnet. Der kantenlose oder lee-re Graph hat keine Kanten. Die Kantendichte ist das Verhaltnis von Kantenzahl zu
33
Anzahl der Kanten im zugehorigen Maximalgraphen bei gegebener Knotenmenge,d. h., |E|/
(
n
2
)
. Graphen mit hoher Kantendichte heißen dicht (dense), die mit geringersparlich (sparse).
Den Schatten eines Graphen erhalten wir, indem wir je zwei entgegengesetzt gerich-tete Kanten durch eine ungerichtete ersetzen, und alle weiteren gerichteten ebenfallsdurch ungerichtete.
Ein Teilgraph ist eine Teilmenge eines Graphen. Mit jeder Kante, die im Teilgraph auf-scheint, mussen auch die Endknoten aufscheinen. Enthalt ein Teilgraph alle Knotendes Originals, so heißt er spannender Teilgraph. Enthalt ein Teilgraph mit den Knotenauch alle Kanten auf dieser Knotenmenge, so heißt er gesattigter oder aufgespannterTeilgraph.
Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent. DieEndknoten einer Kante heißen zu dieser Kante inzident.
Graphen (gerichtete oder ungerichtete) mit n Knoten und k Kanten konnen sowohldurch eine n × k Inzidenzmatrix BG (falls ein gerichteter Graph vorliegt, darf er kei-ne Schlingen enthalten), als auch durch eine n × n Adjazenzmatrix AG beschriebenwerden.
Ungerichteter Graph
BG = (bi,j) i=1,...,n
j=1,...,kbi,j =
1 vj inzident zu ej
0 sonst
AG = (ai,j) i=1,...,n
j=1,...,nai,j =
r r Kanten zwischen vi und vj
0 sonst
Gerichteter Graph
BG = (bi,j) i=1,...,n
j=1,...,kbi,j =
1 ej beginnt in vi
−1 ej endet in vi
0 sonst
AG = (ai,j) i=1,...,n
j=1,...,nai,j =
r r Kanten von vi nach vj
0 sonst
Die Anzahl d+(vi) der von einem Knoten vi wegfuhrenden Kanten heißt Outdegree,die Anzahl d−(vi) der zu dem Knoten hinfuhrenden Kanten heißt Indegree. Bei un-gerichteten Graphen ist d(vi) die Anzahl der mit vi inzidenten Kanten der Grad desKnoten.
34
Es gilt:
d+(vi) =n
∑
j=1
aij d−(vi) =n
∑
j=1
aji d(vi) =n
∑
j=1
aij =n
∑
j=1
aji
Ist d+(v) = 0, so heißt v Senke, ist d−(v) = 0, so heißt v Quelle.
Betrachten wir Kantenfolgen von va nach ve, das sind Folgen von aneinander anschlie-ßenden Kanten, die vom Anfangsknoten va bis zum Endknoten ve durchlaufen werdenkann. Ist der Anfangs- gleich dem Endknoten, so heißt die Kantenfolge geschlossen,andernfalls heißt sie offen.
Eine Kantenfolge, in der keine Kante mehrfach auftritt heißt Kantenzug. Ein Weg ist ei-ne offen Kantenfolge, in der kein Knoten mehrfach auftritt. Ein Zyklus oder Kreis ist ei-ne geschlossene Kantenfolge, in der kein Knoten mehrfach vorkommt (außer Anfangs-und Endknoten). Die Anzahl der Kanten in einer Kantenfolge heißt Lange. Ein Knotenvi heißt in k Schritten von vj aus erreichbar, wenn es eine Kantenfolge der Lange k vonvj nach vi gibt.
Ein ungerichteter Graph heißt zusammenhangend, wenn jeder Knoten des Graphenvon jedem anderen Knoten aus erreichbar ist. Die zusammenhangenden gesattigtenTeilgraphen eines Graphen heißen Zusammenhangskomponenten des Graphen.
Ein gerichteter Graph heißt stark zusammenhangend, wenn jeder Knoten des Graphenvon jedem anderen Knoten aus erreichbar ist. Er heißt schwach zusammenhangend,wenn sein Schatten zusammenhangend ist.
BEMERKUNG: Es gibt eine Kantenfolge der Lange s von vi nach vj wenn das Element
a(s)ij > 0, mit As
G = (a(s)ij ).
BEMERKUNG: Ein Knoten vj ist von vi aus erreichbar, wenn der Eintrag rij > 0,
wobei die Erreichbarkeitsmatrix R = (rij) = (max(a[0]ij , . . . , a
[n−1]ij )) ist,
mit a[k]ij =
1 falls a(k)ij > 0
0 sonst.
Die Distanz d(vi, vj) zweier Knoten in einem zusammenhangenden Graphen ist dieLange des kurzesten Weges zwischen den beiden Knoten.
Eine Euler’sche Linie enthalt jeden Knoten mindestens einmal, jede Kante genau ein-mal. Eine Hamilton’sche Linie enthalt jeden Knoten genau einmal. Geschlossene Eu-ler’sche bzw. Hamilton’sche Linien sind solche, die einen geschlossenen Kantenzugbilden.
Kreisfreie, gerichtete Graphen heißen azyklisch. Ein ungerichteter, kreisfreier Graphheißt Wald. Ein zusammenhangender Wald heißt Baum. Ein Knoten vom Grad 1 einesBaumes heißt Blatt oder Endknoten.
Ein Teilgraph, der alle Knoten eines zusammenhangenden ungerichteten Graphenenthalt und zusatzlich ein Baum ist, nennen wir spannenden Baum oder Gerust.
35
Graphen, die in den folgenden Beispielen verwendet werden und dort nicht explizitangegeben werden, finden sich am Ende dieses Abschnitts.
6.1 Graph G1 gegeben durch: V (G1) = 1, 2, . . . , 8, E(G1) = < x, y > |x teilt y, x < yGraph G2 gegeben durch: V (G2) = 1, 2, . . . , 5, E(G2) = < x, y > |x < y ≤ x + 3Bestimme und zeichne G1 ∩ G2 und G1 ∪ G2! /
6.2 Graph G1 gegeben durch: V (G1) = 1, 2, . . . , 7, E(G1) = < x, y > |x < y ≤ x + 2Graph G2 gegeben durch: V (G2) = 1, 2, . . . , 9, E(G2) = < x, y > |x teilt y, x < yBestimme und zeichne G1 ∩ G2 und G1 ∪ G2! /
6.3 Bestimme alle Quadrupel (a, b, c, d), a, b, c, d ∈ 1, 2, . . . , 7, sodass der von den Knotena, b, c, d in G1 aufgespannte (vollstandige) Teilgraph mit G2 identisch ist! /
6.4 Bestimme alle Quadrupel (a, b, c, d), a, b, c, d ∈ 1, 2, . . . , 7, sodass der von den Knotena, b, c, d in G3 aufgespannte Teilgraph mit G4 identisch ist! /
6.5 Bestimme die Adjazenzmatrizen AG1, AG2
, AG1∩G2und AG1∪G2
fur die Graphen ausBeispiel 6.1 bzw. 6.2! /
6.6 Bestimme die Adjazenzmatrizen AG1und AG3
, sowie die Potenzen A2G1
, A[2]G1
, A2G3
und
A[2]G3
! /
6.7 Bestimme die Adjazenzmatrix AG5, sowie (mit deren Hilfe) die Anzahl der gerichteten
Kantenfolgen der Lange 3 von Knoten 4 nach 6! /
6.8 Entferne aus dem vollstandigen (ungerichteten) Graphen mit der Knotenmenge 1, . . . , 5die Kanten (3, 5) und (4, 5).
a) Stelle den resultierenden Graphen G durch seine Adjazenz- und Inzidenzma-trix dar, wobei im Fall der Inzidenzmatrix die Kanten (i, j) gemaß der Rela-tion
(i, j) vor (i′, j′) − (i < i′ ∨ (i = i′ ∧ j < j′))
anzuordnen sind !
b) Enthalt G eine geschlossene Euler’sche Linie ? Gib diese an bzw. begrundewarum, falls keine solche existiert!
c) Gib eine geschlossene Hamilton’sche Linie in G an!
/
36
6.9 Sei H5 der Graph, der aus G5 durch Umdrehen aller Kantenrichtungen entsteht. Be-stimme die Adjazenzmatrix AH5
, sowie (mit deren Hilfe) die Anzahl der gerichtetenKantenfolgen der Lange 3 von Knoten 4 nach 6! /
6.10 Gegeben sei die Adjazenzmatrix A (mit Mehrfachkanten)
A =
1 1 0 11 0 1 00 1 0 21 0 2 0
a) Zeichne einen dazu gehorigen ungerichteten Graphen mit den Knoten 1, 2, 3, 4!
b) Berechne A2!
c) Finde 5 verschiedene Pfade von 4 nach 4 der Lange 2!
d) Berechne die Erreichbarkeitsmatrix R!
/
6.11 Der 3-dimensionale Hypercube H3 ist durch folgende Knotenmenge und Kantenmen-ge gegeben:
Knoten: V (H3) = x = (x1, x2, x3) |xi ∈ 0, 1, i = 1, 2, 3Kanten: E(H3) = (x, y) |genau zwei Komponenten von x und y stimmen uberein
Ermittle fur H3 die durchschnittliche Distanz der sieben Knoten x 6= (0, 0, 0) zum Kno-ten (0, 0, 0).Hinweis: Fasse die Knoten als Punkte im R3 auf und zeichne diese! /
6.12 Zeichne zwei verschiedene ungerichtete zusammenhangende Graphen mit der Kno-tenmenge V = 1, 2, 3, 4, 5, die geschlossenen Euler’sche Linien enthalten, und gibderen Adjazenzmatrizen und Inzidenzmatrizen an! /
6.13 Gegeben sei der Graph G15.
a) Welche Knoten sind von 3 aus erreichbar?
b) Bestimme die Lange des kurzesten Pfades von 3 nach 6!
c) Bestimme einen Pfad der Lange 8 von 1 nach 6!
/
37
6.14 Der gerichtete Graph G = (V,E) sei durch
V = 1, . . . , 6 und E = (i, j) | i, j ∈ V, 2i + j ≤ 6
gegeben.
a) Zeichne G !
b) Gib die Adjazenzmatrix von G an!
c) Ist G ein schlichter Graph ? – Begrundung!
d) Gib die schwachen Zusammenhangskomponenten von G an!
e) Betrachte den von V ′ = 1, 2 aufgespannten Teilgraphen G′ von G! EnthaltG′ eine geschlossene Euler’sche Linie ? – Begrundung!
/
6.15 Gegeben sei der Graph G24.
a) Bestimme die Adjazenzmatrix von G!
b) Gib die Indegrees und Outdegrees der Knoten von G an!
c) Zeichne den Schatten von G!
/
6.16 Programm: Distanzmatrix. Schreibe ein Programm, das die Distanzmatrix D einesgegebenen zusammenhangenden gerichteten Graphen berechnet und ausgibt, d. h.,jene Matrix D = (dij)i,j , in der dij die Distanz von Knoten i zu Knotenj ist, d. h., dieLange des kurzesten Weges von i nach j!Anleitung: Es soll die Adjazenzmatrix AG des Graphen eingegeben werden. Verwendeweiters die in der Vorlesung gegebene Interpretation der Potenzen An
G von AG! /
6.17 Programm: Euler’sche Linie. Schreibe ein Programm, das einen durch seine Adjazenz-matrix AG gegebenen gerichteten Graphen G durch Hinzufugen von beliebigen Kan-ten so erweitert, dass er eine geschlossene Euler’sche Linie enthalt! /
38
6.18 Programm: Topologische Knotensortierung. Eine topologischen Knotensortierung ist ei-ne Nummerierung der Knoten eines gegebenen azyklischen gerichteten Graphen G,sodass v ∈ V stets eine kleinere Nummer als w ∈ V bekommt, wenn es einen Weg vonv nach w gibt.Implementiere folgenden Algorithmus zur topologischen Knotensortierung:
Solange Knoten nicht nummeriert
- Nummeriere Quellen von G mit der kleinsten noch freien Nummer- Entferne die soeben nummerierten Quellen und die von ihnen
wegf uhrenden Kanten aus G
/
6.19 Programm: Zyklische Graphen.
a) Schreibe ein Programm, das von einem gegebenen Graphen bestimmt, ob erzyklisch oder azyklisch ist!
b) Schreibe ein Programm, das von einem gegebenen Graphen bestimmt, ob erkreisfrei ist! Weiters soll es die Menge der erreichbaren Knoten ausgeben.
/
6.20 Gegeben sei der Graph G16.
a) Bestimme die Anzahl der Pfade der Lange 3 von 5 nach 2 direkt!
b) Bestimme die Anzahl der Pfade der Lange 3 von 5 nach 2 mit Hilfe der MatrixA3
G16!
/
6.21 Bestimme fur die Graphen G6, H6 und G17 (wobei H6 durch Umkehren aller Kanten-richtungen aus G6 entsteht) die entsprechenden Erreichbarkeitsmatrizen R! /
6.22 Zeige fur den Graphen G15 mit Hilfe der Erreichbarkeitsmatrix, dass die Knoten 1 und2 von 3 aus nicht erreichbar sind! /
6.23 Bestimme die starken Zusammenhangskomponenten fur die Graphen G1, G3, G5, G7
und H7 (wobei H7 durch Umkehren aller Kantenrichtungen aus G7 entsteht)! /
39
6.24 Untersuche, ob die Graphen G14, G18, G19, G20, G21, G22, G23 eine geschlossene Eu-ler’sche Linie besitzen und bestimme gegebenenfalls eine solche! /
6.25 Untersuche, ob die Graphen G14, G18, G19, G20, G21, G22, G23 eine geschlossene Hamil-ton’sche Linie besitzen und bestimme gegebenenfalls eine solche! /
6.26 Bestimme in den Graphen G5 und H5 (entstanden durch Umkehrung aller Kanten-richtungen aus G5) die Anzahl der Zyklen der Lange 3, auf denen der Knoten 4 liegt!
/
6.27 Bestimme in den Graphen G9 und G10 die Anzahl der Dreiecke (Kreise der Lange 3)! /
6.28 Untersuche die Graphen G7, G8, G11 und H11 (entstanden durch das Umkehren allerKantenrichtungen aus G11) mit dem Markierungsalgorithmus auf Azyklizitat! /
6.29 Bestimme alle Knotenbasen der Graphen G1, G3, G5, G7 und H7 (entstanden durch dasUmkehren aller Kantenrichtungen aus G7)! /
Graphen G1 − G24 zu den Beispielen
G1:
3
4
2
1
5
6
7 G3:
3
4
2
1
5
6
7
G2:
a b c
d G4:
a b c
d
G5:
1
2 3 4
5
678
G6:
1 2
3
4
40
G7: 1 2 3 4
5 6
7 8
9 1011 12
13 14
G8: 1 2 3
4 5 6
7
G9: 1
2
3
4
G10:
1 2
34
5
G11:
1
2 3 4
5
6 7 8
G12:
1
2
3
4
5
6
7
8 G13:
1 2 3 4
5678
G14:
G15:
1
2 3
4
56 G16:
1
2
3
45
41
G17: 1
2 3
4
G18:
G19:
G20:
!
G21:" #
$
%&
'
G22:
()*
+,-
G23:
./0
1
234
5
67
89
G24: 1
2
3
7 Endliche Automaten
Ein endlicher Automat ist ein formales System (Q, Σ, δ, q0, F ), in dem ein bestimmtesEin-Ausgabeverhalten mit Alphabet Σ durch eine endliche Anzahl interner System-zustande Q und ihrer Ubergange δ : Q × Σ → Q definiert wird, wobei im Zustand q0
gestartet wird, und verschiedene Endzustande F angegeben sind.
42
7.1 Gib eine Beschreibung einer Geldausgabe durch einen Bankomaten als Endlichen Au-tomaten!Hinweis: Berucksichtige sowohl korrekte wie auch fehlerhafte Eingaben und Verhal-tensweisen des Benutzers. Als Nebenbedingung gilt, dass der Code maximal dreimaleingegeben werden kann. /
7.2 Erweitere das Ubergangsdiagramm aus Beispiel 7.1 zu einem Graphen, in dem einegeschlossene Euler’sche Linie existiert, und leite daraus eine Testsequenz ab, die allemoglichen Ubergange abdeckt! /
7.3 Gib Endliche Automaten an, die folgende Sprachen uber dem Alphabet 0, 1 akzep-tieren!
a) Die Menge aller Zeichenketten, die mit ‘00’ enden.
b) Die Menge aller Zeichenketten, die drei aufeinander folgende Nullen enthal-ten.
c) Die Menge aller Zeichenketten, die so beschaffen sind, dass funf aufeinanderfolgende Symbole mindestens zwei Nullen enthalten.
/
BEMERKUNG (REGULARER AUSDRUCK UBER DEM ALPHABET Σ):
1. ∅ ist ein regularer Ausdruck (leere Menge ).
2. ε ist ein regularer Ausdruck (leere Eingabe ε).
3. a ist ein regularer Ausdruck fur alle a ∈ Σ (Menge a).
4. Sind r und s regulare Ausdrucke (Mengen R und S), dann auch
• (r + s) – bezeichnet R ∪ S.
• (rs) – bezeichnet Verkettung RS.
• (r∗) – Kleene’scher Abschluss, d. h., alle moglichen Verkettungen inklu-sive ε.
7.4 Gib regulare Ausdrucke an, die die folgenden Mengen bezeichnen!
a) Die Menge aller Dezimalzahlen mit mindestens einer Ziffer vor und beliebigvielen Ziffern nach dem Dezimalpunkt (Komma).
b) Die Menge aller Passworter aus mindestens einem und hochstens funf Buch-staben, gefolgt von zwei Ziffern.
43
c) Die Menge aller binaren Zeichenketten, in denen nie drei Nullen aufeinanderfolgen.
d) Die Menge aller binaren Zeichenketten, in denen die Anzahl von unmittelbaraufeinander folgenden Nullen stets gerade ist.
/
7.5 Konstruiere einen regularen Ausdruck, der folgendem Ubergangsdiagramm entspricht:
Start 1
0
0
1
0
1
/
7.6 Konstruiere eine (a) Moore-Maschine (b) Mealy-Maschine fur folgenden Prozess:Fur eine Eingabe aus (A + B)∗ soll diese eine ‘1’ ausgeben, falls die Eingabe mit ABAendet, eine ‘2’ ausgeben, falls sie mit AAB endet, und sonst eine ‘3’ ausgeben. /
7.7 Programm: Lindenmayer-System, kontextfreie Grammatik. Ein L-System besteht ausVariablen, Konstanten (die nicht verandert werden konnen), Regeln fur den Austauschvon Variablen (Ersetzungsvorschriften) und Anfangsbedingungen (Axiome), d. h., auswelchem Zustand das L-System startet.
Das L-System Fibonacci mit den Variablen A und B, ohne Konstanten und mit denRegeln
”Ersetze A durch B“ und
”Ersetze B durch AB“ generiert aus der Anfangsbe-
dingung A durch Iteration folgende Strings:
0 : A1 : B2 : AB3 : BAB4 : ABBAB5 : BABABBAB6 : ABBABBABABBAB7 : BABABBABABBABBABABBAB
Betrachten wir die Lange der Strings, so erhalten wir die Fibonacci-Zahlen, was nichtverwunderlich ist, wenn wir beachten, dass jeder String aus der Zusammenfugung(Konkatenation) der beiden letzten Vorganger entsteht (nach Initialisierung der erstenbeiden).
44
L-Sytem Algenwachstum der Alge Chaetomorpha linum:
Alphabet A = A,B,C,D,E, +Variablen V = A,B,C,D,EKonstanten K = +Axiom AErsetzungsvorschriften A → D + B
B → CC → DD → EE → A
Iterieren wir und fassen den Buchstaben ‘+’ als Verzweigung auf, so ergibt sich einBaum, der dem Wachstum der Alge entspricht, wenn wir, wie sonst nicht ublich, alleEntwicklungsstadien gleichzeitig betrachten.
Aufgabe: Gegeben seien eine Menge V = 0, 1 von Variablen, vier Konstanten K =+,−, [, ], ein Axiom als Startbedingung aus diesen Symbolen und eine Ersetzungs-vorschrift fur den Austausch von einzelnen Symbolen in durch eine Kette von Sym-bolen.
a) Schreibe ein Programm, das nach Eingabe des Axioms, der Ersetzungsvor-schrift und einer Iterationstiefe n, eine Schleife, in der der jeweilig im letztenSchritt entstandene String nach der Ersetzungsvorschrift behandelt wird, ge-nau n Mal durchlauft ! Der Ergebnisstring soll ausgegeben werden.
b) Erweitere das Programm um eine graphische Ausgabe, die aus dem Ergebnis-string nach Eingabe eines Winkels α eine Figur zeichnet, indem die Symboledes Strings in folgender Weise interpretiert werden (Zeichenvorschrift):
0 Gehe einen Schritt in die aktuelle Richtung, zeichne nicht.
1 Gehe einen Schritt in die aktuelle Richtung, zeichne eine Kante.
‘+’ Zeichne die nachste Kante um den Winkel α gedreht zur letzten Richtungvom aktuellen Knoten weiter!
‘−’ Zeichne die nachste Kante um den Winkel −α gedreht zur letzten Rich-tung vom aktuellen Knoten weiter!
‘[’ Lege den aktuellen Zustand auf einem Stapel ab (Zeichenposition, Zei-chenrichtung etc.)!
‘]’ Nimm den letzten Zustand vom Stapel und mach diesen zum aktuellen!
Teste die Programme mit:
a) Axiom: 1 − 1 − 1 − 1;Ersetzungsvorschrift: 1 → 11 − 1 − 1 − 1 − 1 − 1 + 1, α = 90
b) Axiom: 1 − 1 − 1 − 1;Ersetzungsvorschrift: 1 → 1 − 1 + 1 − 1 − 1, α = 90
c) Axiom: 1; Ersetzungsvorschrift: 1 − 1 + +1 − 1, α = 60
45
d) Axiom: 1; Ersetzungsvorschrift: 11 + [+1 − 1 − 1] − [1 + 1 + 1], α = 22
/
7.8 Programm: Turing Maschinen. Anfang des 20. Jahrhunderts prasentierte David Hil-bert eine Liste ungeloster Mathematischer Probleme, darunter:
Ist die Mathematik vollstandig, d. h., kann jede ihrer Aussagen entweder bewie-sen oder widerlegt werden?
Ist die Mathematik widerspruchsfrei, oder konnen falsche Aussagen mittels ma-thematisch logischer Beweisfuhrung hergeleitet werden?
Ist die Mathematik entscheidbar, d. h., gibt es ein Verfahren, das fur jede Aussageuberprufen kann, ob diese wahr oder falsch ist?
Kurt Godel zeigte, dass die beiden ersten Aussagen einander ausschließen: Entwederist das Axiomensystem der Mathematik vollstandig, dann fuhrt es zu Widerspruchen,oder es ist widerspruchsfrei, dann gibt es aber Aussagen, von denen nicht entschiedenwerden kann, ob sie wahr oder falsch sind (Unentscheidbarkeit, Unvollstandigkeit).
1936 zeigte Alan M. Turing (1912 - 1954), dass das dritte Problem unlosbar ist (Hal-teproblem). Dies machte eine exakte Definition des Begriffes
”Verfahren“ (Algorith-
mus) erforderlich. Nach Turings Vorstellung muss ein Verfahren rein mechanisch aus-gefuhrt werden konnen. Eine Turingmaschine ist nun ein theoretisches Modell einesRechners zur Abarbeitung eines Algorithmus.
Eine Turingmaschine hat folgende Bestandteile:
– Ein unendlich langes Speicherband. Auf jedem Feld kann genau ein Zeichen desverwendeten Alphabets gespeichert werden; ein spezielles Zeichen des Alpha-bets ist das Leerzeichen.
– Ein Schaltwerk (Ubergangstafel) mit endlich vielen Zustanden, das das Verhaltender Turingmaschine steuert. Siehe etwa die Ubergangstafel und das Ubergangs-diagramm im nachsten Beispiel.
– Einen Schreib-Lesekopf. Er kann den Bandinhalt an der aktuellen Position lesen,ein Zeichen an der aktuellen Position auf das Band schreiben, und sich um einenSchritt nach links oder rechts bewegen.
Zu Beginn befindet sich ein bestimmter Bandinhalt auf dem Speicherband, der Schreib-Lesekopf befindet sich an einer bestimmten Stelle und das Schaltwerk befindet sich imZustand 1. Dann wird die Turingmaschine gestartet. Das Halteproblem besteht nundarin, dass es Turingmaschinen gibt, von denen nicht vorausgesagt werden kann, obsie halten oder nicht!
Jeder digitale Computer kann genau dieselbe Klasse mathematischer Funktionen be-rechnen wie eine Turingmaschine, d. h., eine mathematische Funktion ist berechenbar,wenn sie sich auf einer Turingmaschine berechnen lasst.
46
Aufgabe: Schreibe einen Simulator fur Turingmaschinen, der durch Eingabe einerUbergangstafel gesteuert wird! Dabei soll es moglich sein, den Inhalt des (unendli-chen) Bandes zu initialisieren, d. h. etwa, lauter Leerzeichen (etwa lauter Nullen) oderzufallige Buchstaben aus dem verwendeten Alphabet, das eingegeben werden muss,vor Start der Turing-Maschine auf das Band zu schreiben. /
7.9 Programm: Fleißige Biber. Ein”Fleißiger Biber“ ist eine Turingmaschine mit genau n
Zustanden, gegeben durch eine Ubergangstabelle mit n Zustanden, die eine Maximal-zahl von Buchstaben eines Alphabets ohne Leerzeichen auf ein leeres Band schreibt!Diese Turingmaschine muss halten, darf aber nicht das Band verlassen. d. h., die Tu-ringmaschine darf keine unendliche Schleife oder oszillierende Zustande enthalten.
Ein Kandidat fur den Fleißigen Biber mit 5 Zustanden ist derjenige, der nach mehrerenMillionen Ubergangen 4098 Einser schreibt bevor er halt.Es gibt insgesamt 63 403 380 965 376 verschiedene Biber mit 5 Zustanden!
Simuliere folgende Biber und beschreibe, was diese machen! Ist der Biber fleißig?Das Alphabet ist 0, 1, wobei 0 das Leerzeichen ist.
0 Halt0
1,R
1 1,R
0 1 Halt0
1,L
11,R
0
1,R
11,R
0 1
2
Halt0 1,R
1
1,L 0
1,L
01,R
10,L
1 1,R
0 1
23
Halt
11,L
01,R
0
1,L
10,L
01,R
11,L
10,R
00,R
Folgendes Ubergangsdiagramm und folgende Ubergangstafel beschreiben den selbenBiber – was bewirkt dieser?
0 10
1,R
00,L
11,L
1 0,R
Zustand lese Aktion Z.neu0 0 1,R 1
1 1,L 01 0 0,L 0
1 0,R 1
47
Der folgende Biber beginnt auf einem mit Nullen gefullten Band:
0 1
23
4 Halt
0 1,L
1 1,R 10,L0
1,R1
0,L
00,R
01,L
1
0,R
10,L
0 1,L
/
48
