chapter_2.tex

\chapter{Alphabete, Wörter, Sprachen}
Zur Darstellung von Daten werden Symbole verwendet. Diese wiederum werden zur Bildung von Wörtern genutzt. Und aus Wörtern bildet sich eine Sprache.

\section{Alphabet}
\begin{definition}
Eine endliche nichtleere Menge $\Sigma$ heisst \textbf{Alphabet}. Die Elemente von $\Sigma$ werden als \textbf{Buchstaben, Zeichen oder Symbole} bezeichnet.
\end{definition}

Häufig benötigte Alphabete:
\begin{itemize}
    \item $\Sigma_\text{bool} = \{0,1\}$
    \item $\Sigma_\text{lat} = \{a, b, c, \ldots, z\}$
    \item $\Sigma_\text{Tastatur} = \Sigma_\text{lat} \cup \{A, B, C, \ldots, \textvisiblespace, <, >, \ldots\}$ (Alphabet aller Zeichen auf einer Tastatur)
    \item $\Sigma_m = \{0, 1, 2, \ldots, m - 1\}$ (Alphabet für die $m$-adische Darstellung von Zahlen, $m \geq 1$)
    \item $\Sigma_\text{logic} = \{0, 1, x, (, ), \land, \lor, \lnot\}$ (Alphabet um Boole'sche Formeln darzustellen)
\end{itemize}

\section{Wort}
\subsection{Grundlagen}
Ein \textbf{Wort} wird aus Elementen eines zugrundeliegenden Alphabets gebildet.\\

\begin{definition}
Sei $\Sigma$ ein Alphabet. Ein \textbf{Wort} über $\Sigma$ ist eine endliche Folge von Buchstaben aus $\Sigma$.\\
\end{definition}

\begin{remark}
$\Sigma^*$ ist die Menge aller Wörter über dem Alphabet $\Sigma$. $\Sigma^+ = \Sigma^* - \{\lambda\}$, also die Menge aller Wörter ohne das leere Wort.\\
\end{remark}


\begin{definition}
Das \textbf{leere Wort} wird durch $\lambda$ (oft auch $\epsilon$) dargestellt und entspricht der leeren Folge.\\
\end{definition}

\begin{definition}
Die \textbf{Länge} eines Wortes $w$, bezeichnet durch $|w|$, ist die Länge der Folge, d.h. die Anzahl vorkommender Buchstaben in $w$.\\
\end{definition}

\begin{remark}
Das leere Wort $\lambda$ ist ein Wort über jedem Alphabet.\\
\end{remark}

\begin{definition}
Sei $w \in \Sigma^*$ und $a \in \Sigma$. Dann ist $|w|_a$ definiert als die Anzahl der Vorkommen von $a$ in $w$.
\end{definition}


\subsection{Beispiele für Kodierungen}
\subsubsection{Natürliche Zahlen}
Sei $m$ eine natürliche Zahl. Dann erzeugt die Funktion $\operatorname{Bin}(m) \in \Sigma_\text{bool}^*$ die binäre Darstellung der natürlichen Zahl $m$. Damit $\operatorname{Bin}(m)$ eindeutig ist, soll die Funktion die kürzeste binäre Darstellung liefern (das erste Zeichen ist eine 1).

Die Umkehrfunktion ist $\text{Nummer}(x) = \sum_{i = 1}^n x_i \cdot 2^{n-i}$ und erzeugt für eine binäre Darstellung $x$ die natürliche Zahl.

\subsubsection{Graphen}
Gerichtete Graphen $G = (V, E)$ ($V$ ist die Knotenmenge, $E$ die Kantenmenge) können durch eine Adjazenzmatrix $M_G$ beschrieben werden: $M_G = [a_{ij}]$. Falls der Knoten $v_i \in V$ mit dem Knoten $v_j \in V$ verbunden ist, so gilt für $M_G$: $a_{ij} = 1$, sonst $a_{ij} = 0$. Die Adjazenzmatrix kann nun durch ein Wort über dem Alphabet $\Sigma = \{0, 1, \#\}$ beschrieben werden. Dazu schreibt man den Inhalt jeder Zeile nacheinander und trennt die Zeilen im entstehenden Wort durch $\#$.

Möchte man einen gewichteten Graphen $G = (V, E, h)$ mit einer Funktion $h(e) \in \N - \{0\}$ für eine Kante $e \in E$, so kann dies ebenfalls über dem Alphabet $\Sigma = \{0, 1, \#\}$ gemacht werden. Wieder schreibt man den Inhalt jeder Zeile der Adjazenzmatrix nacheinander. Dabei kodiert man die Gewichtung mittels $\operatorname{Bin}(h(e))$, trennt die einzelnen Matrixeinträge durch $\#$ ab und Zeilen durch $\#\#$.

\subsubsection{Bool'sche Formeln}
Für Bool'sche Formeln verwenden wir das Alphabet $\Sigma_\text{logic} = \{0, 1, x, (, ), \land, \lor, \lnot\}$. In Bool'schen Formeln kommen, im Gegensatz zu unserem Alphabet, beliebig viele Variabeln $x_i$ vor. Unser Alphabet muss aber gleichzeitig endlich sein. Deshalb werden die Variabeln $x_i$ durch das Wort $x\operatorname{Bin}(i)$ kodiert. Die restlichen Symbole können direkt übernommen werden.

\subsection{Konkatenation}
\begin{definition}
Die \textbf{Verkettung (Konkatenation)} für ein Alphabet $\Sigma$ ist eine Abbildung $K: \Sigma^* \times \Sigma^* \to \Sigma^*$, so dass für alle $x, y \in \Sigma^*$
\[
K(x, z) = x \cdot y = xy
\]
gilt.\\
\end{definition}

\begin{remark}
Die Verkettung $K$ über $\Sigma$ ist eine assoziative Operation:
\[
K(u, K(v, w)) = u \cdot (v \cdot w) = u \cdot (vw) = uvw = (u \cdot v) \cdot w = K(K(u, v), w)
\]\\
\end{remark}

\begin{remark}
Für jedes $w \in \Sigma^*$ gilt
\[
w \cdot \lambda = \lambda \cdot w = w
\]\\
\end{remark}

\begin{remark}
Die Konkatenation ist nur für einelementige Alphabete kommutativ.\\
\end{remark}

\begin{remark}
Für alle $x, y \in \Sigma^*$ gilt:
\[
|xy| = |x \cdot y| = |x| + |y|
\]
\end{remark}

\begin{definition}
Sei $\Sigma$ ein Alphabet. Für alle $x \in \Sigma^*$ und alle $i \in \N$ wird die $i$-te Iteration $x^i$ von $x$ definiert als:
\[
x^0 = \lambda,\quad x^1 = x,\quad x^i = x \cdot x^{i-1}
\]
\end{definition}

\subsection{Teilworte}
\begin{definition}
Seien $u, w \in \Sigma^*$ für ein Alphabet $\Sigma$.
\begin{itemize}
  \item $v$ ist ein \textbf{Teilwort} von $w$ $\Leftrightarrow \exists x, y \in \Sigma^*: w = xvy$
  \item $v$ ist ein \textbf{Suffix} von $w$ $\Leftrightarrow \exists x \in \Sigma^*: w = xv$
  \item $v$ ist ein \textbf{Präfix} von $w$ $\Leftrightarrow \exists x \in \Sigma^*: w = vx$
  \item $v$ ist ein \textbf{echtes} Teilwort/Suffix/Präfix von $w$ genau dann, wenn $v \not= w$, $v \not= \lambda$ und $v$ ist ein Teilwort/Suffix/Präfix von $w$
\end{itemize}

\end{definition}

\subsection{Ordnung}
\begin{definition}
Sei $\Sigma = \{s_1, s_2, \ldots, s_m\}$ ein Alphabet für ein beliebiges $m \geq 1$. Weiter sei $s_1 < s_2 < s_3 < \ldots < s_m$ eine Ordnung auf $\Sigma$. Darauf basierend wird die \textbf{kanonische Ordnung} auf $\Sigma^*$ für $u, v \in \Sigma^*$ wie folgt definiert:
\begin{align*}
u < v \Leftrightarrow \quad & |u| < |v|\\
&\lor (|u| = |v| \land u = x \cdot s_i \cdot u' \land v = x \cdot s_j \cdot v'\\
&\text{für beliebige } x, u', v' \in \Sigma^* \text{und } i < j)
\end{align*}

\end{definition}

\section{Sprache}
Eine Sprache wird durch eine beliebige Menge von Wörtern über einem festen Alphabet gebildet.

\begin{definition}
Eine \textbf{Sprache} $L$ über einem Alphabet $\Sigma$ ist eine Teilmenge von $\Sigma^*$.\\
\end{definition}

\begin{itemize}
  \item $L_\emptyset = \emptyset$ ist die leere Sprache (hat keine Elemente)
  \item $L_\lambda = \{\lambda\}$ ist die einelementige Sprache, die nur das leere Wort enthält\\
\end{itemize}

\begin{definition}
Sind $L_1$ und $L_2$ zwei Sprachen über demselben Alphabet $\Sigma$, so ist
\[
L_1 \cdot L_2 = L_1 L_2 = \{vw | v \in L_1, w \in L_2\}
\]
die \textbf{Konkatenation} von $L_1$ und $L_2$.\\
\end{definition}

\begin{definition}
Ist $L$ eine Sprache über $\Sigma$, so wird definiert:
\begin{itemize}
  \item $L^0 = L_\lambda$
  \item $L^{i+1} = L^i \cdot L, \quad \forall i \in \N$
  \item $L^* = \bigcup_{i \in \N} L^i$ (ist der \textbf{Kleene'sche Stern})
  \item $L^+ = \bigcup_{i \in \N - \{0\}} L^i = L \cdot L^*$\\
\end{itemize}
\end{definition}

\begin{remark}
\
\begin{itemize}
  \item $\Sigma^i = \{w | w \in \Sigma^* \land |w| = i\}$
  \item $L_\emptyset L = L_\emptyset = \emptyset$
  \item $L_\lambda L = L$\\
\end{itemize}

\end{remark}

\begin{lemma}
Seien $L_1, L_2, L_3$ Sprachen über dem Alphabet $\Sigma$. Dann gilt $L_1 L_2 \cup L_1 L_3 = L_1 (L_2 \cup L_3)$.\\
\end{lemma}

\begin{lemma}
Seien $L_1, L_2, L_3$ Sprachen über dem Alphabet $\Sigma$. Dann gilt $L_1 (L_2 \cap L_3) \subseteq L_1 L_2 \cap L_1 L_3$\\
\end{lemma}

\begin{definition}
Seien $\Sigma_1, \Sigma_2$ zwei Alphabete. Ein \textbf{Homomorphismus} von $\Sigma_1^*$ nach $\Sigma_2^*$ ist jede Funktion $h: \Sigma_1^* \to \Sigma_2^*$ mit folgenden Eigenschaften:
\begin{itemize}
  \item $h(\lambda) = \lambda$
  \item $h(uv) = h(u) \cdot h(v) \quad \forall u,v \in \Sigma_1^*$\\
\end{itemize}
\end{definition}

\begin{remark}
Um einen Homomorphismus zu spezifizieren reicht es aus für alle Zeichen $a \in \Sigma_1$ $h(a)$ zu definieren.
\end{remark}

\section{Algorithmische Probleme}
Ein Programm ist im Grunde eine Abbildung $A$, welche ein Wort über $\Sigma_1$ in ein Wort über $\Sigma_2$ abbildet: $A: \Sigma_1^* \to \Sigma_2^*$. Somit ist sowohl die Eingabe, wie auch die Ausgabe des Programms als Wort kodiert und $A$ bestimmt für jedes Eingabewort ein bestimmtes Ausgabewort.


Zwei Programme $A$ und $B$ sind \textbf{äquivalent}, wenn für alle $x \in \Sigma_1^*$ $A(x) = B(x)$ gilt.

\subsection{Entscheidungsproblem}
\begin{definition}
Das \textbf{Entscheidungsproblem $(\Sigma, L)$} für ein gegebenes Alphabet $\Sigma$ und eine gegebene Sprache $L \subseteq \Sigma^*$ ist, für jedes $x \in \Sigma^*$ zu entscheiden ob
\[
x \in L \text{ oder } x \not\in L.
\]\\
\end{definition}

\begin{definition}
Ein Algorithmus $A$ \textbf{löst} das Entscheidungsproblem $(\Sigma, L)$, falls für alle $x \in \Sigma^*$ gilt:
\[
A(x) =
\begin{cases}
1, &\text{falls } x \in L \\
0, &\text{falls } x \not \in L
\end{cases}
\]
In diesem Fall sagt man, dass $A$ die Sprache $L$ \textbf{erkennt}.\\
\end{definition}

\begin{definition}
Wenn für eine Sprache $L$ ein Algorithmus existiert, der $L$ erkennt, so sagt man, dass $L$ \textbf{rekursiv} ist.\\
\end{definition}


\begin{definition}
Seien $\Sigma, \Gamma$ zwei Alphabete. Wir sagen, dass ein Algorithmus $A$ eine \textbf{Funktion $f: \Sigma^* \to \Gamma^*$} berechnet, falls
\[
\forall x \in \Sigma^*: A(x) = f(x)
\]
\end{definition}

Das Entscheidungsproblem ist ein Spezialfall einer Funktionsberechnung.

\subsection{Relationsproblem}
\begin{definition}
Seien $\Sigma, \Gamma$ zwei Alphabete, und sei $R \subseteq \Sigma^* \times \Gamma^*$ eine Relation. Ein Algorithmus $A$ löst das \textbf{Relationsproblem} $R$, falls für jedes $x \in \Sigma^*$ gilt:
\[
(x, A(x)) \in R
\]
\end{definition}

\subsection{Optimierungsproblem}
\begin{definition}
Ein \textbf{Optimierungsproblem} ist ein 6-Tupel $\mathcal{U} = (\Sigma_I, \Sigma_O, L, \mathcal{M}, \operatorname{cost}, \operatorname{goal})$:
\begin{itemize}
  \item $\Sigma_I$ ist das Eingabealphabet
  \item $\Sigma_O$ ist das Ausgabealphabet
  \item $L \subseteq \Sigma_I^*$ ist die Sprache der zulässigen Eingaben
  \item $\mathcal{M}$ ist eine Funktion $\mathcal{M}: L \to \mathcal{P}(\Sigma_O^*)$. Für jedes $x \in L$ ist $\mathcal{M}(x)$ die Menge der zulässigen Lösungen für $x$
  \item $\operatorname{cost}$ ist eine Funktion $\operatorname{cost}: \bigcup_{x \in L}(\mathcal{M} \times \{x\}) \to \R^+$ und ist die Preisfunktion
  \item $\operatorname{goal} \in \{\text{Minimum}, \text{Maximum}\}$ ist das Optimierungsziel
\end{itemize}

Eine zulässige Lösung $\alpha \in \mathcal{M}(x)$ heisst \textbf{optimal} für den Problemfall $x$ des Optimierungsproblems $U$, falls
\[
\operatorname{cost}(\alpha, x) = \operatorname{Opt}_\mathcal{U} = \operatorname{goal}\{\operatorname{cost}(\beta, x) | \beta \in \mathcal{M}(x)\}
\]\\
\end{definition}

\begin{definition}
Ein Algorithmus $A$ \textbf{löst} $\mathcal{U}$, falls für jedes $x \in L$:
\begin{enumerate}
  \item $A(x) \in \mathcal{M}(x)$ ($A(x)$ ist eine zulässige Lösung des Problemfalls $x$ von $\mathcal{U}$)
  \item $\operatorname{cost}(A(x), x) = \operatorname{goal}\{\operatorname{cost}(\beta, x) | \beta \in \mathcal{M}(x)\}$
\end{enumerate}
\end{definition}

\begin{remark}
Oft wird die Spezifikation von $\Sigma_I, \Sigma_O$ bei Optimierungsproblemen weggelassen. Man geht davon aus, dass die verwendeten Daten kodiert werden können für ein $\Sigma_I, \Sigma_O$. So bleiben noch vier Dinge übrig, die spezifiziert werden müssen:
\begin{enumerate}
  \item die Menge der Problemfälle $L$, also die zulässigen Eingaben
  \item die Menge der Einschränkungen, gegeben durch jeden Problemfall $x \in L$, und damit $\mathcal{M}(x)$ für jedes $x \in L$. $\mathcal{M}(x)$ gibt uns Lösungen, die den Einschränkungen genügen für ein gegebenes $x \in L$
  \item die Kostenfunktion
  \item das Optimierungsziel
\end{enumerate}

\end{remark}

\subsubsection{Beispiel: Traveling Salesman Problem (TSP)}
\begin{description}
  \item[Eingabe:] Ein gewichteter Graph $(G, c)$, wobei $G = (V, E)$ ein Graph ist und $c: E \to \N - \{0\}$ die Kostenfunktion. Strikt formal müsste man das Eingabealphabet eingeben und mit diesem den Graphen kodieren.
  \item[Einschränkungen:] Für jeden Problemfall $(G, c)$ ist $\mathcal{M}(G, c)$ die Menge aller Hamiltonscher Kreise von $G$ mit der Kostenfunktion $e$.
  \item[Kosten:] Für jeden Hamiltonschen Kreis $H = v_{i_1}, v_{i_2}, \ldots, v_{i_n}, v_{i_1} \in \mathcal{M}(G, c)$:
    \[
    \operatorname{cost}((v_{i_1}, v_{i_2}, \ldots, v_{i_n}, v_{i_1}), (G, c)) = \sum_{j = 1}^n c \left (\{v_{i_j}, v_{i_{(j \mod n) + 1}}\} \right )
    \]
    Die Kosten jedes Hamiltonschen Kreises ist somit die Summe der Gewichte der besuchten Kanten.
  \item[Ziel:] Minimum\\
\end{description}

\begin{definition}
Ein Optimierungsproblem $\mathcal{U}_1 = (\Sigma_I, \Sigma_O, L', \mathcal{M}, \operatorname{cost}, \operatorname{goal})$ ist ein \textbf{Teilproblem} vom Optimierungsproblem $\mathcal{U}_2 = (\Sigma_I, \Sigma_O, L, \mathcal{M}, \operatorname{cost}, \operatorname{goal})$, falls $L' \subseteq L$.
\end{definition}

\subsubsection{Knotenüberdeckung}
\label{sec:knotenueberdeckung}
\begin{definition}
Eine \textbf{Knotenüberdeckung} eines Graphen $G = (V, E)$ ist jede Knotenmenge $U \subseteq V$, so dass jede Kante aus $E$ mit mindestens einem Knoten aus $U$ inzident ist. Eine Kante $\{u, v\} \in E$ ist inzident zu $u$ und $v$.

Anders gesagt: Jede Kante muss an mindestens einem Ende in einem Knoten enden, der in der Knotenmenge der Knotenüberdeckung ist.
\end{definition}

\subsubsection{Beispiel: Maximale Clique Problem (MAX-CL)}
\begin{definition}
Eine Clique eines Graphen $G = (V, E)$ ist jede Teilmenge $U \subseteq V$, so dass $\{\{u, v\} | u, v \in U, u \not= v\} \subseteq E$ (die Knoten von $U$ bilden einen vollständigen Teilgraphen von $G$).
\end{definition}

Das Maximale Clique Problem besteht nun darin eine Clique mit maximaler Kardinalität zu finden. Wir suchen also einen vollständigen Teilgraphen mit maximaler Anzahl von Knoten. Ein vollständiger Teilgraph ist ein Graph $H = (U, F), U \subseteq V, F \subseteq E$, so dass $F$ alle Kanten aus $E$ enthält, die zwei Knoten in $U$ verbinden.

\begin{description}
  \item[Eingabe:] Ein (ungerichteter) Graph $G = (V, E)$
  \item[Einschränkung:] $\mathcal{M}(G) = \{S \subseteq V | \{\{u, v\} | u, v \in S, u \not= v\} \subseteq E\}$
  \item[Kosten:] Für jedes $S \in \mathcal{M}(G)$ ist $\operatorname{cost}(S, G) = |S|$
  \item[Ziel:] Maximum
\end{description}

\subsubsection{Beispiel: Maximale Erfüllbarkeit (MAX-SAT)}
Sei $X = \{x_1, x_2, \ldots \}$ die Menge der Bolle'schen Variabeln. Sei $Lit_X = \{x, \overline{x} | x \in X\}$ die Menge der Literale. Dabei ist $\overline{x}$ die negation von $x$. Eine Klausel ist eine beliebig grosse endliche Disjunktion von Literalen (z.B. $x_1 \lor \overline{x_2} \lor x_3$).

Eine Formel ist in \textbf{konjunktiver Normalform (KNF)}, falls sie eine Konjunktion von Klauseln ist. Also eine Konjunktion von Disjunktionen. Beispiel: $(x_1 \lor \overline{x_2} \lor \overline{x_3}) \land (x_4 \lor \overline{x_5})$.

Das Problem der maximalen Erfüllbarkeit ist, für eine gegebene Formel $\Phi$ in KNF, eine Belegung der Variabeln zu finden, die die maximale mögliche Anzahl an Klauseln von $\Phi$ erfüllt.

\begin{description}
  \item[Eingabe:] Eine Formel $\Phi$ in KNF
  \item[Einschränkung:] Für jede Formel $\Phi$ über $\{x_{i_1}, x_{i_2}, \ldots, x_{i_n}\}$ ist $\mathcal{M}(\Phi) = \{0, 1\}^n$. Jedes $\alpha = \alpha_1 \alpha_2 \ldots \alpha_n \in \mathcal{M}(\Phi), \alpha_j \in \{0, 1\}$ für $j = 1, 2, \ldots, n$ stellt eine Belegung für die Variable $x_{i_j}$ dar.
  \item[Kosten:] Für jedes $\Phi$ und jedes $\alpha \in \mathcal{M}(\Phi)$ ist $\operatorname{cost}(\alpha, \Phi)$ die Anzahl der Klauseln, die durch $\alpha$ erfüllt werden.
  \item[Ziel:] Maximum
\end{description}

\subsubsection{Beispiel: Ganzzahlige Lineare Programmierung (integer linear programming, ILP)}
Für ein gegebenes System von linearen Gleichungen und eine lineare Funktion von Unbekannten des linearen Systems soll eine Lösung dieses Systems berechnet werden. Die Lösung soll dabei minimal sein bezüglich der gegebenen linearen Funktion.

\begin{description}
  \item[Eingabe:] Eine $m \times n$ Matrix $A$ und zwei Vektoren $b = (b_1, \ldots, b_m)^T$ und $c = (c_1, \ldots, c_n)$, wobei die Elemente von $A, b, c$ ganze Zahlen sind.
  \item[Einschränkung:] $\mathcal{M}(A, b, c) = \{ X = (x_1, \ldots, x_n)^T \in \N^n | AX = b\}$. $\mathcal{M}(A, b, c)$ enthält somit alle Lösungsvektoren $X$ für die $AX = b$ gilt.
  \item[Kosten:] Für jedes $X = (x_1, \ldots, x_n) \in \mathcal{M}(A, b, c)$ ist $\operatorname{cost}(X, (A, b, c)) = \sum_{i=1}^n c_i x_i$
  \item[Ziel:] Minimum
\end{description}

\subsection{Weitere Algorithmische Probleme}
\begin{definition}
Sei $\Sigma$ ein Alphabet, $x \in \Sigma^*$. Ein Algorithmus $A$ \textbf{generiert} das Wort $x$, falls $A$ für die Eingabe $\lambda$ die Ausgabe $x$ liefert.\\
\end{definition}

Das folgende Programm erzeugt beispielsweise das Wort $1001$:
\begin{lstlisting}
begin
  write(1001);
end
\end{lstlisting}

Ein solches Programm kann als alternative Darstellung des Wortes verwendet werden.\\

\begin{definition}
Sei $\Sigma$ ein Alphabet und $L \subseteq \Sigma^*$ eine Sprache. Ein \textbf{Aufzählungsalgorithmus $A$ für $L$} gibt für die Eingabe $n \in \N - \{0\}$ die Wortfolge $x_1, x_2, \ldots, x_n$ aus, wobei $x_1, x_2, \ldots, x_n$ die kanonisch ersten $n$ Wörter aus $L$ sind.
\end{definition}

\section{Kolmogorov-Komplexität}
\begin{definition}
Für jedes Wort $x \in \Sigma_\text{bool}^*$ ist die \textbf{Kolmogorov-Komplexität $K(x)$} des Wortes $x$ die binäre Länge des kürzesten Pascal-Programms, das $x$ generiert.
\end{definition}

\begin{lemma}
Es existiert eine Konstante $d$, so dass für jedes $x \in \Sigma_\text{bool}^*$
\[
K(x) \leq |x| + d
\]
\end{lemma}

Die Länge eines solchen Programms ist also nicht wesentlich länger als das Wort selbst. Wir können für jedes Wort $x \in \Sigma_\text{bool}^*$ das Programm
\begin{lstlisting}
begin
  write(x);
end
\end{lstlisting}

Man sieht, dass bloss das Wort $x$ variabel im Programm ist und der Rest eine fixe Länge hat.

Das Wort $x$ wird im Programm in binärer Form eingefügt und leistet deswegen zur binären Darstellung des Programms nur den Beitrag $|x|$.\\

\begin{remark}
Für ein Wort $x \in \Sigma_\text{bool}^*$ braucht das Abspeichern von $\operatorname{Bin}(|x|)$ so viel Platz: $\lceil \log_2 (\operatorname{Bin}(|x|) + 1) \rceil$
\end{remark}

\subsection{Beispiel \#1}
Um die Wörter der Form $y_n = 0^n \in \{0, 1\}^*$ für jedes $n \in \N - \{0\}$ zu generieren, könnte das folgende Programm eingesetzt werden:
\begin{lstlisting}
begin
  for l = 1 to |$n$| do
    write(0);
end
\end{lstlisting}

Wobei sich je nach Wort nur die Kodierung von $n$ im Programm verändert. Somit erhalten wir für die Länge der Kodierung von $n$: $\lceil \log_2(n + 1) \rceil$. Dies gibt uns eine Kolmogorov-Komplexität von $K(y_n) \leq \lceil \log_2(n+1) \rceil + c = \lceil \log_2 |y_n| \rceil + c$

\subsection{Beispiel \#2}
Das Wort $z_n = 0^{n^2} \in \{0, 1\}^*$ für jedes $n \in \N - \{0\}$ kann durch folgendes Programm dargestellt werden:
\begin{lstlisting}
begin
  M := n;
  M := M |$\times$| M;
  for l = 1 to M do
    write(0);
end
\end{lstlisting}

Hier ist wieder bloss $n$ abhängig vom Wort, der Rest des Programms hat eine feste Länge. Wir erhalten somit
\[
K(z_n) \leq \lceil \log_2 (n+1) \rceil + d \leq \lceil \log_2 (\sqrt{|z_n|}) \rceil + d + 1
\]

\subsection{Weiteres}
\begin{definition}
Die Kolmogorov-Komplexität einer natürlichen Zahl $n$ ist $K(n) = K(\operatorname{Bin(n)})$.
\end{definition}

\begin{lemma}
Für jede Zahl $n \in \N - \{0\}$ existiert ein Wort $w_n \in \Sigma_\text{bool}^n$, so dass $K(w_n) \geq |w_n| = n$, es existiert somit für jede Zahl $n$ ein nichtkomprimierbares Wort der Länge $n$.\\
\end{lemma}

\begin{satz}
Seien $A$ und $B$ zwei Programmiersprachen. Dann existiert die Konstante $c_{A, B}$, die nur von $A$ und $B$ abhängig ist, so dass:
\[
|K_A(x) - K_B(x)| \leq c_{A, B} \quad \forall x \in \Sigma_\text{bool}^*
\]

Daraus folgt, dass die verwendete Programmiersprache nicht relevant ist für die Berechnung der Kolmogorov-Komplexität.\\
\end{satz}

\begin{definition}
Ein Wort $x \in \Sigma_\text{bool}^*$ ist \textbf{zufällig}, falls $K(x) \geq |x|$.

Eine Zahl $n \in \N$ ist zufällig, falls $K(n) = K(\operatorname{Bin}(n)) \geq \lceil \log_2(n+1) \rceil -1$.
\end{definition}

\todo[inline]{Satz 2.2, Satz 2.3 (Primzahlsatz)}