HUMBOLDT–UNIVERSITÄT ZU BERLIN

Mathematisch-Naturwissenschaftliche Fakultät II Institut für Mathematik Prof. PhD. Andreas Griewank Dr. Andrej Ponomarenko Dipl.-Ing. Heinz–Jürgen Lange

Humboldt-Universität zu Berlin, Institut für Mathematik, Unter den Linden 6, D-10099 Berlin

Klausur zur Vorlesung Mathematik für Informatiker I

Aufgabe 1: Gegeben seien zwei Vektoren:

u = (−2, 2, −1)^{T} und v = (−2, −1, 2)^{T}

a) Normalisiere die beiden und ergänze sie mit Hilfe des Kreuzproduktes zu einer rechtshändigen orthonormalen Basis in IR^{3} . (3 Punkte)

b) Betrachte den dritten Vektor

w = (−1, −1, 1)^{T}

und prüfe, ob u, v, w ein rechtshändiges System bilden. (2 Punkte)

c) Orthonormalisiere u, v, w mit Hilfe des Gram–Schmidt–Verfahrens. Vergleiche das Ergebnis mit a). (3 Punkte)

Aufgabe 2: Im islamischen Kalender hat jedes Jahr (fast) genau 354 Tage, und wir gehen davon aus, dass das europäische Jahr genau 365 Tage hat.

a) Verifiziere, dass 354 und 365 relativ prim sind. (3 Punkte)

b) Angenommen der 1.Januar und der 1.Tag des Ramadan (ein besonderer Fastenmonat für Muslime) fallen heute zusammen. Stelle die Gleichungen für x auf, die die folgende Frage beantworten: (3 Punkte)

Nach wievielen Tagen x ab heute (heute wird mitgezählt als Tag 1) fallen der 3.Februar und der 10.Tag des Ramadan zusammen?

c) Löse das in b) hergeleitete System. (3 Punkte)

Aufgabe 3:

a) Zeige, dass die komplexen Zahlen z = x + iy als Körper isomorph zu den reellen Matrizen

der Form

ϕ(z) = ( \begin{matrix}x & y \\ −y & x \end{matrix} ) ∈ IR^{2×2}

sind. Wie lässt sich der Betrag |z| durch ϕ(z) ausdrücken? (4 Punkte)

b) Betrachte die folgenden Urbildmengen

T r^{−1}(α) := {A ∈ IR^{n×n} | T r(A) = α}.

Überprüfe, ob die Mengen T r^{−1}(0) und T r^{−1}(1) als Unterräume des Vektorraumes IR^{n×n} affin und/oder linear sind. (3 Punkte)

Aufgabe 4: Mit beliebigen nicht verschwindenden Vektoren a, b ∈ IR^{n} und der Identitätsmatrix I betrachte die quadratische Matrix

A = I − ba^{T}

Untersuche, unter welchen Bedingungen an a und b es einen Skalar α ∈ IR gibt, so dass A eine Inverse besitzt und diese die Form

A^{−1} = I − αba^{T}

annimmt. Hinweis: Keinerlei Determinantenberechnung erforderlich? (4 Punkte)

Aufgabe 5: Betrachte das folgende System linearer Gleichungen

( \begin{matrix}1 & 0 & 2 & 1 \\ 1 & 2 & −1 & 0 \\ 1 & −4 & 2 & 1 \\ 1 & 0 & 1 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix} ) = ( \begin{matrix}4 \\ 2 \\ −2 \\ 2 \end{matrix} )

a) Löse dieses durch Anwendung des Gauß–Eliminationsverfahrens. (3 Punkte)

b) Überprüfe die in a) erhaltene Lösung für x_{3} mittels der Cramerschen Regel. (3 Punkte)

Zusatzaufgabe 6: Beim Karatsuba-Algorithmus erfüllt die Gesamtzahl OP S(p) der für die Multiplikation von zwei Polynomen der Ordnung 2^{p} erforderlichen Multiplikationen und Additionen/Subtraktionen die Rekursion

OP S(p) = 3 OP S(p − 1) + 2^{p+1}

a) Ausgehend von OP S(0) = 1 beweise durch Induktion, dass (4 Bonuspunkte)

OP S(p) ≤ \frac{4}{3}(1 + p)3^{p}

b) Bestimme die entprechende Gesamtzahl von Operationen bei der üblichen komponentenweisen Multiplikation von zwei Polynomen der Ordnung 2^{p}. Entscheide, welches Verfahren im Fall p = 5, d.h. bei der Multiplikation zweier Polynome der Ordnung 32, effektiver ist.

(4 Bonuspunkte)

phone: 030/2093-5820  fax: 030/2093-5848  e-mail: griewank@math.hu-berlin.de         andrej@math.hu-berlin.de
lange@math.hu-berlin.de                                         http://www.mathematik.hu-berlin.de/∼gaggle/MATHINF