| Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung |
| pruefungen:bachelor:aud:loesung-miniklausur-18 [09.01.2019 22:06] – gabriel2029 | pruefungen:bachelor:aud:loesung-miniklausur-18 [30.03.2019 21:17] (aktuell) – gabriel2029 |
|---|
| | ===== Lösungsversuch Miniklausur WS 2018/19 ===== |
| | |
| ==== Aufgabe 1 (Wissensfragen) ==== | ==== Aufgabe 1 (Wissensfragen) ==== |
| **a)** Aussage 2 und 3 sind korrekt. Zur Erklärung: | **a)** Aussage 2 und 3 sind korrekt. Zur Erklärung: |
| * In der Regel entscheidet der statische Typ bei verdeckten Attributen, welches Attribut tatsächlich verwendet wird. Dabei ist es egal, ob es sich um Instanz- oder Klassenattribute handelt. | * In der Regel entscheidet der statische Typ bei verdeckten Attributen, welches Attribut tatsächlich verwendet wird. Dabei ist es egal, ob es sich um Instanz- oder Klassenattribute handelt. |
| * Einer doppelt-verkettete Prioritätswarteschlange legt im Wesentlichen eine doppelt- (und zirkulär) verkettete Liste zugrunde. Diese Liste ist sortiert. Beim Einfügen müssen die beiden aufeinanderfolgenden Elemente gefunden werden, sodass das einzufügende Element genau dazwischen liegt, damit die Liste nach wie vor sortiert ist. Da die doppelt-verkettete Liste nicht über einen wahlfreien Zugriff verfügt, muss im schlimmsten Fall die gesamte Liste durchsucht werden. Dies benötigt eine Laufzeit von O(n). | * Einer doppelt-verkettete Prioritätswarteschlange liegt im Wesentlichen eine doppelt- (und zirkulär) verkettete Liste zugrunde. Diese Liste ist sortiert. Beim Einfügen müssen die beiden aufeinanderfolgenden Elemente gefunden werden, sodass das einzufügende Element genau dazwischen liegt, damit die Liste nach wie vor sortiert ist. Da die doppelt-verkettete Liste nicht über einen wahlfreien Zugriff verfügt, muss im schlimmsten Fall die gesamte Liste durchsucht werden. Dies benötigt eine Laufzeit von O(n). |
| * In Java erbt jedes Objekt von ''java.lang.Object'' (z. B. wird typischerweise die ''equals''-Methode von jeder Klasse unterstützt. Das liegt daran, da jede Klasse Unterklasse von ''java.lang.Object'' ist). Des Weiteren kann man allgemein in Java nur genau eine Klasse mit ''extends'' als Oberklasse einer anderen Klasse definieren, dafür aber eine beliebige Anzahl an Schnittstellen mit ''implements'' implementieren. | * In Java erbt jedes Objekt von ''java.lang.Object'' (z. B. wird typischerweise die ''equals''-Methode von jeder Klasse unterstützt. Das liegt daran, da jede Klasse Unterklasse von ''java.lang.Object'' ist). Des Weiteren kann man allgemein in Java nur genau eine Klasse mit ''extends'' als Oberklasse einer anderen Klasse definieren, dafür aber eine beliebige Anzahl an Schnittstellen mit ''implements'' implementieren. |
| * Wenn sich bei einer Rekursion Methoden gegenseitig aufrufen, spricht man von einer //verschränkten Rekursion//. | * Wenn sich bei einer Rekursion Methoden gegenseitig aufrufen, spricht man von einer //verschränkten Rekursion//. |
| * Betrachtet man die Methode ''fH''. Hier wird (außer beim Basisfall) jedes Mal ''n'' um genau eins dekrementiert, bis der Basisfall erreicht wird. Da das Ausführen __eines Methodenschrittes__ in O(1) geschieht, erreicht man eine Laufzeit von O(n). Da die Methode ''fib'' die Methode ''fH'' mit den Argumenten ''n, 1, 1'' aufruft, liegt die Laufzeit dieser Methode damit auch in O(n). | * Betrachtet man die Methode ''fH''. Hier wird (außer beim Basisfall) jedes Mal ''n'' um genau eins dekrementiert, bis der Basisfall erreicht wird. Da das Ausführen __eines Methodenschrittes__ in O(1) geschieht, erreicht man eine Laufzeit von O(n). Da die Methode ''fib'' die Methode ''fH'' mit den Argumenten ''n, 1, 1'' aufruft, liegt die Laufzeit dieser Methode damit auch in O(n). |
| * Wenn ''n'' negativ ist, wird diese Zahl von ''fH'' im Basisfall behandelt. Die Methode terminiert dann also auch. | * Wenn ''n'' negativ ist, wird diese Zahl von ''fH'' im Basisfall behandelt. Die Methode terminiert dann also auch. |
| * Die Laufzeit von ''fH'' liegt in O(n) (Nachweis siehe Punkt 1). Sie liegt damit nicht in O(log(n)). //(Anmerkung: Würde beispielsweise die Methode ''fH'' eine Laufzeitkomplexität von O(1) haben, dann würde die Laufzeitkomplexität von ''fH'' in auch in O(log(n)) liegen, da die O-Notation in der Regel eine __obere Schranke__ darstellt. In dieser Aufgabenstellung ist allerdings eine schärfere Schranke als zulässig angegeben. Die Aussage ist damit trotzdem falsch. Dieser Sonderfall wurde aber meines Wissens nach in dieser Form noch nicht abgefragt, wenn dann wird nach der schärfsten Schranke gefragt.)// | * Die Laufzeit von ''fH'' liegt in O(n) (Nachweis siehe Punkt 1). Sie liegt damit nicht in O(log(n)). //(Anmerkung: Würde beispielsweise die Methode ''fH'' eine Laufzeitkomplexität von O(1) haben, dann würde die Laufzeitkomplexität von ''fH'' auch in O(log(n)) liegen, da die O-Notation in der Regel eine __obere Schranke__ darstellt. In dieser Aufgabenstellung ist allerdings eine schärfere Schranke als zulässig angegeben. Die Aussage ist damit trotzdem falsch. Dieser Sonderfall wurde aber meines Wissens nach in dieser Form noch nicht abgefragt, wenn dann wird nach der schärfsten Schranke gefragt.)// |
| * Von einer //Endrekursion// spricht man, wenn in jedem Fall (z. B. durch die ''if''-Abfrage), wenn dort eine Rekursion vorkommt, der rekursive Aufruf der Methode die letzte Anweisung ist. Hier trifft das offensichtlich zu. | * Von einer //Endrekursion// spricht man, wenn in jedem Fall (z. B. durch die ''if''-Abfrage), wenn dort eine Rekursion vorkommt, der rekursive Aufruf der Methode die letzte Anweisung ist. Hier trifft das offensichtlich zu. |
| |
| **c)** Die Aussagen 1 und 2 sind richtig. Zur Erklärung: | **c)** Die Aussagen 1 und 2 sind richtig. Zur Erklärung: |
| * Da bei der O-Notation bei Summen nur der Summand zählt, der bei sehr großen Zahlen //das größte Gewicht// hat, muss nur der erste Summand betrachtet werden. Da Konstanten keine Auswirkung auf die O-Notation haben, können sie unbeachtet gelassen werden. (//Anmerkung: Die hier dargestellte Funktion ist ein Polynom. Die O-Laufzeit war also damit eigentlich schon bekannt und war nicht neu zu erschließen.//) | * Da bei der O-Notation bei Summen nur der Summand zählt, der bei sehr großen Zahlen //das größte Gewicht// hat, muss hier nur der erste Summand betrachtet werden. Da Konstanten keine Auswirkung auf die O-Notation haben, können sie unbeachtet gelassen werden. (//Anmerkung: Die hier dargestellte Funktion ist ein Polynom. Die O-Laufzeit war also damit eigentlich schon bekannt und war nicht neu zu erschließen.//) |
| * Hier wird ziemlich präzise die O-Notation beschrieben, nämlich, dass alle Methoden darin liegen, die __höchstens so schnell__ wie g(n) wachsen. | * Hier wird ziemlich präzise die O-Notation beschrieben, nämlich, dass alle Methoden darin liegen, die __höchstens so schnell__ wie g(n) wachsen. |
| * Betrachtet man //pop(push(s, e))//. Hier wird zunächst //e// auf den Stapel gelegt, und anschließend das oberste Element, also //e//, wieder entfernt. Es gilt also //pop(push(s, e)) = s//. Betrachtet man //push(pop(s), e)//. Hier wird zuerst das oberste Elemtn aus //s// entfernt und __anschließend__ //e// auf den Stapel gelegt. Der erste Stapel enthält //e// nun nicht, während der zweite //e// enthält. Die beiden Stapel sind also verschieden. | * Betrachtet man //pop(push(s, e))//. Hier wird zunächst //e// auf den Stapel gelegt, und anschließend das oberste Element, also //e//, wieder entfernt. Es gilt also //pop(push(s, e)) = s//. Betrachtet man //push(pop(s), e)//. Hier wird zuerst das oberste Element aus //s// entfernt und __anschließend__ //e// auf den Stapel gelegt. Der erste Stapel enthält //e// nun nicht, während der zweite //e// enthält. Die beiden Stapel sind also verschieden. |
| * Eine ''if ... else if ... else''-Anweisung kann man in der Regel wie unten gezeigt auflösen. Der //Code Z// kann also nur dann ausgeführt werden, wenn //Bedingung a// und //Bedingung b// nicht erfüllt sind. In dem gegebenen wp-Kalkül wird dieser //Code Z// betrachtet, wenn nur //Bedingung b// nicht erfüllt ist. | * Eine ''if ... else if ... else''-Anweisung kann man in der Regel wie unten gezeigt auflösen. Der //Code Z// kann also nur dann ausgeführt werden, wenn //Bedingung a// und //Bedingung b// nicht erfüllt sind. In dem gegebenen wp-Kalkül wird dieser //Code Z// betrachtet, wenn nur //Bedingung b// nicht erfüllt ist. |
| <code java> | <code java> |
| if (m == null) { | if (m == null) { |
| m = new int[n + 1]; | m = new int[n + 1]; |
| m[1] = [2] = 1; | for (int i = 1; i <= n; i++) m[i] = -1; |
| for (int i = 3; i <= n; i++) m[i] = -1; | |
| return hMem(n, m); | return hMem(n, m); |
| } | } |
| if (m[n] != -1) return m[n]; | if (m[n] != -1) return m[n]; |
| else { | else if (n == 1 || n == 2) { |
| | m[n] = 1; |
| | return m[n]; |
| | } else { |
| m[n] = hMem(hMem(n - 1, m), m) + hMem(n - hMem(n - 1, m), m); | m[n] = hMem(hMem(n - 1, m), m) + hMem(n - hMem(n - 1, m), m); |
| return m[n]; | return m[n]; |
| return 1; | return 1; |
| } | } |
| | int[] m = new int[n + 1]; |
| m[1] = m[2] = 1; | m[1] = m[2] = 1; |
| for (int i = 3; i <= n; i++) { | for (int i = 3; i <= n; i++) { |
| m[i] = m[m[i - 1]] + m[n - m[n - 1]]; | m[i] = m[m[i - 1]] + m[i - m[i - 1]]; //Sollten die n's hier nicht auch i's sein? // hast Recht, wurde ausgetauscht |
| } | } |
| return m[n]; | return m[n]; |
