\documentclass [12pt] {report}
\usepackage{ngerman} %Deutsche Sprache (Umlaute...)
\usepackage[ansinew]{inputenc} %Umlaute im Text erkennen

\usepackage{amsfonts}
\usepackage[dvips]{graphicx} 
\usepackage{fancyhdr}
\setlength{\headheight}{28pt}

\newcommand{\n}{\newline}
\renewcommand{\b}{\textbf}
\renewcommand{\u}{\underline}
\newcommand{\nn}{\par\noindent\n}
\newcommand{\mN}{\mathbb{N}}

\title {BWInf 24.2.2 }
\pagestyle{fancyplain}
\lhead{BWInf 24.2.2 Trimm-Dich-Pfade\n Benito van der Zander}
\rhead{\thepage}
\fancyfoot{}


\begin{document}

%
\chapter{Lösungsidee}
Mein Algorithmus zum Zählen der Übungen basiert auf einem interessanten Effekt, der entsteht wenn man zu einer Folge von Übungen eine weitere hinzufügt. Dann nimmt nämlich die Anzahl der Möglichkeiten Übungen durchzuführen um genau die Anzahl der bisherigen Möglichkeiten abzüglich der Anzahl der Möglichkeiten, die sich ergeben, wenn man nur die Übungen vor dem letzten Auftreten der neuen Übung benutzt, zu.\n
Ist es eine neue Übung, die bisher nicht vorkam, gibt es logischerweise kein letztes Auftreten dieser Übung, weshalb die Anzahl der Möglichkeiten um sich selbst zu nimmt, bzw. sie verdoppelt sich.\n
Das kann man gut an einem Beispiel sehen:
\begin{table*}[h]
	\begin{tabular}{lrlr}
	   Folge   & Möglichkeiten & Teilfolge & Änderung \\
             &  1 & -    &       \\
     \b{a}       &  2 & -    &     \\
     a\b{b}      &  4 & -    &     \\
     \b{a}b\b{a}     &  7 &      & +4 -1 \\
     aba\b{c}    & 14 & -    &       \\
     \u{ab}\b{a}c\b{a}   & 24 & ab   & +14 -4 \\
     \u{a}\b{b}aca\b{b}  & 46 & a    & +24 -2 \\
     \u{abac}\b{a}b\b{a} & 78 & abac & +46-14\\
	\end{tabular}
\end{table*}
Auf diese Weise kann man nun aus einer gegebenen Folge von Übungen, die Anzahl der Möglichkeiten berechnen, indem man einfach immer eine Übung hinzufügt und wie im Beispiel die Anzahl der Möglichkeiten neuberechnet.

\nn
Das komplizierte ist nun zu beweisen, dass dieses Verfahren auch wirklich funktioniert.\n
Als ersten Test kann man das Verfahren für verschiedene Folgen durchführen, und die damit berechnete Anzahl von Möglichkeiten mit einer Anzahl vergleichen, die man auf andere Art (z.B.: durch Aufzählen aller Folgen) ermittelt hat.\n
Damit kann man zwar nicht sicherstellen, dass das Verfahren fehlerfrei ist, da man ja möglicherweise gerade die Folge nicht getestet hat, bei der das Verfahren versagen würde.\n
Deshalb nimmt man besser einen anderen Weg um die Korrektheit des Algorithmus zu zeigen, und zwar in der Art eines mathematischen Beweises.

\nn 
Dabei muss man beweisen, dass der gleich am Anfang beschriebene Effekt beim Hinzufügen einer Übung wirklich auftritt und man auf diese Weise auch tatsächlich die Anzahl der neuen Möglichkeiten erhält.\n
Um eine Folge von Übungen anzugeben, schreibe ich die Übungen direkt hintereinander. Eine Folge, die direkt von einer Übung gefolgt wird, bedeutet die Folge die entsteht, wenn man an die alte Folge, die neue Übung anhängt. Ist $v$ eine Übung, so ist $v^i$ mit $i \in \mN$ die Folge die ensteht, wenn man i-mal hintereinander die Übung $v$ schreibt. (Also $v^0 = $, $v^1 = v$, $v^2 = vv$, $v^3 = vvv$, $\ldots$). Ist $F$ eine Folge, so meint $F*$ die Menge aller Teilfolgen von $F$ und $F^{*v}$ die Menge aller Teilfolgen von $F$, die mit $v$ enden. Ist M eine Menge, so ist $|M|$ wie normal die Anzahl ihrer Elemente.\n
Sei $F=u_{1}u_{2}u_{3} \ldots u_{n-1}u_{n}$ eine Folge von Übungen und $v$ eine neue Übung.\n
Offenbar gilt $|Fv^*| = |F^*| + |Fv^{*v}| - |F^{*v}|$.\n
Daher ist nur die Zahl $|Fv^{*v}| - |F^{*v}|$ zu bestimmen.
\begin{itemize}
	 \item Zu zeigen: $|Fv^{*v}| \geq |F^*|$:\n
	    Sei $T \in F^*$.
	    \begin{itemize}
	      \item Fall 1: $T$ endet mit $v$:\n
	            Dann gilt $T \in Fv^{*v}$. 
	      \item Fall 2: $T$ endet nicht mit $v$:\n
	            Da $F^*$ endlich ist, gibt es ein $i \in \mN$, so dass $Tv^j \in F^*$ für alle $j < i$ und $Tv^j \notin F^*$ für alle $j \geq i$.\n
	            Dann ist $Tv^i \in Fv^{*v}$, da $Tv^i$ aus einer Teilfolge aus $F^*$ mit der angehängten Übung $v$ besteht..
	    \end{itemize}
	    Für jedes Element von $F^*$, gibt es also ein Element in $Fv^{*v}$.\n
	    Daher ist $|Fv^{*v}| = |F^*|$.

   \item Zu zeigen: $|Fv^{*v}| \leq |F|$:\n
   Sei $T \in Fv^{*v}$.
   Angenommen $T \notin F^*$. Dann kann man $T$ als $T = Sv$ schreiben, mit einer Teilfolge $S \in F^*$, wobei natürlich gilt $S \neq S'$ für $Sv \neq S'v$\n
   Für jedes $T \in Fv^{*v}$ gibt es also ein eindeutiges  Element $T' \in F^*$, oder es gilt $T \in F^*$.\n
   Daher ist $|Fv^{*v}| \leq |F|$.
\end{itemize}


\begin{itemize}
	\item Fall 1: Es gibt kein $i$, so dass $u_i = v$, also $v$ kommt in der Folge noch nicht vor.\n
	  Daher ist $F^{*v} = 0$, da es ja kein $v$ in $F$ gibt.\n
	  Also ist $|Fv^*| = |F^*| + |Fv^{*v}| - |F^{*v}| = |F^*| + |F^*| - 0 = 2|F^*|$
	  
	\item Fall2: Es gibt ein $i$, so dass $u_i = v$\n
	  Sei $T = u_1u_2 \ldots u_{i-2}u_{i-1}$.\n
	  Zu zeigen: $|F^{v*}| = |T^*|$.
	  \begin{itemize}
	
	    \item Z.z.: Es gibt mindestens $m - k$ unterschiedliche Teilfolgen von $Fv$, die mit $v$ enden:
	    
	    \item Z.z.: Es gibt maximaal $m - k$ unterschiedliche Teilfolgen von $Fv$, die mit $v$ enden:\n
	    Offenbar ist jede Teilfolge von $F$, die mit $v$ endet, eine Teilfolge von $Tv$.\n
	    Das heißt es gibt genau $|T|$ Teilfolgen von $F$, die mit 
	    Es gibt genau $k$ unterschiedliche Teilfolgen von $Fv$, die mit $v$ enden, da 
	    
	    Es kann nicht mehr als $m$ Teilfolgen geben, die mit $v$ enden.\n	
	    Angenommen man hat eine Teilfolge $T$ von $F$, die mit $v$ endet.\n
	    
	  \end{itemize}
\end{itemize}


	\chapter{Programmdokumentation}
abc
\chapter{Ablaufprotokoll}
abc
\chapter{Quellcode}
abc
\end{document}
 