\documentclass[xcolor=dvipsnames,10pt]{beamer}
\beamertemplatenavigationsymbolsempty

% Sonderzeichen
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{unicode-math}
\usepackage{mathtools}
\usepackage{linearA}
\usepackage{emoji}
\setemojifont{Segoe UI Emoji}

% Brüche
\usepackage{xfrac}
% \newcommand\sfrac[2]{#1/#2}

% Aufzählungen
\usepackage{enumerate}
\usepackage{multicol}

% Tabellen
\usepackage{tabularx}

% Bilder
\usepackage{graphicx}
\graphicspath{{graphics/}}
\usepackage{subcaption}

% Algorithmen
\usepackage{algpseudocode}
\usepackage{listings}
\usepackage{lstautogobble}

% C++
\lstset{
	language=C++,
	tabsize=2,
	basicstyle=\ttfamily,
	keywordstyle=\color{PineGreen},
	showstringspaces=false,
	commentstyle={\ttfamily\color{gray}},
	frame=single,
	rulecolor=\color{PineGreen},
	breaklines,
	morekeywords={string}
}

\makeatletter
\algrenewcommand\ALG@beginalgorithmic{\small}
\makeatother

\algrenewcommand\algorithmicend{\textcolor{\highlight}{\texttt{\textbf{end}}}}
\algrenewcommand\algorithmicdo{\textcolor{\highlight}{\texttt{\textbf{do}}}}
\algrenewcommand\algorithmicwhile{\textcolor{\highlight}{\texttt{\textbf{while}}}}
\algrenewcommand\algorithmicfor{\textcolor{\highlight}{\texttt{\textbf{for}}}}
\algrenewcommand\algorithmicforall{\textcolor{\highlight}{\texttt{\textbf{for all}}}}
\algrenewcommand\algorithmicloop{\textcolor{\highlight}{\texttt{\textbf{loop}}}}
\algrenewcommand\algorithmicrepeat{\textcolor{\highlight}{\texttt{\textbf{repeat}}}}
\algrenewcommand\algorithmicuntil{\textcolor{\highlight}{\texttt{\textbf{until}}}}
\algrenewcommand\algorithmicprocedure{\textcolor{\highlight}{\texttt{\textbf{procedure}}}}
\algrenewcommand\algorithmicfunction{\textcolor{\highlight}{\texttt{\textbf{function}}}}
\algrenewcommand\algorithmicif{\textcolor{\highlight}{\texttt{\textbf{if}}}}
\algrenewcommand\algorithmicthen{\textcolor{\highlight}{\texttt{\textbf{then}}}}
\algrenewcommand\algorithmicelse{\textcolor{\highlight}{\texttt{\textbf{else}}}}
\algrenewcommand\algorithmicrequire{\textcolor{\highlight}{\texttt{\textbf{Require:}}}}
\algrenewcommand\algorithmicensure{\textcolor{\highlight}{\texttt{\textbf{Ensure:}}}}
\algrenewcommand\algorithmicreturn{\textcolor{\highlight}{\texttt{\textbf{return}}}}
% \newcommand{\key}[1]{\textcolor{\highlight}{\fontfamily{lmtt}\selectfont{\textbf{#1}}}}
\newcommand{\key}[1]{\textcolor{\highlight}{\texttt{\textbf{#1}}}}
\algrenewcommand\algorithmiccomment[1]{\hfill\raisebox{.2ex}{\textcolor{\highlight}{\scriptsize$\blacktriangleright$}} \raisebox{.1ex}{\textcolor{gray}{\footnotesize #1}}}
\algrenewtext{EndWhile}{\textcolor{\highlight}{\texttt{\textbf{od}}}}
\algrenewtext{EndFor}{\textcolor{\highlight}{\texttt{\textbf{od}}}}
\algrenewtext{EndIf}{\textcolor{\highlight}{\texttt{\textbf{fi}}}}
\algrenewtext{EndFunction}{\textcolor{\highlight}{\texttt{\textbf{end}}}}

% foreach
\algnewcommand\algorithmicforeach{\textcolor{\highlight}{\texttt{\textbf{foreach}}}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

% full line comment
\newcommand{\linecomment}[1]{\Statex{\raisebox{.2ex}{\textcolor{\highlight}{\scriptsize$\blacktriangleright$}} \raisebox{.1ex}{\textcolor{gray}{\footnotesize #1}}}}

% Befehl für Quellenangabe
% #1 ist die URL, #2 der angezeigte Text
\providecommand{\src}[2]{\scriptsize \textcolor{gray}{[source: \href{#1}{\textcolor{gray}{#2}}]}}

% Damit man Anführungszeichen hübscher schreiben kann als "`"'
\newcommand{\enquote}[1]{``{#1}''}

% Gaußklammern
\providecommand{\floor}[1]{\left \lfloor #1 \right \rfloor }
\providecommand{\ceil}[1]{\left \lceil #1 \right \rceil }

% Mathekommentare
\newcommand{\mathcomm}[1]{\triangleright~\text{\footnotesize#1}}

% Tikz
\usepackage{tikz}
\usetikzlibrary{calc,tikzmark,fit,shapes,arrows.meta,decorations.pathreplacing,bending}
\usepackage{pgfplots}
\pgfplotsset{compat=1.17}

% entferne footnote-Striche
\renewcommand\footnoterule{}

% Beamer theme (Metropolis + Custom colors + Font)
\definecolor{mgLightBG}{HTML}{FFFBFC}
\definecolor{mgDarkBG}{HTML}{272F40}
\definecolor{mgLightText}{HTML}{F5EFED}
\definecolor{mgDarkText}{HTML}{0F0A0A}
\definecolor{mgHighlight}{HTML}{2292a4}

% \definecolor{mgLightBG}{HTML}{fffcef}
% \definecolor{mgDarkBG}{HTML}{393939}
% \definecolor{mgLightText}{HTML}{d2ebcd}
% \definecolor{mgDarkText}{HTML}{393939}
% \definecolor{mgHighlight}{HTML}{2292a4}

\providecommand{\highlight}{mgHighlight}

% \usepackage[sfdefault,light]{roboto}
\usepackage{fontspec}
\usetheme[titleformat=smallcaps,sectionpage=progressbar,numbering=none,progressbar=frametitle,block=fill]{metropolis}
\makeatletter
\setlength{\metropolis@titleseparator@linewidth}{2pt}
\setlength{\metropolis@progressonsectionpage@linewidth}{2pt}
\setlength{\metropolis@progressinheadfoot@linewidth}{2pt}
\makeatother
\setbeamercolor{progress bar}{fg=mgHighlight,bg=mgLightText}
\setbeamercolor{normal text}{fg=mgDarkText}
\setbeamercolor{alerted text}{fg=mgHighlight}
\setbeamercolor{background canvas}{bg=mgLightBG}
\setbeamercolor{frametitle}{fg=mgLightText,bg=mgDarkBG}
\setbeamercolor{footnote}{fg=mgDarkText}
\setbeamercolor{footnote mark}{fg=mgHighlight}
\setbeamercovered{invisible}
\setbeamercovered{again covered={\opaqueness<1->{15}}}

% Beamer Inline List
\newcommand\paraitem{%
	\quad
	\makebox[\labelwidth][r]{%
	\makelabel{%
	\usebeamertemplate{itemize \beameritemnestingprefix item}}}\hskip\labelsep}

% Highlight
\newcommand*{\myhl}[1]{%
	\tikz[baseline=(text.base)]\node(text)[rectangle, fill=mgHighlight!50, rounded corners, inner sep=0.3mm]{#1};%
}

% Kurzschreibweisen
\usepackage{xspace}
\newcommand{\triang}{\raisebox{.4ex}{\alert{\scriptsize $\blacktriangleright$}}\xspace}
\newcommand{\setN}{\mathbb{N}}
\newcommand{\setZ}{\mathbb{Z}}
\newcommand{\setQ}{\mathbb{Q}}
\newcommand{\setR}{\mathbb{R}}
\newcommand{\Oh}[1]{\mathcal{O}\left({#1}\right)}
\newcommand{\OhOmega}[1]{\Omega\left({#1}\right)}
\newcommand{\OhTheta}[1]{\Theta\left({#1}\right)}
\newcommand{\EStar}{E^{*}}
\newcommand{\binStar}{\{0,1\}^{*}}
\newcommand{\pct}{\,\scalebox{.9}{\%}\xspace}
\newcommand{\Java}{\texttt{\textsc{Java}}\xspace}
\newcommand{\langC}{\texttt{\textsc{C}}\xspace}
\newcommand{\Python}{\texttt{\textsc{Python}}\xspace}
\newcommand{\R}{\texttt{\textsc{R}}\xspace}
\newcommand{\Matlab}{\texttt{\textsc{Matlab}}\xspace}
\newcommand{\PHP}{\texttt{\textsc{PHP}}\xspace}
\newcommand{\Lua}{\texttt{\textsc{Lua}}\xspace}
\newcommand{\Cpp}{\texttt{\textsc{C++}}\xspace}
\usepackage{mathtools}
\newcommand{\defeq}{\vcentcolon=} % := (benötigt mathtools)
\newcommand{\eqdef}{=\vcentcolon} % =: (benötigt mathtools)
\providecommand{\dotminus}{\mathbin{\vphantom{+}\text{\mathsurround=0pt \ooalign{\noalign{\kern-.35ex}\hidewidth$\smash{\cdot}$\hidewidth\cr \noalign{\kern.35ex}$-$\cr }}}}
\newcommand{\True}{\textsc{True}\xspace}
\newcommand{\False}{\textsc{False}\xspace}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand{\Null}{\textsc{Null}\xspace}
\newcommand{\Hinweis}[1]{\smallskip\noindent(\emph{Hinweis:} {#1})}
\newcommand{\Bemerkung}[1]{\smallskip\noindent(\emph{Bemerkung:} {#1})}

% Counter für Aufgaben
\newcounter{AufgabenNummer}
\setcounter{AufgabenNummer}{1}

% Übungsblatt
\newcommand\Nummer{10}
\newcommand\Aufgabe{Aufgabe \Nummer{}.\arabic{AufgabenNummer}\stepcounter{AufgabenNummer}}

\begin{document}
\begin{frame}
\frametitle{Aufgabe}
	\parbox{\linewidth}{%
		\alert{\triang \Aufgabe} (Weihnachtsversion): Es seien die beiden Folgen von Tupeln gegeben:
		\begin{itemize}
			\item{\scriptsize $K_1 = $ (\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}, \text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{christmas-tree}}), (\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}\text{\emoji{snowflake}}, \text{\emoji{christmas-tree}}), (\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{snowflake}}, \text{\emoji{santa-claus}}), (\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}, \text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}), (\text{\emoji{snowflake}}, \text{\emoji{snowflake}}\text{\emoji{snowflake}}\text{\emoji{christmas-tree}})}
			\item{\scriptsize $K_2 = $ $(101, 10)$, $(1, 01)$, $(010, 10)$, $(10, 0)$}
		\end{itemize}
		
		Zeigen oder widerlegen Sie die folgende Aussagen:
		\begin{enumerate}[\quad (i)]
			\item $K_1 \in PCP$
			\item $K_2 \in PCP$
		\end{enumerate}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		{\scriptsize\begin{center}
			$K_1 = $ \only<3>{\myhl{(\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}, \text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{christmas-tree}})}}\only<1-2,4->{(\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}, \text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{christmas-tree}})}, \only<6>{\myhl{(\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}\text{\emoji{snowflake}}, \text{\emoji{christmas-tree}})}}\only<1-5,7->{(\text{\emoji{christmas-tree}}\text{\emoji{christmas-tree}}\text{\emoji{snowflake}}, \text{\emoji{christmas-tree}})}, \only<4>{\myhl{(\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{snowflake}}, \text{\emoji{santa-claus}})}}\only<1-3,5->{(\text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}\text{\emoji{snowflake}}, \text{\emoji{santa-claus}})}, \only<7>{\myhl{(\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}, \text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}})}}\only<1-6>{(\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}}, \text{\emoji{snowflake}}\text{\emoji{christmas-tree}}\text{\emoji{santa-claus}})}, \only<2,5>{\myhl{(\text{\emoji{snowflake}}, \text{\emoji{snowflake}}\text{\emoji{snowflake}}\text{\emoji{christmas-tree}})}}\only<1,3-4,6->{(\text{\emoji{snowflake}}, \text{\emoji{snowflake}}\text{\emoji{snowflake}}\text{\emoji{christmas-tree}})}
		\end{center}}
		
		\alert{$K_1 \in PCP$} mit \only<2>{\alert{$i_1 = 5$}}\only<1,3->{$i_1 = 5$}, \only<3>{\alert{$i_2 = 1$}}\only<1-2,4->{$i_2 = 1$}, \only<4>{\alert{$i_3 = 3$}}\only<1-3,5->{$i_3 = 3$}, \only<5>{\alert{$i_4 = 5$}}\only<1-4,6->{$i_4 = 5$}, \only<6>{\alert{$i_5 = 2$}}\only<1-5,7->{$i_5 = 2$} und \only<7>{\alert{$i_6 = 4$}}\only<1-6>{$i_6 = 4$}. \uncover<2->{Es ergibt sich damit:}
		\begin{center}
			\uncover<2->{\emoji{snowflake}}\uncover<3->{{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{christmas-tree}}\uncover<4->{{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{santa-claus}\phantom{$\vert$}\emoji{snowflake}}\uncover<5->{{$\vert$}\emoji{snowflake}}\uncover<6->{{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{snowflake}}\uncover<7->{{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{santa-claus}}\\
			\uncover<2->{\emoji{snowflake}\phantom{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}}\uncover<3->{{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}}\uncover<4->{{$\vert$}\emoji{santa-claus}}\uncover<5->{{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}}\uncover<6->{{$\vert$}\emoji{christmas-tree}}\uncover<7->{{$\vert$}\emoji{snowflake}\phantom{$\vert$}\emoji{christmas-tree}\phantom{$\vert$}\emoji{santa-claus}}
		\end{center}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\begin{center}
			$K_2 = $ $(101, 10)$, $(1, 01)$, $(010, 10)$, $(10, 0)$
		\end{center}
		
		\uncover<1->{\alert{$K_2 \notin PCP$.}} \uncover<2>{Der einzig mögliche Anfang der Folge kann nur das erste Tupel \alert<2>{$(101, 10)$} sein, da sich bei allen anderen Tupeln die beiden Komponenten im ersten Symbol unterscheiden.} \uncover<3>{Darauf muss ein Tupel folgen, dessen zweite Komponente mit $1$ beginnt.} \uncover<4>{Mit dem Tupel \alert<4>{$(101, 10)$} ergibt sich allerdings \alert<4>{$101\underline{1}01 \cdots \neq 101\underline{0} \cdots \lightning$}.} \uncover<5>{Also muss das zweite gewählte Tupel \alert<5>{$(010, 10)$} sein.}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\begin{center}
			$K_2 = $ $(101, 10)$, $(1, 01)$, $(010, 10)$, $(10, 0)$
		\end{center}
		
		\only<1,4-13>{\uncover<1>{Es ergibt sich:}
		\begin{align*}
			&\textcolor{Apricot}{101}\textcolor{PineGreen}{010}\only<4-10>{\textcolor{WildStrawberry}{101}}\only<6>{\alert{1}}\only<7>{\alert{10}}\only<8>{\alert{101}}\only<9-10>{\alert{010}}\only<11->{\textcolor{blue}{010}}\only<12->{\textcolor{Apricot}{1}}\only<12->{\textcolor{PineGreen}{1}}\only<13->{\textcolor{WildStrawberry}{010}} \cdots\\
			&\textcolor{Apricot}{10}\textcolor{PineGreen}{10}\only<4-10>{\textcolor{WildStrawberry}{10}}\only<6>{\alert{01}}\only<7>{\alert{0}}\only<8>{\alert{10}}\only<9-10>{\alert{10}}\only<11->{\textcolor{blue}{10}}\only<12->{\textcolor{Apricot}{01}}\only<12->{\textcolor{PineGreen}{01}}\only<13->{\textcolor{WildStrawberry}{10}} \cdots
		\end{align*}}
		\only<2-3>{\uncover<2>{\alert{Beobachtung:} Es muss auf jeden Fall das Tupel \alert<2>{$(1, 01)$} verwendet werden, da bei allen anderen Tupeln die erste Komponente länger als die zweite ist.} \uncover<3>{Weiter kann das genannte Tupel höchstens zweimal hintereinander verwendet werden, da es keine Möglichkeit gibt \alert{$111$} mit den zweiten Komponenten zu erzeugen.}}
		
		\only<4-10>{\uncover<4>{Angenommen wir wählen als drittes Tupel \textcolor{WildStrawberry}{$(101,10)$}.} \uncover<5-8>{Dann sind Tupel \alert<6>{$(1, 01)$}, \alert<7>{$(10, 0)$} und \alert<8>{$(101, 10)$} nicht möglich.} \uncover<9>{Das vierte Tupel muss also \alert<9>{$(010, 10)$} sein.} \uncover<10>{Hierauf folgt wieder $(101,10)$ und diese Konstellation wiederholt sich immer wieder.}}
		
		\only<11-13>{\uncover<11>{Es ist also nicht möglich, $(101,10)$ als drittes Tupel zu verwenden. Das heißt, das dritte gewählte Tupel muss \only<11>{\textcolor{blue}{$(010,10)$}}\only<12->{$(010,10)$} sein.} \uncover<12>{Nun lassen wir auf dieses Tupel zweimal \alert<12>{$(1,01)$} folgen \textcolor{black!40}{(einzig sinnvolle Wahl)}.} \uncover<13>{Das nächste Tupel muss \alert<13>{$(010,10)$} sein und wir befinden uns wieder in der Anfangssituation.}}
		
		\only<14>{Zusammengefasst bedeutet das, dass \alert{$K_2 \notin PCP$}.}
	}
\end{frame}

\begin{frame}
\frametitle{Aufgabe}
	\parbox{\linewidth}{%
		\alert{\triang \Aufgabe}: Sei \textsc{01-PCP} die Variante des Postschen Korrespondenzproblems, bei der die Eingabetupel auf das Alphabet $\{0,1\}$ beschränkt sind (d.\,h.\ die Wörter der Wortpaarfolge sind nicht-leere Binärstrings). Zeigen Sie, dass diese Variante \alert{unentscheidbar} ist.
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\uncover<1>{Die Idee bei dieser Aufgabe ist es, das \textsc{PCP} auf \textsc{01-PCP} zu \alert{reduzieren};} \uncover<+>{dann gilt, dass \textsc{01-PCP} nicht entscheidbar sein kann, da \textsc{PCP} nicht entscheidbar ist.} \uncover<+>{Gegeben sei eine \textsc{PCP}-Instanz über einem beliebigen Alphabet $\Sigma$.} \uncover<+>{Wir müssen nun jedes Symbol $\alpha \in \Sigma$ als \alert{Binärstring} kodieren.} \uncover<+>{Allerdings muss man bei der Kodierung aufpassen, dass keine \alert{\enquote{falschen} Lösungen} entstehen.} \uncover<+>{Würde bspw. ein Symbol $\alpha$ mit $0$ kodiert werden und ein zweites Symbol $\beta$ mit $00$, dann wäre $0 \cdot 0 = 00$, allerdings $\alpha \cdot \alpha \neq \beta$.} \uncover<+>{Um diese Problematik zu umgehen, kann man die Kodierung so wählen, dass alle Kodierungen die gleiche Länge haben oder, dass bei allen Kodierungen der \enquote{Rand} eines Symbols explizit erkennbar ist.} \uncover<+>{Prinzipiell funktioniert hier jede präfixfreie (oder suffixfreie) Kodierung.}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\uncover<1>{Eine (für die Reduktion passende) Kodierung könnte bspw. wie folgt konstruiert werden:} \uncover<+>{Sei $\Sigma = \{\alpha_1, \dots, \alpha_m\}$.} \uncover<+>{Wir ersetzen jedes Symbol \alert{$\alpha_i$} durch den Binärstring \alert{$01^i$} (also eine Null gefolgt von $i$ Einsen).} \uncover<+>{Außerdem ersetzen wir in jedem Wort der Wortpaarfolge der gegebenen Probleminstanz die Symbole passend zur Kodierung.} \uncover<+>{Diese Funktion  ist total und berechenbar und erfüllt somit die Eigenschaften einer Reduktionsfunktion.} \uncover<+>{Da die Funktion bijektiv ist, gilt auch offensichtlich, dass die gegebene Probleminstanz genau dann eine Lösung hat, wenn auch die kodierte Instanz eine Lösung besitzt} \uncover<+>{und somit gilt \alert{$\textsc{PCP} \leq \textsc{01-PCP}$}.}
	}
\end{frame}

\begin{frame}
\frametitle{Aufgabe}
	\parbox{\linewidth}{%
		\alert{\triang \Aufgabe}: Sei \textsc{$1$-PCP} die Variante des Postschen Korrespondenzproblems, bei dem man die Eingabetupel auf das Alphabet $\{1\}$ beschränkt. Zeigen Sie, dass \textsc{1-PCP} \alert{entscheidbar} ist.
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\uncover<1>{Wenn das Alphabet nur aus einem Zeichen besteht, dann kommt es nur auf die \alert{Längen} der einzelnen Teilworte an. Darum kann man das ganze \enquote{rechnerisch} entscheiden.} \uncover<+>{Folgender Algorithmus entscheidet das unäre PCP:
		\begin{enumerate}[\quad 1.]
			\item Wenn für alle Paare $(x_i, y_i)$ gilt: ${|x_i|} > {|y_i|}$, dann \alert{lehne ab}.
			\item Wenn für alle Paare $(x_i, y_i)$ gilt: ${|x_i|} < {|y_i|}$, dann \alert{lehne ab}.
			\item Sonst \alert{akzeptiere}.
		\end{enumerate}}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		\uncover<1>{Im letzten Schritt kann der Algorithmus problemlos akzeptieren, denn: Entweder es gibt ein Paar $(x_i, y_i)$ mit \alert{${|x_i|} = {|y_i|}$}.} \uncover<+>{Dann ist dieses Paar eine gültige Lösung.} \uncover<+>{Oder es existieren zwei Paare $(x_i, y_i)$ und $(x_j, y_j)$, so dass gilt: \alert{${|x_i|} > {|y_i|}$} und \alert{${|x_j|} < {|y_j|}$}.} \uncover<+>{Um nun mit den beiden Paaren zwei gleiche Wörter zu bilden müssen wir \alert{$n \cdot {|x_i|} + m \cdot {|x_j|} = n \cdot {|y_i|} + m \cdot {|y_j|}$} lösen.} \uncover<+>{Diese Gleichung ist äquivalent zu \alert{$n \cdot ({|x_i|} - {|y_i|}) = m \cdot ({|y_j|} - {|x_j|})$}} \uncover<+>{und hat eine Lösung mit \alert{$n = ({|y_j|} - {|x_j|})$} und \alert{$m = ({|x_i|} - {|y_i|})$}.}
	}
\end{frame}

\begin{frame}
\frametitle{Lösung}
	\parbox{\linewidth}{%
		Wenn man nun \alert<1-2>{$n$-mal Paar $(x_i, y_i)$} und \alert<1-2>{$m$-mal Paar $(x_j, y_j)$} nimmt, ergeben sich gleiche Wörter:
		{\footnotesize\begin{align*}
			\uncover<2-3>{&~ x_i^{\alert<3>{n}} \cdot x_j^{\alert<3>{m}} &=&~ y_i^{\alert<3>{n}} \cdot y_j^{\alert<3>{m}} \\}
			\uncover<3-4>{\equiv &~ \alert<4>{x_i}^{|y_j| - |x_j|} \cdot \alert<4>{x_j}^{|x_i| - |y_i|} &=&~ \alert<4>{y_i}^{|y_j| - |x_j|} \cdot \alert<4>{y_j}^{|x_i| - |y_i|} \\}
			\uncover<4-5>{\equiv &~ \alert<5>{(|y_j| - |x_j|)} \cdot |x_i| + \alert<5>{(|x_i| - |y_i|)} \cdot |x_j| &=&~ \alert<5>{(|y_j| - |x_j|)} \cdot |y_i| + \alert<5>{(|x_i| - |y_i|)} \cdot |y_j| \\}
			\uncover<5-6>{\equiv &~ |x_i||y_j| \alert<6>{- |x_i||x_j| + |x_i||x_j|} - |x_j||y_i| &=&~ \alert<6>{|y_i||y_j|} - |x_j||y_i| + |x_i||y_j| \alert<6>{- |y_i||y_j|} \\}
			\uncover<6-7>{\equiv &~ |x_i||y_j| - |x_j||y_i| &=&~ \alert<7>{- |x_j||y_i|} + |x_i||y_j| \\}
			\uncover<7-8>{\equiv &~ \alert<8>{|x_i||y_j| - |x_j||y_i|} &=&~ \alert<8>{|x_i||y_j| - |x_j||y_i|} \\}
			\uncover<8-9>{\equiv &~ \alert<9>{1^{|x_i||y_j| - |x_j||y_i|}} &=&~ \alert<9>{1^{|x_i||y_j| - |x_j||y_i|}}}
		\end{align*}}%
		
		\uncover<9>{Da \alert{${|x_i|} > {|x_j|} > 0$} und \alert{${|y_j|} > {|y_i|} > 0$} ist \alert{$1^{|x_i||y_j| - |x_j||y_i|}$} ein gültiges Wort.}
	}
\end{frame}
\end{document}