# TI 1, Endklausur 2019/20
## Disclaimer
Dies ist keine tatsächliche Klausurbearbeitung. Dies ist eine für didaktische Zwecke angelegte Lösung, die ich nach besten Gewissen, in größtmöglicher Kürze und unter Beachtung der Beweisqualität angelegt habe. Ich gebe keine Gewähr auf Vollständigkeit, Korrektheit oder sonst irgendwas. Besonders nicht auf Kekse. Es waren schon immer meine.

### Tipps
- Stefan ist kein Unmensch. Alle Aufgaben sind gut lösbar, kommt man auf die richtige Idee. Wenn ihr Schwierigkeiten und das Gefühl habt, ihr erklärt Rocket Science, so ist wahrscheinlich euer Ansatz nicht ganz korrekt und es lohnt sich nochmal 5 Minuten darüber nachzudenken und die Idee (für euch) sauber aufzuschreiben.
- Sind in der Klausur Tipps gegeben, ist es sehr ratsam sich in diese Richtung eine Lösung zu überlegen. Meist kommt ihr so sehr schnell auf einen richtigen Lösungsansatz.

## 1
### Anmerkung
Die Aufgabe lässt sich mit weniger Nachdenken aber mehr Schreibarbeit durch KRT lösen, was ihr nicht für diesen Zweck gezeigt bekommen habt. In diesem Fall ist es egal welche der Teilaussagen ihr durch die anderen herleitet, so ist die Reihenfolge etwas starrer.

### a.
Wir zeigen die Aussage über den Satz von Rice. Sei $d \in N, e \in BA_0$ und $\varphi_e = \varphi_d$. Da $\varphi_e = \varphi_d$ gilt und $e \in BA_0$ ist, muss für alle $y_1, y_2 \in range(\varphi_e) = range(\varphi_d)$ gelten, dass $|y_1 - y_2| < 0$ ist. Somit muss $d \in BA_0$ gelten und $BA_0$ ist eine semantische Menge. $BA_0$ ist keine triviale semantische Menge ($\notin \{\emptyset, N\}$, was gezeigt werden muss). Nach dem Satz von Rice ist eine semantische Menge nicht entscheidbar, womit auch $BA_0$ nicht entscheidbar ist.

**Anmerkung: Indexmenge und semantische Menge beschreiben dieselbe Struktur**

### b.
Wir reduzieren $BA_0$ auf $BA$. Sei dazu $$f: e \mapsto \langle e, 0\rangle$$ unsere Reduktionsfunktion. $f$ ist total berechenbar, da die Paarbildungsfunktion total berechenbar ist. Es bleiben die Beweisrichtungen zu zeigen.

Fall 1: $e \in BA_0$. So ist nach Definition $\langle e, 0\rangle \in BA$ und somit auch $f(e) \in BA$.
Fall 2: $e \notin BA_0$. So ist nach Definition $\langle e, 0\rangle \notin BA$ und somit auch $f(e) \notin BA$.

Da $BA_0$ auf $BA$ reduziert werden kann und $BA_0$ nicht entscheidbar ist, darf $BA$ nicht entscheidbar sein.

### c.
Dies wäre der Teil, den ich mit KRT machen würde. Sicher kann mensch aber auch eine Reduktion von einer beliebigen, nicht-semi-entscheidbare Menge machen auf $BA$.

### d.
Wir zeigen die Aussage über die Berechenbarkeit der partiell charakterischen Funktion von $\overline{BA}$

Wir definieren uns die Funktion $$\forall e, a \in N: g(\langle e, a \rangle) = \begin{cases} 1, \text{falls } \exists y_1, y_2 \in range(\varphi_e):y_1 > y_2 \land |y_1 - y_2| > a \\ \uparrow \end{cases}.$$
$g$ ist berechenbar, da wir für alle Werte von $y_1$ alle Werte $y_2 < y_1$ durchgehen können, indem wir alle Werte in $range(\varphi_e)$ mithilfe der Diagonalisierung durchgehen ($\varphi_e$ kann an Stellen undefiniert sein) (--> unbeschränkte Suche). Außerdem sind die Absolutfunktion und arithmetische Operationen berechenbar.

Sei nun $\langle e, a \rangle \in \overline{BA}$. So muss es Elemente $y_1, y_2$ geben, für die $|y_1 - y_2| > a$ gilt. Da wir mit der unbeschränkten Suche alle geordneten Paare (Reihenfolge ist wegen des Betrags egal) von Elementen in $range(\varphi_e)$ durchgehen, würden wir diese Elemente finden, womit $g(\langle e, a \rangle) = 1$ ist.
Sei nun $\langle e, a \rangle \notin \overline{BA}$. So gibt es keine Elemente $y_1, y_2$, für die $|y_1 - y_2| > a$ gilt. Somit kann die Funktion nie zwei Elemente finden, für die $|y_1 - y_2| > a$ gilt und die unbeschränkte Suche und somit auch $g(\langle e, a \rangle)$ bleiben undefiniert.

Hiermit ist klar geworden, dass $g(\langle e, a \rangle) = 1$ genau dann gilt, wenn $\langle e, a \rangle \in \overline{BA}$ ist und sonst undefiniert ist. Somit ist $g$ die partiell charakteristische Funktion für $\overline{BA}$. Da $g$ berechenbar ist, ist $\overline{BA}$ semi-entscheidbar.

### Joker für b, c, d (eingesetzt für c.)
Angenommen die Aussagen b, d sind gezeigt. Angenommen $BA$ sei semi-entscheidbar. Da $\overline{BA}$ semi-entscheidbar ist und $BA$ semi-entscheidbar ist, muss $BA$ entscheidbar sein. Da dies nicht der Fall ist, muss unsere Annahme falsch sein. Da zwei Aussagen bereits gelten, ist die dritte falsch.

## 2
### a.
**Nur Notizen**
Formalisierung: Zug als Array, Lok hat Wert 0 ...

Lest die Aufgabe genau (ist mir hier wieder passiert): Mensch sortiert nicht selbst, sondern gibt nur die Anzahl der Sortieroperationen aus ...

Wir definieren in einem Array $A$ einen benachbarten Fehlstand an der Stelle $i$, wenn $A[i] > A[i+1]$ gilt.

Algorithmus: Anzahl der benachbarten Fehlstände feststellen und dies mal 2 ausgeben.

Beweis: Wir betrachten eine (aufeinander folgende) Sequenz mit aufeinander folgenden Werten als ein Element mit dem Wert des ersten Elements in der Sequenz. Dann speichern wir alle Elemente aus dem Eingabearray von hinten nach vorne in dem zweiten Array (Gleise), je an der Stelle des Wertes des aktuellen Elements. Dann können wir von $1$ bis $n$ alle Stellen im zweiten Array durchgehen und an das Ausgabearray anhängen. Das ganze ist sortiert, was sich schnell zeigen lässt. Somit ist $2 \cdot \#(\text{benachbarte Fehlstände})$ eine obere Schranke für die Anzahl. Da jeder Fehlstand behoben werden muss, was nur durch ein Ab und Anhängen an das Array geht, ist dies eine untere Schranke und somit die korrekte Ausgabe. Der Algorithmus ist korrekt, da er die korrekte Formel berechnet.

Laufzeit: $O(n)$

### b
**Notizen**
Algo, der schneller als $O(n)$ ist, also mindestens $2$ Elemente nicht liest. Adversary:
Erlaubte Operationen: Leseoperation auf Array an Stelle $i$
Algo: Es wird eine aufsteigende Sortierung vorgehalten und die gelesenen Stellen markiert. Da der Lösungsalgorithmus in $o(n)$ laufen soll, sind mindestens $2$ Stellen nicht gelesen worden. Egal wo diese liegen, erzeugen sie entweder Fehlstellungen (falls nicht sortiert zurückgegeben) oder nicht (falls sortiert zurückgegeben). Da Anzahl Fehlstände nach 2.a. die Anzahl der Koppelvorgänge festlegt, kann somit auf eine Ausgabe des Lösungsalgorithmus immer eine passende, falsche, aber valide Eingabe zurückgegeben werden.

Bleibt zu zeigen:
* Ausgaben immer valide (da merken)
* Ausschreiben der Antworten auf die Ausgaben

## 3
**Formalisierung und Notizen**

Eingabe: Array $T$ der Länge $n$ über natürliche Zahlen, welches die Wörterlängen beinhaltet; die Zeilenbreite $B \in N^+$, die minimale und maximale Leerzeichenlänge $l_{min}, l_{max} \in N$
Ausgabe: Ein Array $Z$ über Tupel von natürlichen Zahlen, welches die Zerlegung des Textes in Zeilen beinhaltet.

Wir definieren uns $b(i, j, l)$ so wie in der Aufgabenstellung (ausschreiben ...).
Wir sagen ein Intervall von $i$ bis $j$ bzw. Tupel $(i, j)$ ist zu kurz, wenn $b(i, j, l_{max}) < B$ ist.
Wir sagen ein Intervall von $i$ bis $j$ bzw. Tupel $(i, j)$ ist zu lang, wenn $b(i, j, l_{min}) > B$ ist.

Der Algorithmus ist korrekt, wenn die Tupel von $Z$ als geschlossene Intervalle interpretiert den Raum der natürlichen Zahlen von $1$ bis $n$ zerlegen.
Außerdem muss $Z$ gültig sein, was heißt, dass alle Tupel $(i, j) \in Z$ nicht zu lang sind. Außerdem darf es keine gültige Zerlegung $Z'$ geben, für die Anzahl der zu kurzen Tupel in $Z'$ kleiner ist als die Anzahl der zu kurzen Tupel in $Z$ (Minimalität).

Algorithmus: DP-Algo:
An Stelle $i$ der Datenstruktur steht der minimale Wert an zu kurzen Zeilen, wenn alle Zeilen bisher gültig sind und nach dem Wort $T[i]$ ein Zeilenumbruch kommt.
Für jede Stelle in der DP-Datenstruktur schaue ich alle vorherigen Stellen $j$ an (sofern das Intervall $(i, j)$ nicht zu lang ist), wie viele zu kleine Intervalle gebildet werden, wenn nach Wort $T[j]$ der letzte Zeilenumbruch vor dem Wort $T[i]$ kam.

Beweis über Induktion (bzw. DP-Template).

Laufzeit in $O(n^2)$, bei der Berechnung der Übergänge muss man aufpassen nicht in $O(n^3)$ abzurutschen (Summe will berechnet werden ...). Wer genauer sein will, kann auch $O(n \cdot \min(n, B))$ nennen, da wir im jeden DP-Schritt maximal $B$ Elemente durchschauen (jedes Wort hat eine Mindestlänge von $1$). Asymptotisch änder dies leider nicht viel und es sind auch keine Bonuspunkte zu erwarten (vielleicht aber ein Fleißbienchen).

Diese Lösung berechnet nur die minimale Anzahl an zu kurzen Zeilen. Um die Zeilen nun auch auszugeben, kann man sich in der DP-DS zusätzlich das vorherige Element speichern, wo der letzte Zeilenumbruch war (zurzeit lesen wir nur den wert von dieser Stelle). So kann mensch nach diesem Algo die Zerlegung wiederherstellen.

Tipps:
* definiert euch "zu kurz" und "zu lang" für Zeilen, sodass ihr auch ohne Formelwirrwar schnell argumentieren könnt. Dies kann auch schon vor der Formalisierung geschehen
* Damit ihr nicht in Greedy abrutscht: Schreibt euch Beispiele auf und geht dann schnell zu DP über
* Solltet ihr in der Klausur keine Zeit mehr haben, den Algo auf die tatsächliche Ausgabe der Zerlegung zu überführen, schreibt eure Vorgehensweise was ihr ändern würdet, meistens reicht dies für eine korrekte Lösung. Schreibt außerdem, wieso dies die Korrektheit und die Laufzeit des Algorithmus nicht verändert.

## Fehler
In dieser Bearbeitung sind einige Fehler. Diese dienen zu 100% didaktischen Zwecken und sind nicht aus Versehen hier reingekommen. Solltet ihr diese didaktischen Lücken finden, kommentiert es gerne und/oder gebt mir kurz Bescheid.