Dynamische-Programmierung_Aufgaben.tex

\documentclass{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{enumerate}

\begin{document}
\section*{Aufgaben zum Thema dynamische Programmierung}
\begin{enumerate}[(1)]

\item Was ist die grundlegende Idee hinter der Methode der dynamischen Programmierung?

\item Die Fakultätsfunktion $n!$ lässt sich folgendermaßen rekursiv definieren: \newline
$0! = 1$\newline
$n! = n\cdot(n-1)!$ 	für $n \geq 1$
\begin{enumerate}[(a)]
\item Geben Sie ein Programm in Pseudocode an, welches $n!$  mittels dynamischer Programmierung und Bottom-Up-Ansatz berechnet.
\item Das Programm soll nun so modifiziert werden, dass es nach einmaligem Berechnen von $n!$ jeden Aufruf $k!$ mit $k \leq n$ in $O(1)$ bearbeiten kann. Beschreiben Sie eine Möglichkeit dafür.
\end{enumerate}

\item Der Binomialkoeffizient $\binom{n}{k}$ kann folgendermaßen rekursiv berechnet werden:
\begin{center}
$\binom{n}{k}=\begin{cases}
0, & \text{falls } k > n;\\
1, & \text{falls } k=0 \text{ oder } n=k;\\
\binom{n-1}{k-1} + \binom{n-1}{k}, & \text{sonst.}
\end{cases}$
\end{center}
Geben Sie ein Programm in Pseudocode an, welches $\binom{n}{k}$ mittels dynamischer Programmierung und Bottom-Up-Ansatz berechnet. Hinweis: Verwenden Sie eine Matrix (d.h. ein 2-dimensionales Array), um die Lösungen der Teilprobleme zu speichern.

\end{enumerate}
\end{document}