Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort: 461 13
2006

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen

- Prüfungsaufgaben -
Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Theoretische Informatik

Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 3

Thema Nr. 1

1. Betrachten Sie über dem Alphabet ‘= {a,b} die Sprachen
= {w € SS *;w_ enthilt das Teilwort aa mindestens einmal }
M= {w € > ";w enthält eine gerade Anzahl von a’s }
a) Geben Sie für jede der Sprachen Z und M einen vollständigen deterministischen
endlichen Automaten an, der diese Sprache akzeptiert.
b) Geben Sie für die Sprachen Z und M, sowie für deren Komplemente L= yi. *\Lund
M= > "\M ‚jeweils einen regulären Ausdruck an, der diese Sprache beschreibt.
c) Konstruieren Sie einen vollständigen deterministischen endlichen Automaten, der

die Sprache LMM akzeptiert.
Hinweis: Verwenden Sie die Automaten aus Teilaufgabe a).

Fortsetzung nächste Seite!
Frühjahr 2006 Einzelprüfungsnummer: 46113 Seite: 2

2. Unter der (binären) Länge /(n) einer positiven natürlichen Zahl versteht man die Anzahl
der Ziffern in der Binärdarstellung von r, wobei führende Nullen weggelassen werden,
also beispielsweise / (23) = 5, da 10111 die Binärdarstellung der Dezimalzahl 23 ist. Per
Konvention setzt man / (0) =1.

a) Konstruieren Sie ein LOOP-Programm zur Berechnung der Längenfunktionn > /(n).

b) Geben Sie eine primitiv-rekursive Definition der Längenfunktion n—/(n) an.

3. Ein Übungsleiter zur Algorithmik-Vorlesung möchte sich die Korrekturarbeiten zu den Programmieraufgaben erleichtern. Er gibt an, dass er ein Programm TESTER geschrieben habe,
welches Folgendes leistet: Zu jeder Aufgabe vergleicht TESTER den. Programmtext studentischer Lösungen mit einer Musterlösung des Übungsleiters und stellt fest, ob in beiden Fällen
dieselbe Funktion berechnet wird.

Kommentieren Sie diese Behauptung!

4. Betrachten Sie die beiden folgenden Entscheidungsprobleme:

- TEILMENGENSUMME
- Instanzen sind Paare ((4 ser, a) bestehend aus Vektoren positiver natürlicher Zahlen

(@,...,a,)e N! und Zahlen k € N, wobei n21.
- Gefragt ist, ob es eine Teilmenge / <{1,2,...,n} gibt mit > ek

- PARTITIONIERUNG
- Instanzen sind Vektoren positiver natürlicher Zahlen (a,,...,a,)e N’ mit n21.

- Gefragt ist, ob es eine Teilmenge / <{1,2,...,n} gibt mit > ely = > sary

a) Zeigen Sie, dass die Abbildung

(nda) (read ker Doa kt}

i=l

eine polynomielle Reduktion von TEILMENGENSUMME auf PARTITIONIERUNG ist.

b) Was folgt daraus für die Zeitkomplexität von PARTITIONIERUNG?
Frühjahr 2006 Einzelprüfungsnummer: 46113 Seite: 3

Thema Nr. 2

l. Geben Sie einen vollständigen deterministischen endlichen Automaten an, der die Zeichenketten
liber {a,b,c} mit einer geraden Anzahl von a’s als Sprache hat.

2. Zeigen Sie, dass der Schnitt kontextfreier Sprachen nicht kontextfrei zu sein braucht.
3. Zeigen Sie, dass f:NxN— WN: mit

x- fallsx> y
oy)={

sonst
primitiv rekursiv ist.

4. Leiten Sie die Zeitkomplexität von Mergesort her.
(Mergesort(Feld)

Ist |Feld| > 1, so
{mergesort (Erste Hälfte des Feldes);
mergesort (Zweite Hälfte des Feldes);
verschmelze die beiden Hälften

}
gebe das Feld zurück)