Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
Frühjahr
Kennwort; — 46 1 1 5
2019 |

Arbeitsplatz-Nr.:

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

— Prüfungsaufgaben —

Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Theoretische Informatik /Algorithmen/Datenstrukturen
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 8

Bitte wenden!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!
Aufgabe 1
Antworten Sie mit „Stimmt“ oder „Stimmt nicht“. Begründen Sie Ihr Urteil.
(a) Sei % = {a,b}. Wenn L, < %* regulär ist, dann ist auch das Komplement %* \ Lı regulär.
(b) Für reguläre Ausdrücke a, ß gilt L((@ + ß)*) = L(a* + B*).

(c) Kontextfreie Sprachen sind unter der Kleene-Stern-Operation abgeschlossen, d. h. für kontextfreies L C %* ist auch L* kontextfrei.

(d) Wenn es einen deterministischen Algorithmus gibt, der in polynomieller Zeit entscheidet, ob
eine vorgelegte aussagenlogische Formel eine erfüllende Belegung hat, dann it P=NP.

(e) N P-vollständige Probleme sind unentscheidbar.

(f) Die Menge der (Kodierungen von) Turingmaschinen, die bei leerer Eingabe nach maximal
1000 Schritten halten, ist entscheidbar.

Fortsetzung nächste Seite!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 3

Aufgabe 2

(a) Konstruieren Sie einen endlichen Automaten, dessen Sprache die Schnittmenge der Sprachen
der folgenden zwei deterministischen endlichen Automaten ist.

a a, b

b
start (a — RD a
b

(b) Sei L = {a*b’c” |i,j € N}. Stellen Sie sich vor, dass ein Schüler/eine Schülerin $ behauptet,
einen deterministischen endlichen Automaten A konstruiert zu haben, der genau die Sprache
L akzeptiert. Sie argumentieren mit dem Pumping-Lemma, dass L nicht regulär ist und
deshalb die Sprache von A nicht L sein kann. 5 hält Ihre Argumentation für zu abstrakt
und ist immer noch von der Korrektheit von A überzeugt.

Sie können S$ überzeugen, wenn Sie ein Wort w angeben, das Element von L ist, aber nicht
von A akzeptiert wird oder von A akzeptiert wird und nicht Element von L ist.

Beschreiben Sie ein Verfahren, wie Sie in Abhängigkeit von A ein solches Wort w finden.

Aufgabe 3
Gegeben sei die kontextfreie Grammatik G = (V,D, P, S) mit Sprache L(G), wobei V={$} und
x = {a,b}. P bestehe aus den folgenden Produktionen:

S—+SS|aSb|e

(a) Geben Sie alle neun Wörter w € L(G) mit Länge |w| < 6 an.

(b) Bringen Sie G in Chomsky-Normalform und erklären Sie Ihre Vorgehensweise.

Fortsetzung nächste Seite!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 4

Aufgabe 4

Gegeben sei die Turingmaschine M = (Q, 9, F,%,T,D, 6) mit Zustandsmenge Q = {qo, 91, q2, GF};
wobei go der Startzustand ist. Die Turingmaschine hält, wenn sie den Zustand g; annimmt (F =
{q;}). Das Eingabealphabet ist D = {a,b}, das Bandalphabet ist I’ = ZU {U} mit Blank-Zeichen
U für leeres Feld. Die Übergangsfunktion 6:QxT— QxXTx{L,N,R}, wobei der Schreib-LeseKopf mit Z nach links, mit N nicht und mit R nach rechts bewegt wird, ist durch folgende Tabelle
gegeben (bspw. ist ö(go,a) = (q,5,L)):

a b U

do (q1,b, L) (qo, b, R) (qm, 0, L)
71 (m1, a, L) (q1,b, L) (2,0, R)

q2 (qo, a, L) (qa, b, R) (4,0, N)

(a) Beschreiben Sie möglichst exakt, welche Schritte (Zustände, Schreibvorgänge, Bewegung des
SL-Kopfes) die Turingmaschine bei der Abarbeitung des Wortes bab ausführt.

(b) Beschreiben Sie möglichst exakt, welche Schritte (Zustände, Schreibvorgänge, Bewegung des
SL-Kopfes) die Turingmaschine bei der Abarbeitung des Wortes baba ausführt.

(c) Charakterisieren Sie, bei welchen Eingaben die Turingmaschine hält und bei welchen nicht.
Begründen Sie, ob Sie damit das Halteproblem gelöst haben.

Fortsetzung nächste Seite!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 5
Aufgabe 5 (Algorithmen und Datenstrukturen)

Gegeben sind eine endliche Menge von Wörtern T = {50,..., $m—1} und ein Zielwort w der Länge
n. Gefragt ist, ob das Zielwort w als Konkatenation von Wörtern aus T' zusammengesetzt werden
kann, wobei die Wörter in T beliebig oft verwendet werden dürfen.

Beispiel:

w = apfelmuffinsundschokomuffins
T = {f,lmu,e, ap, fin, ins, sund, kom, u,n,
su, dscho, unds, nd, uff, hok, felm}

w = ap felm uff ins u n dscho kom uff ins

Mit w(i, 7) bezeichnen wir das Segment vom i-ten (Start bei 0) bis zum (einschl) j-ten Buchstaben
von w. Im Beispiel: w(3, 10) = elmuffin

Der folgende Algorithmus lést das Problem in exponentieller Zeit.

write(i,j): /* kann w(i,j) dargestellt werden? x*/
if (i > j) return true;
for (k=0..m-1)
if (w(i,j) == s_k) return true;
for (1=i..)j-1)
if (write (i,1l) && write (1+1,j)) return true;
return false;

main:
write (0,n-1);

(a) Entwerfen Sie mithilfe von dynamischer Programmierung einen Algorithmus, der das Problem in polynomieller Zeit löst.

(b) Geben Sie die Laufzeit Ihres Algorithmus in O-Notation an, wobei Sie zur Vereinfachung
annehmen dürfen, dass m, die Zahl der Muster, konstant ist.

(c) Nennen Sie zwei weitere Beispiele für die Anwendungen dynamischer Programmierung.
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 6

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1 (Turniergraph)

Ein Turniergraph ist ein gerichteter Graph auf n Knoten, in dem zwischen je zwei verschiedenen
Knoten u, v genau eine Kante existiert - entweder (w,v) oder (v, uw), aber niemals beide oder keine,
siehe Abbildung 1.

(a) Turniergraph (b) Kein Turniergraph (c) Kein Turniergraph

Abbildung 1: Beispiele zur Veranschaulichung der Definition des Turniergraphs

(a) Zeigen Sie, dass in jedem Turniergraph mindestens ein Knoten existiert, von dem mindestens (n — 1)/2 Kanten ausgehen.

(b) Eine Knotenmenge 5 dominiert, falls für jeden Knoten x ¢ S ein Knoten s € $ existiert, so
dass (s,x) eine Kante des Graphen ist.

Geben Sie einen Algorithmus an, der in jedem Turniergraphen eine dominierende Knotenmenge der Größe O(logn) findet. Argumentieren Sie, dass Ihr Algorithmus korrekt ist. Sie
dürfen hierzu die Aussage von Teilaufgabe (a) nutzen.

(c) Angenommen, es ist bekannt, dass die kleinste dominierende Knotenmenge O(logn) Knoten
enthält. Geben Sie einen Algorithmus an, der diese Knotenmenge in n° Schritten berechnet,
wobei se O(logn) gilt.

Aufgabe 2 (Tiefensuche)

(a) Führen Sie auf dem angegebenen Graphen eine Tiefensuche, ausgehend vom Knoten A,
aus. Dokumentieren Sie tabellarisch, in welcher Reihenfolge die Kanten betrachtet werden
und ob die jeweils betrachtete Kante dem Tiefensuchbaum hinzugefügt wird. Falls mehrere
Knoten zur Auswahl stehen, wählen Sie stets den Knoten mit der lexikographisch niedrigeren
Bezeichnung.

Zeichnen Sie den resultierenden Baum.

Fortsetzung nächste Seite!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 7

O
880

(b) Gegeben sei nun ein gerichteter Graph G = (V, E), dessen Knoten mit natürlichen Zahlen
beschriftet sind. Für jeden Knoten v soll der Knoten mit geringster Beschriftung bestimmt
werden, der von v aus erreichbar ist. Geben Sie einen Algorithmus mit Laufzeit O(|V|(|V|+
|E|)) an, der dieses Problem löst.

(c) Für das Problem aus Teil (b) existiert auch ein Algorithmus mit Laufzeit O(|V| + |E]).
Geben Sie den verbesserten Algorithmus an. Argumentieren Sie, dass Ihr Algorithmus die
geforderte Laufzeit erreicht.

Aufgabe 3 (AVL-Bäume)

(a) Zeigen oder widerlegen Sie die folgende Aussage: Wird ein Element in einen AVL-Baum
eingefügt und unmittelbar danach wieder gelöscht, so befindet sich der AVL-Baum wieder
in seinem Ursprungszustand.

(b) Fügen Sie in den gegebenen Baum den Schlüssel 11 ein.

Rebalancieren Sie anschließend den Baum so, dass die AVL-Eigenschaft wieder erreicht wird.
Zeichnen Sie den Baum nach jeder Einfach- und Doppelrotation und benennen Sie die Art
der Rotation (Links-, Rechts-, Links-Rechts-, oder Rechts-Links-Rotation). Argumentieren
Sie jeweils über die Höhenbalancen der Teilbäume.

Tipp: Zeichnen Sie nach jedem Schritt die Höhenbalancen in den Baum ein.

Fortsetzung nächste Seite!
Frühjahr 2019 Einzelprüfungsnummer: 46115 Seite: 8
Aufgabe 4 (Formale Sprachen und Komplexität)

Das Shuffle-Produkt L; x La zweier Sprachen L;, La ist bekanntlich definiert durch
Lı x La = {uyvyugd2...UnUn | Ui2..-Un € Ly und vyv2...Un € La}

wobei Uj,...,Un, U1,---;Un Wé6rter sind (méglicherweise leer). Die Sprache L, x Lz enthalt also
alle Worter, die man durch Verzahnen eines Wortes in L, mit einem Wort in L» erhalten kann.

Beispiel:
{aab, abab} x {aa} = {aaaab, aaaba, aabaa, aaabab, aabaab, aababa, abaaab, abaaba, ababaa}
Shuffle-Produkte spielen bei der Verifikation nebenläufiger Programme eine wichtige Rolle.

(a) Es sei L = {a”b"|m,n > 0}, also die Sprache des regulären Ausdrucks a*b*. Zeigen Sie, dass
gilt LxL = {a,b}*.

(b) Das Shuffle-Produkt regulärer Sprachen ist wiederum regulär. Begründen Sie dies durch
eine geeignete Automatenkonstruktion. Mit anderen Worten: Beschreiben Sie, wie man aus
zwei endlichen Automaten Aı = (D,Q,6,qr, F') und Aa = (%,Q’, 6’, q7, F') über demselben
Alphabet einen Automaten für L(Aı)* L(Aa) konstruiert.

(c) Begründen Sie, ob die folgende Aussage wahr ist:
“Jedes NP-vollständige Problem ist entscheidbar.”