Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: Herbst 661 13

Arbeitsplatz-Nr.: 2 0 1 2

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

— Prüfungsaufgaben —
Fach: Informatik (vertieft studiert)
Einzelprüfung: Theoret. Informatik, Algorithmen

Anzahl der gestellten Themen (Aufgaben): 2
Anzahl der Druckseiten dieser Vorlage: 7

Bitte wenden!
Herbst 2012 Einzelprüfungsnummer 66115 Seite 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Wir fixieren das Alphabet © = {a,b} und definieren Z < D* durch

L = {w |in w kommt das Teilwort bab vor}

Z.B. ist babaabb € L, aber baabaabb ¢ L. Der folgende nichtdeterministische Automat A erkennt

T. .
Le

NA.

a,b ri

a) Wenden Sie die . Potenzmengenkonstruktion auf A an und geben Sie den resultierenden deterministischen Automaten an. Nicht erreichbare Zustände sollen nicht dargestellt werden.

b) Konstruieren Sie aus dem so erhaltenen deterministischen Automaten den Minimalautomaten
für L. Beschreiben Sie dabei die Arbeitsschritte des verwendeten Algorithmus in nachvollziehbarer Weise.

c) Geben Sie die Aquivalenzklassen der Myhill-Nerode Aquivalenz von L durch Repräsentanten
an. (Diese Aquivalenz ist definiert durch ge ~~, y <=> Vu.cue LS yu L.) -

Tipp: Die Vereinigung aller Klassen muss {a,b}* ergeben und ihre Anzahl entspricht der
Zustandszahl des Minimalautomaten.

Aufgabe 2:

Wir fixieren wieder das Alphabet © = {a,b} und betrachten die Sprache
L = {(abo)"a(baa)” |n > 1}.

a) Obwohl es auf den ersten Blick nicht so aussieht, ist diese Sprache regulär. Begründen Sie das
durch Angabe eines regulären Ausdrucks für L.

b) Professor Plem versucht fälschlicherweise mithilfe des Pumpinglemmas nachzuweisen, dass L
nicht regulär sei. Er schreibt:

Nehmen wir widerspruchshalber an, L sei regulär. Dann gäbe es eine Pumpingzahl n. Wir
betrachten w = (aba)"a(baa)*. Sei jetzt w = xyz eine Zerlegung derart, dass |xy| < n und.
ly| > 1. Laut Pumpinglemma wäre nun aber xz auch in L. Das ist ein Widerspruch, da ry
nach Annahme vollständig im (aba)”-Block von w liegt und somit zz nicht in L sein kann.

Begründen Sie detailliert, an welcher Stelle Professor Plem irrt und geben Sie eine Pumpingzahl
n für L an. Legen Sie konkret dar, wie jedes Wort w € L mit |w| > n so zerlegt werden kann,
wie es vom Pumpinglemma garantiert wird.

Fortsetzung nächste Seite!
Herbst 2012 Einzelprüfungsnummer: 66115 Seite: 3

Aufgabe 3:

Das 0-1-Integer Linear Programming Problem (0-1ILP) ist wie folgt definiert:

a) GEGEBEN: Eine Liste V von Variablen z1,...,&m und eine Liste U von Ungleichungen tı > 0,...,t„ > 0, wobei die t, lineare Terme mit den Variablen
%1,...,%n Sind. Eine konkrete Instanz wäre zum Beispiel V : x, Y,z und
U: aty+z—-1>0, 2+(1-9)-220.

b) GESUCHT: Eine Belegung der Variablen mit Werten aus {0, 1} (jede Variable ist entweder 0
oder 1), sodass alle Ungleichungen erfüllt sind.

Weisen Sie nach, dass 0-1-ILP NP-vollständig ist. Für die eine Richtung bietet sich eine Reduktion
von 3SAT an.

. Aufgabe 4:
Gegeben ist ein Array a von ganzen Zahlen der Länge n, z.B.:

7;0 123 45 6 789

a5 -6 42 -5 7-2 -7 35

Im Beispiel ist also rn = 10. Es soll die maximale Teilsumme berechnet werden, also der W..5 des

Ausdrucks
Ok
LIS max =

Im Beispiel ist dieser Wert 8 und wird für ö= 8,5 = 10 erreicht. Entwerfen Sie ein Divide-AndConquer Verfahren, welches diese Aufgabenstellung in Zeit Öfn logn) löst. Skizzieren Sie Ihre
Lösung hinreichend detailliert.

Tipp: Sie sollten ein geringfügig allgemeineres Problem lösen, welches neben der maximalen Teilsumme auch noch die beiden “maximalen Randsummen” berechnet. Die werden dann bei der
Endausgabe verworfen.
Herbst 2012 Einzelprüfungsnummer 66115 Seite 4

Thema Nr. 2
(Aufgabengruppe)

Es sind alle. Aufgaben dieser Aufgabengruppe zu bearbeiten!

4

Aufgabe 1: endliche Automaten
Konstruieren Sie cinen deterministischen endlichen Automaten (DFA) A

(durch Angabe von A oder eines Diagramms für A)
für die folgende Sprache L:

L besteht aus der Menge aller Binärzahlen ohne führende Nullen
bei denen die Anzahl der Einsen ungerade und die Anzahl der Nullen gerade ist.

Aufgabe 2: reguläre Sprachen

Zeigen oder widerlegen Sie, dass die folgende Sprache L regulär ist.

Zeigen: durch Angabe eines endlichen Automaten oder eines regulären Ausdrucks
Widerlegen: mit dem Pumping Lemma

L = {wc wiev |w e {a,b} *, wi®V ist die Spiegelung von w}
L ist die Menge der Palindrome mit der Markierung c.

Aufgabe 3: Minimierung DFA
Minimieren Sie den folgenden deterministischen Automaten mit den Zuständen {0,1,2,3,4,5}
und den Endzuständen {1,2,4,5}. 0 ist der Startzustand.

Fortsetzung nächste Seite!
Herbst 2012 Einzelprüfungsnummer 66115 Seite 5

1

Aufgabe 4: Berechenbarkeit und Komplexität
Gegeben sei die Sprache L= {we w|w e {a,b}*} (Duplikate von Worten)

a) Geben Sie eine Turingmaschine M mit L(M) = L an.
Beschreiben Sie in Worten, wie Ihre Turingmaschine arbeitet.

b) Welche Zeit- und welche Speicherkomplexität in O-Notation hat Ihre Turingmaschine?
Erläutern Sie dies anhand Ihrerin a) gegebenen Beschreibung

c) Skizzieren Sie, warum L eine O(log n) speicher-beschränkte Sprache ist.

Aufgabe 5: Komplexität
Die Kinder in einem Kindergarten sollen einen Kreis bilden, bei dem sich nebeneinander
stehende Kinder die Hand reichen. Es gibt aber Kinder, die sich nicht mögen und sich nicht die
Hand reichen wollen. Diese dürfen im Kreis nicht nebeneinander stehen. Nur dann ist der Kreis
zulässig.

Formal:
Gegeben sei eine Menge von n Kindern K = [kı....,kn} und eine symmetrische binäre Relation E

bestehend aus allen Paaren {k, k'} mit der Eigenschaft dass sich k und k' nicht mögen.
Problem:
Kann man einen zulässigen Kreis bilden?

Begründen Sie warum dieses Problem NP-vollständig ist.

Hinweis:

Das Hamilton Problem ist NP-vollstandig. Dies können Sie bei Ihrer Begründung verwenden.
Das Hamilton (genauer Hamilton Kreis) Problem in einem ungerichteten Graph G= (V;E) ist die
Frage, ob es einen Weg w (Rundreise) genau einmal durch jeden Knoten gibt, so dass Anfangsund Endknoten zusammenfallen, siehe auch Informatik Duden unter den Stichworten NP und
Königsberger Brückenproblem

Aufgabe 6: O-Notation
Gegeben seien die Funktionen EN — N und g!N > N, wobei f{n)=(n-1)? und g(n)=(2n+3)(3n+2).
Geben Sie an, welche der folgenden Aussagen gelten. Beweisen Sie Ihre Angaben.

a) f({n)eO(g(n))

b) g(eO(fin))

Fortsetzung nächste Seite!
Herbst 2012 Einzelprüfungsnummer 66115 Seite 6

Aufgabe 7: Heap und binärer Suchbaum

a) Fügen Sie nacheinander die Zahlen 3,5,1,2,4
(i) in einen leeren binären Suchbaum ein
(ii)  ineinen leeren Heap ein
Geben Sie die Ergebnisse an (Zeichnung)

b) Geben Sie zwei Merkmale an, bei denen sich Heaps und binäre Suchbäume wesentlich
unterscheiden. Ein wesentlicher Unterschied zwischen Bubblesort und Mergesort ist z.B.
die worst case Laufzeit mit O(n?) für Bubblesort und O(n log n) für Mergesort.

Aufgabe 8: AVL-Bäume
Gegeben sei der folgende AVL-Baum T. Führen Sie auf T folgende Operationen durch.

(a) Fügen Sie den Wert 1 in T ein. Balaneieren Sie falls nötig und geben Sie den entstandenen
Baum (als Zeichnung) an.

Fügen Sie nun den Wert 28 in T ein. Balancieren Sie falls nötig und geben Sie den
entstandenen Baum (als Zeichnung) an.

(b) Löschen Sie aus T den Wert 15. Balancieren Sie falls nötig und geben Sie den
entstandenen Baum (als Zeichnung) an.

Fortsetzung nächste Seite!
Herbst 2012 Einzelprüfungsnummer 66115 Seite 7

Aufgabe 9: Dijkstra

Gegeben sei der unten stehende gerichtete Graph G=(V, E) mit positiven Kantenlängen I(e) für
jede Kante eeE.

In welcher Reihenfolge werden die Knoten von G durch den Dijkstra-Algorithmus bei der
Berechnung der kürzesten Wege von Knoten s ausgehend endgültig bearbeitet? _