# TI 2 -- Exam 2020
## Klausur

[TI 2 - Exam 2020](https://moodle.hpi.de/pluginfile.php/20457/mod_folder/content/0/20-exam.pdf)

## Disclaimer
Keine Garantie auf irgendwas, weder auf korrekte Lösungen noch auf schönen Aufschrieb oder Gegolftheit.

## 1 -- Plastikmüll in der Havel

### (a)
Gegeben ist ein Baum $G=(V,E,w)$ als Adjazenzliste mit positiv gewichteten Kanten gegeben durch die Gewichtsfunktion $w$. Die Knoten repräsentieren die Flussabzweigungen, die Kanten die Flussverläufe mit dem Gewicht entsprechenden Menge an Müll. Die Wurzel des Baumes ist die Quelle des Flusses, die Blattknoten stellen alle das Meer dar, da wir einen Baum und keinen DAG haben wollen.

Wir geben eine natürliche Zahl $l$ aus, die die Menge an Müll angibt, die wir in zwei Flussabfahrten maximal sammeln können.

Der Algorithmus ist korrekt, wenn es zwei Wege von der Wurzel zu Blattknoten gibt, für die das Gewicht der insgesamt benutzten Kanten $l$ ist. Zusätzlich darf es keine zwei Wege vom Wurzelknoten zu Blattknoten geben, wo das Gewicht der insgesamt genutzten Kanten größer ist als $l$.

#### Notiz
Nehmt euch wirklich die Zeit für die Formalisierung. Wenn ihr hier die Aufgabe schon gut versteht spart ihr euch sehr viel Zeit bei der Entwicklung des Algos hinterher.

Die Erklärung für die Blattknoten ist nicht nötig, hier aber für einen besseren Lesefluss hilfreich (je verständlicher ihr schreibt, desto mehr sind die Korrigierenden geneigt, gute Bewertungen zu vergeben ;) ).

### (b)
_(Algorithmus-Idee)_
Wir entwickeln ein Baum-DP-Algorithmus, bei dem wir für jeden Knoten $v$ zwei Werte speichern: Das maximale Gewicht von einem Weg von $v$ zu Blattknoten und das maximale Gewicht von Kanten auf zwei Wegen von $v$ zu Blattknoten.

_(Algorithmus-Beschreibung)_
Wir führen ein Baum-DP durch.

Je Knoten $v$ speicher wir uns zwei Werte.
In $v_1$ speichern wir das maximale Kantengewicht, wenn ein Weg von $v$ zu einem Blattknoten genommen wird - genannt 1-Weg-Gewicht.
In $v_2$ speichern wir das maximale Gewicht der Kanten, die bei zwei Wegen von $v$ zu einem Blattknoten genutzt werden - genannt 2-Weg Gewicht.

Wir berechnen die Werte von den Blättern zur Wurzel, diese Reihenfolge können wir durch eine Tiefensuche erzielen.

Für Blätter sind beide Werte $0$.

Für einen inneren Knoten $v$, sei $desc(v)$ die Menge der Kindknoten von $v$. Für $v$ berechnet sich die Wert wie folgt:
Für $v_1$ nehmen wir das Maximum aller 1-Weg-Gewichte von Kindknoten addiert zu dem entsprechenden Gewicht der Kante vom Kindknoten zu $v$.
$$
v_1 = \max(\{u_1 + w(v,u) ~|~ u \in desc(v)\})
$$
Sei $u$ dieser Kindknoten. Für $v_2$ berechnen wir nun
$$
v_2 = \max(\{t_2 + w(v,t) ~|~ t \in desc(v)\} \cup \{t_1 + w(v,t) + v_1 ~|~ t\in desc(v) \land t \not= u\})
$$

Als Ausgabe geben wir vom Wurzelknoten $z$ den Wert $z_2$ zurück.

_(Korrektheitsbeweis)_
Für führen einen Beweis über Induktion, dass die Datenstruktur korrekt befüllt ist.

Die Blattknoten sind korrekt berechnet, da ein Weg von diesen Knoten zu Blattknoten keine Kanten benötigt und somit das Gewicht von $0$ korrekt ist.

Wir nehmen nun an, dass für einen inneren Knoten $v$ bereits alle Werte von nachfolgenden Knoten berechnet wurden. Durch die Tiefensuche ist dies sichergestellt.

Der Weg mit größtem Gewicht von $v$ zu einem Blattknoten muss über einen von $v$s Kindknoten führen. Da für diese die maximalen Gewichte von Wegen zu Blattknoten bereits berechnet sind und wir den Weg zu diesen Kindknoten (die Kante von $v$ zum entsprechenden Kindknoten) mit berücksichtigen, muss das Maximum über diese Werte auch das maximale Gewicht eines Weges zu einem Blattknoten sein. $v_1$ ist somit korrekt berechnet.

Für $v_2$ gibt es zwei Möglichkeiten: Entweder beide Wege führen über den gleichen Kindknoten oder über zwei verschiedene.
Gegeben die Wege führen über den gleichen Kindknoten $u$. Der Wert von $u_2$, der uns das maximale Gewicht zurückgibt, wenn zwei Wege von $u$ zu Blattknoten verlaufen, ist bereits korrekt berechnet. Da wir zusätzlich die Kante zu $u$ berücksichtigen, ist das Resultat das Gewicht aller Kanten, die bei zwei Wegen von $v$ über $u$ zu Blattknoten benutzt werden.
Gegeben die Wege verlaufen über unterschiedliche Kindknoten $u,t$. Da die Wege keine überschneidenden Knoten haben, muss das Gewicht von einem der wege bereits in $v_1$ gespeichert sein, da dieses das maximale Gewicht eines Weges von $v$ zu einem Blattknoten ist. Da wir weiter das Maximum über alle anderen Wege nehmen, ist das Ergebnis das maximale Gewicht von zwei Wegen von $v$ über zwei verschiedene Kindknoten.

Da alle Teilwerte korrekt berechnet sind, muss das Maximum über diese Werte auch das maximale Gewicht von zwei Wegen von $v$ zu Blattknoten zurückgeben.

Somit ist unsere Datenstruktur korrekt befüllt. Sei $z$ der Wurzelknoten. So ist -- nach der Definition der Datenstruktur -- der Wert von $z_2$ die korrekte Ausgabe und unser Algorithmus ist korrekt.

_(Laufzeitanalyse)_
Die Eingabe ist in $\mathcal{O}(|V| + |E|)$, wobei $|V| = |E| -1$ gilt, da es sich um einen Baum handelt.
Da wir jeden Knoten nur zwei mal bei der Berechnung der Werte des Elternknotens betrachten, ist die Laufzeit in $\mathcal{O}(|V|)$. Die Ausgabe ist in $\mathcal{O}(1)$. Somit läuft der Algorithmus insgesamt in $\mathcal{O}(|V|)$.

### Notiz
Die Geschichte mit der Tiefensuche für die richtige Reihenfolge kann man auch weglassen, wenn ihr trotzdem kurz anführt, dass ihr eine korrekte Berechnungsreihenfolge finden könnt.

Die Formelnotation bei der Berechnungsvorschrift ist meiner Ansicht nach deutlich lesbar als eine natürlichsprachliche Definition - ihr könnt aber auch gerne diese nutzen.

Es muss nicht explizit hingeschrieben werden, dass ihr einen Beweis über Induktion führt, auch wenn ihr dies eigentlich macht. Wichtig ist trotzdem, dass alle notwendigen Aspekte (Basisfall, Induktionsschritt, mögliche Berechnungsreihenfolge) enthalten sind.

Ja, der Beweis ist etwas länger aufgeschrieben als er vielleicht nötig wäre. Hier würde ich euch aber raten: Die 5 Minuten mehr für einen ordentlich begründeten (statt mglw. zu kurzem) Beweis lohnen sich in Anbetracht der vergebenen Punkte und der Sicherheit in die eigene Lösung.

## 2 -- Langweilige 08-15 Sprache
$$
L = \{a^p b^q ~|~ p,q \in \mathbb{N} \land p=\lfloor \frac{q}{3} \rfloor\}
= \{a^p b^q ~|~ p,q \in \mathbb{N} \land (3p=q \lor 3p+1=q \lor 3p+2=q)\}
$$

### (a)
Wir geben eine kontextfreie Grammatik an:
Sei $G = (T=\{a,b\}, N=\{S, R\}, P, S)$ mit den Produktionsregeln $P$
$$
S \to aSbbb ~|~ R, \qquad\text{wir pumpen die Wörter von den Rändern her auf}\\
R \to \varepsilon ~|~ b ~|~ bb\qquad\text{wir gucken uns den Rest der möglichen Wörter an}
$$
_(Erklärungen nicht notwendig)_

Wir zeigen, dass $L = L(G)$ gilt.

Sei $w \in L$. Für ein $k \in \mathbb{N}$ und $j \in \{0,1,2\}$ nehmen wir an, dass $w = a^k b^{k+j}$. Durch $k$-fache Anwendung der Regel $S \to aSbbb$ können wir das Wort auf $k$ $a$s und $3k$ $b$s aufpumpen. Durch Anwendung der Regeln $S \to R$ und $R$ zu $j$ vielen $b$s bekommt das Wort zusätzlich $j$ $b$s. Da alle $a$s nach Anwendung der Produktionsregeln links von allen $b$s stehen, haben wir so $w$ konstruiert.

Sei $w \in L(G)$. Da bei allen Regeln die $a$ links von den Variablen und allen $b$s stehen, müssen in $w$ alle $a$s vor $b$s vorkommen. Durch die Produktionsregeln von $S$ ausgehend werden für jedes produzierte $a$ $3$ $b$s produziert. Da die Regel $R$ offensichtlich nur einmal pro Wort angewendet werden kann und die Anzahl der $b$s um $0$ bis $2$ erhöht, muss für ein $k \in \mathbb{N}$ und ein $j \in \{0,1,2\}$ gelten, dass $|w|_a = k$ und $|w|_b = 3k+j$. Dies entspricht der Definition von $L$, wodurch $w \in L$ ist.

### (b)
Wir beweisen die Aussage durch das Pumping Lemma für reguläre Sprachen.

Sei $k \in \mathbb{N}$ beliebig. Wir betrachten das Wort $w=a^{k}b^{3k}$. Offensichtlich ist $w \in L$ und $|w| > k$. Für jede Aufteilung $w=xyz$ mit $y \not= \varepsilon$ und $|xy| \leq k$ muss somit gelten, dass $y$ nur aus $a$s besteht. Somit gilt für das Wort $w'=xy^0z$, dass es mindestens ein $a$ weniger hat als $w$. Somit hat aber $w'$ maximal $k-1$ $a$s und $3k$ $b$s. Somit ist $w' \notin L$. Dies ist ein Widerspruch gegen das Pumping Lemma und $L$ kann nicht regulär sein.