===== Lösungsversuch Miniklausur WS 2018/19 =====

==== Aufgabe 1 (Wissensfragen) ====
**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.
  * 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.
  * Wenn sich bei einer Rekursion Methoden gegenseitig aufrufen, spricht man von einer //verschränkten Rekursion//.

**b)** Aussage 1 und 4 sind korrekt. Zur Erklärung:
  * 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.
  * 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.

**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 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.
  * 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.
<code java>
if (/* Bedingung a*/) {
    /* Code X */
} else {
    if (/* Bedingung b*/) {
        /* Code Y */
    } else {
        /* Code Z */
    }
}
</code>

==== Aufgabe 2 (Dynamische Programmierung) ====
**a)** Es handelt sich um eine //verschachtelte Rekursion//, da die Argumente für den rekursiven Aufruf von h selbst durch einen rekursiven Aufruf von h ermittelt werden. //(Anmerkung: Nach der Miniklausur gab es noch die Diskussion, ob die Methode nicht auch noch kaskadenartig-rekursiv ist. Das kann ich allerdings nicht direkt sagen, da zumindest die dargestellte Antwort akzeptiert wurde.)//

**b)** Das "Abschreiben" der Rekursionsgleichung genügt.
<code java>
int h(int n) {
    if (n == 1 || n == 2) return 1;
    else return h(h(n - 1)) + h(n - h(n - 1));
}
</code>
**c)** Hier gilt es klassisches Memoization zu implementieren, indem man in einem Array bereits ermittelte Ergebnisse speichert. Die größte Schwierigkeit hierbei ist, das Array ohne eine zusätzliche Methode zu initialisieren.
<code java>
int hMem(int n, int[] m) {
    if (m == null) {
        m = new int[n + 1];
        for (int i = 1; i <= n; i++) m[i] = -1;
        return hMem(n, m);
    }
    if (m[n] != -1) return m[n];
    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);
        return m[n];
    }
}
</code>
**d)** Für klassisches Bottom-Up-DP muss sichergestellt werden, dass man keine Werte aus dem Array verwendet, die noch nicht berechnet wurden. Da die Folge allerdings für einige Werte schon abgebildet wurde und man sieht, dass diese sogar langsamer als linear ansteigt, kann man davon ausgehen, dass klassisches Bottom-Up-DP funktioniert.
<code java>
int hIter(int n) {
    if (n == 1) {
        return 1;
    }
    int[] m = new int[n + 1];
    m[1] = m[2] = 1;
    for (int i = 3; i <= n; i++) {
        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];
}
</code>

==== Aufgabe 3 (Backtracking) ====
Für den vorgegebenen Methodenkopf bietet es sich an, in jedem Rekursionsschritt zwei Zahlen mit dem Wert ''n'' in dem Array zu platzieren. Wenn man den Basisfall ''n'' kleiner gleich 0 erreicht hat, wurden alle Zahlen gesetzt. Dies ergibt folgenden Code:
<code java>
boolean fill(int n, int[] a) {
    if (n <= 0) {
        return true;
    }
    for (int i = 0; i < a.length - n - 1; i++) {
        int j = i + n + 1; // Zwischen i und j müssen genau n andere Zahlen sein
        if (a[i] == 0 && a[j] == 0) {   
            a[i] = a[j] = n;
            if (fill(n - 1, a)) return true;
            a[i] = a[j] = 0;
        }
    }
    return false;
}
</code>

//(Anmerkung: Auf den ersten Blick verleitet die Existenz der Variable n einen dazu, über jeden Eintrag vom Anfang bis zum Ende bzw. umgekehrt zu iterieren und jedes Mal alle Zahlen von 1 bis n auszuprobieren, sodass die in der Aufgabenstellung geforderte Bedingung erfüllt ist. Dieses Verfahren ist aber sowohl deutlich komplexer als auch wahrscheinlich nicht so vom Aufgabensteller gedacht, da man n nicht ohne Weiteres auf 2*n erhöhen kann, um dieses Backtracking zu realisieren.)//

==== Aufgabe 4 (ADT) ====
**a)** Nach der Gelbphase beginnt die Rotphase, die insgesamt 8 Zeiteinheiten dauert. Die beiden anderen Phasen dauern jeweils insgesamt nur 1 Zeiteinheit, weshalb man für diese einfach die Ampel weiterschalten kann. Wenn die verbleibende Zeiteinheiten noch größer als 1 ist, wird in einem Schritt diese nur um 1 dekrementiert und die Farbe der Ampel nicht geändert.

//tickA(Am(ROTGELB, 1)) = Am(GRUEN, 4)//

//tickA(Am(GELB, 1)) = Am(ROT, 8)//

//tickA(Am(f, 1)) = Am(schalten(f), 1)//

//tickA(Am(f, n)) = Am(f, n - 1)//

**b)** Zunächst einmal kommt die Zahl 5 in keinem Axiom vor. Der Fußgänger kann diese Zahl jedes Mal und zu jedem Zeitpunkt von 0 auf 5 setzen. Wenn beide Ampeln rot sind und der Fußgängercountdown auf 5 gesetzt ist, stagnieren die Ampeln in der bisherigen Phase, während der Fußgängercountdown in jeder Zeiteinheit um 1 dekrementiert wird. Ist der Fußgängercountdown auf 0 oder mindestens eine Ampel ist nicht rot, schalten die Ampeln wieder wie gewohnt. Daraus folgen diese Axiome:

//tickK(Kr(Am(fa, ta), Am(fb, tb)), f) =//

// ... (Kr(Am(fa, ta), Am(fb, tb)), f - 1)     falls f_a = ROT und f_b = ROT und f > 0//

// ... (Kr(tickA(Am(fa, ta)), tickA(Am(fb, tb)), f)     sonst//