\documentclass[compress,handout]{beamer} %[compress,handout]

% Mapping input character to symbol
% \usepackage[utf8]{inputenc}
% OR
\usepackage[latin1]{inputenc}

% Mapping symbol to character in font
\usepackage[T1]{fontenc}

\usepackage[ngerman]{babel}
\usepackage[longend,algoruled,vlined,german]{algorithm2e}%[titlenumbered]
\usepackage{subfigure}
\usepackage{dsfont}
%\usepackage{hhline}
%\usepackage{colortbl}
% \usepackage{ifpdf}     % for pdflatex & pstex figures
% \usepackage{pstricks}  % wird hier nur für die Farben verwendet
% \usepackage[svgnames]{xcolor}

% \ifpdf %
%  \newcommand{\inputfig}[1]{\input{#1.pspdftex}}%
%  \DeclareGraphicsRule{.pspdftex}{pdf}{.pspdftex}{}%
% \else%
%  \newcommand{\inputfig}[1]{\input{#1.pstex_t}}%
% \fi%

%\DeclareGraphicsRule{.pspdftex}{pdf}{.pspdftex}{}%
\newcommand{\inputfig}[1]{\input{#1.pspdftex}}%

\renewcommand{\O}{\mathcal{O}}
\newcommand{\Otilde}{\mathcal{\tilde{O}}}
\newcommand{\NP}{\ensuremath{\mathcal{NP}}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\ZPP}{\mathcal{ZPP}}

\makeatletter
% \ifcase\@ptsize
%   \font\mtimes=cmsy10 scaled \magstep3 % was 4
% \or
%   \font\mtimes=cmsy10 scaled 1577      %\magsetp3.5
% \or
  \font\mtimes=cmsy10 scaled \magstep4
%\fi
\def\bigtimes{\mathop{\lower.15\baselineskip\hbox{\mtimes\char"02}}}
\makeatother

\newcommand{\N}{\mathds{N}}
\newcommand{\Q}{\mathds{Q}}
\newcommand{\R}{\mathds{R}}

%\newcommand{\Pr}{\mathrm{Pr}}
\newcommand{\E}{\mathds{E}}

%\newcommand{\probname}[1]{\textsc{#1}}
\newcommand{\probname}[1]{\textbf{#1}}

% Volkers defs
\newtheorem{observation}[theorem]{Beobachtung}

\newcommand{\IA}[1]{\smallskip\noindent{\bf Induktionsanfang (\boldmath$#1$\unboldmath):}}
\newcommand{\IS}[1]{\smallskip\noindent{\bf Induktionsschritt (\boldmath$#1$\unboldmath):}}

% \makeatletter
% \def\case{\@ifnextchar[{\c@@se}{\c@se}}
% \def\c@se#1{\@case{Fall~#1:}}
% \def\c@@se[#1]#2{\@case{Fall~#2 (#1):}}
% \def\@case#1{\par\smallskip\noindent\boldmath{\bf#1\ }\unboldmath\ignorespaces}
% \makeatother

%\def\argmax{\mathop{\operator@font argmax}}
\def\argmax{\mathop{argmax}}
%\def\argmin{\mathop{\operator@font argmin}}
\def\argmin{\mathop{argmin}}
\def\floor#1{\lfloor#1\rfloor}
\def\ceil#1{\lceil#1\rceil}
\def\Floor#1{\left\lfloor#1\right\rfloor}
\def\Ceil#1{\left\lceil#1\right\rceil}
\def\ament#1#2{\left(#1\atop#2\right)}
\def\cdotfill{\leaders\hbox to .4em{\hfil$\cdot$\hfil}\hfill}
\def\dashfill{\leaders\hbox to 1em{\hfil$-$\hfil}\hfill}

%\def\opt{\mathop{\operator@font opt}}
\def\opt{\mathop{opt}}

\newcommand{\rvec}[3]{(#1_{#2}, \ldots ,#1_{#3})}
\newcommand{\word}[3]{#1_{#2} \cdots #1_{#3}}
\newcommand{\setsep}{\mathchoice{\::\:}{\,:\,}{:}{{:}}}
\newcommand{\set}[2]{\left\{#1\setsep#2\right\}}
\newcommand{\pp}{\raisebox{1.5pt}{$\scriptstyle++$}}
\newcommand{\mm}{\raisebox{1.5pt}{$\scriptstyle--$}}

\newcommand{\problemdesc}[4]{
\begingroup\clubpenalty10000\widowpenalty10000
%\par\vskip\topsep\vskip\partopsep\par\noindent
\begin{problem}
\noindent\underline{\scshape#1\strut\label{#2}}%
\par\nobreak\vskip.2\baselineskip
\setbox0\hbox{\bf Eingabe: }\dimen0=\wd0
\setbox1\hbox{\bf Gesucht: }\ifnum\wd1>\wd0\dimen0=\wd1\fi
\advance\dimen0 by 2pt
\vskip-\parskip\noindent
\hbox to\dimen0{\box0\hfil}\hangindent\dimen0\hangafter1\ignorespaces#3
\par\vskip-\parskip\noindent
\hbox to\dimen0{\box1\hfil}\hangindent\dimen0\hangafter1\ignorespaces#4
\end{problem}%
%\par\vskip\topsep\vskip\partopsep\par
\endgroup}

% \newrgbcolor{red}{1.0 0 0}
% \newrgbcolor{mediumgray}{0.5 0.5 0.5}
% \newrgbcolor{darkgreen}{0.0 0.6 0.0}


\mode<presentation>
{
  \usetheme[]{Warsaw}
%   \usetheme[]{Boadilla}
%  \usetheme[]{Copenhagen}
%  \useoutertheme{infolines} % show only current (compressed) section/subsection
  \setbeamercovered{transparent}
}

% \input{tumlogo}

\title[String Matching]{Proseminar String Matching}
%\subtitle{String Matching}

\author[H.\ Täubig]{PD Dr.\ habil.\ Hanjo Täubig}

\institute[TUM]{
  Lehrstuhl für Theoretische Informatik\\
  (Prof.\,Dr.\ Susanne Albers)\\
  Institut für Informatik\\
  Technische Universität München
}

\date[WS'16/17]{Wintersemester 2016/17}

\subject{String Matching}
\keywords{string matching, bioinformatics, algorithms}

% \titlegraphic{\oTUM{1cm}}

% \logo{\TUM{0,5cm}} % does not work (?), see author

\beamerdefaultoverlayspecification{<+->}

% \includeonlylecture{lec-2016-10-18}

\AtBeginSection[]% nichts tun bei *-Form (\section*{})
{
  \begin{frame}
    \frametitle{Übersicht}
    \tableofcontents[currentsection,hideothersubsections]
  \end{frame}
}

\begin{document}

\frame{\titlepage}


%% Proseminar 1 - 18.10.2016
\lecture[18.10.2016]{Vorlesung vom 18.10.2016}{lec-2016-10-18}


\section{Proseminar}

\subsection{Organisatorisches}

\begin{frame}
  \frametitle{Übersicht}
  \tableofcontents[hideallsubsections]  % options: [pausesections,hideallsubsections]
\end{frame}

\begin{frame}
  \frametitle{Formalitäten}

  \begin{itemize}
  \item Modul: IN0013

  \item Bereich:

    Proseminar im Bereich Informatik III (Theoretische Informatik)

  \item Semesterwochenstunden:

    2\,SWS Proseminar

  \item ECTS: 4 Credits

  \item Seminarzeiten:

    \begin{tabbing}
%      Donnerstag \= \kill
      Dienstag \= 14:15 -- 15:45 Uhr (MI 03.11.018)%\\*
%      Freitag  \> 13:15 -- 14:45 Uhr (MI Hs 3)
    \end{tabbing}

  \item Web:

    http://www14.in.tum.de/lehre/2016WS/proseminar/
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Dozent}

  \begin{itemize}
  \item PD Dr.\ habil.\ Hanjo Täubig\\
    (Lehrstuhl für Effiziente Algorithmen / Prof.\ Mayr)\\
    (Lehrstuhl für Theoretische Informatik / Prof.\ Albers)

  \item eMail:\\
    taeubig@in.tum.de

  \item Web:\\
    http://www14.in.tum.de/personen/taeubig/

  \item Telefon: 089 / 289-17740

  \item Raum: MI 03.09.039

  \item Sprechstunde: vorzugsweise 13-14 Uhr\\
    (bzw.\ nach Vereinbarung)
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Ziele des Proseminars}

  \begin{itemize}
  \item Literaturrecherche
    \begin{itemize}
    \item Bibliothek: Buch ausleihen / Online-Zugriff
    \item Web: Google Scholar, Microsoft Academic Search, etc.
    \end{itemize}
  \item Vortrag
    \begin{itemize}
    \item Erstellung der Slides mit \LaTeX\ (beamer package),
      PowerPoint oder mit einem ähnlichen Programm nach Wahl
    \item Halten des Vortrags (ca.\ 45\,min)
    \end{itemize}
  \item Mitarbeit / Diskussion
  \item Ausarbeitung
    \begin{itemize}
    \item Erstellung mit \LaTeX
    \item ca.\ 6 Seiten Text (plus Abbildungen, plus Literaturverzeichnis)
    \end{itemize}
  \end{itemize}

%   \vfill
  (Bewertung)
\end{frame}




\section[Textsuche]{Algorithmen zur Textsuche}

\subsection{Definitionen}

\begin{frame}
  \frametitle{Alphabet}
  \begin{definition}
    Ein \alert{Alphabet} ist eine endliche Menge von Symbolen.

    \vspace{0,2cm}
    Wir bezeichnen es meistens mit~$\Sigma$.
  \end{definition}

  \vfill
  \begin{Beispiel}
    $\Sigma=\{a,b,c,\ldots,z\}$, $\Sigma=\{0,1\}$,
    $\Sigma=\{A,C,G,T\}$
% evt. Protein-Codes
  \end{Beispiel}
\end{frame}

\begin{frame}
  \frametitle{Wörter}
  \begin{definition}
    \alert{Wörter} über $\Sigma$ sind endliche Folgen von Symbolen
    aus~$\Sigma$.

    \vspace{0,2cm}
    Wir notieren Wörter meist in der Form\\
    $w=\word{w}{0}{n-1}$ oder $w=\word{w}{1}{n}$.
  \end{definition}

  \vfill
  \begin{Beispiel}
    $\Sigma=\{a,b\}$, dann ist $w=abba$ ein Wort über~$\Sigma$.
  \end{Beispiel}
\end{frame}

\begin{frame}
  \frametitle{Wortlänge, Wortmengen}
  \begin{definition}
    Die \alert{Länge} eines Wortes~$w$ wird mit \alert{$|w|$} bezeichnet und
    entspricht der Anzahl der Symbole in~$w$.

    \vspace{0,2cm}
    Das Wort der Länge~$0$ heißt \alert{leeres Wort} und wird
    mit~\alert{$\varepsilon$} bezeichnet.
  \end{definition}

  \vfill
  \begin{definition}
    Die Menge aller Wörter über~$\Sigma$ wird mit \alert{$\Sigma^*$}
    bezeichnet.

    \vspace{0,2cm}
    Die Menge aller Wörter der Länge größer gleich~$1$ über $\Sigma$
    wird mit $\alert{\Sigma^+}:=\Sigma^*\setminus\{\varepsilon\}$
    bezeichnet.

    \vspace{0,2cm}
    Die Menge aller Wörter über $\Sigma$ der Länge~$k$ wird mit
    $\alert{\Sigma^{k}} \subseteq \Sigma^*$ bezeichnet.
  \end{definition}
\end{frame}

\begin{frame}
  \frametitle{Präfix, Suffix, Teilwort}
  \begin{definition}
    {\small
      Im Folgenden bezeichne
      $[a:b] = \{n\in \mathbb{Z} \mid a\leq n \wedge n \leq b\}$ für
      $a,b\in\mathbb{Z}$.
    }

    Sei $w = w_1 \cdots w_n$ ein Wort der Länge~$n$ über $\Sigma$, dann heißt
    \begin{itemize}
    \item $w'$ \alert{Präfix} von~$w$, wenn $w' = w_1 \cdots w_\ell$ mit $\ell\in[0:n]$

    \item $w'$ \alert{Suffix} von~$w$, wenn $w'= w_\ell \cdots w_n$ mit $\ell\in[1:n+1]$

    \item $w'$ \alert{Teilwort} von $w$, wenn $w'= w_i \cdots w_j$ mit $i,j\in[1:n]$
      
    \end{itemize}
    (Für $w' = w_i\cdots w_j$ mit $i>j$ soll gelten $w' = \epsilon$.)
  \end{definition}

  \vfill
  Das leere Wort~$\varepsilon$ ist also Präfix, Suffix und Teilwort
  eines jeden Wortes über $\Sigma$.
\end{frame}

\begin{frame}
  \frametitle{Textsuche}
  \begin{tabbing}
    \textbf{Problem:}\\*
    Pro\= \kill
    \\*
    \> \emph{Gegeben}:\ \= Text~$t \in \Sigma^*;\;
    |t|=n$; \\*
    \> \> Suchwort $s \in \Sigma^*;\; |s|=m \leq n$\\*
    \\*
    \> \emph{Gesucht}:\ \> $\exists \ i \in [0:n-m]$ mit $t_i \cdots t_{i+m-1} = s$ ? \\*
    \> \> (bzw. alle solchen Positionen~$i$)
  \end{tabbing}
\end{frame}


\subsection{Naiver Algorithmus}

\begin{frame}
  \frametitle{Naiver Algorithmus}
  \begin{itemize}
  \item Suchwort $s$ wird Buchstabe für Buchstabe mit dem Text $t$
    verglichen
    \vfill
  \item Stimmen zwei Buchstaben nicht überein ($\rightarrow$
    Mismatch), so wird $s$ um eine Position "`nach rechts"' verschoben
    und der Vergleich von $s$ mit $t$ beginnt von neuem.
    \vfill
  \item Vorgang wird wiederholt, bis $s$ in $t$ gefunden wird oder bis
    klar ist, dass $s$ in $t$ nicht enthalten ist.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Naiver Algorithmus}
  \begin{center}
    \includegraphics{NaivAlg}
  \end{center}
\end{frame}


\begin{frame}
  \frametitle{Naiver Algorithmus: Implementation}
\begin{algorithm}[H]
  \BlankLine
  \caption{bool Naiv (char $t[]$, int $n$, char $s[]$, int $m$)}
%  \{
  int $i:=0$, $j:=0$\;
  \While{($i\leq n-m$)}{
    \While{($t[i+j]=s[j]$)}{
      $j\pp$\;
      \If{($j=m$)}{
        \Return TRUE\;
      }
    }
    $i\pp$\;
    $j:=0$\;
  }
  \Return FALSE\;
%  \}
\end{algorithm}
\end{frame}

\begin{frame}
  \frametitle{Match und Mismatch}
  \begin{definition}
    Stimmen zwei Zeichen bei einem Vergleich überein, so nennt man
    dies ein \alert{Match}, ansonsten ein \alert{Mismatch}.
  \end{definition}
\end{frame}

\begin{frame}
  \frametitle{Analyse des naiven Algorithmus}
  \begin{itemize}
  \item zähle Vergleiche von Zeichen,
  \item äußere Schleife wird $(n-m+1)$-mal durchlaufen,
  \item die innere Schleife wird maximal $m$-mal durchlaufen.
  \item maximale Anzahl von Vergleichen: $(n-m+1)m$,
  \item Laufzeit: \alert{$\O(nm)$}
  \end{itemize}
\end{frame}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
