\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{1}
\newcommand{\ABGABEDATUM}{am 25. April 2014 bis 10 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Grundlagen der theoretischen Informatik}\hfill SoSe 2014 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Vollst\"andige Induktion}{10 Punkte}

In dieser Aufgabe sollen Sie das Prinzip der vollst\"andigen
Induktion wiederholen. 

\begin{enumerate}
  \item Sei $n \geq 2$.
    Beweisen Sie durch vollst\"andige Induktion, dass eine Menge mit $n$ Elementen
    $n(n-1)/2$ Teilmengen mit genau zwei Elementen hat.
  \item Zeigen Sie durch vollst\"andige Induktion: F\"ur alle $n \geq 1$ ist
    \[
      1\cdot 1! + 2 \cdot 2! + \dots + n \cdot n! = (n+1)! -1.
    \]
\end{enumerate}

\AUFGABE{W\"orter}{10 Punkte}

 F\"ur ein \emph{Alphabet} $\Sigma$ mit $k$ Elementen 
  ist  $\Sigma^*$ die Menge der W\"orter (Folgen), die
  man aus den Buchstaben von $\Sigma$ bilden kann.
\begin{enumerate}
  \item Wieviele W\"orter in $\Sigma^*$ haben die 
    L\"ange $n$ (bestehen aus $n$ Buchstaben)? 
  \item Wieviele Palindrome in $\Sigma^*$ haben die L\"ange $n$?
(Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen
gleich ist.)
  \item Wieviele W\"orter der L\"ange $n=2,3,4,5,6,7,8$ \"uber dem Alphabet
  $\Sigma = \{\texttt{(},\texttt{)}\}$ sind ``g\"ultige''
  Klammerausdr\"ucke wie zum Beispiel \texttt{(()(()(()))())} und
  \texttt{((()))}? (Un\-g\"ul\-tig sind etwa 
  \texttt{(((())} --- mehr offene als geschlossene Klammern, und
  \texttt{())(()} --- die zweite schlie\ss{}ende Klammer hat keine
   \"offnende Partnerklammer.)
   Finden Sie eine (Rekursions-)Formel f\"ur die Anzahl 
   der g\"ultigen Klammerausdr\"ucke der L\"ange $n$.
\end{enumerate}

\AUFGABE{Kleene-Stern}{10 Punkte}

Sei $\Sigma$ ein Alphabet.
Eine \emph{formale Sprache} $A \subseteq \Sigma^*$ ist eine
Menge von W\"ortern \"uber $\Sigma$.
Der \emph{Kleene-Abschluss} von $A$ ist die Menge 
aller W\"orter, die man erh\"alt, indem man endlich
viele W\"orter aus $A$ hintereinander schreibt (inklusive
dem leeren Wort $\varepsilon$).
Sind $A, B \subseteq \Sigma^*$ formale Sprachen, so ist die 
\emph{Konkatenation} von $A$ und $B$, $A \circ B$, die
Menge aller W\"orter, die man erhalten kann, indem man 
ein Wort aus $B$ hinter ein Wort aus $A$ schreibt.
Beweisen oder widerlegen Sie:
\begin{enumerate}
  \item $(A \cup B)^* = A^* \cup B^*$;
  \item $(A \cap B)^* = A^* \cap B^*$;
  \item $(A  \circ B)^* = A^* \circ B^*$;
  \item $(A^*)^* = A^*$; und
  \item $A \subseteq B \Rightarrow A^* \subseteq B^*$. 
\end{enumerate}
\end{description}
\end{document}
