TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Diff 2023SS
Zur Navigation springen
Zur Suche springen
Vergleich mit TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS23
1) Man überprüfe die Gleichung
n(n + 1)(2n + 1)
12 + 22 + 32 + · · · + n2 =
6
für die ersten fünf natürlichen Zahlen und beweise sodann deren Gültigkeit für alle natürlichen
Zahlen durch vollständige Induktion.
2) Man zeige, dass n3 − n für alle n ∈ N stets durch 3 teilbar ist, mittels
@@ -18,33 +18,34 @@ Zahlen durch vollständige Induktion.
3) Man zeige durch vollständige Induktion, dass 7n − 1 für alle n ∈ N durch 6 teilbar ist.
4–13) Man beweise mittels vollständiger Induktion:
4) 5)
n
n
X 1 n
(n − 1)n(n + 1) = (n ≥ 1)
j(j + 1) n+1
X
j(j − 1) = (n ≥ 2) j=1
3
j=2
n n
X X 3n (2n − 1) + 1
6) j2j = 2n+1 (n − 1) + 2 (n ≥ 0) 7) j3j−1 = (n ≥ 1)
4
j=0 j=1
8) 9)
n
n
X l 3 2n + 3
5 = − (n ∈ N)
3l 4 4 · 3n
X
k5 = (n5n+1 − (n + 1)5n + 1) (n ≥ 1)
k
k5 = (n5n+1 − (n + 1)5n + 1) (n ≥ 1) l=1
16
k=1
@@ -63,13 +64,13 @@ k=1
Ln = + .
2 2
7 n
�
13) Ist F0 = 0, F1 = 1 und Fn+2 = Fn+1 + Fn für alle n ∈ N, so gilt Fn < 4 .
1
�14) Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge x1 = 1 und
xk+1 = xk + 8k für k ≥ 1 allgemein gilt:
@@ -81,10 +82,10 @@ xk+1 = xk + 18k + 15 für k ≥ 0 allgemein gilt:
xn = (3n + 1)2 , für alle n ≥ 0.
16) Man zeige mittels vollständiger Induktion, dass für die rekursiv definierte Folge x0 = 1 und
xk+1 = axk + b für k ≥ 0 (wobei a, b ∈ R, a 6= 1, und weiters a0 = 1 für alle reellen a zu
interpretieren ist)1) allgemein gilt:
an − 1
xnx n = an + b , für alle n ≥ 0.
a−1
17) an sei die größte Anzahl von Teilen, in die die Ebene durch n Geraden zerlegt werden kann.
@@ -96,12 +97,12 @@ chung gilt:
18) 9n3 − 3 ≤ 8n 19) 4n2 ≤ 2n
20) 3n + 2n ≤ 3n 21) (n + 1)3n ≤ 4n
n
X n
X n−1
X k
X
22) Man zeige für alle n ∈ N \ {0}: aak b kbk = a nan bk − (ak+1 − ak ) bj .
k=1 k=1 k=1 j=1
23) Wo steckt der Fehler im Induktions- Beweis“ der folgenden Behauptung:
”
@@ -129,7 +130,8 @@ aussetzung b), dass a − 1 = b − 1 ist, womit aber auch a = b gilt.
31) Man finde alle sechsten Wurzeln von z = 8i in C und stelle sie in der Gaußschen Zahlenebene
dar.
2
�32) Man finde alle sechsten Wurzeln von z = −27 in C und stelle sie in der Gaußschen Zahlenebene
dar.
33) Man bestimme rechnerisch (ohne Taschenrechner) und graphisch Summe und Produkt der
@@ -153,7 +155,7 @@ komplexen Zahlen z1 = 3 − 4i und z2 = [2, π2 ].
42) Stellen Sie alle Lösungen der quadratischen Gleichung z 2 + 2z + 4 = 0 sowohl in der Form
a + bi, a, b ∈ R, als auch in Polarkoordinatenform r(cos ϕ + i sin ϕ), r ≥ 0, 0 ≤ ϕ < 2π, dar.
43) Wie Bsp. 42) für z 2 + 4z + 8 = 0.
44) Für welche komplexe Zahlen gilt z = z11z ?
z1 + z2 2 z1 − z2 2 1
45) Man zeige + = (|z1 |2 + |z2 |2 ).
2 2 2
@@ -203,8 +205,7 @@ aller Teiler von N durch 12 teilbar ist.
63) Beweisen Sie die folgenden Behauptungen oder widerlegen Sie sie durch ein konkretes Gegen-
beispiel.
a) Falls ac ≡ bc mod m, c 6= 0 und c | m, dann gilt auch a ≡ b mod m
c.mc .
b) Falls a ≡ b mod m, dann gilt auch a2 ≡ b2 mod m.
@@ -213,13 +214,14 @@ beispiel.
64–69) Bestimmen Sie alle Lösungen der folgenden Kongruenzen bzw. beweisen Sie die Unlösbar-
keit (in Z):
64) a) 8x ≡ 4 mod 16, b) 8x ≡ 4 mod 15.
65) a) 6x ≡ 3 mod 9, b) 6x ≡ 4 mod 9.
66) a) 3x ≡ 9 mod 11, b) 3x ≡ 9 mod 12.
67) a) x2 ≡ 1 mod 3, b) x2 ≡ 1 mod 5.
68) a) x2 ≡ 2 mod 5, b) x2 ≡ 2 mod 7.
69) a) x2 − 3x + 2 ≡ 0 mod 5, b) x2 − 3x + 2 ≡ 0 mod 6.
70) Man beweise die folgenden Regeln für das Rechnen mit Kongruenzen:
(a) a ≡ b mod m, c ≡ d mod m ⇒ a + c ≡ b + d mod m
(b) a ≡ b mod m, c ≡ d mod m ⇒ a · c ≡ b · d mod m
@@ -230,7 +232,7 @@ keit (in Z):
a1 a2 . . . a12 p verwendet. Dabei wird die letzte der 13 Ziffern, das ist die Prüfziffer p, im EAN-Code
so bestimmt, dass
a1 + 3a2 + a3 + 3a4 + · · · + a11 + 3a12 + p ≡ 0 mod 10
gilt. Man zeige, dass beim EAN-Code ein Fehler in einer einzelnen Ziffer stets erkannt wird,
während eine Vertauschung von zwei benachbarten Ziffern genau dann nicht erkannt wird, wenn
@@ -255,7 +257,7 @@ keine Quadratzahl sein kann.
76) Beweisen Sie mit Hilfe von Kongruenzen, dass zwei Quadratzahlen, deren Summe durch 3
teilbar ist, selbst durch 3 teilbar sind.
77) Sei a die Aussage Es gibt eine größte natürliche Zahl.“ und b die Aussage 0 ist die größte
” ”
natürliche Zahl.“ Man entscheide, ob die Aussagen a ⇒ b bzw. b ⇒ a wahr oder falsch sind.
78–83) Entscheiden Sie mit Hilfe einer Wahrheitstafel, ob die folgenden Äquivalenzen richtig sind.
@@ -331,22 +333,22 @@ ten Reflexivität, Symmetrie, Antisymmetrie und Transitivität:
(d) M = R, a R b ⇔ a − b ∈ Z
(e) M = Rn , (x1 , . . . , xn )xn) R (y1 , . . . , yn )yn) ⇔ xi ≤ yi ∀i = 1, . . . , n
109) Man zeige, dass durch
a R b ⇔ 3 | a 2a2 − b2b 2 für alle a, b ∈ Z
eine Äquivalenzrelation R in der Menge Z erklärt wird, und bestimme die zugehörende Partition.
110) Man zeige, dass durch
a R b ⇔ 6 | a 2a2 − b2b 2 für alle a, b ∈ Z
eine Äquivalenzrelation R in der Menge Z erklärt wird, und bestimme die zugehörende Partition.
111) Sei M = R × (R \ {0}) und R eine Relation auf M gegeben durch
a c
(a, b)R(c, d) :⇔ = .
b d
Zeigen Sie, dass R eine Äquivalenzrelation ist und bestimmen Sie die durch R induzierte Partition
von M .
@@ -371,7 +373,7 @@ ihr Durchschnitt R = R1 ∩ R2 Äquivalenzrelation auf M ist. Gilt dies auch fu
R1 ∪ R2 ?
7
�121) Sei T70 die Menge aller natürlichen Zahlen, die 70 teilen. Man vergleiche die Hassediagramme
der beiden Halbordnungen hP({a, b, c}), ⊆i und hT70 , |i.
122) Sei T24 die Menge aller natürlichen Zahlen, die 24 teilen. Man vergleiche die Hassediagramme
@@ -451,7 +453,7 @@ Surjektivität und Bijektivität:
2x + 1
146) Man zeige, dass die Funktion f : R \ {7} → R \ {2}, y = , bijektiv ist, und bestimme
x−7
ihre Umkehrfunktion.
10x + 1
147) Man zeige, dass die Funktion f : R \ {6} → R \ {−10}, y = , bijektiv ist, und
@@ -478,12 +480,12 @@ Zeigen Sie, dass die Menge aller unendlichen Wörter“ über dem Alphabet A u
155) Sei A eine abzählbar unendliche Menge und P(A) die Potenzmenge von A. Zeigen Sie, dass
P(A) überabzählbar ist. Hinweis: Fassen Sie P(A) als Menge von unendlichen 0-1-Folgen auf.
156) Zeigen Sie, daß R \ Q überabzählbar ist.
157) Man beweise die Beziehung n+1 nn n
� � � n� n�
�
k+1 = k+1 + k durch Interpretation von k als Anzahl
der k-elementigen Teilmengen einer n-elementigen Menge.
158) Man beweise die Beziehung n+1 n n n n!
� � � �
k+1 = k+1 + k mit Hilfe der Formel k = k!(n−k)! .
159) Von m weißen Kugeln, die mit den Zahlen 1, . . . , m nummeriert sind, sollen k ≥ 1 Kugeln
@@ -493,9 +495,8 @@ Erklären Sie, warum aus dem Ergebnis die folgende Gleichung folgt:
m � � � �
X n−1 m
= .
n=1
k−1 k
n=1
160) Wieviele Wörter“ der Länge 28 gibt es, bei denen genau 5-mal der Buchstabe a, 14-mal b,
”
@@ -548,18 +549,18 @@ die Ziffer drei?
176) Wieviele natürliche Zahlen n < 1000 000 enthalten in ihrer Dezimalentwicklung genau vier-
mal die Ziffer zwei?
177) Man beweise nachstehende Identitäten für Binomialkoeffizienten:
� � � � � � � � � � n � �
n n n n n+1 X n
(a) = (b) + = (c) = 2n
k n−k k k+1 k+1 k
k=0
178) Man beweise die Formel
� � X n � �2 n � �� �
2n n X n n
= = .
n k k n−k
k=0 k=0
(Hinweis: Man betrachte die Koeffizienten von (1 + x)n (1 + x)n = (1 + x)2n .)
@@ -588,8 +589,8 @@ Differentialrechnung):
182) 183)
n � � n � �
X n X n
k4k k5k
k k
k=0 k=0
@@ -600,8 +601,8 @@ Differentialrechnung):
n � � n � �
X
k n X n
(−1) k (n − k)2k
k k
k=0 k=0
186) Eine Datei enthalte 7 Datensätze vom Typ A, 4 vom Typ B, 6 vom Typ C, 2 vom Typ D und
@@ -628,9 +629,6 @@ Zeigen Sie: Zu jedem Zeitpunkt des Turniers gibt es mindestens zwei Spieler, die
von Spielen bestritten haben.
193–206) Die folgenden Aufgaben sollen mit dem Inklusions-Exklusionsprinzip bearbeitet werden!
193–195) “Eine Person kann Sprache X” ist hier immer so aufzufassen, dass die Person notwen-
digerweise X spricht, eventuell aber auch noch weitere Sprachen.
193) In einer Menge von n Personen können 10 Personen Deutsch, 7 Englisch, 5 Französisch, 6
Deutsch und Englisch, 4 Deutsch und Französisch, 3 Englisch und Französisch, 3 alle drei Sprachen
und niemand keine der drei Sprachen. Wie groß ist n?
@@ -646,11 +644,11 @@ oder fünfte Potenz einer natürlichen Zahl sind?
oder sechste Potenz einer natürlichen Zahl sind?
198) Wieviele natürliche Zahlen n mit 1 ≤ n ≤ 103 gibt es, die durch 3 und 5, aber weder durch
9 noch durch 11 teilbar sind?
199) Wieviele natürliche Zahlen n mit 1 ≤ n ≤ 104 gibt es, die durch 9 und 11, aber weder durch
5 noch durch 7 teilbar sind?
12
�199) Wieviele natürliche Zahlen n mit 1 ≤ n ≤ 104 gibt es, die durch 9 und 11, aber weder durch
5 noch durch 7 teilbar sind?
200)�200) Wieviele natürliche Zahlen n mit 1 ≤ n ≤ 104 gibt es, die durch 3, 5 und 7, aber weder
durch 9 noch durch 11 teilbar sind?
201) Wie viele natürliche Zahlen n mit 1 ≤ n ≤ 1000 gibt es, die durch 3, 5 oder 13 teilbar sind?
Wie viele sind weder durch 3, noch durch 5, noch durch 13 teilbar?
@@ -658,7 +656,7 @@ Wie viele sind weder durch 3, noch durch 5, noch durch 13 teilbar?
Quadratzahlen, noch dritte, noch 4. Potenzen natürlicher Zahlen sind?
203) Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a, b, c, d,
e, f, g, in denen weder der Block abcd“ noch der Block fa“ vorkommt.
” ”
204) Man bestimme die Anzahl aller Anordnungen (Permutationen) der Buchstaben a, b, c, d,
e, f, in denen weder der Block bcf“ noch der Block eb“ vorkommt.
” ”
@@ -694,24 +692,20 @@ Ecke ziehen kann, wenn er immer nur nach rechts oder oben ziehen und kein Feld o
Hauptdiagonale berühren darf.
Hinweis: Man zeige, dass die gesuchte Zahlenfolge und die Folge der Catalanzahlen die selbe
Rekursion erfüllen.
1 2n
�
210) Sei Cn die n-te Catalan-Zahl gegeben durch Cn = n+1 n . Man zeige für n ≥ 1 die
gleichwertigen Darstellungen
� � � �
2n 2n 2 · 6 · . . . · (4n − 2)
(a) Cn = − , (b) Cn = .
n n+1 2 · 3 · . . . · (n + 1)
13
� 1 2n
�
210) Sei Cn die n-te Catalan-Zahl gegeben durch Cn = n+1 n . Man zeige für n ≥ 1 die
gleichwertigen Darstellungen
� � � �
2n 2n 2 · 6 · . . . · (4n − 2)
(a) Cn = − , (b) Cn = .
n n+1 2 · 3 · . . . · (n + 1)
211)�211) Man zeige, dass die Folge der Catalan-Zahlen Cn , n ≥ 0, gegeben ist durch die Rekursion
4n + 2
C0 = 1, Cn+1 = · Cn (n ≥ 0).
n+2
Hinweis: Man zeige zunächst die Darstellung (b) aus der vorigen Aufgabe für Cn .
212) Wie viele Möglichkeiten gibt es, 2n Punkte auf einer Geraden so oberhalb der Geraden
paarweise zu verbinden, dass sich die Verbindungslinien nicht kreuzen?
@@ -719,27 +713,27 @@ paarweise zu verbinden, dass sich die Verbindungslinien nicht kreuzen?
paarweise die Hände reichen, ohne dass eine Überkreuzung stattfindet?
214) Man finde alle Lösungen der Differenzengleichung
(a) 2xn+1 − 3xn + 1 = 0 (n ≥ 0),
(b) xn+1 − xn + 7 = 0 (n ≥ 0).
215) Man bestimme die allgemeine Lösung der Differenzengleichung
2
xn+1 = xn + 1 (für n ≥ 0)
3
und die partikuläre Lösung, die der Anfangsbedingung x0 = 6 genügt.
216) Man bestimme die allgemeine Lösung der Differenzengleichung
xn
xn+1 = , n = 0, 1, 2, . . .
1 + xn
mit x0 6= −1, −1/2, −1/3, . . . .
(Hinweis: Man benütze die Transformation xn = 1/yn .)
217) Gesucht ist die allgemeine Lösung der linearen Differenzengleichung
2
xn+1 = 32n xn + 3n , n = 0, 1, 2, . . .
218) Bestimmen Sie die Lösung der Differenzengleichung
xn+1 = (n + 1)xn + (n + 1)!, x0 = 1.
n 1
219) Bestimmen Sie die allgemeine Lösung der Differenzengleichung an = n+2 an−1 + n2 +3n+2 .
@@ -751,37 +745,38 @@ mit x0 6= −1, −1/2, −1/3, . . . .
222) Beim Sortieren von n Zahlen durch “Direktes Einfügen” gilt für die Anzahl vn der Vergleiche
(im ungünstigsten Fall)
v1 = 0 und vn = vn−1 + n − 1, n = 2, 3, . . .
14
�undund für die Zahl wn der Wertzuweisungen
w1 = 0 und wn = wn−1 + n + 1, n = 2, 3, . . . .
Warum? Man bestimme explizite Formeln für vn und wn .
223) Gesucht sind die allgemeinen Lösungen der linearen homogenen Differenzengleichungen
14
�223) Gesucht sind die allgemeinen Lösungen der linearen homogenen Differenzengleichungen
(a) xn+2 − 5xn+1 − 6xn = 0,
(b) xn+2 − 6xn+1 + 12xn = 0,
(c) xn+2 − 5xn+1 + 6.25xn = 0.
224) Gesucht sind die allgemeinen Lösungen der linearen homogenen Differenzengleichungen
(a) xn+2 − 7xn+1 + 12xn = 0,
(b) xn+2 + xn+1 + xn = 0,
(c) xn+2 − 8xn+1 + 16xn = 0.
225) Gesucht sind die allgemeinen Lösungen der linearen homogenen Differenzengleichungen
(a) xn+2 + 12xn+1 + 36xn = 0,
(b) xn+2 − 2xn+1 + 5xn = 0,
(c) xn+2 + 11xn+1 + 28xn = 0.
226) Gesucht sind die allgemeinen Lösungen der linearen homogenen Differenzengleichungen
(a) xn+2 + 3xn+1 + 2xn = 0,
(b) xn+2 − 6xn+1 + 25xn = 0,
(c) xn+2 + 11xn+1 + 30.25xn = 0.
227) Man bestimme die Lösung nachstehender Differenzengleichung zu den vorgegebenen An-
fangsbedingungen:
@@ -789,32 +784,33 @@ fangsbedingungen:
228) Gesucht ist die allgemeine Lösung der Differenzengleichung
xn+2 − 6xn+1 + 9xn = 8 + 3n , n = 0, 1, 2, . . .
229–234) Berechnen Sie die folgenden Summen durch Aufstellen und Lösen einer Rekursion mittels
Ansatzmethode.
Xn Xn
229) i 230) i2
i=1 i=1
n
X n
X
i
231) q 232) iq i
i=1 i=1
n
X n
X
233) i(i − 1) 234) i2 q i
i=1 i=1
15
�235–251)235–251) Lösen Sie die Rekursion mit der Ansatzmethode:
235) an = 2an−1 + 2n−1 (n ≥ 1), a0 = 1.
236) an = 2an−1 + 22n−2 (n ≥ 1), a0 = 5.
237)15
�237) an = 3an−1 + 3n−1 (n ≥ 1), a0 = 2.
238) an = 5an−1 + 2n−1 − 6n5n (n ≥ 1), a0 = 2.
239) an = 2an−1 + (1 + 2n )2 (n ≥ 1), a0 = 2.
240) an + an−1 + an−2 = 1 + sin(nπ/3) (n ≥ 2), a0 = 3, a1 = −1.
@@ -852,12 +848,13 @@ bezeichne die Anzahl der möglichen Folgen der Länge n.
259) an sei die Anzahl aller 0-1-Folgen der Länge n, in denen es keine benachbarten Nullen gibt.
260) an sei die Anzahl aller n-stelligen Zahlen, in denen je 3 aufeinander folgende Ziffern keinen
Block der Form 000, 111, 222, . . . , 999 bilden.
16
�261)261) Lösen Sie das System von Rekursionen an+1 = 2an + 4bn , bn+1 = 3an + 3bn (n ≥ 0) mit
den Startwerten a0 = 1, b0 = −1, indem Sie das System in eine äquivalente Rekursion zweiter
Ordnung umformen.
262)16
�262) Lösen Sie das System von Rekursionen an+1 = 3an + 5bn , bn+1 = 4an + 4bn (n ≥ 0) mit den
Startwerten a0 = 1, b0 = 2, indem Sie das System in eine äquivalente Rekursion zweiter Ordnung
umformen.
263) Lösen Sie das System von Rekursionen an+1 = 2an + 5bn , bn+1 = 4an − bn (n ≥ 0) mit den
@@ -881,41 +878,33 @@ Startwerten a0 = b0 = 1 unter Benützung erzeugender Funktionen.
274) Man löse das System von Rekursionen an+1 = 3an + 5bn , bn+1 = 4an + 4bn (n ≥ 0) mit den
Startwerten a0 = b0 = 2 unter Benützung erzeugender Funktionen.
275)
(a) Im nachstehenden Graphen gebe man je ein Beispiel für eine Kantenfolge, die kein Kantenzug
ist, einen Kantenzug, der keine Bahn ist, bzw. eine Bahn, jeweils vom Knoten 6 zum Knoten
1 an.
(b) Desgleichen finde man eine geschlossene Kantenfolge, die kein geschlossener Kantenzug ist,
einen geschlossenen Kantenzug, der kein Zyklus ist, bzw. einen Zyklus, jeweils durch den
Knoten 5.
(c) Man zeige, dass G schwach, aber nicht stark zusammenhängend ist, und bestimme die
starken Zusammenhangskomponenten.
1 2
17
� 1 28 3
8 37 4
6 5
7 4
6 5
276–278)17
�276–278) Man bestimme G1 ∩ G2 und G1 ∪ G2 :
276) G1 : V (G1 ) = {1, 2, . . . , 8}, E(G1 ) = {hx, yi | x teilt y, x < y},
G2 : V (G2 ) = {1, 2, . . . , 5}, E(G2 ) = {hx, yi | x < y ≤ x + 3}.
277) G1 : V (G1 ) = {1, 2, . . . , 7}, E(G1 ) = {hx, yi | x < y ≤ x + 2},
@@ -924,7 +913,7 @@ Startwerten a0 = b0 = 2 unter Benützung erzeugender Funktionen.
G2 : V (G2 ) = {1, 2, . . . , 9}, E(G2 ) = {hx, yi | xy < 25, x < y}.
279–289) Die Abbildungen aller Graphen Gi , auf die in den folgenden Aufgaben
Bezug genommen wird, finden Sie auf Seite 21.20.
279) Man bestimme alle Quadrupel (a, b, c, d), a, b, c, d ∈ {1, 2, . . . , 7}, sodass der von den Knoten
a, b, c, d in G1 aufgespannte Teilgraph mit G2 identisch ist.
280) Man bestimme alle Quadrupel (a, b, c, d), a, b, c, d ∈ {1, 2, . . . , 7}, sodass der von den Knoten
@@ -932,7 +921,6 @@ a, b, c, d in G3 aufgespannte Teilgraph mit G4 identisch ist.
281) Man bestimme die kleinste transitive Relation R, die G1 (als Relation aufgefasst) umfasst.
282) Man bestimme die kleinste transitive Relation R, die G3 (als Relation aufgefasst) umfasst.
283) Konstruieren Sie, wenn möglich einen ungerichteten Graphen mit den Graden
(a) 2, 2, 3, 3, 4, 4
(b) 2, 3, 3, 4, 4, 4
@@ -941,23 +929,18 @@ a, b, c, d in G3 aufgespannte Teilgraph mit G4 identisch ist.
284) Ein schlichter Graph G = (V, E) heißt kubisch, wenn jeder Knoten v ∈ V Knotengrad
d(v) = 3 hat.
(a) Geben Sie ein Beispiel für einen kubischen Graphen mit α0 (G) = 6 an!
(b) Gibt es einen kubischen Graphen mit ungerader Knotenanzahl α0 (G)?
(c) Zeigen Sie, daß es zu jedem n ≥ 2 einen kubischen Graphen mit α0 (G) = 2n gibt!
18
�285)285) Man bestimme die starken Zusammenhangskomponenten des Graphen G1 .
286) Man bestimme die starken Zusammenhangskomponenten des Graphen G3 .
287) Man bestimme die starken Zusammenhangskomponenten des Graphen G5 .
288) Man bestimme die starken Zusammenhangskomponenten des Graphen G7 .
289) Sei Ḡ7 jener Graph, der aus G7 durch Umdrehen aller Kantenrichtungen entsteht. Man
bestimme die starken Zusammenhangskomponenten und die Reduktion Ḡ7RḠ7 R des Graphen Ḡ7 .
290) Bezeichne G = (V, E) einen gerichteten Graphen, V die Knoten-, E ⊆ V 2 die Kantenmenge.
Definitionsgemäß heißen zwei gerichtete Graphen Gi = (Vi , Ei ), i = 1, 2, isomorph, wenn es eine
bijektive Abbildung f : V1 → V2 gibt mit: (x, y) ∈ E1 (d.h. die Knoten x und y sind in G1 durch
@@ -967,7 +950,8 @@ G2 durch eine Kante verbunden sind).
(a) Skizzieren Sie zwei gerichtete Graphen Gi = (Vi , Ei ) mit |Vi | = 6 (i = 1, 2), die nicht
isomorph sind.
18
� (b) Begründen Sie, warum die von Ihnen gewählten Beispiele tatsächlich nicht isomorph im
Sinne obiger Definition sind.
(c) Wieviele Kanten muss ein stark zusammenhängender gerichteter Graph mit sechs Knoten
@@ -978,8 +962,11 @@ G2 durch eine Kante verbunden sind).
Knotengrade und zeige, dass die Anzahl der Knoten, die einen ungeraden Knotengrad besitzen,
gerade ist. Gilt diese Aussage in jedem ungerichteten Graphen?
292) Welche der nachstehenden Adjazenzmatrizen stellt einen Baum dar?
0 0 0 0 0 1
0 0 0 0 0 1
0 0 0 1 0 1 0 0 1 0 0 0
0 0 0 0 1 1 0 1 0 1 0 1
@@ -996,7 +983,7 @@ gerade ist. Gilt diese Aussage in jedem ungerichteten Graphen?
293–302) Die Abbildungen aller Graphen Gi , auf die in den folgenden Aufgaben
Bezug genommen wird, finden Sie auf Seite 21.20.
293) Man bestimme die Adjazenzmatrix AG1 und die Potenz A2G1 .
294) Man bestimme die Adjazenzmatrix AG3 und die Potenz A2G3 .
295) Sei Ḡ5 jener Graph, der aus G5 durch Umdrehen aller Kantenrichtungen entsteht. Man
@@ -1006,9 +993,7 @@ folgen der Länge 3 von 4 nach 6.
4 liegt.
297) Sei Ḡ5 jener Graph, der aus G5 durch Umdrehen aller Kantenrichtungen entsteht. Man
bestimme im Graphen Ḡ5 die Anzahl der Zyklen der Länge 3, auf denen der Knoten 4 liegt.
19
�298)298) Man bestimme im Graphen G9 mit Hilfe von A3G9 die Anzahl der Dreiecke (d. h. die Anzahl
der Kreise der Länge 3).
299) Man bestimme im Graphen G10 mit Hilfe von A3G10 die Anzahl der Dreiecke (d. h. die Anzahl
der Kreise der Länge 3).
@@ -1023,7 +1008,7 @@ falls eine.
2019
� 2 7
G1 G2 d
1
@@ -1037,19 +1022,19 @@ falls eine.
6 a b c
4 5
8 7 6
G5 4
G6
1 5 1 2
4 3
2 3
8 3 4 1 2 3
1 2 7
G8
G7 4 5
6
5 6 11 12 9 10
13 14 7
1 3 4 3
G9 4 G10 5
@@ -1063,12 +1048,12 @@ G11
6 7 8
7
8 7 6 5
G12 3 G13
1 4 6
8
2
5 1 2 3 4
@@ -1077,7 +1062,7 @@ G12 3
2120
�303) Man zeige, dass es in einem schlichten, gerichteten Graphen G = hV, Ei immer zwei Knoten
x, y ∈ V , x 6= y, gibt mit gleichem Weggrad d+ (x) = d+ (y), wenn es keinen Knoten x ∈ V (G)
mit Weggrad d+ (x) = 0 gibt.
@@ -1124,7 +1109,7 @@ gen:
2221
�317) Zum Abarbeiten der Knoten eines Binärbaumes verwendet man gerne rekursive Algorithmen,
die in wohldefinierter Reihenfolge die folgenden Schritte ausführen:
@@ -1169,13 +1154,13 @@ Kruskalalgorithmus einen minimalen und einen maximalen spannenden Baum.
4
320) x = 2 321) x = 3
322) x = 4 323) x = 5
2322
�324) In der folgenden schematisch skizzierten Landkarte sind für eine bestimmte Fracht die
Transportkosten zwischen einzelnen Orten angegeben. Bestimmen Sie mit Hilfe des Dijkstra-
Algorithmus einen billigsten Weg vom Ort P1 zum Ort P10 .
@@ -1191,8 +1176,7 @@ Algorithmus einen billigsten Weg vom Ort P1 zum Ort P10 .
1
10 2
P4 4 P8
9 1 9
10 2
1
@@ -1204,7 +1188,6 @@ einen Entfernungsbaum bezüglich des Knotens v0 .
v1 v2
8
1 3
1 7
v0 4 v3
@@ -1236,12 +1219,12 @@ die inverse Permutation π −1 : � �
π= .
358769412
2423
�329) Man bestimme zu den Permutationen
� � � �
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
σ= , ρ=
1 4 5 2 3 7 6 8 5 4 2 1 8 7 6 3
die Permutationen σ ◦ ρ2 und σ −1 ρ−1 σ 2 sowie deren Zyklendarstellungen und Vorzeichen.
330) Gegeben sind die Permutationen π = (1346), ρ = (134562) und σ = (126)(35) der S6 . Man
@@ -1262,7 +1245,7 @@ die Zyklendarstellung, sowie die Zyklendarstellung ohne Klammern an:
Menge {0, 1, . . . , 9} bijektiv sind, d.h. Permutationen festlegen.
334) Schreiben Sie π aus Aufgabe 328 als Produkt von Zweierzyklen.
335) Sei eine Permutation π von {1, 2, . . . , n} in zweizeiliger Darstellung gegeben. Unter der
Inversionstafel von π versteht man die Folge (b1 , . . . , bn ),bn), wobei bk ≥ 0 angibt, wieviele größere
Zahlen in der zweiten Zeile links vom Element k stehen. Bestimmen Sie für die Permutation π
aus Aufgabe 328) die Inversionstafel.
Wie kann man bei Kenntnis der Inversionstafel die Permutation rekonstruieren? Demonstrieren
@@ -1290,18 +1273,18 @@ eine Halbgruppe ist. Gibt es ein neutrales Element? Wenn ja, welche Elemente hab
A∗ , B ∗ , A∗ B, AB ∗ , (A ∪ B)∗ und ABA∗ B.
2524
�339–357) Untersuchen Sie, ob die Menge M mit der Operation ◦ ein Gruppoid, eine Halbgruppe,
ein Monoid bzw. eine Gruppe ist:
339) M = {0, 1, 2}, m ◦ n = min(m + n, 2) 340) M = {0, 1, 2, 3}, m ◦ n = min(mn, 3)
341) M = {−2, −1, 0, 1, 2}, m ◦ n = mn 342) M = {z ∈ C | |z| = 2}, z1 ◦ z2 = z12z2
343) M = {z ∈ C | |z| = 1}, z1 ◦ z2 = z1 z2 344) M = {z ∈ C | |z| = 2}, z1 ◦ z2 = z1 z2
345) M = {z ∈ C | |z| = 2 oder |z| = 1221 }, z1 ◦ z2 = z1 z2
346) M = P(A), d. h. die Potenzmenge der Menge A, B ◦ C = B ∪ C.
347) M = P(A), d. h. die Potenzmenge der Menge A, B ◦ C = B ∩ C.
348) M = P(A), d. h. die Potenzmenge der Menge A, B◦C = B△C (die symmetrische Differenz).
349) M = P(A), d. h. die Potenzmenge der Menge A, B ◦ C = B \ C (die Mengendifferenz).
a+b
350) M = Q, a ◦ b = a − b. 351) M = {x ∈ Q | x ≥ 0}, a ◦ b = 1+ab .
352) M = Q, a ◦ b = ab + 1. 353) M = Q \ {1}, a ◦ b = a + b − ab.
354) M = Q \ {0}, a ◦ b = a/b. 355) M = Q \ {−1}, a ◦ b = a + b + ab.
@@ -1337,7 +1320,7 @@ dann Untergruppe von G, wenn
(i) a, b ∈ U ⇒ ab ∈ U, (ii) e ∈ U, (iii) a ∈ U ⇒ a−1 ∈ U
2625
�für alle a, b ∈ G erfüllt ist. Dies ist genau dann der Fall, wenn a, b ∈ U ⇒ ab−1 ∈ U .
366) Man zeige: Eine nichtleere Teilmenge U einer endlichen Gruppe G ist genau dann Unter-
gruppe von G, wenn
@@ -1378,15 +1361,15 @@ von U . Ist U Normalteiler von S3 ?
375) Sei U die von (123) erzeugte Untergruppe der S3 . Man bestimme die Linksnebenklassen
von U . Weiters stelle man fest, ob U Normalteiler von S3 ist und bestimme gegebenenfalls die
Gruppentafel der Faktorgruppe S3 /U .
376) Es sei U eine Untergruppe der Gruppe (G, ◦).G. Man zeige, dass die Relation a ∼ b ⇐⇒ a ◦ U =
b ◦ Ub◦U eine Äquivalenzrelation auf G ist und dass die Äquivalenzklassen von ∼ die Links-
nebenklassenLinksnebenklassen
von U in G sind.
377) Man zeige, dass die von 3̄ erzeugte Untergruppe U von hZ9 , +i ein Normalteiler von hZ9 , +i
ist und bestimme die Gruppentafel der Faktorgruppe Z9 /U .
2726
�378) Man zeige, dass die von 4̄ erzeugte Untergruppe U von hZ12 , +i ein Normalteiler von hZ12 , +i
ist und bestimme die Gruppentafel der Faktorgruppe Z12 /U .
379) Man zeige, dass die von 5̄ erzeugte Untergruppe U von hZ15 , +i ein Normalteiler von hZ15 , +i
@@ -1431,12 +1414,12 @@ von +2 an.
bezüglich der Addition ist (die jeweils komponentenweise definiert sein soll), sowie dass f (0, 1) =
(0, 1, 1, 2), f (1, 0) = (1, 0, 2, 0). Man ermittle daraus f (w) für alle w ∈ (Z3 )2 .
2827
�399) Wie Bsp. 398) für f (1, 0) = (0, 1, 2, 1), f (0, 1) = (1, 0, 0, 2).
400) Wie Bsp. 398) für f (1, 0) = (1, 0, 0, 2), f (1, 1) = (1, 2, 0, 1).
401) Wie Bsp. 398) für f (2, 0) = (0, 1, 2, 2), f (1, 2) = (2, 2, 1, 0).
402) Man bestimme die primen“ Restklassen modulo 9, d. h. alle Restklassen ā für die gilt
”
ggT(a, 9) = 1. Man zeige, dass die Menge Γ9 dieser primen Restklassen bezüglich der Restklas-
senmultiplikation eine Gruppe bildet.
403) Wie Bsp. 402) für die primen Restklassen modulo 16.
@@ -1479,7 +1462,7 @@ modulo 2.
420) Von der Menge K ⊆ C sei bekannt: i) R ⊆ K, ii) 1 + 3i ∈ K und iii) hK, +, ·i ist ein Körper
(mit der Addition bzw. Multiplikation aus C). Zeigen Sie, dass K = C sein muss.
2928
�421) Von der Menge K ⊆ C sei bekannt: i) R ⊆ K, ii) 1 − i ∈ K und iii) hK, +, ·i ist ein Körper
(mit der Addition bzw. Multiplikation aus C). Zeigen Sie, dass K = C sein muss.
422) Gibt es eine Menge K mit R ( K ( C, die mit der üblichen Addition bzw. Multiplikation
@@ -1529,7 +1512,7 @@ erhalten bleiben:
von Rx mit a0 = 0. Zeigen Sie: I ist ein Ideal von Rx.
3029
�437) Seien I1 , I2 zwei Ideale eines Ringes R. Zeigen Sie, dass dann I1 ∩ I2 ein Ideal von R ist.
Gilt dies auch für I1 ∪ I2 ?
438) Sei hR, +, ·i ein beliebiger
@@ -1577,7 +1560,7 @@ bordnung.
3130
�455–460) Bildet R2 mit den angegebenen Operationen einen Vektorraum über R?
455) (x1 , x2 ) + (y1 , y2 ) = (x1 + y1 , 0), λ(x1 , x2 ) = (λx1 , 0).
456) (x1 , x2 ) + (y1 , y2 ) = (0, x2 + y2 ), λ(x1 , x2 ) = (0, λx2 ).
@@ -1622,7 +1605,7 @@ x3 enthält.
484) Bestimmen Sie den kleinsten Teilraum des Vektorraumes aus 482) der die Polynome x − x2
und x + x3 enthält.
3231
�485) Bestimmen Sie den kleinsten Teilraum des Vektorraumes aus 482) der die Polynome 2x2 +
x − 1, 3x2 − x + 2 und 5x2 − 5x + 8 enthält.
486) Bestimmen Sie den kleinsten Teilraum des Vektorraumes aus 482) der die Polynome 1 + x −
@@ -1660,49 +1643,49 @@ sind, wenn x1 − x2 , x2 , x2 − x3 linear unabhängig sind.
(0, 7, −1, 3), (−3, 1, 0, −4).
503) Untersuchen Sie, ob die folgenden Vektoren des Z45 linear unabhängig sind: (1, 2, 3, 4),
(2, 3, 4, 1), (3, 4, 2, 1).
P nPn i
504) Sei V = i=0 ai x | ai ∈ R, n ∈ N der Vektorraum aller Polynome mit reellen Koeffi-
zienten. Untersuchen Sie, ob 1 + x + x3 , 3 − x + x2 und −5 + x + x2 − x3 linear unabhängig
sind.
505) Wie 504, nur für 1 − x + x3 , 3 − x2 + x3 und −5 + 3x + x2 − 4x3 .
3332
�506) Wie 504, nur für 1 − x − 3x2 , 2 − 2x2 und 3 + 3x − 2x2 .
507) Sei V = {f | f : R → R} der Vektorraum aller reellwertigen Funktionen. Untersuchen Sie,
ob f und g mit f (x) = sin(x) und g(x) = cos(x) linear unabhängig sind.
508) Wie 507, nur für f (x) = sin(x) und g(x) = sin(2x).
509) Wie 507, nur für f (x) = cos(x) und g(x) = cos(2x).
510) Wie 507, nur für f (x) = cos(x) und g(x) = ex .
511) Wie 507, nur für f, g, h mit f (x) = e−x , g(x) = ex und h(x) = xex .xex.
512) Wie 507, nur für f, g, h mit f (x) = ex , g(x) = xex und h(x) = x2 ex .
513) Wie 507, nur für f, g, h mit f (x) = 1, g(x) = ex und h(x) = e3x .
514) Sei � �
1 2
A= .
3 −2
Untersuchen Sie, ob die Matrizen I2 , A und A2 im Vektorraum der reellen 2×2-Matrizen linear
unabhängig sind.
515) Sei � �
−1 1
A= .
3 −2
Untersuchen Sie, ob die Matrizen I2 , A und A2 im Vektorraum der reellen 2×2-Matrizen linear
unabhängig sind.
516) Sei � � � �
1 2 1 1
A= und B = .
3 −1 −2 3
Untersuchen Sie, ob die Matrizen A, B und B 2 im Vektorraum der reellen 2×2-Matrizen linear
unabhängig sind.
517) Sei � � � �
1 2 1 1
A= und B = .
3 −1 −2 3
Untersuchen Sie, ob die Matrizen A, B und A · B im Vektorraum der reellen 2×2-Matrizen linear
unabhängig sind.
518) Beweisen Sie, dass jede quadratische Matrix A als Summe einer symmetrischen Matrix B
(d.h., B = B T ) und einer schiefsymmetrischen Matrix C (d.h., C = −C T ) geschrieben werden
kann. (Hinweis: Wählen Sie B = 1221 (A + AT ).) Wie sieht diese Zerlegung konkret für die Matrix
1 −2 2
A = 4 1 1
@@ -1718,10 +1701,10 @@ ist.
519) A x2
= 520) A x2
=
x1 − 2x3 x1 − 3x3
x3 x3
3433
�
x1 � �
3x 1 + 5x 2 − x 3
@@ -1734,24 +1717,24 @@ Sie, dass U und W Teilräume von V sind und bestimmen Sie deren Dimension.
Sie, dass U und W Teilräume von V sind und bestimmen Sie deren Dimension.
524) Sei V = C3 , U = {(z1 , z2 , z3 ) ∈ V | z1 = 2z2 = 3z3 }, W = {(z1 , z2 , z3 ) ∈ V | z2 = 0}. Zeigen
Sie, dass U und W Teilräume von V sind und bestimmen Sie deren Dimension.
� � � � � �
2 2 1 2 1
525) Sei f : R → R die lineare Abbildung mit f = f = . Bestimmen
0 3 −2
Sie ker(f ) und f (R2 ) sowie dim(ker(f )) und den Rang von f . Verifizieren Sie die Beziehung
dim(ker(f )) + rg(f ) = dim R2 und bestimmen Sie die Matrix von f bezüglich der kanonischen
Basis.
� � � � � �
2 2 0 3 1
526) Sei f : R → R die lineare Abbildung mit f = f = . Bestimmen
1 2 −1
Sie ker(f ) und f (R2 ) sowie dim(ker(f )) und den Rang von f . Verifizieren Sie die Beziehung
dim(ker(f )) + rg(f ) = dim R2 und bestimmen Sie die Matrix von f bezüglich der kanonischen
Basis.
� � � � � � � �
2 2 1 1 2 0
527) Sei f : R → R die lineare Abbildung mit f = ,f = . Bestimmen
1 0 1 1
Sie ker(f ) und f (R2 ) sowie dim(ker(f )) und den Rang von f . Verifizieren Sie die Beziehung
dim(ker(f )) + rg(f ) = dim R2 und bestimmen Sie die Matrix von f bezüglich der kanonischen
Basis.
@@ -1759,9 +1742,9 @@ Basis.
vier Wochen eines Monats sei wie folgt gegeben:
Woche / Rohstoff R1 R2 R3
1. Woche 8 4 12
2. Woche 10 6 5
3. Woche 7 8 5
4. Woche 11 7 9
Diese Rohstoffe sollen bei einem von zwei Lieferanten L1 , L2 bezogen werden, wobei die Rohstoff-
@@ -1778,7 +1761,7 @@ sie für alle vier Wochen. Soll der Produzent beim Lieferanten L1 oder L2 beste
3534
�529) Drei Produkte P1 , P2 , P3 werden aus Rohstoffen R1 und R2 hergestellt. Die Herstellungs-
kosten setzen sich aus den Rohstoffpreisen und den Arbeitskosten zusammen. Die benötigten
Resourcen sind in der folgenden Tabelle gegeben.
@@ -1820,10 +1803,10 @@ B = {x0 , x1 , . . . , xn } von V .
540) Wie 538) für die Abbildung F (p(x)) = p(x + 1) − p(x).
541) Sei V = R[x] der Vektorraum der Polynome in x mit Koeffizienten aus R. Sei weiters eine
Abbildung I definiert durch
n n
X X xk+1
I( ak xkx k ) = ak .
k+1
k=0 k=0
Untersuchen Sie, ob I eine lineare Abbildung ist. Ist diese Abbildung injektiv, surjektiv oder
@@ -1831,14 +1814,14 @@ bijektiv?
542) Wie 541) für die Abbildung S(p(x)) = p(x − 1).
3635
�543) Sei V = Rn [x] der Vektorraum der Polynome in x vom Grad ≤ n mit Koeffizienten aus R.
Sei weiters eine Abbildung A definiert durch
n
X n
X
A( ak xkx k ) = k(k − 1)ak xk−2 .
k=0 k=2
Zeigen sie, dass A linear ist und bestimmen Sie die Matrix von A bezüglich der Basis B =
{x0 , x1 , . . . , xn } von V .
@@ -1854,27 +1837,27 @@ nenfalls mit Hilfe des Gaußschen Eliminationsverfahrens alle Lösungen:
545–549) Bestimmen Sie mit dem Gaußschen Eliminationsverfahren die Lösung des Gleichungs-
systems über dem Körper K:
545)
a) K = R, b) Wie a), jedoch K = Z2 .
3x1 + x2 − 2x3 + x4 = 2
x1 + x2 − x3 − x4 = 1
5x1 + x2 − 3x3 + 3x4 = 1
546)
a) K = R, b) Wie a), jedoch K = Z2 .
−3x1 + x2 + 2x3 + x4 = 2
−x1 + x2 + x3 − x4 = 1
−5x1 + x2 + 3x3 + 3x4 = 1
547)
a) K = R, b) Wie a), jedoch K = Z3 .
2x1 + x2 + x3 + x4 = 1
x1 + x3 − 2x4 = 1
7x1 + x3 + x4 = 7
548)
a) K = Q, b) Wie a), jedoch K = Z3 .
2x1 + x2 + x3 = 0
x1 + x3 = 1
4x1 + x3 = 4
549)
a) K = Q, b) Wie a), jedoch K = Z11 .
2x1 + 5x2 − 2x3 = 5
3x1 + x3 = 4
− x2 + 2x3 = 1
@@ -1882,7 +1865,7 @@ systems über dem Körper K:
3736
�550) Wir betrachten Systeme von drei Ebenengleichungen fi (x, y, z) = ai1 x + ai2 y + ai3 z = bi
mit Lösungsmengen Li ⊆R3 , i = 1, 2, 3. Geben Sie jeweils eine Systemmatrix
@@ -1897,49 +1880,48 @@ mit geeigneten aij und bi aus R so an, dass die Li folgende Lage zueinander habe
551) Wie 550, aber mit
(a) L1 ∩ L2 = L1 ∩ L3 = L2 ∩ L3 ist die z-Achse.
(b) L1 ∩ L2 = ∅ und L1 ∩ L3 6= ∅ =
66= L2 ∩ L3 .
552–561) Bestimmen Sie den Rang der folgenden reellen Matrizen
552) 553)
1 2 3 4 5 −2 1 3 −4 5
2 3 4 5 6 −4 3 5 −6 7
3 4 5 6 7 5 −4 −6 7 −8
4 5 6 7 8 3 2 −4 5 −6
554) 555)
3 0 3 −1 5 1 −4 1 −2 3 5
−2 1 −1 1 1 1 5 2 3 −4 −6
2 4 5 6 7 1 6 3 −4 5 7
7 1 −2 3 8 1 7 −4 5 −6 −8
556) 557)
1 0 3 −1 5 1 −2 3 −4 5
2 3 4 5 6 −2 3 −4 5 −6
3 4 5 6 7 3 −4 5 −6 7
4 5 6 7 8 −4 5 −6 7 −8
558) 559)
1 −2 3 −4 5 6 1 −2 3 −4 5 6
−2 3 −4 5 −6 −7 −2 3 −4 5 −6 7
3 −4 5 −6 7 8 3 −4 5 −6 7 8
−4 5 −6 7 −8 −9 −4 5 −6 7 −8 9
560) 561)
0 −1 −1 −3 0 0 −3 −2 3 −4 0 6
−2 1 −4 5 −6 −1 −2 3 −4 −2 −6 2
3 −1 3 −6 2 1 3 −4 0 1 −3 3
−4 1 −2 7 −3 −1 −5 1 −1 0 −3 0
3837
�562) Sei n ≥ 1. Bestimmen Sie den Rang der folgenden Matrix über R:
2 5 8 . . . 3n − 1
@@ -1954,22 +1936,24 @@ mit geeigneten aij und bi aus R so an, dass die Li folgende Lage zueinander habe
2 6 10 . . . 4n − 2
6 10 14 . . . 4n + 2
.
.. .. .. ...
..
. . . . .
4n − 2 4n + 2 4n + 6 . . . 8n − 6
564–567) Bestimmen Sie die inverse Matrix A−1 .
564) 565)
−1 3 2 1 3 2
A = −2 4 6 . A= 2 4 6 .
1 −2 2 −1 −2 2
566) 567)
2 4 6 −1 −2 2
A= 1 3 2 . A = −1 −3 2 .
−1 −2 2 2 4 6
568) Berechnen Sie zur folgenden Matrix A mit Einträgen aus R die Matrix A3 :
@@ -1995,7 +1979,7 @@ bestimme man C = AB und verifiziere den Determinantensatz det C = det A · det B
3938
�571) Für die Matrizen A, B mit
1 3 2 −1 3 2
@@ -2048,11 +2032,11 @@ von x die inverse Matrix A−1 .
für das die Matrix regulär ist und bestimmen Sie für dieses p die inverse Matrix A−1 .
4039
�
6 3 7 2 2 0
585) A = 8 5 9 586) A = 4 1 1
9 3 10 0 1 2
587–594) Man bestimme die Eigenwerte der Matrix A sowie zu jedem Eigenwert alle Eigenvekto-
ren:
@@ -2060,10 +2044,10 @@ ren:
3 −1 1 −1
587) A = 588) A =
−1 3 −1 1
0 12 2112
5 −8 10
589) A = 2112 0 12 590) A = −8 11 2
1 1
2 2 0 10 2 2
@@ -2093,9 +2077,9 @@ ren:
(a) Für welche i ∈ {1, 2, 3} gibt es eine lineare Abbildung fi : R2 → R3 mit folgenden Eigen-
schaften?
• f1 : (1, 0) 7→ (2, 1, 0), (0, 1) 7→ (1, 2, 3)
• f2 : (1, 0) 7→ (2, 1, 0), (0, 1) 7→ (1, 2, 3), (1, 1) 7→ (2, 2, 2)
• f3 : (1, 0) 7→ (2, 1, 0), (0, 1) 7→ (1, 2, 3), (1, 1) 7→ (3, 3, 3)
(b) Wählen Sie als f eine lineare Abbildung fi aus (a). Geben Sie die f zugehörige Matrix A,
die dazu transponierte Matrix AT sowie jene Matrix B an, welche g := f ◦ f T entspricht,
@@ -2109,7 +2093,7 @@ ren:
4140
�597) Für die Vektoren x = (1, 2, 3), y = (3, −1, 2) und z = (2, 2, 1) berechne man
(a) die Längen von x, y und z,
@@ -2145,9 +2129,9 @@ Berechnen Sie für die Vektoren x = (1, 2, 3) und y = (3, −1, 2)
(c) Sei U der Raum aller Vektoren x = (x1 , x2 , x3 ) ∈ R3 , für welche die Matrix
aa1 b 1b1 x 1
A = aa2 b 2b2 x 2
aa3 b 3b3 x 3
einen Rang ≤ 2 besitzt. Welche Dimension d hat U , sofern a = (a1 , a2 , a3 ) und b = (b1 , b2 , b3 )
linear unabhängig sind. (Begründung!)
@@ -2161,7 +2145,7 @@ Berechnen Sie für die Vektoren x = (1, 2, 3) und y = (3, −1, 2)
fahren von Gram-Schmidt eine Orthonormalbasis gebildet werden (wobei das gewöhnliche innere
Produkt zugrunde zu legen ist).
4241
�606) Man zeige, dass die Menge C = {000, 213, 022, 231} eine Untergruppe von hZ34 , +i bildet
und bestimme die Nebenklassen von C.
607) Zu den Nebenklassen aus Bsp. 606) sollen die Nebenklassenanführer mit minimalem Ge-
@@ -2181,7 +2165,7 @@ werden, das jedem Wort in Z52 ein entsprechendes Wort aus C zuordnet.
sowie die Menge C aller Codewörter.
0 1 0 0 1
H=H = 0 0 1 0 1
1 0 0 1 1
613) Für den Code aus Bsp. 612) sollen zu allen Wörtern vom Gewicht 1 und 2 die Syndrome
@@ -2201,7 +2185,7 @@ minimalem Gewicht aus und stelle ein entsprechendes Korrekturschema K(C) auf.
sowie die Menge C aller Codewörter.
0 0 1 0 1
H=H = 1 1 0 0 1
0 1 0 1 0
617) Für den Code aus Bsp. 616) sollen zu allen Wörtern vom Gewicht 1 und 2 die Syndrome
@@ -2210,7 +2194,7 @@ minimalem Gewicht aus und stelle ein entsprechendes Korrekturschema K(C) auf.
4342
�618–619) Es sei ein (n, k)-Linearcode durch die Generatormatrix G gegeben. Man bestimme n, k,
sowie eine Kontrollmatrix H, die möglichst viele Nullen enthält.
618) 619)
@@ -2232,5 +2216,5 @@ Fehlerwort vom Gewicht 1 als Nebenklassenanführer genommen werden kann.
44
�43
��