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.

if (/* Bedingung a*/) {
    /* Code X */
} else {
    if (/* Bedingung b*/) {
        /* Code Y */
    } else {
        /* Code Z */
    }
}

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.

int h(int n) {
    if (n == 1 || n == 2) return 1;
    else return h(h(n - 1)) + h(n - h(n - 1));
}

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.

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];
    }
}

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.

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];
}

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:

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;
}

(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.)

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