| AuD Übung 0q (Stefan Bosse) [14.11.2025] |
| Punkte: | Total | /2 | 1. | /2 | 2. | /2 | 3. | /2 | 4. | /2 | 5. | /2 |
In dieser Übung sollen zwei Ziele erricht werden:
Ausgabe : 14.11.2024
Abgabe : 23.11.2024
Die uJ VM kann nur Java Code verarbeiten welcher mit dem speziellen Runtime Environment (RT) verknüpft ist. Im Java Code immer package java.lang;import uj.lang.*; voranstellen.
Die Laufzeit soll in dieser Übung für verschiedene Algorithmen in Abhängigkeit eines Parameters N gemessen werden. Der Parameter N ist ein Maß für die Problemgröße, i.a. ein lineares Maß des Problems, das ist aber definitionsabhängig. Z.B. mei Matrixoperationen könnte N die Anzahl der Zeilen oder Spalten sein, und da bei quadratischen Matrizen wäre N dann ein quadratsches Maß der Problemgröße (N × N).
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.
// profile
N=100
e=pow(1+1/N,N)
print(e,abs(E-e))
Algorithmus A
// profile
e=0;N=100
function fac(n) { return n<2?1:n*fac(n-1) }
for(n=0;n<=N;n++) {
e=e+1/fac(n)
}
print(e,abs(E-e))
Algorithmus B
Aufgabe 1. Wie hängt beim Algorithmus B die Laufzeit ungefähr von N ab?
Wirklich?
Aufgabe 2. Implementiere Algortihmus B in der Java Test Klasse (main Methode), gebe das Ergebnis mit System.out.println aus. Führe das Profiling für B durch und trage die Werte in nachfolgender Tabelle ein. Prüfe das Ergebnis durch einen Plot (unten).
Ab hier sollen Algorithmen in Java implementiert und mit der integrietren uJ VM getestet werden. Der java Programmkode wird extern via websh mit einem Java Compiler übersetzt.
cGFja2FnZSBqYXZhLmxhbmc7CmltcG9ydCB1ai5sYW5nLio7CgpjbGFzcyBGdW5jdGlvbnMgewogIHN0YXRpYyBmbG9hdCBmYWMoZmxvYXQgbikgewogICAgcmV0dXJuIG48Mj8xOm4qZmFjKG4tMSk7CgoKICB9Cn0KcHVibGljIGNsYXNzIEV4cCB7CiAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oKSB7CiAgICBpbnQgTj0xMCxuOwogICAgZmxvYXQgZT0wOwogICAgZm9yKG49MDtuPD1OO24rKykgewogICAgICBlPWUrMS9GdW5jdGlvbnMuZmFjKG4pOwogICAgfQogICAgU3lzdGVtLm91dC5wcmludGxuKGUpOwogIH0KfQ==
make (Linux, Mac) oder makew (Windows) und run. (websh index 0) help or hit TAB for a list of commands.|
▸
|
✗
≡
|
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?
In der Numerik gilt es Algorithmen hinsichtlich folgender Kriterien zu untersuchen:
Ein allgemeiner Hinweis:
Die uJ VM nimmt Java bis Version 7 an, Lambda Ausdrücke sind nicht vorgesehen. Stattdessen wird eine einfache Function Klasse implementiert, um die zu integrierenden Funktionen (z.B. sin) an die Berechnungsfunktion zu übergeben.
Bei Verwendung der uJ VM 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. Teste 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.
Numerische Integration.cGFja2FnZSBqYXZhLmxhbmc7CmltcG9ydCB1ai5sYW5nLio7CgovLzxpPiBUaGUgb25seSB3YXkgdG8gZGVmaW5lIGZ1bmN0aW9ucyB0aGF0IGNhbiBiZSBwYXNzZWQgdG8gbWV0aG9kczwvaT4KCmFic3RyYWN0IGludGVyZmFjZSBGdW5jdGlvbiB7CiAgIGZsb2F0IGFwcGx5KGZsb2F0IHgpOwp9Cgo8Yj5jbGFzczwvYj4gSW50ZWdyYXRlICB7CiAgcHVibGljIGZsb2F0IGludGVncmF0ZTEoRnVuY3Rpb24gZixmbG9hdCBhLCBmbG9hdCBiLCBpbnQgTikgewogICAgLy88aT4gRWluemVscHVua3Q8L2k+CgogICAgZmxvYXQgeT0wOwogICAgZmxvYXQgZGVsdGE9KGItYSkvTjsKICAgIDxiPmZvcjwvYj4oZmxvYXQgeD1hO3g8Yjt4Kz1kZWx0YSkgeT15K2RlbHRhKmYuYXBwbHkoeCk7CiAgICA8Yj5yZXR1cm48L2I+IHk7CiAgfQogIHB1YmxpYyBmbG9hdCBpbnRlZ3JhdGUyKEZ1bmN0aW9uIGYsZmxvYXQgYSwgZmxvYXQgYiwgaW50IE4pIHsKICAgIC8vPGk+IFRyYXBlejwvaT4KCiAgICBmbG9hdCB5PTA7CiAgICBmbG9hdCBkZWx0YT0oYi1hKS9OOwogICAgPGI+Zm9yPC9iPihmbG9hdCB4PWE7eDxiO3grPWRlbHRhKSAKICAgICAgICB5PXkrZGVsdGEvMiooZi5hcHBseSh4KStmLmFwcGx5KHgrZGVsdGEpKTsKICAgIDxiPnJldHVybjwvYj4geTsKICB9CiAgcHVibGljIGZsb2F0IGludGVncmF0ZTMoRnVuY3Rpb24gZixmbG9hdCBhLCBmbG9hdCBiLCBpbnQgTikgewogICAgLy88aT4gU2ltcHNvbjwvaT4KCiAgICBmbG9hdCB5PTA7CiAgICBmbG9hdCBkZWx0YT0oYi1hKS9OOwogICAgPGI+Zm9yPC9iPihmbG9hdCB4PWE7eDxiO3grPWRlbHRhKSAKICAgICAgICB5PXkrZGVsdGEvNiooZi5hcHBseSh4KSs0KmYuYXBwbHkoeCtkZWx0YS8yKStmLmFwcGx5KHgrZGVsdGEpKTsKICAgIDxiPnJldHVybjwvYj4geTsKICB9CiAgcHVibGljIGZsb2F0IFNWKEZ1bmN0aW9uIGYsZmxvYXQgYSxmbG9hdCBiLGZsb2F0IGUsIGZsb2F0IHQsZmxvYXQgaCkgewogICAgZmxvYXQgSTsKICAgIGZsb2F0IGcgPSAxNSplLyhiLWEpOwogICAgPGI+aWY8L2I+ICh0ID49IGIpIDxiPnJldHVybjwvYj4gMDsvLzxpPiBFcmZvcmRlcmxpY2hlciBCZXJlaWNoIGludGVncmllcnQ/PC9pPgoKICAgIC8vPGk+IERpZSBTaW1wc29ucmVnZWwuPC9pPgoKICAgIGZsb2F0IElTID0gaC8zKihmLmFwcGx5KHQpKyA0KmYuYXBwbHkodCtoKStmLmFwcGx5KHQrMipoKSk7CiAgICAvLzxpPiBEaWUgenVzYW1tZW5nZXNldHp0ZSBTaW1wc29ucmVnZWwuPC9pPgoKICAgIGZsb2F0IElaUyA9IGgvNiooZi5hcHBseSh0KSsKICAgICAgICAgICAgICAgICAgICAgNCpmLmFwcGx5KHQraC8yKSsKICAgICAgICAgICAgICAgICAgICAgMipmLmFwcGx5KHQraCkrCiAgICAgICAgICAgICAgICAgICAgIDQqZi5hcHBseSh0KzMqaC8yKSsKICAgICAgICAgICAgICAgICAgICAgZi5hcHBseSh0KzIqaCkpOwogICAgPGI+aWY8L2I+IChNYXRoLmFicyhJWlMtSVMpIDw9IChnKmgpKSB7IC8vPGk+IERpZSBGZWhsZXJhYnNjaGFldHp1bmcuPC9pPgoKICAgICAgSSA9IElaUzsgLy88aT4gQXVmc3VtbWllcnVuZy48L2k+CgogICAgICBJICs9IFNWKGYsYSxiLGUsdCsyKmgsKGItKHQrMipoKSkvMik7IC8vPGk+IFJlc3RsaWNoZXMgSW50ZXJ2YWxsLjwvaT4KCiAgICAgIDxiPnJldHVybjwvYj4gSTsKICAgIH0gPGI+ZWxzZTwvYj4gewogICAgICA8Yj5yZXR1cm48L2I+IFNWKGYsYSxiLGUsdCxoLzIpOyAvLzxpPiBWZXJmZWluZXJ1bmcuICA8L2k+CgogICAgfQogIH0KICBwdWJsaWMgZmxvYXQgaW50ZWdyYXRlNChGdW5jdGlvbiBmLGZsb2F0IGEsIGZsb2F0IGIsIGZsb2F0IGVwcykgewogICAgLy88aT4gQWRhcHRpdmUgU2ltcHNvbjwvaT4KCiAgICBmbG9hdCB5PXRoaXMuU1YoZixhLGIsZXBzLGEsKGItYSkvMik7CiAgICA8Yj5yZXR1cm48L2I+IHk7CiAgfQp9CgpwdWJsaWMgPGI+Y2xhc3M8L2I+IEludGVncmFsIHsKICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbigpIHsKICAgIEludGVncmF0ZSBpbSA9IDxiPm5ldzwvYj4gSW50ZWdyYXRlKCk7CiAgICBpbnQgTj0xMDsKICAgIGZsb2F0IGVwcz0oZmxvYXQpMC4wMDAwMTsKICAgIGZsb2F0IGE9MSxiPTQ7CiAgICAvLzxpPiAoeCkgPT4geyByZXR1cm4gTWF0aC5zaW4oeCkgfTwvaT4KCiAgICBGdW5jdGlvbiBmb28gPSA8Yj5uZXc8L2I+IEZ1bmN0aW9uKCkgewogICAgICBwdWJsaWMgZmxvYXQgYXBwbHkoZmxvYXQgeCkgewogICAgICAgIDxiPnJldHVybjwvYj4gTWF0aC5zaW4oeCk7CiAgICAgIH0KICAgIH07CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oaW0uaW50ZWdyYXRlMShmb28sYSxiLE4pKTsKICAgIFN5c3RlbS5vdXQucHJpbnRsbihpbS5pbnRlZ3JhdGUyKGZvbyxhLGIsTikpOwogICAgU3lzdGVtLm91dC5wcmludGxuKGltLmludGVncmF0ZTMoZm9vLGEsYixOKSk7CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oaW0uaW50ZWdyYXRlNChmb28sYSxiLGVwcykpOwogIH0KfQ==
make (Linux, Mac) oder makew (Windows) und run. (websh index 1) help or hit TAB for a list of commands.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?