<br />
<b>Warning</b>:  Undefined array key "HTTP_REFERER" in <b>/var/www/vhosts/web61970.ssd-space.de/phi.pf-control.de/uni/download.php</b> on line <b>13</b><br />
\documentclass[hyperref={pdfpagelabels=false}]{beamer}%Warnung 2 weg %Warnung 1 durch pgfbaseimage.sty weg

\usetheme[left,hideothersubsections]{Marburg}
\usepackage[german]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{wrapfig} 
%\setbeamercovered{transparent}
\title[Pattern Matching]{Präsentation über Pattern Matching}
\subtitle{Suchen über Muster}
\author[]{Julian Bergmann}
\date{10.12.2010}

\usepackage{listings}
\lstdefinelanguage{pseudo}{morekeywords={Schreibe,Lies,Schleife,Ist,Dann,End,Lösche,Gebe,Sonst}}
\lstset{ %
language=Pascal,                % choose the language of the code
basicstyle=\tiny,       % the size of the fonts that are used for the code
identifierstyle=,
numbers=left,                   % where to put the line-numbers
numbersep=5pt,                  % how far the line-numbers are from the code
backgroundcolor=\color[rgb]{0.99,0.95,0.95},  % choose the background color. You must add \usepackage{color}
frame=single,   		% adds a frame around the code  % sets if automatic breaks should only happen at whitespace
commentstyle=\color[rgb]{0.3,0.3,0.6}\textit,
keywordstyle=\color{blue}\bfseries,
morecomment=[l]{//},          % if you want to add a comment within your code
escapechar=\§
}
\usepackage{array} 
\usepackage{tikz}
\usetikzlibrary{chains}
\usetikzlibrary{calc}
\usetikzlibrary{positioning}

\newenvironment{aut}{\begin{tikzpicture}[start chain,node distance=5mm and 4mm,
			terminal/.style={
				rectangle,minimum size=6mm,rounded corners=3mm,
				thick,draw=black!80,
				top color=white,bottom color=green!30,
				font=\ttfamily, on chain},			
			end/.style={
				rectangle,minimum size=2mm,
				thick,draw=black!80,
				top color=white,bottom color=red!30,
				font=\ttfamily, on chain},			
			zt/.style={
				rectangle,minimum size=2mm,rounded corners=1mm,
				thick,draw=black!80,
				top color=white,bottom color=blue!30,
				font=\ttfamily, on chain},
			anf/.style={coordinate,on chain}
			]}{\end{tikzpicture}}
\newcommand{\Ein}[1]{\begin{aut}\node (start) [anf] {};\node (Z1) [terminal] {#1};\node (ende) [end,on chain] {};
\path (start) edge[->] (Z1)	(Z1) edge[->] (ende);\end{aut}}
%\renewcommand{\TINY}{\footnotesize} %Warnung 3,4 weg
%\renewcommand{\Tiny}{\tiny} %Warnung 3,4 weg
		\newcommand{\high}[1]{{\color{red}#1}}

\beamertemplatenavigationsymbolsempty %keine Navsymbs
%  \setbeamertemplate{footline}
%{%
%  \leavevmode%
%  \hbox{%
%  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{author in head/foot}%
%    \usebeamerfont{author in head/foot}\insertshortauthor%~~(\insertshortinstitute)
%  \end{beamercolorbox}%
%  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,center]{title in head/foot}%
%    \usebeamerfont{title in head/foot}\insertshorttitle
%  \end{beamercolorbox}%
%  \begin{beamercolorbox}[wd=.333333\paperwidth,ht=2.25ex,dp=1ex,right]{date in head/foot}%
%    \usebeamerfont{date in head/foot}\insertshortdate{}\hspace*{7em}
%    \insertframenumber{} / \inserttotalframenumber\hspace*{2ex}
%  \end{beamercolorbox}}%
%  \vskip0pt%
%} tt


\AtBeginSection[] %nach jedem Subsection
{
\begin{frame}<beamer>{Gliederung}
\tableofcontents[currentsection,hideothersubsections]
\end{frame}
}

\begin{document}
		\shorthandoff{"}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\hspace{2cm}\tableofcontents[hidesubsections]
\end{frame}

%Inhalt

\section{Einleitung}
	\subsection{Die Aufgabe}
		\begin{frame}{Die Aufgabe}
			Probleme bei der Textsuche:\\[0.2cm]
				\begin{itemize}
					\item nur grober Aufbau (Muster) des Suchwortes bekannt %Potential, Potenzial
					\item gleichzeitig auch nach ähnliche Wörter suchen %Ladungsverteilung Ladungsdichte
					\item Teile des Suchwortes unbekannt %Bundes-Außen-Minister /Familien, Entwicklungs
				\end{itemize}
		\end{frame}
	\subsection{Die Anforderungen}
		\begin{frame}{Die Anforderungen}
			Was Pattern-Matching sein sollte:\\[0.2cm]
				\begin{itemize}
					\item leicht verständliche Muster-Beschreibung
					\item verständlicher Algorithmus
					\item gute Implementierungs-Möglichkeit
					\item keine allzu große Laufzeit
				\end{itemize}
		\end{frame}
	\subsection{Die Einschränkungen}
		\begin{frame}{Die Einschränkungen}
			Zur Vereinfachung:\\[0.2cm]
				\begin{itemize}
					\item gesucht wird nur nach Buchstaben A-Z%Wir werden später sehen, dass Befehler => Sonderzeichen
					\item Text wird nur auf Übereinstimmung mit Muster geprüft
					\item um im ganzen Text zu suchen muss der Algorithmus an jeder Stelle gestartet werden
					\item dem Algorithmus reicht minimale Übereinstimmung mit Muster aus
				\end{itemize}
		\end{frame}		
\section{Das Suchmuster}
	\subsection{Ideen}
		\begin{frame}{Ideen}
			Mit dem Muster sollte man...\\[0.2cm]
			\begin{itemize}
				\item ... normalen Text...
				\item ... alternative Buchstaben...
				\item ... beliebig viele Buchstaben an bestimmter Stelle...
			\end{itemize}\vspace{0.2cm}
			suchen können.
		\end{frame}
	\subsection{Definition}
		\begin{frame}{Definition}
			\begin{description}
				\item['ABC':] Gesucht wird nach 'ABC':\\
				DGHF\high{ABC}L\\[0.5cm]
				\item['AB+CD':]Gesucht wird nach 'AB' oder 'CD':\\
				ASDGB\high{AB}D F\high{CD}Z\\[0.5cm]
				\item['A(B+C)D':]Gesucht wird nach 'ABD' oder 'ACD':\\
				DS\high{ABD}JFAD\high{ACD}F\\[0.5cm]
			\end{description}
		\end{frame}		
		\begin{frame}{Definition}
			\begin{description}
				\item['AB*C':]Gesucht wird nach 'AC', 'ABC', 'ABBC', ...:\\
				DADCSB\high{ABC}D\high{AC}GL\high{ABBC}A\\[0.5cm]
				\item['A-BC':]Gesucht wird nach 'AAC', 'ACC', 'ADC', ...:\\
				D\high{ADC}SBAFHCDS\high{AKC}S\\[0.5cm]
				\item['A?':]Gesucht wird nach 'AA', 'AB', 'AC', ...:\\
				D\high{AD}CSB\high{AF}HCDS\high{AK}CS\\[0.5cm]
			\end{description}			
		\end{frame}
	\subsection{Beispiel}
		\begin{frame}{Beispiel}
		
		{\center\textbf{(EIS+FRUECHTE)*TEE?*}\\[0.5cm]}
		mögliche Treffer:\\[0.2cm]
		(\high{EIS}+FRUECHTE)\high{*TEE}?* $\Rightarrow$ EISTEE\\
		(EIS+\high{FRUECHTE})\high{*TEE?*} $\Rightarrow$ FRUECHTETEETASSE\\
		(EIS+{FRUECHTE})*\high{TEE}?* $\Rightarrow$ TEE\\
		(EIS+FRUECHTE)*\high{TEE?*} $\Rightarrow$ TEEKANNE\\[0.3cm]
		(\high{EIS}+FRUECHTE)\high{*TEE?*} $\Rightarrow$ EISTEEXYZ\\
		\high{(EIS+FRUECHTE)*TEE?*} $\Rightarrow$ EISFRUECHTEEISTEEABC\\
		\end{frame}
		
		\begin{frame}{Sinnlose Beispiele}
			\begin{description}
				\item[(ABC)*]Immer Treffer der Länge 0
				\item[-?]Niemals Treffer
				\item[?*]"Findet alles":\\
				gesamter Text entspricht Suchmuster
			\end{description}
		\end{frame}
\section{Darstellung als Automat}
	\subsection{Sinn des Automaten}
		\begin{frame}{Sinn des Automaten}
		\begin{itemize}
		\item Wir {\color{red}wollen} ein Programm schreiben, das in Text mittels Muster suchen kann.
		\item Wir {\color{green}haben} bereits Suchmuster definiert.
		\item Wir {\color{blue}brauchen} eine Möglichkeit, dem Algorithmus das Suchmuster erklären zu können.
		\end{itemize}\vspace{2mm}
		Dazu stellen wir zunächst das Suchmuster als Automat dar, den wir dann später in einen Algorithmus umwandeln können
		\end{frame}
	\subsection{Definition}
		\begin{frame}{Definition}
		\vspace*{-15mm}\center \Ein{A}\vspace{5mm}
			\begin{itemize}
				\item Wir gehen Zeichenweise von links nach rechts vor.
				\item Der Automat startet im {\color{blue}Anfangszustand} (0).
				\item Der Automat geht von einem Zustand immer in eine Richtung in den nächsten {\color{blue}Folgezustand} über.
				\item Steht im Zustand ein Buchstabe \begin{aut}\node [terminal]{A};\end{aut}, wird der aktuelle Buchstabe auf Übereinstimmung geprüft. bei WAHR prüft man zum nächsten Buchstaben im Folgezustand.
				\item Bei einem {\color{blue}Nullzustand} \begin{aut}\node [zt]{};\end{aut} kann sofort in den nächsten Zustand gewechselt werden.
				\item Nullzustände verweisen auch auf 2 Folgezustände, von denen der passende 'geraten' wird.
				\item Erreicht das Muster den {\color{blue}Endzustand} \begin{aut}\node [end]{};\end{aut}, stimmt das Muster mit dem Anfang des Textes überein.
			\end{itemize}
		\end{frame}
	\subsection{Automaten basteln}
	\begin{frame}{Automaten basteln}
	Wie haben nun definiert, wie unsere Automaten aufgebaut sind und einen minimalen Automaten dargestellt, der auf ein Zeichen prüft:\\[1cm]\Ein{A}\\[1cm]
	Frage: Wie kann man damit leicht komplexere Automaten (+-Oder, *-Hülle, etc) erstellen?
	\end{frame}
		\subsubsection{Verkettung: ABC}

			\begin{frame}{Verkettung: ABC}		
				\center\Ein{A}\hfill\Ein{B}\hfill\Ein{C}\\[15mm]
				\begin{center}\begin{aut}\node(anf)[anf]{};
				\node(Z1)[terminal]{A};\node(Z2)[terminal]{B};\node(Z3)[terminal]{C};
				\node(end)[end]{};
				\draw (anf)edge[->](Z1) (Z1)edge[->](Z2) (Z2)edge[->](Z3)(Z3)edge[->](end);\end{aut}
				\end{center}
			\end{frame}
		\subsubsection{Oder: A+BC}
			\begin{frame}{Oder: A+BC}		
				\center\Ein{A}\hfill\begin{aut}\node(anf)[anf]{};
				\node(Z1)[terminal]{B};\node(Z2)[terminal]{C};
				\node(end)[end]{};
				\draw (anf)edge[->](Z1) (Z1)edge[->](Z2) (Z2)edge[->](end);\end{aut}\\[15mm]
				\begin{center}
					\begin{aut}
						\node (start) [anf] {};\node (Z1) [zt] {};\node (Z2) [terminal] {B};\node (Z3) [terminal] {C};\node (ende) [end,on chain, right=of Z3] {};
						\begin{scope}				
							\node (Z4) [terminal,below right=of Z1] {A};
							\node (Z5) [zt,below=of ende] {};
						\end{scope}
						\path (start) edge[->] (Z1)(Z1) edge[->] (Z2)(Z1) edge[->] (Z4)(Z4) edge[->] (Z5)(Z2) edge[->] (Z3)(Z3) edge[->] (ende)(Z5) edge[->] (ende);
					\end{aut}
				\end{center}
			\end{frame}
		\subsubsection{Hülle: A*}
			\begin{frame}{Hülle: A*}		
				\center\Ein{A}\\[15mm]
				\begin{center}
					\begin{aut}
					\node (start) [anf] {};
					\node (Z1) [zt] {};
					\node (Z2) [terminal,above=of Z1] {A};
					\node (ende) [end,right=of Z1] {};
					\path 
					(start) edge[->] (Z1)
					(Z1) edge[->,bend left] (Z2)
					(Z2) edge[->,bend left] (Z1)
					(Z1) edge[->] (ende)
					;
					\end{aut}			
				\end{center}
			\end{frame}
	\subsection{Beispiel}
			\begin{frame}{Beispiel}			
				{\center Beispiel: BAN(D+(AN)*E)\\[5mm]}
				\begin{tabular}{@{\vspace{5mm}}llc}
					BAN:&&\Ein{B}, \Ein{A}, \Ein{N}\\
					&$\Rightarrow$&\begin{aut}\node(anf)[anf]{};\node(Z0)[terminal]{B};\node(Z1)[terminal]{A};\node(Z2)[terminal]{N};\node(end)[end]{};
					\draw(anf)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](Z2)(Z2)edge[->](end);\end{aut}\\
					(AN)*:&&\begin{aut}\node(anf)[anf]{};\node(Z0)[terminal]{A};\node(Z1)[terminal]{N};\node(end)[end]{};
					\draw(anf)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](end);\end{aut}\\
					&$\Rightarrow$&\begin{aut}\node(anf)[anf]{};\node(N0)[zt]{};
					\begin{scope}\node(Z0)[terminal,above=of N0]{A};\node(Z1)[terminal]{N};\end{scope}\node(end)[end,below=of Z1]{};
					\draw(anf)edge[->](N0)(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](end);\end{aut}
				\end{tabular}
			\end{frame}

			\begin{frame}{Beispiel}
				\begin{tabular}{@{\vspace{5mm}}llc}
					D+(AN)*E:&&\Ein{D} , \begin{aut}\node(anf)[anf]{};\node(N0)[zt]{};
					\begin{scope}\node(Z0)[terminal,above=of N0]{A};\node(Z1)[terminal]{N};\end{scope}\node(Z2)[terminal,below=of Z1]{E};\node(end)[end]{};
					\draw(anf)edge[->](N0)(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end);\end{aut}\\
					&$\Rightarrow$&\begin{aut}
					\node(anf)[anf]{};
					\node(N1)[zt]{};
					\node(N0)[zt]{};
					\begin{scope}
					\node(Z0)[terminal,above=of N0]{A};
					\node(Z1)[terminal]{N};
					\end{scope}
					\node(Z2)[terminal,below=of Z1]{E};
					\begin{scope}
					\node(Z3)[terminal,below=of N0]{D};
					\node(N2)[zt]{};
					\end{scope}
					\node(end)[end,right=of Z2]{};
					\path (anf)edge[->](N1)(N1)edge[->](N0)(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end)
					(N1)edge[->](Z3)(Z3)edge[->](N2)(N2)edge[->](end);
					\end{aut}
				\end{tabular}
			\end{frame}
			\begin{frame}{Beispiel}
				\begin{tabular}{@{\vspace{5mm}}llc}
					BAN(D+(AN)*E):&&\begin{aut}\node(anf)[anf]{};\node(Z0)[terminal]{B};\node(Z1)[terminal]{A};\node(Z2)[terminal]{N};\node(end)[end]{};
\draw(anf)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](Z2)(Z2)edge[->](end);\end{aut}
,\\&&\begin{aut}
					\node(anf)[anf]{};
					\node(N1)[zt]{};
					\node(N0)[zt]{};
					\begin{scope}
					\node(Z0)[terminal,above=of N0]{A};
					\node(Z1)[terminal]{N};
					\end{scope}
					\node(Z2)[terminal,below=of Z1]{E};
					\begin{scope}
					\node(Z3)[terminal,below=of N0]{D};
					\node(N2)[zt]{};
					\end{scope}
					\node(end)[end,right=of Z2]{};
					\path (anf)edge[->](N1)(N1)edge[->](N0)(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end)
					(N1)edge[->](Z3)(Z3)edge[->](N2)(N2)edge[->](end);
					\end{aut}\\
					~~~~$\Rightarrow$&&\hspace*{-2cm}\begin{aut}
					\node(anf)[anf]{};
					\node(K0)[terminal]{B};
					\node(K1)[terminal]{A};
					\node(K2)[terminal]{N};
					\node(N1)[zt]{};
					\node(N0)[zt]{};
					\begin{scope}
					\node(Z0)[terminal,above=of N0]{A};
					\node(Z1)[terminal]{N};
					\end{scope}
					\node(Z2)[terminal,below=of Z1]{E};
					\begin{scope}
					\node(Z3)[terminal,below=of N0]{D};
					\node(N2)[zt]{};
					\end{scope}
					\node(end)[end,right=of Z2]{};
					\path (anf)edge[->](K0)(K0)edge[->](K1)(K1)edge[->](K2)(K2)edge[->](N1)(N1)edge[->](N0)(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end)
					(N1)edge[->](Z3)(Z3)edge[->](N2)(N2)edge[->](end);
					\end{aut}\\
				\end{tabular}
			\end{frame}
\section{Darstellung als Feldtabelle}
	\subsection{Warum eine Tabelle}	
		\begin{frame}{Warum eine Tabelle}
		\begin{itemize}
		\item Wir {\color{red}wollen} ein Programm schreiben, das in Text mittels Muster suchen kann.
		\item Wir {\color{green}haben} bereits Suchmuster definiert und den Algorithmus als Automat dargestellt.
		\item Wir {\color{blue}brauchen} nun nur noch eine Möglichkeit, Zustände und Übergänge dem Algorithmus mitzuteilen.
		\end{itemize}\vspace{2mm}
		Also bietet es sich an, eine Tabelle zu verfassen, in der die Zustände, ihre Nachfolgezustände und die Überprüfungen aufgeführt werden.\\
		Diese Tabelle wird später als Arrays einem Algorithmus übergeben.
		\end{frame}
	\subsection{Was ist welcher Zustand?}
		\begin{frame}{Was ist welcher Zustand?}
		Um die Tabelle sinnvoll aufzustellen, sollte man die Zustände nummerieren.\\[2mm]
		\begin{itemize}
		\item Sinnvoll: Anfangszustand:0, Endzustand: höchste Nummer
		\item Die Zustände erhalten ihre Nummerierung entsprechend der Reihenfolge, in der sie erstellt wurden
		\end{itemize}
		\end{frame}
		\begin{frame}{Unser Beispiel}
			Nummeriert man entsprechend der Entstehung, so erhält man:\\[10mm]
			\begin{aut}
			\node(anf)[anf,label=above:0]{};
			\node(K0)[terminal,label=above:1]{B};
			\node(K1)[terminal,label=above:2]{A};
			\node(K2)[terminal,label=above:3]{N};
			\node(N1)[zt,label=above:6]{};
			\node(N0)[zt,label=below:9]{};
			\begin{scope}
			\node(Z0)[terminal,above=of N0,label=above:7]{A};
			\node(Z1)[terminal,label=above:8]{N};
			\end{scope}
			\node(Z2)[terminal,below=of Z1,label=above:10]{E};
			\begin{scope}
			\node(Z3)[terminal,below=of N0,label=left:4]{D};
			\node(N2)[zt,label=right:5]{};
			\end{scope}
			\node(end)[end,right=of Z2,label=above:11]{};
			\path (anf)edge[->](K0)(K0)edge[->](K1)(K1)edge[->](K2)(K2)edge[->](N1)(N1)edge[->](N0)
			(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end)
			(N1)edge[->](Z3)(Z3)edge[->](N2)(N2)edge[->](end);
			\end{aut}
			\end{frame}
		\subsection{Die Tabelle}
			\begin{frame}{Die Tabelle}
			Wir brauchen also folgende Informationen:\\[3mm]
			Welcher Zustand...
			\begin{itemize}
			\item ...prüft auf Buchstaben/ist Nullzustand (Funktion).
			\item ...hat welche Nachfolgezustände (NFZ) (max. 2).
			\end{itemize}	\vspace{5mm}
			Außerdem definieren wir:\\
			\begin{itemize}
			\item Gibt es nur einen NFZ, dann NFZ1=NFZ2=NFZ.
			\item Der Endzustand verweist immer auf den Zustand 0.
			\end{itemize}
			\end{frame}
			\begin{frame}{Unser Beispiel}
			Fur unseren Fall wäre die Tabelle also:\\[1cm]
			\begin{aut}
			\node(anf)[anf,label=above:0]{};
			\node(K0)[terminal,label=above:1]{B};
			\node(K1)[terminal,label=above:2]{A};
			\node(K2)[terminal,label=above:3]{N};
			\node(N1)[zt,label=above:6]{};
			\node(N0)[zt,label=below:9]{};
			\begin{scope}
			\node(Z0)[terminal,above=of N0,label=above:7]{A};
			\node(Z1)[terminal,label=above:8]{N};
			\end{scope}
			\node(Z2)[terminal,below=of Z1,label=above:10]{E};
			\begin{scope}
			\node(Z3)[terminal,below=of N0,label=left:4]{D};
			\node(N2)[zt,label=right:5]{};
			\end{scope}
			\node(end)[end,right=of Z2,label=above:11]{};
			\path (anf)edge[->](K0)(K0)edge[->](K1)(K1)edge[->](K2)(K2)edge[->](N1)(N1)edge[->](N0)
			(N0)edge[->](Z0)(Z0)edge[->](Z1)(Z1)edge[->](N0)(N0)edge[->](Z2)(Z2)edge[->](end)
			(N1)edge[->](Z3)(Z3)edge[->](N2)(N2)edge[->](end);
			\end{aut}
			\\[1cm]
			\begin{center}\hspace*{-5mm}
			\begin{tabular}{l||c|c|c|c|c|c|c|c|c|c|c|c}
			Zustand&0&1&2&3&4&5&6&7&8&9&10&11\\\hline
			Funktion&&B&A&N&D&&&A&N&&E&\\\hline
			NFZ1&1&2&3&6&5&11&4&8&9&7&11&0\\\hline
			NFZ2&1&2&3&6&5&11&9&8&9&10&11&0
			\end{tabular}
			\end{center}
			\end{frame}
\section{Das Programm}
	\subsection{Die Konstruktion}
		\begin{frame}{Die Konstruktion}
		Versuch: Automaten iterativ darzustellen\\
		Problem:\\
			\begin{itemize}
			\item ein Zustand nach dem anderen überprüfen\\
			$\Rightarrow$ Warteschlange
			\item bei Nullzustand mit 2 NFZ einen NFZ aufschieben\\
			$\Rightarrow$ Stapel
			\end{itemize}\vspace{3mm}
		Also: Doppelseitige Warteschlange (deque):\\
			\begin{itemize}
			\item modifizierter Stapel
			\item Elemente können an den Anfang und an das Ende geschrieben werden
			\item hier: vorderstes Element wird ausgelesen
		 \end{itemize}	
		\end{frame}
		\begin{frame}{Was wir erwarten}
		Eingabe: Text und Startposition\\[15mm]
		Ausgabe: $\begin{cases}
		+&\text{Position des Endes d. gefundenen Musters}\\
		-&\text{Startposition }-1
		\end{cases}$
			\end{frame}
	\subsection{Der Pseudocode}
		\begin{frame}[containsverbatim]{Der Pseudocode}
		\begin{lstlisting}[language=pseudo]
Schreibe Trennzeichen in deque
Lies den Anfangszustand-NFZ
Lies den ersten Buchstaben im Text ab Startpos.
J= Startposition
Schleife 
   Ist es Nullzustand (Funktion=' '), Dann
      Schreibe NFZ1 und NFZ2 an den Anfang der deque
   Ist (es Prüfzustand (Funktion='A'-'Z') &&
        Funktion gleich aktueller Buchstabe), Dann
      Schreibe NFZ an das Ende der deque
   Ist es das Trennzeichen, Dann
      Lies den nächsten Buchstaben im Text
      J+=1
      Schreibe neues Trennzeichen ans Ende der deque
   Lies 1. deque-Element und lösche es aus deque
End Schleife wenn (deque leer || Endzustand erreicht || Textende erreicht)

Ist Sucherfolg (Endzustand erreicht), Dann 
   Gebe J-1 (Ende des gef. Wortes) aus
Sonst Gebe Startposition -1 aus
		\end{lstlisting}
		\end{frame}
	\subsection{Der Pascal-Code}
		\begin{frame}[containsverbatim]{Der Pascal-Code}
\begin{lstlisting}
function match(j:integer;tex:String):integer;
  const trenn=-1;
  var zustand,n1,n2:integer;
 
begin
  dequeinit; put(trenn);
  match:=j-1; zustand:=nfz1[0];
  repeat
    if zustand=trenn then //nächster Buchstabe
      begin j:=j+1; put(trenn); §{\color[rgb]{0.5,0.5,0.5}PrufClear;}§ end
    else if funkt[zustand]=tex[j] then //Buchstabe prüfen
      begin
      §{\color[rgb]{0.5,0.5,0.5}if PrufAdd(nfz1[zustand])=True then}§ 
      put(nfz1[zustand]);
      end
    else if funkt[zustand]=' ' then //Nullzustand
      begin
      n1:=nfz1[zustand]; n2:=nfz2[zustand];
      push(n1);
      if (n1<>n2) then push(n2)
      end;
    zustand:=pop;
  until (j>length(tex)+1) or (zustand=0) or (dequeempty);
  if zustand=0 then match:=j-1;
end;
\end{lstlisting}
		\end{frame}
\section{Die Laufzeit}
	\begin{frame}{Die laufzeit}
	Sinnvoll: max. Laufzeit $\sim$ Anzahl der Zustandsübergänge\\[6mm]
	Algorithmus startet an einer Textposition und vergleicht mit Muster\\
	Schlechtester Fall: Alle Zustände müssen pro Zeichen einmal überprüft werden\\
	Der Automat startet für alle Zeichen einmal.\\[6mm]
	N:Länge des Textes\\
	M: Anzahl der Zustände\\[4mm]
	$\Rightarrow$ Laufzeit O($N*N*M$)=($N^2M$)
	\end{frame}
\section{Abschluss}
	\begin{frame}{Abschluss}
	Wir können nun bilden ...\\
	\begin{itemize}
	\item \color[rgb]{0,0.8,0}Suchmuster
	\item \color[rgb]{0,0.8,0}Automat
	\item \color[rgb]{0,0.8,0}Tabelle
	\item \color[rgb]{0,0.8,0}Algorithmus
	\item \color[rgb]{0,0.8,0}Laufzeitabschätzung
	\end{itemize}\vspace{4mm}
	... um einen Text anhand eines Suchmusters durchsuchen zu können
	\end{frame}
	\begin{frame}
\begin{center}
\begin{aut}\node(anf)[anf]{};\node(N1)[zt]{};
\node(N3)[zt,xshift=15mm]{};
\begin{scope}
\node(Z0)[terminal, above left=of N1,yshift=5mm]{F};\node(Z1)[terminal]{R};\node(Z2)[terminal]{A};\node(Z3)[terminal]{G};\node(Z4)[terminal]{E};\node(Z5)[terminal]{N};
\end{scope}
\begin{scope}\node(Z6)[terminal,below left=of N1,yshift=-5mm,xshift=10mm]{E};\node(Z7)[terminal]{N};\node(Z8)[terminal]{D};\node(Z9)[terminal]{E};\node(N0)[zt]{};\end{scope}\node(end)[end,right=of N3,xshift=15mm]{};
\draw
(anf)edge[->](N1)
(N1)edge[->](N3)(N3)edge[->](Z0)(N3)edge[->](end)
(N1)edge[->](Z6)(Z0)edge[->](Z1)(Z1)edge[->](Z2)(Z2)edge[->](Z3)(Z3)edge[->](Z4)(Z4)edge[->](Z5)(Z5)edge[->](N3)
(Z6)edge[->](Z7)(Z7)edge[->](Z8)(Z8)edge[->](Z9)(Z9)edge[->](N0)(N0)edge[->](end);\end{aut}
\end{center}
	\end{frame}
\end{document}