| AuD Übung 01 (Stefan Bosse) [15.11.2024] |
| Punkte: | Total | /2 | 1. | /2 | 2. | /2 | 3. | /2 | 4. | /2 | 5. | /2 |
In dieser Übung sollen zwei Ziele erricht werden:
Ausgabe : 7.11.2024
Abgabe : 15.11.2024
Hinweis: Wenn zu Beginn der folgenden Codesnippets im Kommentar profile steht wird ein Profiling mit einer Bytecode VM des Codes durchgeführt. Man erhält am Ende eine Statistik aller aufgerufenen Bytecode Instruktionen. Wichtig ist nur die Gesamtsumme opCount als ein Maß für die Anzahl der ausgeführten Einheitsoperationen. Im Code immer nur N verändern.
Für die Vertiefung: Weitere Informationen zum Profiler finden sich hier https://github.com/joskid/continuum wo die JavaScript Virtual Machine beschrieben wird.
Im Gegensatz zur Messung der Laufzeit ist die Messung der ausgeführten Einheitsoperationen ein stabiles Maß und gibt meistens fast linear proportional die Rechenzeit wieder.
Im folgenden sollen die beiden Algorithmen A und B bezüglich Rechenaufwand und Rechengenauigkeit verglichen werden.
Ausführung Algorithmus A|
▸
|
✗
≡
|
|
▸
|
✗
≡
|
Aufgabe 1. Wie hängt beim Algorithmus B die Laufzeit ungefähr von N ab?
Wirklich?
Aufgabe 2. Führe das Profiling für B durch und trage die Werte in nachfolgende Tabelle ein. Prüfe das Ergebnis durch einen Plot (unten).
|
▸
|
✗
≡
|
Aufgabe 3. Wie ist das Ergebnis? Entspricht es der theoretischen Erwartung? Wo kommen die wesentlichen Beiträge zur Laufzeit und Abhängigkeit von N her?
Ab hier sollen Algorithmen in Java mit dem integrierten JS Transpiler implementiert werden.
In der Numerik gilt es Algorithmen hinsichtlich folgender Kriterien zu untersuchen:
Ein allgemeiner Hinweis:
Der Java2JS Transpiler besteht aus einem Parser, Generator und einen Typprüfer. Der Parser nimmt Java bis Version 7 an, Lambda Ausdrücke sind als Workaround implementiert und dürfen nur einfache Operationen und Anweisungen enthalten (inkl. return). Der Generator erzeugt JavaScript Code. Der Transpiler an sich schluckt alles, auch semantisch/operational falschen Java Code (inkl. Tpyfehlern). Es könnten dann Fehler bei der Ausführung (Runtime Error) auftreten. Der Typprüfer ist nicht vollständig. Teils werden nur Warnungen ausgegeben, die dann aber bei der Ausführung zu Programmfehlern führen können.
Bei Verwendung des Transpilers können alle Klassen inklusive einer öffentlichen Hauptklasse, die die main Methode enthält, in einem Codeabschnitt eingefügt und ausgeführt werden. Eine Trennung ist nicht erforderlich.
Aufgabe 4. Lese das Modul B Abschnitt Approximation von Integralen. Implementiere die dort vorgestellten Algorithmen Trapezregel, Simpson, und adaptive Simpsonregel, jeweils in dem nachfolgenden Klassentemplate Integrate bezeichnet als Methoden integrate2, integrate3, und integrate4. Test die Algorithmen mit N=10-10000 bzw. ε=1E-2 - 1E-7 für die Funktionen sin und exp. Notiere das Ergebnis (Ausgabe) und den opCounts vom Profiling.
|
▸
ℙ
[] |
✗
≡
|
Y2xhc3MgSW50ZWdyYXRlICB7CiAgcHVibGljIGZsb2F0IGludGVncmF0ZTEoRnVuY3Rpb24gPEZsb2F0LEZsb2F0PmYsZmxvYXQgYSwgZmxvYXQgYiwgaW50IE4pIHsKICAgIC8vIEVpbnplbHB1bmt0CiAgICBmbG9hdCB5PTA7CiAgICBmbG9hdCBkZWx0YT0oYi1hKS9OOwogICAgZm9yKGZsb2F0IHg9YTt4PGI7eCs9ZGVsdGEpIHk9eStkZWx0YSpmLmFwcGx5KHgpOwogICAgcmV0dXJuIHk7CiAgfQogIHB1YmxpYyBmbG9hdCBpbnRlZ3JhdGUyKEZ1bmN0aW9uIDxGbG9hdCxGbG9hdD5mLGZsb2F0IGEsIGZsb2F0IGIsIGludCBOKSB7CiAgICAvLyBUcmFwZXoKICAgIGZsb2F0IHk9MDsKICAgIGZsb2F0IGRlbHRhPShiLWEpL047CiAgICBmb3IoZmxvYXQgeD1hO3g8Yjt4Kz1kZWx0YSkgCiAgICAgICAgeT15K2RlbHRhLzIqKGYuYXBwbHkoeCkrZi5hcHBseSh4K2RlbHRhKSk7CiAgICByZXR1cm4geTsKICB9CiAgcHVibGljIGZsb2F0IGludGVncmF0ZTMoRnVuY3Rpb24gPEZsb2F0LEZsb2F0PmYsZmxvYXQgYSwgZmxvYXQgYiwgaW50IE4pIHsKICAgIC8vIFNpbXBzb24KICAgIGZsb2F0IHk9MDsKICAgIGZsb2F0IGRlbHRhPShiLWEpL047CiAgICBmb3IoZmxvYXQgeD1hO3g8Yjt4Kz1kZWx0YSkgCiAgICAgICAgeT15K2RlbHRhLzYqKGYuYXBwbHkoeCkrNCpmLmFwcGx5KHgrZGVsdGEvMikrZi5hcHBseSh4K2RlbHRhKSk7CiAgICByZXR1cm4geTsKICB9CiAgcHVibGljIGZsb2F0IFNWKEZ1bmN0aW9uIDxGbG9hdCxGbG9hdD5mLGZsb2F0IGEsZmxvYXQgYixmbG9hdCBlLCBmbG9hdCB0LGZsb2F0IGgpIHsKICAgIGZsb2F0IEk7CiAgICBmbG9hdCBnID0gMTUqZS8oYi1hKTsKICAgIGlmICh0ID49IGIpIHJldHVybiAwOy8vIEVyZm9yZGVybGljaGVyIEJlcmVpY2ggaW50ZWdyaWVydD8KICAgIC8vIERpZSBTaW1wc29ucmVnZWwuCiAgICBmbG9hdCBJUyA9IGgvMyooZi5hcHBseSh0KSsgNCpmLmFwcGx5KHQraCkrZi5hcHBseSh0KzIqaCkpOwogICAgLy8gRGllIHp1c2FtbWVuZ2VzZXR6dGUgU2ltcHNvbnJlZ2VsLgogICAgZmxvYXQgSVpTID0gaC82KihmLmFwcGx5KHQpKwogICAgICAgICAgICAgICAgICAgICA0KmYuYXBwbHkodCtoLzIpKwogICAgICAgICAgICAgICAgICAgICAyKmYuYXBwbHkodCtoKSsKICAgICAgICAgICAgICAgICAgICAgNCpmLmFwcGx5KHQrMypoLzIpKwogICAgICAgICAgICAgICAgICAgICBmLmFwcGx5KHQrMipoKSk7CiAgICBpZiAoTWF0aC5hYnMoSVpTLUlTKSA8PSAoZypoKSkgeyAvLyBEaWUgRmVobGVyYWJzY2hhZXR6dW5nLgogICAgICBJID0gSVpTOyAvLyBBdWZzdW1taWVydW5nLgogICAgICBJICs9IFNWKGYsYSxiLGUsdCsyKmgsKGItKHQrMipoKSkvMik7IC8vIFJlc3RsaWNoZXIgSW50ZXJ2YWxsLgogICAgICByZXR1cm4gSTsKICAgIH0gZWxzZSAKICAgICAgcmV0dXJuIHRoaXMuU1YoZixhLGIsZSx0LGgvMik7IC8vIFZlcmZlaW5lcnVuZy4gIAogIH0KICBwdWJsaWMgZmxvYXQgaW50ZWdyYXRlNChGdW5jdGlvbiA8RmxvYXQsRmxvYXQ+ZixmbG9hdCBhLCBmbG9hdCBiLCBmbG9hdCBlcHMpIHsKICAgIC8vIEFkYXB0aXZlIFNpbXBzb24KICAgIC8vIEludGVncmF0ZSBpbSA9IHRoaXM7CiAgICBmbG9hdCB5PXRoaXMuU1YoZixhLGIsZXBzLGEsKGItYSkvMik7CiAgICByZXR1cm4geTsKICB9Cn0KcHVibGljIGNsYXNzIFRlc3QgewogIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgIEludGVncmF0ZSBpbSA9IG5ldyBJbnRlZ3JhdGUoKTsKICAgIGludCBOPTEwOwogICAgZmxvYXQgZXBzPTAuMDAwMTsKICAgIGZsb2F0IGE9MSxiPTQ7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oaW0uaW50ZWdyYXRlMQogICAgICAoKHgpIC0+IHsgcmV0dXJuIE1hdGguc2luKHgpOyB9LAogICAgICBhLGIsTikpOwogICAgU3lzdGVtLm91dC5wcmludGxuKGltLmludGVncmF0ZTIKICAgICAgKCh4KSAtPiB7IHJldHVybiBNYXRoLnNpbih4KTsgfSwKICAgICAgYSxiLE4pKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbihpbS5pbnRlZ3JhdGUzCiAgICAgICgoeCkgLT4geyByZXR1cm4gTWF0aC5zaW4oeCk7IH0sCiAgICAgIGEsYixOKSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oaW0uaW50ZWdyYXRlNAogICAgICAoKHgpIC0+IHsgcmV0dXJuIE1hdGguc2luKHgpOyB9LAogICAgICBhLGIsZXBzKSk7CiAgfQp9IA==
Aufgabe 5. Was ist das Endergebnis? Wie sieht es bezüglich Genauigkeit und Rechenaufwand bei den vier verschiedenen Verfahren aus? Wie unterscheiden sich die Sunus und Exponentialfunktionen, und warum? Ist bei dem dynamisch adaptiven Verferhren ein "Komplexitätsklasse" erkennbar?