AuD Übung 02 (Stefan Bosse) [15.11.2024]
Gruppe und Namen der Mitglieder
Punkte:Total/21./22./23./24./25./26./2

Übung Numerik (02)

In dieser Übung sollen drei Ziele erricht werden:

  1. Vektoren und Matrizen in Java verwenden und Arithmetik darauf anwenden;
  2. Anwendung der Algorithmen auf konkrete Daten.
  3. Wieder Laufzeitbetrachtungen anstellen und einordnen können.

Ausgabe : 15.11.2024

Abgabe : 22.11.2024

Komplexitätsanalyse

Aufgabe 1. Was bedeutet die O-Notation?


Aufgabe 2. Was ist der Unterschied zwischen Big-O und Littel-o Notation?


Aufgabe 3. Welche berechnten Laufzeiten (Aufwand S) sind gleich oder kleiner O(n2)?


Vektoren und Matrizen

Ab hier sollen Algorithmen in Java mit dem integrierten JS Transpiler implementiert werden. Es dürfen keine weiteren externen Java Klassen/Module/Packages außer System verwendet werden!

Vektoren und Matrizen

\[ {v}={\left(\matrix{{v}_{{1}}\\{v}_{{2}}\\..\\{v}_{{n}}}\right)}\\ {m}={\left(\matrix{{a}_{{{1},{1}}}&..&{a}_{{{1},{m}}}\\{a}_{{{2},{1}}}&..&{a}_{{{2},{m}}}\\..&..&..\\{a}_{{{n},{1}}}&..&{a}_{{{n},{m}}}}\right)} \]

sind die wichtigsten Datenstrukturen in der Matheamatik und Numerik.

Für Matrixalgebra brauchen wir Vektoren und Matrizen. In Java können diese mittels der Array Klasse von einem beliebigen Datentyp direkt erzeugt werden. Matrizen sind im Grunde Arrays von (eindimensionalen) Arrays.


Erzeugung von Vektoren und Matrizen in Java

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 

Die Arrays sind nicht initialisert! Das muss explizit erfolgen, z.B. mit einem Wert 0.

Es können aber auch initialierte Arrays (oder Arrays von Arrays, also Matrizen) erzeugt werden. Das wird nachfolgend gezeigt.


Vektoren und Matrizen von konstanten Werten in Java

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 

Im folgenden sollen diese nativen Arrays (oder Arrays von Arrays als Matrizen) in komfortable Vektor- und Matrixklassen in Java eingebettet werden, mit einer Reihe von Operationen der linearen Vektor- und Matrixalgebra.

Matrix Numerik Klasse

Aufgabe 4. Lese das Modul B Abschnitt Vektor- und Matrixalgebra. Erstelle eine Vektor und Matrix Klasse die die Operationen +,-*,/ und Negieren von Vektoren und Matrizen (elementweise) implementieren sowie das Skalarprodukt und das Matrixprodukt. Dabei soll es in-place (Nutzung der Quellmatrix) und out-of-place (neue Ergebnismatrix) möglich sein diese Operationen durchzuführen. Es wird in beiden Fällen die Zielmatrix (oder der Zielvektor) zurück gegeben. Weiterhin muss die Konstruktorfunktion und eine Print Methode erstellt werden. Die diagonal Methode erzeugt eine Einheitsmatrix. Die data Methode gibt das reine Datenarray zurück. Die Vector und Matrix Klassen sollen jeweils die Metadaten als Klassenvariablen implementieren (nrow,ncol) sowie die Daten mittels data. Die fehlen in den Templates noch. Zuletzt soll es eine fromArray Methode geben, die vor allem für die Initialisierung mit Konstantwert Arrays verwendet werden soll (also z.B. beim Vektor new float[]{1,2,3,4}, bei Matrix new float[][]{{1,2},{3,4}}).


Vektor Klasse

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 


Matrix Klasse

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 


Test Vektoren und Matrizenerzeugung

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 
 

cHVibGljIGNsYXNzIFZlY3RvciAgewogIGludCBuY29sOwogIGZsb2F0IFtdIGRhdGE7CiAgcHVibGljIFZlY3RvcihpbnQgX25jb2wsIGZsb2F0IGluaXQpIHsKICAgIHRoaXMubmNvbD1fbmNvbDsKICAgIHRoaXMuZGF0YT1uZXcgZmxvYXRbbmNvbF07CiAgICBmb3IoaW50IGk9MDtpPG5jb2w7aSsrKSAKICAgICAgICB0aGlzLmRhdGFbaV09aW5pdDsKICB9CiAgcHVibGljIFZlY3RvciBmcm9tQXJyYXkoZmxvYXQgW10gYXJyKSB7CiAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgdGhpcy5kYXRhW2ldPWFycltpXTsKICAgIHJldHVybiB0aGlzOwogIH0KICBwdWJsaWMgVmVjdG9yIGFkZChWZWN0b3IgYiwgQm9vbCBpbnBsYWNlKSB7CiAgICBWZWN0b3IgdGFyZ2V0PXRoaXM7CiAgICBpZiAoIWlucGxhY2UpIHsKICAgICAgdGFyZ2V0PW5ldyBWZWN0b3IodGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bmNvbDtpKyspIAogICAgICB0YXJnZXRbaV09dGhpcy5kYXRhW2ldK2IuZGF0YVtpXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBWZWN0b3Igc3ViKFZlY3RvciBiLCBCb29sIGlucGxhY2UpIHsKICAgIFZlY3RvciB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IFZlY3Rvcih0aGlzLm5jb2wsMGYpOwogICAgfQogICAgZm9yKGludCBpPTA7aTxuY29sO2krKykgCiAgICAgIHRhcmdldFtpXT10aGlzLmRhdGFbaV0tYi5kYXRhW2ldOwogICAgcmV0dXJuIHRhcmdldDsKICB9CiAgcHVibGljIFZlY3RvciBtdWwoVmVjdG9yIGIsIEJvb2wgaW5wbGFjZSkgewogICAgVmVjdG9yIHRhcmdldD10aGlzOwogICAgaWYgKCFpbnBsYWNlKSB7CiAgICAgIHRhcmdldD1uZXcgVmVjdG9yKHRoaXMubmNvbCwwZik7CiAgICB9CiAgICBmb3IoaW50IGk9MDtpPG5jb2w7aSsrKSAKICAgICAgdGFyZ2V0W2ldPXRoaXMuZGF0YVtpXSpiLmRhdGFbaV07CiAgICByZXR1cm4gdGFyZ2V0OwogIH0KICBwdWJsaWMgVmVjdG9yIGRpdihWZWN0b3IgYiwgQm9vbCBpbnBsYWNlKSB7CiAgICBWZWN0b3IgdGFyZ2V0PXRoaXM7CiAgICBpZiAoIWlucGxhY2UpIHsKICAgICAgdGFyZ2V0PW5ldyBWZWN0b3IodGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bmNvbDtpKyspIAogICAgICB0YXJnZXRbaV09dGhpcy5kYXRhW2ldL2IuZGF0YVtpXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBWZWN0b3IgbmVnKEJvb2wgaW5wbGFjZSkgewogICAgVmVjdG9yIHRhcmdldD10aGlzOwogICAgaWYgKCFpbnBsYWNlKSB7CiAgICAgIHRhcmdldD1uZXcgVmVjdG9yKHRoaXMubmNvbCwwZik7CiAgICB9CiAgICBmb3IoaW50IGk9MDtpPG5jb2w7aSsrKSAKICAgICAgdGFyZ2V0W2ldPS10aGlzLmRhdGFbaV07CiAgICByZXR1cm4gdGFyZ2V0OwogIH0KICBwdWJsaWMgZmxvYXQgcHJvZChWZWN0b3IgYikgewogICAgZmxvYXQgc3VtPTA7CiAgICBmb3IoaW50IGk9MDtpPG5jb2w7aSsrKSB7CiAgICAgIHN1bT1zdW0rdGhpcy5kYXRhW2ldKmIuZGF0YVtpXTsKICAgIH0KICAgIHJldHVybiBwcm9kOwogIH0KICBwdWJsaWMgZmxvYXQgW10gZ2V0RGF0YSgpIHsKICAgIHJldHVybiB0aGlzLmRhdGE7CiAgfQogIHB1YmxpYyB2b2lkIHByaW50KCkgewogIH0KfQpwdWJsaWMgY2xhc3MgTWF0cml4ICB7CiAgaW50IG5jb2w7CiAgaW50IG5yb3c7CiAgZmxvYXQgW11bXSBkYXRhOwogIHB1YmxpYyBNYXRyaXgoaW50IF9ucm93LCBpbnQgX25jb2wsIGZsb2F0IGluaXQpIHsKICAgIHRoaXMubmNvbD1fbmNvbDsKICAgIHRoaXMubnJvdz1fbnJvdzsKICAgIHRoaXMuZGF0YT1uZXcgZmxvYXRbbnJvd11bbmNvbF07CiAgICBmb3IoaW50IGk9MDtpPG5yb3c7aSsrKSAKICAgICAgZm9yKGludCBqPTA7ajxuY29sO2orKykgCiAgICAgICAgdGhpcy5kYXRhW2ldW2pdPWluaXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggZnJvbUFycmF5KGZsb2F0IFtdW10gYSkgewogICAgZm9yKGludCBpPTA7aTxucm93O2krKykgCiAgICAgIGZvcihpbnQgaj0wO2o8bmNvbDtqKyspIAogICAgICAgIHRoaXMuZGF0YVtpXVtqXT1hW2ldW2pdOwogICAgcmV0dXJuIHRoaXM7CiAgfQogIHB1YmxpYyBNYXRyaXggYWRkKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgICB0YXJnZXRbaV1bal09dGhpcy5kYXRhW2ldW2pdK2IuZGF0YVtpXVtqXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggc3ViKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgICB0YXJnZXRbaV1bal09dGhpcy5kYXRhW2ldW2pdLWIuZGF0YVtpXVtqXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggbXVsKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgICB0YXJnZXRbaV1bal09dGhpcy5kYXRhW2ldW2pdKmIuZGF0YVtpXVtqXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggZGl2KE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgICBmb3IoaW50IGo9MDtqPG5jb2w7aisrKSAKICAgICAgICB0YXJnZXRbaV1bal09dGhpcy5kYXRhW2ldW2pdL2IuZGF0YVtpXVtqXTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBNYXRyaXggbmVnKEJvb2wgaW5wbGFjZSkgewogICAgTWF0cml4IHRhcmdldD10aGlzOwogICAgaWYgKCFpbnBsYWNlKSB7CiAgICAgIHRhcmdldD1uZXcgTWF0cml4KHRoaXMubnJvdyx0aGlzLm5jb2wsMGYpOwogICAgfQogICAgZm9yKGludCBpPTA7aTxucm93O2krKykgCiAgICAgIGZvcihpbnQgaj0wO2o8bmNvbDtqKyspIAogICAgICAgIHRhcmdldFtpXVtqXT0tdGhpcy5kYXRhW2ldW2pdOwogICAgcmV0dXJuIHRhcmdldDsKICB9CiAgcHVibGljIE1hdHJpeCBwcm9kKE1hdHJpeCBiLCBCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGZsb2F0IHN1bTsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIHsKICAgICAgZm9yKGludCBqPTA7ajxuY29sO2orKykgewogICAgICAgIHN1bT0wZjsKICAgICAgICBmb3IoaW50IGs9MDtrPG5jb2w7aysrKSB7CiAgICAgICAgICBzdW09c3VtK3RoaXMuZGF0YVtpXVtrXSpiLmRhdGFba11bal0KICAgICAgICB9CiAgICAgICAgdGFyZ2V0W2ldW2pdPXN1bTsKICAgICAgfQogICAgfQogICAgcmV0dXJuIHRhcmdldDsKICB9CiAgcHVibGljIE1hdHJpeCBkaWFnb25hbChmbG9hdCB2YWx1ZSxCb29sIGlucGxhY2UpIHsKICAgIE1hdHJpeCB0YXJnZXQ9dGhpczsKICAgIGlmICghaW5wbGFjZSkgewogICAgICB0YXJnZXQ9bmV3IE1hdHJpeCh0aGlzLm5yb3csdGhpcy5uY29sLDBmKTsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8bnJvdztpKyspIAogICAgIHRhcmdldFtpXVtpXT12YWx1ZTsKICAgIHJldHVybiB0YXJnZXQ7CiAgfQogIHB1YmxpYyBmbG9hdCBbXVtdIGdldERhdGEoKSB7CiAgICByZXR1cm4gdGhpcy5kYXRhOwogIH0KICBwdWJsaWMgdm9pZCBwcmludCgpIHsKICAgIFN0cmluZyBsaW5lID0gIiI7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG5yb3c7IGkrKykgewogICAgICAgIGxpbmUgKz0gIlsiOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbmNvbDsgaisrKSB7CiAgICAgICAgICAgIGlmKGo9PW5jb2wtMSl7CiAgICAgICAgICAgICAgICBsaW5lICs9IGRhdGFbaV1bal0rIl1cbiI7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBsaW5lICs9IGRhdGFbaV1bal0rIiAiOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKGxpbmUpOwogIH0KfSAKcHVibGljIGNsYXNzIFRlc3QgewogIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgIE1hdHJpeCBxID0gbmV3IE1hdHJpeCgzLDMsMCk7CiAgICBNYXRyaXggciA9IG5ldyBNYXRyaXgoMywzLDApOwogICAgZmxvYXQgW11bXSBxSTEgPSBuZXcgZmxvYXQgW11bXXt7MywyLDV9LHs0LDYsN30sezUsLTEsLTJ9fTsKICAgIGZsb2F0IFtdW10gckkxID0gbmV3IGZsb2F0IFtdW117ezEzLDEsNX0sezQsMiwtN30sezEsMSwyfX07CiAgICBxLmZyb21BcnJheShxSTEpOwogICAgci5mcm9tQXJyYXkockkxKTsKICAgIHEucHJpbnQoKTsKICAgIHIucHJpbnQoKTsKICB9Cn0=

Aufgabe 5. Teste nachfolgende mathematische Rechnungen (jede Zeile ist eine Aufgabe, ⊙ ist das Skalar- oder Matrixprodukt.

\[ {a}={\left({3},{10},-{4}\right)},{b}={\left({2},{9},{10}\right)},{a}\odot{b}\\ {a}={\left({3},{10},-{4}\right)},{b}={\left({2},{9},{10}\right)},{a}+{b}\\ {a}={\left({3},{10},-{4}\right)},{b}={\left({2},{9},{10}\right)},{a}\cdot{b}\\ {q}={\left(\matrix{{3}&{2}&{5}\\{4}&{6}&{7}\\{5}&-{1}&-{2}}\right)},{r}={\left(\matrix{{13}&{1}&{5}\\{4}&{2}&-{7}\\{1}&{1}&{2}}\right)},{q}\odot{r}\\ {q}={\left(\matrix{{3}&{2}&{5}\\{4}&{6}&{7}\\{5}&-{1}&-{2}}\right)},{r}={\left(\matrix{{13}&{1}&{5}\\{4}&{2}&-{7}\\{1}&{1}&{2}}\right)},{q}\cdot{r} \]

Tipp: Initialisiere die Matrizen folgendermaßen: 

    float [][] qI = {{1,2,3},{4,5,6},{7,8,9}};
    float [][] rI = {{1,2,3},{4,5,6},{7,8,9}};
    Matrix q = new Matrix(3,3,0);
    Matrix r = new Matrix(3,3,0);
    q.fromArray(qI);
    r.fromArray(rI);

Man könnte alternativ q.fromArray(new float[][]{{3,2,...},..,{}}) verwenden, jedoch führt das zu sehr hohen Parsingzeiten (Ursache liegt im extrem schlechten Design des verwendeten Parser, Performanzschwäche ist nicht behebar). Verfahre ähnlich bei Vektoren.


Lösungen zu Vektor- und Matrizenrechnungen berechnen lassen

 ▸ 
 ℙ 
[]
 ✗ 
 ≡ 

Aufgabe 6. Die Lösungen sind als Tex/AsciiMath in korrekter mathematischer Notation hier einzutragen (auf das Doppelquadrat klicken und ein Editor öffnet sich):

AsciiMath Syntax: 

Vector: v=((1),(2),(..),(4))
Matrix: m=((1,2,3),(3,4,5),(6,7,8))
Ergebnisse


 ▸ 
 ⧉ 
 

VEJB

Created by the NoteBook Compiler Ver. 1.32.4 (c) Dr. Stefan Bosse (Wed Nov 27 2024 20:50:10 GMT+0100 (Central European Standard Time))