% 1. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,5cm
\textheight=24cm
%\textheight=26cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{1}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 0.~\"Ubungsblatt\par
}
 (freiwillige Vorübungen)
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{0}

\item (0 Punkte) Die Programmiersprache \textsc{Schleife} hat die folgenden
  einfachen Regeln:
  \begin{itemize}
  \item Es gibt einen unendlichen Vorrat an Variablen \texttt{X0},
 \texttt{X1}, \texttt{X2}, \texttt{X3}, \dots, die beliebige
 natürliche Zahlen ($\ge0$) speichern können.
\item Es gibt die einfachen Anweisungen \texttt{X$i$ = 0}
  (Inititalisierung),
 \texttt{X$i$ = X$j$} (Kopieren),
 \texttt{X$i$ = X$i$ + 1} (Hinaufzählen) und
 \texttt{X$i$ = X$i$ - 1} (Herunterzählen).
(Beim Herunterzählenwird \texttt{X}$i$ unverändert gelassen,
wenn es den Wert 0 hat, weil die Variablen keine negativen
Werte enthalten können.)

\item 
Außerdem gibt es eine \emph{Schleifenanweisung}:
$$
\parbox{10cm}{\texttt{WIEDERHOLE X$i$ MAL}
  \\\null\quad\emph{Anweisungsfolge}
\\\texttt{SCHLEIFENENDE}}
$$
Wenn die Variable \texttt{X}$i$ zu Beginn der Ausführung den Wert $n$
hat, wird die Schleife $n$-mal wiederholt, auch wenn
\texttt{X}$i$ zwischendurch geändert wird.
Schleifen können auch geschachtelt sein.
  \end{itemize}
Es gibt keine Ein- und Ausgabeanweisungen. Die Eingabeparameter eines
Programms stehen zu Beginn in den ersten Variablen \texttt{X0},
 \texttt{X1}, \dots. Alle übrigen Variablen sind zu Beginn auf 0
 gesetzt.
Das Ergebnis des Programms ist der Wert, der am Ende in \texttt{X0}
steht.

Das folgende Programm berechnet zum Beispiel die Summe von zwei Zahlen
\texttt{X0} und \texttt{X1}:
$$
\parbox{10cm}{\texttt{WIEDERHOLE X1 MAL}
  \\\null\quad\texttt{X0 = X0 + 1}
\\\texttt{SCHLEIFENENDE}}
$$


 \begin{enumerate}
 \item Schreiben Sie ein Programm zur Berechnung des Produktes von
\texttt{X0} und \texttt{X1}.

\item  Schreiben Sie ein Programm, dass den Rest der Division von
\texttt{X1} durch \texttt{X0} berechnet. (Wenn $\texttt{X0}=0$ ist
soll das Ergebnis \texttt{X1} sein.)

 \item Schreiben Sie ein Programm zur Berechnung von
$2^\mathtt{X0}$.

\item Schreiben Sie ein Programm, dass mit allen Variablen auf Null
  beginnt, aus höch\-stens $n=2,3,4,5,6,7$ Anweisungen besteht, und am
  Ende einen möglichst großen Wert in \texttt{X0} hat.
(Dabei gilt ein \texttt{WIEDERHOLE}-\texttt{SCHLEIFENENDE}-Paar
als eine einzige Anweisung.)

\item Die Programmiersprache \textsc{Schleife++} hat zusätzlich
  bedingte Anweisungen:
$$
\parbox{10cm}{\texttt{IF X$i$>X$j$ THEN}
  \\\null\quad\emph{Anweisungsfolge}
\\\texttt{ENDIF}}
$$
Wie kann mein ein solches Programm durch Eliminieren aller bedingten
Anweisungen in ein \textsc{Schleife}-Programm übersetzen?
 \end{enumerate}

\item (0 Punkte) F\"ur ein \emph{Alphabet} $\Sigma$ mit $k$ Elementen 
  ist  $\Sigma^*$ ist die Menge der Wörter (Folgen), die
  man aus den Buchstaben von $\Sigma$ bilden kann.
\begin{enumerate}
\item[(a)] Wieviele Wörter in $\Sigma^*$ haben die L\"ange $n$ (bestehen aus $n$ Buchstaben)? 
\item[(b)]Wieviele Palindrome in $\Sigma^*$ haben die L\"ange $n$?
(Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen
gleich ist.) 
\end{enumerate}

\item (0 Punkte)
Durch wiederholte Anwendung des \emph{Homomorphismus}
$$0\to 01,\ 1\to 0$$
auf das Ausgangswort $0$ erhält man die Folge der Wörter
$$w_0=0,\ w_1=01,\ w_2=010,\ w_3=01001,\ w_4=01001010,\ w_5=0100101001001,\ \ldots$$
\begin{enumerate}
\item Beschreiben Sie, was ein Homomorphismus ist, und was die
  Anwendunge eines Homomorphismus auf ein Wort (über einem gegebenen
  Alphabet) bedeutet. (Lassen Sie sich dabei von diesem Beispiel und
  dem Beispiel in
  der nächsten Aufgabe leiten, anstatt gleich im Lehrbuch nachzuschlagen.)
\item Welche Länge hat das Wort $w_n$?
\item Jedes Wort ist ein Anfangsstück (\emph{Präfix}) des
  darauffolgenden Wortes, sodass die Folge gegen ein unendliches Wort $w_\infty$
  ``konvergiert''.
Wieviele verschiedene Teilwörter (zusammenhängende Teilfolgen) der
Längen
$n=1,2,3,4,5$ enthält~$w_\infty$?
\item (*) Gegen welchen Wert konvergiert der Anteil der Einsen in $w_n$ an der Gesamtzahl der Symbole?
\end{enumerate}

\item (0 Punkte)
Durch wiederholte Anwendung des Homomorphismus
$$0\to 100,\ 1\to 001$$
auf das Ausgangswort $0$ erhält man die Folge der Wörter
$$w_0=0,\ w_1=100,\ w_2=001100100,\ w_3=100001001001100100001100100,\ \ldots$$
\begin{enumerate}
\item Welche Länge hat das $n$-te Wort?
\item Gegen welchen Wert konvergiert der Anteil der Einsen?
\item Die Wörter, die mit 0 beginnen, konvergieren gegen ein
  unendliches Wort. Wieviele verschiedene Teilwörter der Längen
  $n=1,2,3,4,5$ enthält dieses Wort?
\item Im Gegensatz zur vorigen Aufgabe ist hier nicht jedes Wort ist
  eine Verlängerung des vorhergehenden Wortes.
An welcher Eigenschaft des Homomorphismus mag das liegen?
\end{enumerate}


\end{enumerate}

\hrule
\medskip\noindent
Kriterien zur Erlangung eines Scheines:
\begin{enumerate}
\item
In jeder Vorlesungswoche muss eine Übungsaufgabe gelöst und abgegeben werden. 
Insgesamt müssen 60\,\% der Gesamtpunktezahl der Übungen erreicht werden.
Die Übungsaufgaben können in Zweiergruppen (oder einzeln) abgegeben werden.
\item
 Von jeweils zwei aufeinanderfolgenden Übungszetteln müssen
mindestens je 30\,\% der Punkte erreicht werden. (Eine einmalige
Ausnahme wird toleriert.)

\item Aktive Teilnahme an den wöchentlichen Tutorien und einmaliges
  Vorrechnen eines Übungsbeispiels pro Person, nach vorheriger
  Einteilung in einer Liste. Da die Aufgaben gemäß Punkt 1 dazu nicht
  ausreichen, gibt es auf den Übungsbättern zusätzliche Aufgaben für
  diesen Zweck (und auch einfach zum Üben).


\item
50\,\% der Punkte bei der Zwischenklausur und 50\,\% der Punkte bei der Abschlussklausur 
(oder bei der entsprechenden Nachklausur).
\end{enumerate}
Der Schein wird benotet. Die Note ergibt sich aus den Klausuren. 
\end{document}
