Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: ___________ Herbst 66115
2016

Arbeitsplatz-Nr.:

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

— Prüfungsaufgaben —

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

Anzahl der Druckseiten dieser Vorlage: 6

Bitte wenden!
Herbst 2016 Einzelprüfungsnummer 66115 Seite 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Teilaufgabe I
Gegeben ist der deterministische endliche Automat (Q, {0,1} 5,qo, F ), wobei

Q={A4,B,C,D,E},qo = 4,F ={E} und

- Minimieren Sie den Automaten mit dem bekannten Minimierungsalgorithmus. Dokumentieren
Sie die Schritte geeignet.

Geben Sie einen regulären Ausdruck für die erkannte Sprache an.

Geben Sie die Äquivalenzklassen der Myhill-Nerode-Äquivalenz der Sprache durch reguläre
Ausdrücke an.

- Geben Sie ein Beispiel einer regulären Sprache an, für die kein deterministischer endlicher
Automat mit höchstens zwei Endzuständen existiert.

- Geben Sie ein Beispiel einer regulären Sprache an, für die kein deterministischer endlicher
Automat mit weniger als fünf Zuständen existiert.

Teilaufgabe II
Ordnen Sie die folgenden Sprachen über &={a,b} bestmöglich in die Chomsky-Hierarchie ein und
geben Sie jeweils eine kurze Begründung (1-2 Sätze).

- Li={ab"|n >21}
- IL, = {a'b"| die Turingmaschine mit Gödelnummer n hält auf leerer Eingabe}
- L;=2°\Li
- L4=="\Ly
- Ls={a'b™|n+ m ist Vielfaches von drei}
- L¢= {a"b" | Quadratzahl}
Teilaufgabe II

Sie sind an der Entwicklung eines Konfigurationssystems für Desktopumgebungen beteiligt. Eine
gültige Desktopumgebung besteht aus k Komponenten, z.B. Mailer, Editor, Browser,
Tabellenkalkulation, etc. Für jede Komponente i = 1,...k gibt es eine Menge A; von unterschiedlichen
Versionen, z. B. kmail, Outlook, thunderbird für den Mailer etc.

Leider sind manche Versionen nicht miteinander kompatibel, so harmoniert Outlook nicht mit dem
Betriebssystem Linux. Die bekannten Inkompatibilitaten sind in einer Menge P von Paaren
zusammengefasst.

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

Gefragt ist, ob es möglich ist, für jede verlangte Komponente eine Version so auszuwählen, dass keine
zwei ausgewählten Versionen inkompatibel sind. Formal sind also endliche Mengen A,ı,..., Ar und eine
endliche Menge P von Paaren gegeben.

Gefragt ist, ob eine Auswahl von Elementen yı eAı,..., Yn e Ar existiert, sodass (y;, y;) € P für alle i, j.
Wir nennen dieses Problem KPAKET.

—  Begründen Sie, dass KPAKET in NP liegt. Beschreiben Sie eine Reduktion von KNFSAT
(Erfüllbarkeit von konjunktiven Normalformen) auf KPAKET. Sie müssen dazu eine Instanz von
KNFSAT in eine äquivalente Instanz von KPAKET übersetzen. Idee: die Komponenten
entsprechen den Klauseln, die Literale einer Klausel den Versionen.

—  Geben Sie konkret die Übersetzung der KNFSAT Instanz Cı = {-4,-3B,-D},
= {-E} ‚C= {-C,4} ‚C4= {c} ‚C= {B} ‚Ce = {=G, D} ‚Cı= {G} an.

— Was können Sie aufgrund dieser Reduktion über die Komplexitätsklassen, in denen KPAKET
liegt, aussagen?

Teilaufgabe IV

Es sei A[0.. n - 1] ein Array von paarweise verschiedenen ganzen Zahlen.

Wir interessieren uns für die Zahl der Inversionen von A; das sind Paare von Indices (i, j), sodass i <j
aber A[i] > A[j]. Die Inversionen im Array [2, 3, 8, 6, 1] sind (0, 4), da A[0] > A[4] und weiter (1, 4),
(2, 3), (2, 4), (3, 4). Es gibt also 5 Inversionen.

1. Wie viel Inversionen hat das Array [3, 7, 1, 4, 5, 9, 2]?

2. Welches Array mit den Einträgen {l, ..., 2} hat die meisten Inversionen, welches hat die
wenigsten?

3. Entwerfen Sie eine Prozedur
int merge(int[]a, int i, int h, int j);

welche das Teilarray a[i.,j] sortiert und die Zahl der in ihm enthaltenen Inversionen zurückliefert,
wobei die folgenden Vorbedingungen angenommen werden:

- OQ<i<h<j <n, wobei n die Länge von a ist (n = a.length).

- ali.h] und a[h + 1..,j] sind aufsteigend sortiert.

- Die Einträge von ali..j] sind paarweise verschieden.
Ihre Prozedur soll in linearer Zeit, also O(j - i) laufen.
Orientieren Sie sich bei Ihrer Lösung an der Mischoperation des bekannten Mergesort-Verfahrens.

4. Entwerfen Sie nun ein Divide-and-Conquer-Verfahren zur Bestimmung der Zahl der Inversionen,
indem Sie angelehnt an das Mergesort-Verfahren einen Algorithmus ZI beschreiben, der ein
gegebenes Array in sortierter Form liefert und gleichzeitig dessen Inversionsanzahl berechnet.

Im Beispiel wäre also

ZI([2, 3, 8, 6, 1) = C1, 2, 3, 6, 8], 5)

Die Laufzeit Ihres Algorithmus auf einem Array der Größe n soll O(n log(n)) sein.

Sie dürfen die Hilfsprozedur merge aus dem vorherigen Aufgabenteil verwenden, auch, wenn Sie
diese nicht gelöst haben.

5. Begründen Sie, dass Ihr Algorithmus die Laufzeit O(n log(n)) hat.
6. Geben Sie die Lösungen folgender asymptotischer Rekurrenzen (in O-Notation) an:

(a) T(n)=2 * T(n/2) + Ollog n)
(b) T(n) =2 * T(n/2) + O(n’)
(c) T(n) =3 * T(n/2) + O(n)
Herbst 2016 Einzelprüfungsnummer: 66115 Seite: 4

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:
Geben Sie eine kontextfreie Grammatik für folgende Sprache über dem Alphabet {a,b} an.

Lo = {a™b” | m,n € N und m # n}

Aufgabe 2:

a) Sei LZ, die von dem folgenden deterministischen, endlichen Automaten akzeptierte Sprache.
Geben Sie einen nichtdeterministischen, endlichen Automaten an, der die Sprache Lj akzeptiert.
Cy

b) Konstruieren Sie einen deterministischen, endlichen Automaten für folgende Sprache.

= {w € {a,b}*| die Anzahl der Buchstaben a in w ist ungerade und w endet nicht auf a}

c) Sei Nt = {1,2,3,...} die Menge der positiven natürlichen Zahlen und sei g : Nt — Nt
definiert durch
g(z) = größte Zweierpotenz, die Teiler von z ist.

Geben Sie das Programm einer Turing-Maschine an, die g berechnet, wobei Ein- und Ausgabe
binär dargestellt werden. Es genügt, wenn Ihr Programm für Binärzahlen ohne führende Nullen
korrekt arbeitet.

Beispiel: Ihr Programm muss bei Eingabe der Binärdarstellung von 28 die Binärdarstellung
von 4 ausgeben, denn 4 ist die größte Zweierpotenz, die Teiler von 28 ist.

Aufgabe 3:

Sei Mo, Mı,... eine Gödelisierung aller Registermaschinen (RAMs). Beantworten Sie folgende
Fragen zur Aufzählbarkeit und Entscheidbarkeit. Beweisen Sie Ihre Antworten.

a) Ist folgende Menge entscheidbar?
A={reN|x> 100 oder M, hält bei Eingabe x}

b) Ist folgende Menge entscheidbar?
B={(z,y) €NxN | M, halt bei Eingabe x genau dann, wenn M, bei Eingabe y halt}

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

c) Ist folgende Menge aufzählbar?
C={zeN|M, hält bei Eingabe 0 mit dem Ergebnis 1}

Aufgabe 4:

a) G bezeichne die Menge der geraden natürlichen Zahlen und Kg < N das spezielle Halteproblem. Definieren Sie eine in polynomieller Zeit berechenbare Funktion r, die G auf Ko

reduziert. Beweisen Sie, dass r in polynomieller Zeit berechenbar ist und die Reduktion von
G auf K, leistet.

b) Beweisen Sie, dass die Fakultätsfunktion f(x) = x! nicht in polynomieller Zeit berechenbar
ist. (Zahlen werden hier wie üblich binär kodiert.)

Aufgabe 5:

In dieser Aufgabe sollen Sie eine Datenstruktur entwerfen, die den minimalen Abstand in einer
dynamischen Menge M von ganzen Zahlen aufrechterhält. Zu Beginn sei M leer.

Die Laufzeiten sollen für alle Operationen logarithmisch in der Größe der aktuell gespeicherten
Menge M sein.

Argumentieren Sie auch, warum Ihre Implementierung die Laufzeiten einhält.

Tipp: Erweitern Sie eine bekannte Datenstruktur.

a) Wir betrachten zunächst den einfacheren Fall einer halbdynamischen Menge, bei der Zahlen

nicht wieder entfernt werden können. Entwerfen Sie hierfür eine Datenstruktur, die folgende
Operationen bereitstellt:

- Insert(int k): Fügt die Zahl k in die Menge M, falls k nicht bereits enthalten ist. Sonst
bleibt die Operation wirkungslos.

- MinDist(): Liefert den minimalen Abstand zwischen zwei Zahlen in M, falls M mindestens
zwei Zahlen enthält, sonst wird —1 zurückgegeben.

b) Nun betrachten wir den allgemeinen Fall einer dynamischen Menge. Entwerfen Sie hierfür
eine Datenstruktur, die zusätzlich zu den Operationen Insert und MinDist (definiert wie in
Teilaufgabe a)), auch folgende Operation bereitstellt:

- Delete(int k): Löscht die Zahl k aus der Menge M, falls k in der Menge enthalten ist. Sonst
bleibt die Operation wirkungslos.

Aufgabe 6:

In dieser Aufgabe betrachten wir nur einfache Pfade (also Pfade, die jeden Knoten höchstens
einmal enthalten) und Wurzelbäume (also Bäume mit einem ausgezeichneten Knoten, der Wurzel).
Die Kanten der Wurzelbäume sind nicht gerichtet; Pfade können also „aufsteigen“ und wieder

„absteigen“.
a) Lässt sich in einem beliebigen ungerichteten Graphen der längste Pfad effizient bestimmen?

b) Betrachten wir nun einen Spezialfall. Geben Sie einen effizienten Algorithmus an, der für einen
gegebenen Wurzelbaum den längsten Pfad bestimmt, der bei der Wurzel beginnt.

c) Geben Sie einen effizienten Algorithmus an, der in einem gegebenen Wurzelbaum den längsten
Pfad insgesamt bestimmt. Verwenden Sie den Algorithmus aus Teilaufgabe b) als Unterroutine.

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

d) Geben Sie einen rekursiven Algorithmus an, der in Linearzeit in einem gegebenen Wurzelbaum
beides bestimmt: den längsten Pfad insgesamt und den längsten Pfad, der in der Wurzel
beginnt.

Aufgabe 7:
Sortieren mit Quicksort

a) Gegeben ist die Ausgabe der Methode Partition (s. Pseudocode), rekonstruieren Sie die Eingabe.

Konkret sollen Sie das Array A= ( __, —, 1, —, —) so vervollständigen, dass der Aufruf
Partition(A, 1, 5) die Zahl 3 zurückgibt und nach dem Aufruf gilt, dass A = (1,2, 3,4, 5) ist.

Geben Sie A nach jedem Durchgang der for-Schleife in Partition an.
b) Beweisen Sie die Korrektheit von Partition (z.B. mittels einer Schleifeninvarianten)!

c) Geben Sie für jede natürliche Zahl n eine Instanz I, der Länge n an, so dass QuickSort(J,)
An?) Zeit benötigt. Begründen Sie Ihre Behauptung.

d) Was müsste Partition (in Linearzeit) leisten, damit QuickSort Instanzen der Länge n in
O(nlogn) Zeit sortiert? Zeigen Sie, dass Partition mit der von Ihnen geforderten Eigenschaft
zur gewünschten Laufzeit von Quick$ort führt.

Algorithm: QuickSort(int[] A, £=1, r = A.length)
if £<rthen
m = Partition(A, £,r)
QuickSort(A, 2,m — 1)
QuickSort(A,m + 1,r)

Algorithm: Partition(A, £, r)
pivot = Alr]
i=l
for j = to r—1do
if Aj] < pivot then
Swap(A, 7, j)
i=i+l1l
Swap(A,i,r)
return 2
Algorithm: Swap(A, i, 7)
temp = Ali]
Ali] = Aly]
Alj] = temp