\documentclass[a4paper, 12pt]{article}

% Deutsch
% \usepackage{ngerman}
% \usepackage[ansinew]{inputenc}
% \usepackage[T1]{fontenc}
% \usepackage{lmodern}
\usepackage[main=ngerman,british]{babel}

% Sonderzeichen
% \usepackage{bbold}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{mathtools}

% Zeilenumbruch
\usepackage{breqn}

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

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

% Farbe (für Lösungen)
\usepackage{xcolor}
\definecolor{darkgray}{gray}{0.3}

% Footer / Header
\usepackage{fancyhdr}
\usepackage{lastpage}

% Für den Header
\usepackage[strict]{changepage}

% Seitenlayout und -stil
\usepackage[a4paper,top=15mm,bottom=25mm,left=25mm, right=25mm]{geometry}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0.0pt}
\cfoot{(Seite \thepage \hspace{1pt} von \pageref{LastPage})}
\usepackage{adjustbox}

% zum Testen
% \overfullrule=2cm
\usepackage{lipsum}

\usepackage{graphicx}
\usepackage{tikz}
% \usetikzlibrary{calc,decorations.pathreplacing,shapes.geometric,arrows.meta}
\usetikzlibrary{calc,decorations.pathreplacing,shapes,arrows.meta,bending}
\usepackage{rotating}
\usepackage{caption}
\usepackage{subcaption}
\renewcommand{\figurename}{\footnotesize Abb.}

% Algorithmen
\usepackage{algorithm, comment}
\usepackage{algpseudocode}
\usepackage{listings}
\usepackage{lstautogobble}

% Sprachen
\lstdefinelanguage{goto}
	{morekeywords={GOTO,IF,THEN,HALT},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily
}
\lstdefinelanguage{pseudo}
	{morekeywords={function,if,then,else,fi,for,to,step,do,od,end,while,repeat,until,foreach,return},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\bfseries\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily,
	mathescape=true,
	numbers=left,
	numbersep=5pt,
	numberstyle=\small\color{darkgray},
	frame=leftline,
	rulecolor=\color{darkgray}
}

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

% loop
\algrenewcommand\algorithmicloop{\textbf{loop}}
\algdef{S}[WHILE]{LoopX}[1]{\algorithmicloop\ #1\ \algorithmicdo}
\newcommand{\EndLoopX}{\algrenewtext{EndWhile}{{\newalgstyle end}}\EndWhile\algrenewtext{EndWhile}{{\newalgstyle od}}}

% custom keywords
\newcommand{\key}[1]{{\ttfamily\bfseries\color{teal}#1}}
\newcommand{\Input}[1]{\Statex\key{Input:} {#1}}

% full line comment
\newcommand{\linecomment}[1]{\Statex{\color{darkgray}$\triangleright$ #1}}

% algorithmic-Anpassungen
\algrenewcommand\algorithmiccomment[1]{{\color{darkgray}\hfill$\triangleright$ #1}}
\newcommand\newalgstyle{\ttfamily\bfseries\color{teal}}
\algrenewcommand\algorithmicend{{\newalgstyle end}}
\algrenewcommand\algorithmicdo{{\newalgstyle do}}
\algrenewcommand\algorithmicwhile{{\newalgstyle while}}
\algrenewcommand\algorithmicfor{{\newalgstyle for}}
\algrenewcommand\algorithmicforall{{\newalgstyle for all}}
\algrenewcommand\algorithmicforeach{{\newalgstyle for each}}
\algrenewcommand\algorithmicloop{{\newalgstyle loop}}
\algrenewcommand\algorithmicrepeat{{\newalgstyle repeat}}
\algrenewcommand\algorithmicuntil{{\newalgstyle until}}
\algrenewcommand\algorithmicprocedure{{\newalgstyle procedure}}
\algrenewcommand\algorithmicfunction{{\newalgstyle function}}
\algrenewcommand\algorithmicif{{\newalgstyle if}}
\algrenewcommand\algorithmicthen{{\newalgstyle then}}
\algrenewcommand\algorithmicelse{{\newalgstyle else}}
\algrenewcommand\algorithmicrequire{{\newalgstyle Require:}}
\algrenewcommand\algorithmicensure{{\newalgstyle Ensure:}}
\algrenewcommand\algorithmicreturn{{\newalgstyle return}}
\algrenewtext{EndWhile}{{\newalgstyle od}}
\algrenewtext{EndFor}{{\newalgstyle od}}
\algrenewtext{EndLoop}{{\newalgstyle od}}
\algrenewtext{EndIf}{{\newalgstyle fi}}
\algrenewtext{EndFunction}{{\newalgstyle end}}

% kleine Aufzählungszeichen & Prozent
% \renewcommand{\labelitemi}{\raise .5ex\hbox{\tiny$\bullet$}}
\renewcommand\labelitemi{$\vcenter{\hbox{\tiny$\bullet$}}$}
% \renewcommand{\labelitemi}{\boldmath$\cdot$}
\newcommand{\pct}{\,\scalebox{.9}{\%} }

% \Item-Befehl, damit Align-Umgebungen in der richtigen Zeile beginnen
\newcommand\Item[1][]{%
  \ifx\relax#1\relax  \item \else \item[#1] \fi
  \abovedisplayskip=0pt\abovedisplayshortskip=0pt~\vspace*{-\baselineskip}
}

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

% für die Kurzschreibweisen
\usepackage{xspace}

% Kurzschreibweisen
\newcommand{\setN}{\mathbb{N}}
\newcommand{\setZ}{\mathbb{Z}}
\newcommand{\setQ}{\mathbb{Q}}
\newcommand{\setR}{\mathbb{R}}
\newcommand{\sigStar}{\Sigma^{*}}
\newcommand{\EStar}{E^{*}}
\newcommand{\binStar}{\{0,1\}^{*}}
\newcommand{\Oh}[1]{\mathcal{O}({#1})}
\newcommand{\OhOmega}[1]{\Omega({#1})}
\newcommand{\OhTheta}[1]{\Theta({#1})}
\newcommand{\qed}{\hfill $\square$}
\newcommand{\Null}{\textsc{Null}\xspace}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand{\True}{\textsc{True}\xspace}
\newcommand{\False}{\textsc{False}\xspace}
\newcommand{\defeq}{\vcentcolon=} % := (benötigt mathtools)
\newcommand{\eqdef}{=\vcentcolon} % =: (benötigt mathtools)
\newcommand{\Hinweis}[1]{\smallskip\noindent(\emph{Hinweis:} {#1})}
\newcommand{\Bemerkung}[1]{\smallskip\noindent(\emph{Bemerkung:} {#1})}
\newcommand{\ztm}[2]{\begin{array}{c} {#1} \\ {#2} \end{array}}

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

% Mathekommentare
\newcommand{\mathcomm}[1]{\triangleright~\text{#1}}
% Farbig unterstreichen
\def\mathunderline#1#2{\color{#1}\underline{{\color{black}#2}}\color{black}}

% Silbentrennung
\hyphenation{While-Schlei-fe}
\hyphenation{While-be-rech-en-bar}

% Mayaziffern
\usepackage{fontspec}
\newfontface{\babm}{BabelStone Mayan Numerals}
\DeclareRobustCommand\mzero{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E0}}}%
}
\DeclareRobustCommand\mone{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E1}}}%
}
\DeclareRobustCommand\mtwo{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E2}}}%
}
\DeclareRobustCommand\mthree{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E3}}}%
}
\DeclareRobustCommand\mfour{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E4}}}%
}
\DeclareRobustCommand\mfive{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E5}}}%
}
\DeclareRobustCommand\msix{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E6}}}%
}
\DeclareRobustCommand\mseven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E7}}}%
}
\DeclareRobustCommand\meight{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E8}}}%
}
\DeclareRobustCommand\mnine{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E9}}}%
}
\DeclareRobustCommand\mten{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EA}}}%
}
\DeclareRobustCommand\meleven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EB}}}%
}
\DeclareRobustCommand\mtwelve{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EC}}}%
}
\DeclareRobustCommand\mthirteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2ED}}}%
}
\DeclareRobustCommand\mfourteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EE}}}%
}
\DeclareRobustCommand\mfifteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EF}}}%
}
\DeclareRobustCommand\msixteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F0}}}%
}
\DeclareRobustCommand\mseventeen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F1}}}%
}
\DeclareRobustCommand\meighteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F2}}}%
}
\DeclareRobustCommand\mnineteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F3}}}%
}

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

% Counter für Lösungen
\newcounter{LoesungNummer}
\setcounter{LoesungNummer}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ÄNDERN
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variablen für Übungsnummer und Abgabedatum
\newcommand\Nummer{3}
\newcommand\Abgabe{26.\,November 2021 um 12 Uhr}
\newif\ifhideloesung
\usepackage{substr}
\IfSubStringInString{\detokenize{loesung}}{\jobname}{}{\hideloesungtrue}
% \hideloesungtrue % Nicht kommentiert = Lösungen versteckt

% Environment für Aufgaben
\newenvironment{aufgabe}[1]{\noindent \textbf{Aufgabe \Nummer{}.\arabic{AufgabenNummer}} \textit{(#1 Punkte)} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{AufgabenNummer} \bigskip}

% Environment für Lösungen
\newenvironment{loesung}{\color{blue} \noindent \textbf{Lösung} \nopagebreak \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Lösungen 2
\newenvironment{loesung2}{\color{blue} \noindent \textbf{Lösung \Nummer{}.\arabic{LoesungNummer}} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{LoesungNummer} \bigskip}

% Environment für Ankündigungen
\newenvironment{ankuendigung}{\noindent \hrulefill \medskip \par \noindent \textbf{Ankündigung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Mitteilung
\newenvironment{mitteilung}{\noindent \hrulefill \medskip \par \noindent \textbf{Mitteilung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Definitionen
\newenvironment{definition2}{\noindent \textbf{Definition(en)} \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Dateinamensschema
% \newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \bigskip}
\newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \pagebreak}

% Kopfzeile
\newcommand{\Kopfzeile}{
\begin{center}
	\noindent
	\parbox[t][5em][c]{0.5\textwidth}{
	\begin{flushleft}
		\textmd{Datenstrukturen und Effiziente Algorithmen} \\
		\textit{Fachbereich IV - Informatik} \\
		\textit{Universität Trier}
	\end{flushleft}}
	\hfill
	\parbox[t][5em][c]{0.49\textwidth}{
	\begin{flushright}
		Moritz Gobbert \\
		\textit{gobbert@uni-trier.de} \\
		\textit{Raum H\,428}
	\end{flushright}}
\end{center}
\bigskip
}

% Titel
\newcommand{\Titel}{
\begin{center}
	{\Large Berechenbarkeit und Komplexitätstheorie} \\
	Wintersemester 2021/2022 \\
	Aufgabenblatt \Nummer \\
	\textbf{Abgabe: \Abgabe}
\end{center}
}

\ifhideloesung
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\loesung\hide
	\let\endloesung\endhide
\else
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\dateinamensschema\hide
	\let\enddateinamensschema\endhide
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                               Textanfang                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
	\Titel
	\bigskip
	\begin{dateinamensschema}
		Geben Sie nur eine \emph{einzelne} Datei ab. Diese Datei sollte vorzugsweise im \texttt{pdf}-Format sein. Falls Ihre Abgabe aus mehr als einer Datei besteht, dann packen Sie diese bitte zusammen in ein \texttt{zip}-Archiv. Notieren Sie auf Ihrer Abgabe die Namen und Matrikelnummern aller an der Abgabe beteiligten Personen. Achten Sie darauf, dass Ihre Datei leserlich ist -- insbesondere bei Fotos einer handschriftlichen Abgabe. Bezeichnen Sie die abzugebende Datei nach dem folgenden Muster:
		
		\begin{center}\texttt{Nachname\_Vorname\_Matrikelnummer.pdf} (bzw.\ \texttt{.zip})\end{center}
		
		\noindent{}Falls Sie als Gruppe abgeben reichen als Dateiname die Daten eines Gruppenmitglieds -- die Daten der anderen Mitglieder stehen in der Lösung selbst. Zur Abgabe gibt es in \emph{Moodle} einen passenden Abschnitt namens \enquote{\texttt{Übung \Nummer}} in dem Sie Ihre Lösungen hochladen können.
		
		Abgabetermin ist Freitag, der \textbf{\Abgabe}.
	\end{dateinamensschema}
	
	\begin{definition2}
		\begin{itemize}
			\item Die $k$-stellige Cantor'sche Bijektion\footnote{Vgl.\ Definition in Kapitel 3 auf Seite 16 im Skript.} $\langle \cdot \rangle: \setN^{k} \rightarrow \setN$ ist definiert als:
			\begin{align*}
				\langle x_1, \dots ,x_{k-1}, x_k \rangle = \langle x_1, \langle \ldots \langle x_{k-1}, x_k \rangle \dots \rangle \text{~mit~} \langle x, y \rangle = y + \left(\sum_{i=1}^{x+y}~i\right)
			\end{align*}
			Weiter bezeichnen $p_1$, \dots,  $p_k$ die Umkehrfunktion(en) der Cantor'schen Bijektion, sodass $\langle p_1(z), \dots, p_k(z) \rangle = z$ gilt. (Die tatsächliche Berechnung der Komponenten ist im Skript auf Seite 17 beschrieben.)
			\item Die Ackermannfunktion $A: \setN_0 \times \setN_0 \rightarrow \setN$ ist wie folgt definiert:
		\begin{align*}
			A(0, y) &= y + 1 \\
			A(x + 1, 0) &= A(x, 1) \\
			A(x + 1, y + 1) &= A(x, A(x+1, y))
		\end{align*}
		\end{itemize}
	\end{definition2}
	
	\begin{aufgabe}{2 + 2}
		Sei $f: \mathbb{N} \rightarrow \mathbb{N}$ eine \textsc{While}-berechenbare, injektive, totale Funktion.
		\begin{enumerate}[\quad a)]
			\item Zeigen Sie, dass die Umkehrfunktion $f^{-1}$ von $f$ ebenfalls \textsc{While}-berechenbar ist.
			\item Gilt das gleiche auch für \textsc{Loop}-berechenbare Funktionen? (Begründen Sie Ihre Antwort.)
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item \textsc{While}-berechenbare Funktionen müssen nicht total sein; Also darf die gesuchte Umkehrfunktion $f^{-1}$ partiell sein. Da $f$ injektiv ist, ist die folgende Umkehrfunktion wohldefiniert:
			\begin{gather*}
				f^{-1}(y) = \begin{cases}x \text{, falls }f(x) = y\\\text{undefiniert, sonst}\end{cases}
			\end{gather*}
			Um nun $f^{-1}$ zu berechnen, kann man einen Algorithmus schreiben, der alle $x$ ausprobiert, bis er dasjenige findet, für das gilt $f(x) = y$.
			
			Beispielsweise:
			\begin{algorithmic}[1]
				\State $x_0 \defeq 0$
				\State $x_t \defeq 1$
				\While{$x_t \neq 0$}
					\State $x_0 \defeq x_0 + 1$
					\If{$f(x_0) = y$}
						\State $x_t \defeq 0$
					\EndIf
				\EndWhile
			\end{algorithmic}
			\item Nein. \textsc{Loop}-berechenbare Funktionen müssen total sein, aber eine Umkehrfunktion ist nicht zwingend total. (Bspw. ist $f \colon \setN \rightarrow \setN$, $x \mapsto 2\cdot x$ total, aber die Umkehrfunktion $f^{-1} \colon \setN \rightarrow \setN$ ist nur für gerade Zahlen definiert.) Prinzipiell kann man in den meisten Fällen den Definitionsbereich einschränken um die undefinierten Fälle auszuschließen. Also statt $f^{-1} \colon \setN \rightarrow \setN$ kann man $f^{-1} \colon f(\setN) \rightarrow \setN$ setzen. (Im obigen Beispiel wäre dann $f^{-1} \colon \{x \in \setN \colon \exists x' \in \setN~2 \cdot x' = x\} \rightarrow \setN$ eine totale Funktion.) Allerdings müsste dann die Definition der \textsc{Loop}-Programme aus der Vorlesung, die beliebige natürliche Zahlen als Eingabe erlaubt, etwas verändert werden.
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{2 + 2}
		\begin{enumerate}[\quad a)]
			\item Gilt $\langle 1, 2, 3\rangle \leq \langle 2, 2, 2\rangle$? (Begründen Sie kurz.)
			\item Bestimmen Sie $a,b,c \in \setN$, sodass $\langle a, b, c \rangle = 102$.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Nein, denn:
				\begin{align*}
					\langle 1,2,3 \rangle &= \langle 1,\langle 2,3 \rangle \rangle \\
							&= \langle 1, 18 \rangle \\
							&= 208 \\
					\langle 2,2,2 \rangle &= \langle 2,\langle 2,2 \rangle \rangle \\
							&= \langle 2, 12 \rangle \\
							&= 117 \\
				\end{align*}
				Und $208 \nleq 117$.
			\item Es gilt $\langle 2,3,1 \rangle = \langle 2, 11 \rangle = 102$
		\end{enumerate}
	\end{loesung}
	
	% \begin{aufgabe}{5}
		% Eine Möglichkeit zu zeigen, dass die Ackermann-Funktion \textsc{While}-berechenbar ist, ist die Rekursion durch einen Stack \enquote{aufzulösen}. Dann benötigt man nur eine einzelne \mbox{\textsc{While}}-Schleife um $A(x,y)$ auszurechnen. Zeigen Sie, dass die beiden üblichen Stack-Operationen \textsc{Push}\footnote{Einfügen eines Elements auf die oberste Position des Stacks} und \textsc{Pop}\footnote{Zurückliefern und Entfernen des obersten Elements des Stacks} \textsc{While}-berechenbar sind. Begründen Sie kurz!

		% \Hinweis{Arbeiten Sie mit der Cantor'schen Bijektion und ihrer Umkehrfunktion. Stack-Elemente sind natürliche Zahlen.}			
	% \end{aufgabe}
	
	% \begin{loesung}
		% Sei im folgenden $s$ der Stack. \textsc{Push($x$)} kann man implementieren durch $s \defeq \langle x, s \rangle$ und \textsc{Pop()} kann man implementieren als $x \defeq d^{(2)}_1(s)$ und $s \defeq d^{(2)}_2(s)$. Sowohl die Cantor'sche Bijektion als auch ihre Umkehrfunktion(en) sind berechenbar, also auch die Stack-Operationen. Ebenfalls gilt für einen (beliebigen) Stack $s$ und eine beliebige Zahl $n \in \setN$, dass man durch hintereinander ausführen der beiden Operationen den Stack $s$ wieder (unverändert) erhält, denn $d^{(2)}_2(\langle x, s \rangle) = s$. Umgekehrt ergibt sich auch $\langle d^{(2)}_1(s), d^{(2)}_2(s) \rangle = s$.
		
		% Das ist nicht relevant für die Lösung, aber man kann $A(x,y)$ wie folgt berechnen ($y$ ist am Ende das Ergebnis):
		
		% \begin{center}
		% \begin{minipage}[h]{0.8\textwidth}
		% \begin{algorithmic}[1]
			% \Function{Ackermann}{$x$,$y$}
				% \State $s \defeq \langle x, 0 \rangle$ \Comment{Initialisiere $s$ und \textsc{Push($x$)}}
				% \State $sz = 1$
				% \While{$sz > 0$} \Comment{Solange der Stack nicht leer ist...}
					% \State $x \defeq d^{(2)}_1(s)$ \Comment{\textsc{Pop()}}
					% \State $s \defeq d^{(2)}_2(s)$
					% \State $sz \defeq sz - 1$
					% \If{$x = 0$} \Comment{Verankerung}
						% \State $y \defeq y+1$
					% \ElsIf{$y = 0$} \Comment{zweiter Fall}
						% \State $s \defeq \langle x - 1, s \rangle$ \Comment{Rekursiver Aufruf $A(x-1,1)$}
						% \State $sz \defeq sz + 1$
						% \State $y \defeq 1$
					% \Else
						% \State $s \defeq \langle x-1, s \rangle$ \Comment{Rekursive Aufrufe im dritten Fall}
						% \State $s \defeq \langle x, s \rangle$
						% \State $sz \defeq sz + 2$
						% \State $y \defeq y - 1$
					% \EndIf
				% \EndWhile
				% \State\Return{$y$}
			% \EndFunction
		% \end{algorithmic}
		% \end{minipage}
		% \end{center}
	% \end{loesung}
	
	\begin{aufgabe}{2 + 3 + 2}
		\begin{enumerate}[\quad a)]
			\item Implementieren Sie die Ackermann-Funktion in einer Programmiersprache Ihrer Wahl! (Die gewählte Sprache sollte \enquote{lesbar} sein -- \textsc{Brainfuck}, \textsc{Malbolge} oder sonstige esoterische Programmiersprachen werden wahrscheinlich nicht korrigiert.)
			\item Modifizieren Sie Ihre Implementierung aus dem vorigen Teil so, dass diese nicht rekursiv arbeitet, sondern die Rekursion durch einen Stack auflöst.
			\item Schreiben Sie ein \textsc{While}-Programm, welches die Ackermann-Funktion berechnet.
		\end{enumerate}
		\Hinweis{Implementieren Sie den Stack im \textsc{While}-Programm mithilfe der Cantor'schen Bijektion. Sie dürfen $\langle x, y\rangle$, $p_1$ und $p_2$ im \textsc{While}-Programm nutzen, ohne diese selbst zu implementieren.}
	\end{aufgabe}
	
	\begin{loesung}
	\begin{enumerate}[\quad a)]
		\item Die rekursive Variante der Ackermann-Funktion als \textsc{Lua}-Code:
			\lstset{
			language=[5.0]Lua,
			tabsize=2,
			basicstyle=\ttfamily\footnotesize,
			commentstyle=\ttfamily,
			commentstyle=\ttfamily\color{gray},
			keywordstyle=\color{teal},
			numbers=left,
			numberstyle=\tiny,
			stepnumber=1,
			breaklines=true,
			frame=single,
			captionpos=b,
			autogobble
		}
		\begin{lstlisting}
			function AckermannRek(x,y)
				if x == 0 then
					return y + 1
				elseif y == 0 then -- hier: x > 0
					return AckermannRek(x-1,1)
				else -- x,y > 0
					return AckermannRek(x-1,AckermannRek(x,y-1))
				end
			end
		\end{lstlisting}
		\item Die stackbasierte Variante der Ackermann-Funktion als \textsc{Lua}-Code:
			\lstset{
			language=[5.0]Lua,
			tabsize=2,
			basicstyle=\ttfamily\footnotesize,
			commentstyle=\ttfamily,
			commentstyle=\ttfamily\color{gray},
			keywordstyle=\color{teal},
			numbers=left,
			numberstyle=\tiny,
			stepnumber=1,
			breaklines=true,
			frame=single,
			captionpos=b,
			autogobble
		}
		\begin{lstlisting}
			function AckermannStack(x,y)
				s = {x} -- Stack mit x als Element initialisiert
				while #s > 0 do -- #s: Anzahl der Stackelemente
					x = table.remove(s) -- entspricht s.pop()
					if x == 0 then
						y = y + 1
					elseif y == 0 then
						table.insert(s, x-1) -- entspricht s.push(x-1)
						y = 1
					else
						table.insert(s,x-1) -- entspricht s.push(x-1)
						table.insert(s,x) -- entspricht s.push(x)
						y = y-1
					end
				end
				return y
			end
		\end{lstlisting}
		\item Das zugehörige \textsc{While}-Programm:
			\begin{algorithmic}[1]
			\Function{Ackermann}{$x$,$y$}
				\State $s \defeq \langle x, 0 \rangle$ \Comment{Initialisiere $s$ und \textsc{Push($x$)}}
				\State $sz = 1$
				\While{$sz > 0$} \Comment{Solange der Stack nicht leer ist...}
					\State $x \defeq p_1(s)$ \Comment{\textsc{Pop()}}
					\State $s \defeq p_2(s)$
					\State $sz \defeq sz - 1$
					\If{$x = 0$} \Comment{Verankerung}
						\State $y \defeq y+1$
					\ElsIf{$y = 0$} \Comment{zweiter Fall}
						\State $s \defeq \langle x - 1, s \rangle$ \Comment{Rekursiver Aufruf $A(x-1,1)$}
						\State $sz \defeq sz + 1$
						\State $y \defeq 1$
					\Else
						\State $s \defeq \langle x-1, s \rangle$ \Comment{Rekursive Aufrufe im dritten Fall}
						\State $s \defeq \langle x, s \rangle$
						\State $sz \defeq sz + 2$
						\State $y \defeq y - 1$
					\EndIf
				\EndWhile
				\State\Return{$y$}
			\EndFunction
		\end{algorithmic}
	\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}