Nelius/Nöcker

14. Übungsblatt

MATHEMATIK FÜR INFORMATIKER I (WS 2000/01)

Abgabe: Montag, 12.2.2001 bis 13.00 Uhr !!! Internet–Adresse der Vorlesung: http://math–www.uni–paderborn.de/~chris/index9.html

Benutze bei diesen Aufgaben \underline{keinen} Taschenrechner!

51. Aufgabe: Seien A := ( \begin{matrix}1 & 0 & 1 \\ −1 & 2 & 1 \\ 0 & 1 & 2 \end{matrix} ) ∈ M_{3}(IR) und b = ( \begin{matrix}2 \\ 1 \\ 1 \end{matrix} ) ∈ IR^{3}.

a) Beweise, daß die Matrix A invertierbar ist, und berechne nach dem Verfahren (10.28) die inverse Matrix von A.

b) Bestimme alle Lösungen des LGS’s Ax = b .

c) Kann es ein c ∈ IR^{3} geben, so daß das LGS Ax = c nicht lösbar ist? Begründe die Antwort!

d) Stelle die Matrix A als ein Produkt von Elementarmatrizen dar. Mache die Probe! (4)

52. Aufgabe: Seien A := ( \begin{matrix}1 & 0 & 1 & 1 & −1 \\ 2 & 1 & −1 & 1 & 0 \\ 3 & 1 & 0 & 2 & −1 \\ 1 & 1 & 0 & 0 & 0 \end{matrix} ) ∈ M_{4,5}(IR) und b = ( \begin{matrix}2 \\ 0 \\ 2 \\ 0 \end{matrix} ) , b′ = ( \begin{matrix}1 \\ 0 \\ 2 \\ 0 \end{matrix} ) ∈

IR^{4}. Bestimme die Lösungsmengen der LGS’e Ax = b und Ax = b′ mit Hilfe des Gauß-Algorithmus. (4)

53. Aufgabe: Löse das LGS ( \begin{matrix}1 & 0 & 2 \\ 0 & 1 & 3 \\ 1 & 1 & 0 \end{matrix} ) x = ( \begin{matrix}3 \\ 4 \\ 2 \end{matrix} ) über ZZ_{5}. Hierbei stehen die Zahlen

0, 1, 2, 3, 4 für die Restklassen modulo 5, und bei der Addition und Multiplikation dieser Zahlen ist immer modulo 5 zu rechnen! Gib die Lösungen explizit an. Wieviele Lösungen gibt es? (3)

Zum Ausklang der Übungen noch eine schöne Aufgabe, deren Text wieder einmal viel länger ist als die Lösung:

54. Aufgabe: Moderne Kommunikationsgeräte (wie z.B. Handies, Satelliten, CD-Player) arbeiten digital, d.h., alle Daten werden als Folge von 0 und 1 (sog. Bitströmen) dargestellt. Ein Problem ist dabei das Erkennen von Übertragungsfehlern, d.h. statt des gesendeten Bits a kommt das Bit 1 − a an. Solche Probleme werden in der Codierungstheorie behandelt. Dazu nutzt man lineare Gleichungssysteme und Matrizen.

1. Die einfachste Art, einen Fehler zu erkennen, ist, ein Bit a dreimal zu schicken, also aaa statt a. Drei Bits x_{1}x_{2}x_{3} werden dann vom Empfänger als Einheit gelesen. Das Wort ist richtig empfangen worden, wenn gilt

x_{2} = x_{3} und x_{1} = x_{3}.  (1)

Schreiben Sie diese Gleichungen in eine Matrixschreibweise vom Typ

H · ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} )

um, wobei alle Einträge modulo 2 gerechnet werden, da sie Bits darstellen! Bestimmen Sie die Menge aller Lösungen des Gleichungssystems (1) in ZZ_{2}. Die Elemente dieser Lösungsmenge sind 3-Bit-Worte x_{1}x_{2}x_{3} und werden Worte des Codes genannt.

2. Kommt nun ein Wort an, das kein Wort des Codes ist, so wird es korrigiert. Das geschieht wie folgt: zwei Bits sind gleich, ein Bit ist davon verschieden. Das ursprüngliche Bit ist dann gleich dem Wert, der zweimal vorkommt. Bsp: empfangen 101, dann ist das ursprünglich gesendete Bit 1. Wie lautet also der ursprünglich gesendete Bitstrom, wenn man folgende 3-Bit-Folge empfängt?

101 111 001 010 110 001 100

3. Das Problem ist: statt ursprünglich ein Bit werden nun 3 Bit gesendet, d.h., die Nachricht wird um den Faktor 3 aufgebläht. Mit sogenannten Hamming-Codes kann man einen kleineren Faktor erreichen. Man sendet immer 4 Bits x_{1}, x_{2}, x_{3}, x_{4} und fügt drei Kontrollbits y_{1}, y_{2}, y_{3} hinzu. Ein Codewort ist dann ein 7-Bit-Wort x_{1}x_{2}x_{3}x_{4}y_{1}y_{2}y_{3}, das folgendes Gleichungssystem erfüllt:

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

In der i-ten Spalte der Matrix steht also gerade die Zahl i in binärer Schreibweise (^{t}(0, 0, 1) steht also für binär (001), d.h. 1)! Codieren Sie alle 4-Bit-Worte x_{1}x_{2}x_{3}x_{4} mit diesem Code, indem Sie y_{1}, y_{2}, y_{3} bestimmen, so dass ^{t}(x_{1}, x_{2}, x_{3}, x_{4}, y_{1}, y_{2}, y_{3}) eine Lösung von (2) ist.

4. Zeigen Sie: Addiert man zwei Codeworte a, b ∈ ZZ_{2}^{7}, so ist das Wort c = a + b auch ein Codewort, d.h. eine Lösung von (2).

5. Man kann die fehlerhafte Übertragung des i-ten Bits (1 ≤ i ≤ 7) beim Codewort a = t(x_{1}, x_{2}, x_{3}, x_{4}, y_{1}, y_{2}, y_{3}) wie folgt in Formeln darstellen: man addiert den Einheitsvektor e_{i} ∈ ZZ_{2}^{7} (in Zeile i steht eine 1, sonst 0) zu a. Zeigen Sie: Multipliziert man die Matrix aus (2) von rechts mit a + e_{i}, so ist die Lösung gerade der Vektor, der transponiert die Binärdarstellung von i ist.

6. Man erhält also die ursprünglichen Bits zurück, indem man jeden 7-stelligen empfangenen Bit-Vektor von rechts an die Matrix aus (2) multipliziert. Ist das Ergebnis ^{t}(0, 0, 0), so ist das empfangene Wort korrekt, und man nimmt die ersten vier Bit als ursprüngliche Nachricht. Andernfalls erhält man als Ergebnis den Index des falsch übertragenen Bits. Dieses Bit korrigiert man: aus 0 mache 1 bzw. aus 1 wird 0. Dann nimmt man die ersten vier Bit als ursprüngliche Nachricht. Wie lautet also die ursprünglich gesendete Folge von 4 Bits, wenn man folgende 7-Bit-Folge empfängt?

t(0, 1, 1, 0, 0, 1, 1) ^{t}(0, 1, 1, 0, 1, 0, 1)

7. Um welchen Faktor wird die ursprüngliche Nachricht bei diesem Hamming-Code aufgebläht?