VP ” Geometrisches Rechnen“

Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
SS 2016
Fachbereich
Computerwissenschaften
VP Geometrisches Rechnen“
”
1. Aufgabenblatt für VP am 18.3.2016
Beispiel 1 Im folgenden seien x, y, z ∈ N typisierte Variable. Das Prädikat S(x, y, z) gelte genau
dann wenn x + y = z ist. Entsprechend gelte P (x, y, z) g.d.w. x ∗ y = z und L(x, y) g.d.w. x < y ist.
Formulieren Sie die folgenden Sätze in der Prädikatenlogik:
1. Zu jedem x und jedem y gibt es ein z mit x + y = z .
2. Kein x ist kleiner als 0 .
3. Für alle x gilt: x + 0 = x .
4. Es gibt ein x mit x ∗ y = y für alle y .
Beispiel 2 Warum sind die folgenden Sätze der Umgangssprache nicht korrekt?
1. Der Gewinner erhält ein wertvolles Geschenk und eine Fernreise oder einen Geldpreis.
2. Bei rotem und gelbem Licht der Ampel hier halten.
3. Die Negationen der Aussage Alle Menschen sind sterblich :
• Kein Mensch ist sterblich.
• Alle Menschen sind unsterblich.
Beispiel 3 Jemand hat sich die Mühe gemacht, die Anzahl der Schritte zweier Algorithmen für
Inputgröße n exakt zu ermitteln, und hat festgestellt, daß der erste Algorithmus immer n log2 n
viele Schritte benötigt, wogegen der zweite Algorithmus immer 512n Schritte benötigt, jeweils gleich
für den besten/durchschnittlichen/schlimmsten Fall. Welchen Algorithmus würden Sie verwenden?
Warum?
Beispiel 4 Ordnen Sie die folgenden Terme (mit n ∈ N) gemäß deren asymptotischem Wachstum. Es soll also eine Sortierung f1 , f2 , f3 , . . . entstehen, sodaß fi ∈ O(fi+1 ). Weiters ist zwischen
aufeinanderfolgenden Termen in dieser Sortierung auch auf Θ-Äquivalenz zu prüfen.
√
n
n nn 1 n! 3n 32n log n n2 .
(3/4)n log2 (n!) n log3 n 22 3n 4log2 n 2log2 n
Natürlich dürfen Sie mathematisches Standardwissen verwenden, ohne dies extra zu beweisen, etwa
betreffend n! und log.
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.
Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
SS 2016
Fachbereich
Computerwissenschaften
VP Geometrisches Rechnen“
”
2. Aufgabenblatt für VP am 8.4.2016
Beispiel 5 Damit eine Menge M einen Vektorraum über einem Körper K bildet, muß unter anderem
gelten, daß für alle a ∈ M jeweils ein b ∈ M existiert, sodaß a + b = 0. Kann man folgern, daß ein
derartiges b für jedes a ∈ M eindeutig bestimmt ist? Warum (nicht)?
Beispiel 6 Seien a1 , . . . , an Vektoren aus einem Vektorraum V über einem Körper F , für ein n ∈ N.
Zeigen Sie: Falls ein Vektor a aus V sich durch zwei verschiedene Linearkombinationen von a1 , . . . , an
ausdrücken läßt, dann bilden a1 , . . . , an jedenfalls keine Basis von V .
Beispiel 7 In der Vorlesung wurde die Hypothese formuliert, daß man eine Basis eines Vektorraums
V auch so definieren könnte: Sei A := {a1 , . . . , an } für n Vektoren a1 , . . . , an aus V . Es gelte
(1) [A] = V ,
(2) ∀B (B ⊂ A ⇒ [B] ⊂ V ).
Beweisen Sie die Äquivalenz dieser Definition zu der in der Vorlesung formulierten Definition. (Dabei
soll X ⊂ Y bedeuten, daß X eine echte Teilmenge von Y ist.)
Beispiel 8 Wir betrachten den Vektorraum, der alle reellwertigen stetigen Abbildungen von R nach
R enthält. Offenbar sind die Funktionen sin, cos und exp Vektoren dieses Vektorraums. (Wie üblich
ist exp(x) := ex für alle x ∈ R.) Liegt exp im Teilraum [{sin, cos}]?
Beispiel 9 Sei n ∈ N. Was ist die Dimension des Vektorraums (über R), welcher von den n Vektoren
 






1
2
3
n
 2 
 3 
 4 
 n+1 
 






 






v1 =  3  , v2 =  4  , v3 =  5  , . . . , vn =  n + 2 
 .. 
 .. 
 .. 


..
 . 
 . 
 . 


.
n
n+1
n+2
2n − 1
aufgespannt wird?
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.
Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
Fachbereich
Computerwissenschaften
SS 2016
VP Geometrisches Rechnen“
”
3. Aufgabenblatt für VP am 15.4.2016
Beispiel 10 Beweisen Sie, daß die konvexe Hülle einer Menge M ⊂ R4 eine konvexe Menge ist.
Beispiel 11 Wir behaupten, daß die affine Hülle von fünf verschiedenen Punkten P1 , P2 , . . . , P5
des R6 nicht notwendigerweise immer einen Teilraum des R6 bildet. Ist diese Behauptung richtig?
Beweisen oder widerlegen Sie diese Behauptung.
Beispiel 12 Welche Punkte der komplexen Zahlenebene werden durch folgende drei Teilmengen
von C beschrieben?
M1 := {z ∈ C: |z| ≤ 1}
M2 := {a + ib: a, b ∈ R ∧ |a − 1| + |b| = 1}
M3 := {a + ib: a, b ∈ R ∧ max{|a|, |b|} ≤ 2}
Beispiel 13 Zeigen Sie, daß
|z1 · z2 | = |z1 | · |z2 |
und
|z1 + z2 | ≤ |z1 | + |z2 |
und
|z3−1 | = |z3 |−1
für alle z1 , z2 , z3 ∈ C mit z3 6= 0 gelten.
Beispiel 14 Für z1 ∈ C und z2 ∈ C \ {0} definieren wir
z − 1
z −i = 1
z1
z2
:= z1 · z2−1 . Lösen Sie damit die Gleichung
über C. (Ermitteln Sie also alle z ∈ C, für welche diese Gleichung erfüllt ist. Natürlich nehmen
wir dabei z1/z2 als z1 · z2−1 für z1 , z2 ∈ C.)
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.
Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
SS 2016
Fachbereich
Computerwissenschaften
VP Geometrisches Rechnen“
”
4. Aufgabenblatt für VP am 22.4.2016
Beispiel 15 Zeigen Sie, daß ein Quaternion P ∈ H genau dann ein Einheitsquaternion ist, wenn es
einen Winkel φ ∈ R sowie einen Einheitsvektor u ∈ R3 gibt, sodaß P = (cos φ, u sin φ).
Beispiel 16 Jemand behauptet, daß 1 und 4 Wurzeln des Polynoms x5 − 10x4 + 35x3 − 50x2 + 24x
aus R[x] sind. Verifizieren Sie diese Behauptung und bestimmen Sie alle weiteren Wurzeln durch
Durchdividieren durch die entsprechenden Faktoren. (Hinweis: Polynome dividiert man so, wie man
in der Schule das händische Dividieren gelernt hat.)
Beispiel 17 Berechnen Sie mittels des Euklidischen Algorithmus den größten gemeinsamen Teiler
von (x3 − 3x2 + 5x − 3) und (x3 − 1) aus R[x]. (Hinweis: Der normale“ Euklidische Algorithmus
”
funktioniert auch in Polynomringen.)
Beispiel 18 Finden Sie (quadratische) Beispielmatrizen, welche zeigen, daß
(1) AB 6= BA,
(2) AB = 0 6⇒ [A = 0 ∨ B = 0],
(3) (AB)−1 6= A−1 B−1 .
Beispiel 19 Berechnen Sie in Z7 :

 
1 2 3 4
6 5 5
 2 3 4 1   4 2 4

 
 3 4 1 2 · 6 2 5
4 3 2 1
1 5 0

3
2 

6 
6
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.
Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
SS 2016
Fachbereich
Computerwissenschaften
VP Geometrisches Rechnen“
”
5. Aufgabenblatt für VP am 29.4.2016
Beispiel 20 Leiten

a 0
A :=  0 1
c 0
Sie eine notwendige und hinreichende Bedingung dafür her, daß die Matrix

b
0 
d
invertierbar ist und berechen Sie dann A−1 .
Beispiel 21 Sei A eine invertierbare quadratische Matrix. Beweisen Sie explizit (ohne Verweis auf
das entsprechende Lemma aus der Vorlesung): At ist invertierbar und wir haben (At )−1 = (A−1 )t .
Beispiel 22 Wir nehmen an, daß das Gleichungssystem Ax = b konsistent ist, wobei A ∈ Mm×n (R).
Beweisen explizit (ohne Verweis auf das entsprechende Theorem aus der Vorlesung), daß die Lösung
eindeutig ist genau dann wenn der Rang von A gleich n ist.
Beispiel 23 Argumentieren Sie, warum die in der Vorlesung (in Lem. 89) angeführten elementaren
Zeilenumformungen den Rang einer Matrix nicht ändern.
Beispiel 24 Bringen Sie die folgende erweiterte Matrix durch elementare Zeilenumformungen in
eine Treppennormalform und lösen Sie damit das zugrundeliegende lineare Gleichungssystem.


0
0
1 0 2 0 6 0
 2
2
0 0 6 0 14 0 


 −1 −1 0 2 −1 0 3 1 


 −1 −1 −2 1 −6 0 −14 0 
−2 −2 0 0 −6 2 −6 0
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.
Ao.Univ.-Prof. Dr. Martin Held
Universität Salzburg
Fachbereich
Computerwissenschaften
SS 2016
VP Geometrisches Rechnen“
”
6. Aufgabenblatt für VP am 13.5.2016
Beispiel 25 Beweisen Sie, daß das Vertauschen zweier Spalten einer Matrix das Vorzeichen ihrer
Determinante aber nicht deren Absolutbetrag ändert.
Beispiel 26 Beweisen Sie:
(1) Die Determinante einer Matrix ist Null, falls sie zwei gleiche Spalten enthält.
(2) Die Determinante einer Matrix ändert sich nicht, wenn man zu einer Spalte ein Vielfaches einer
anderen Spalte dazu addiert.
Hinweis: Sie dürfen zum Beweis natürlich Lem. 96–98 voraussetzen.
Beispiel 27 Ermitteln Sie die folgenden Lösungen händisch(!) und kontrollieren Sie sie jeweils
mittels Mathematica. (Gauß-Elimination ist nicht zwingend notwendig. Wenn Sie dieses Beispiel
vorführen wollen, sollten Sie auch in der Lage sein, die Berechnung mittels Mathematica am PC im
Hörsaal vorzuführen!)
1. Lösen Sie über C das folgende lineare Gleichungssystem:
3a + 3b + c + d + e
2a + 2b + 2d + 2e
a + 4b + c + d + e
3a + 3b + d + e
a + 3b + c + d + e
2. Berechnen

1
 5

 1

 0
1
=
=
=
=
=
0
0
0
0
0
Sie die Determinante der Matrix

2 3 4 5
4 3 2 1 

0 1 0 1 
.
1 0 1 0 
2 3 2 1

 
2
2
 0   0
 
Beispiel 28 Bilden die Vektoren 
 6 , 3
0
4
 
 
1
−1
  2   0
, ,
  6   3
0
4


 eine Basis des R4 ?

Beispiel 29 Für welche rationale Werte von a hat das folgende System eine nicht-triviale Lösung?
Berechnen Sie die entsprechenden Lösungen.
x − 2y + 3z = 0
ax + 3y + 2z = 0
6x + y + az = 0
Diese Angaben sind unter www.cosy.sbg.ac.at/~held/teaching/geom rechnen/vp bsp.pdf auch
im WWW verfügbar. Bitte lösen Sie immer nur die für die nächste VP vorgesehenen Beispiele. Sofern
nicht explizit anders angegeben, sind alle Antworten detailliert zu begründen.

Download Report