Grundlagen der theoretischen Informatik, SS 2005 — 0. Übungsblatt

(freiwillige Vorübungen)

1. (0 Punkte) Die Programmiersprache Schleife hat die folgenden einfachen Regeln:

• Es gibt einen unendlichen Vorrat an Variablen X0, X1, X2, X3, …, die beliebige natürliche Zahlen (≥ 0) speichern können.

• Es gibt die einfachen Anweisungen Xi = 0 (Inititalisierung), Xi = Xj (Kopieren), Xi = Xi + 1 (Hinaufzählen) und Xi = Xi - 1 (Herunterzählen). (Beim Herunterzählenwird Xi unverändert gelassen, wenn es den Wert 0 hat, weil die Variablen keine negativen Werte enthalten können.)

• Außerdem gibt es eine Schleifenanweisung:

         WIEDERHOLE Xi MAL

Anweisungsfolge

         SCHLEIFENENDE

Wenn die Variable Xi zu Beginn der Ausführung den Wert n hat, wird die Schleife n-mal wiederholt, auch wenn Xi zwischendurch geändert wird. Schleifen können auch geschachtelt sein.

Es gibt keine Ein- und Ausgabeanweisungen. Die Eingabeparameter eines Programms stehen zu Beginn in den ersten Variablen X0, X1, …. Alle übrigen Variablen sind zu Beginn auf 0 gesetzt. Das Ergebnis des Programms ist der Wert, der am Ende in X0 steht.

Das folgende Programm berechnet zum Beispiel die Summe von zwei Zahlen X0 und

X1:
       WIEDERHOLE X1 MAL
         X0 = X0 + 1
       SCHLEIFENENDE

(a) Schreiben Sie ein Programm zur Berechnung des Produktes von X0 und X1.

(b) Schreiben Sie ein Programm, dass den Rest der Division von X1 durch X0 berechnet. (Wenn X0 = 0 ist soll das Ergebnis X1 sein.)

(c) Schreiben Sie ein Programm zur Berechnung von 2^{X0}.

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

(e) Die Programmiersprache Schleife++ hat zusätzlich bedingte Anweisungen:

         IF Xi>Xj THEN

Anweisungsfolge

         ENDIF

Wie kann mein ein solches Programm durch Eliminieren aller bedingten Anweisungen in ein Schleife-Programm übersetzen?

2. (0 Punkte) Für ein Alphabet Σ mit k Elementen ist Σ^{∗} ist die Menge der Wörter (Folgen), die man aus den Buchstaben von Σ bilden kann.

(a) Wieviele Wörter in Σ^{∗} haben die Länge n (bestehen aus n Buchstaben)?

(b) Wieviele Palindrome in Σ^{∗} haben die Länge n? (Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen gleich ist.)

3. (0 Punkte) Durch wiederholte Anwendung des Homomorphismus

0 → 01, 1 → 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, …

(a) 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.)

(b) Welche Länge hat das Wort w_{n}?

(c) Jedes Wort ist ein Anfangsstück (Präfix) des darauffolgenden Wortes, sodass die Folge gegen ein unendliches Wort w_{∞} “konvergiert”. Wieviele verschiedene Teilwörter (zusammenhängende Teilfolgen) der Längen n = 1, 2, 3, 4, 5 enthält w_{∞}?

(d) (*) Gegen welchen Wert konvergiert der Anteil der Einsen in w_{n} an der Gesamtzahl der Symbole?

4. (0 Punkte) Durch wiederholte Anwendung des Homomorphismus

0 → 100, 1 → 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, …

(a) Welche Länge hat das n-te Wort?

(b) Gegen welchen Wert konvergiert der Anteil der Einsen?

(c) 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?

(d) 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?

Kriterien zur Erlangung eines Scheines:

1. 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.

2. Von jeweils zwei aufeinanderfolgenden Übungszetteln müssen mindestens je 30 % der Punkte erreicht werden. (Eine einmalige Ausnahme wird toleriert.)

3. 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).

4. 50 % der Punkte bei der Zwischenklausur und 50 % der Punkte bei der Abschlussklausur (oder bei der entsprechenden Nachklausur).

Der Schein wird benotet. Die Note ergibt sich aus den Klausuren.