Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:.

Herbst
46115

Kennwort:

2017
Arbeitsplatz-Nr.:

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

— Prüfungsaufgaben —

Fach:

Informatik (Unterrichtsfach)

Einzelprüfung: Th. Informatik, Algorith./Datenstr.
Anzahl der gestellten Themen (Aufgaben): 2
Anzahl der Druckseiten dieser Vorlage:

12

Bitte wenden!

Einzelprüfungsnummer: 46115

Herbst 2017

Seite: 2

Thema Nr. 1

(Aufgabengruppe)
Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!
Aufgabe 1:
Endliche Automaten

Betrachten Sie den NEA A:

a) Konstruieren Sie mit Hilfe der Potenzmengenkonstruktion einen deterministischen endUchen
Automaten, der dieselbe Sprache wie A erkennt.

b) Geben Sie einen deterministischen endUchen Automaten an, der das Komplement der Sprache
L(A) erkeimt.
Aufgabe 2:
Berechenbarkeit

Zeigen Sie, dass die Sprayche

{(wi;w2) 1
7^ M^(£)}
nicht entscheidbar ist. Hier bezeichnet
die von Wi kodierte Turingmaschine imd M^iis) das
Ergebnis der Berechmmg von
bei Eingabe e (für i € {1,2}). Sie dürfen davon ausgehen,
dass die Maschinen hnmer entweder die Eingabe akzeptieren, ablehnen oder nicht anhalten. Wir
definieren dann

ja
falls Mu,j die Eingabe e akzeptiert
= < nein falls M«,, die Eingabe e ablehnt
loop falls
bei Eingabe e nicht anhält
Falls beide Maschinen nicht anhalten, dann ist

My,^{e)= My^{£)= loop.
Aufgabe 3:
Kontext&eie Sprachen

a) Geben Sie eine kontextfreie Grammatik für Li = L{a*{bc)*d) an. Erklären Sie Ihre Grammatik
(z.B. die Aufgaben der einzelnen Nichtterminale).
Fortsetzunsr nächste Seite!

Einzelprüfungsnnmmer: 46115

Herbst 2017

Seite: 3

b) Geben Sie eine kontextfreie Grammatik für I/2 = {a^bd^ \ n ^ m} an. Erklären Sie Ihre
Grammatik (z.B. die Aufgaben der einzelnen Nichtterminale).
c) Gegeben sei die folgende kontextfreie Grammatik G mit Startsjonbol S in ChomskyNormalform:

S-^AA\AC
A —AB I ö
B^b\c

C

SO \BB\c

Betrachten Sie außerdem das nachfolgende Tableau, das durch Anwendung des CYKAlgorithmus mit der Grammatik G imd dem Wort w = aacbab enstanden ist, aber bei dem
der Inhalt einiger Zellen gelöscht wurde. Beispielsweise bedeutet das G in Zelle 9, dass aus
der Variable G das Teilwort cb hergeleitet werden kann.

i) Geben Sie an, welche Variablen jeweils in den Zellen 12, 13, 14, 18 und 21 enthalten sein
sollten und erklären Sie auch warum.

ii) Liegt das Wort w = aacbab in der Sprache L{G)1 Begründen Sie Ihre Antwort mit Hilfe
von (i).

a

a

c

b

a

b

A

A

B,C

B

A

B

.1/

\2/

.\3/

\5/

\6>

s,c

Fortsetziiner nächste Seite!

Herbst 2017

Einzelprüfungsnummer: 46115

Seite: 4

Aufgabe 4:
Komplexität

Betrachten Sie die folgenden Probleme:
3SAT

Gegeben:
Eine aussagenlogische Formel in konjunktiver Normalform ip mit je drei Literalen pro Klausel.
Frage:

Ist ip erfüllbar?
4SAT

Gegeben:

Eine aussagenlogische Formel in konjimktiver Normalform ^p mit je vier Literalen pro Klausel.
Frage:
Ist (p erfüllbar?

a) Zeigen Sie, dass sich 3SAT in polynomieller Zeit auf 4SAT reduzieren lässt,
d.h. 3SAT <p4SAT .

b) Was können Sie aus a) folgern, wenn Sie wissen, dass 3SAT NP-vollständig ist?
c) Was können Sie aus a) folgern, wenn Sie wissen, dass 4SAT NP-vollständig ist?
Aufgabe 5:
Die Begründung zählt

Beantworten Sie die folgenden Fragen und geben Sie eine kurze Begründimg (in ein bis drei Sätzen)
an. Nur Ihre Begründung wird bewertet.

a) Gibt es reguläre Sprachen L, so dass L* eine endliche Sprache ist?

b) Gibt es unendüch viele reguläre Ausdrücke a, so dass L{a*) n L{a)= L(a)?
c) Gibt es WHILEl-Programme, die NP-vollständige Probleme lösen?

d) Falls Li und L2 kontextfreie Sprachen sind, ist Lir\L2 dann immer eine entscheidbare Sprache?
e) Wir nennen eine Sprache L LOOP-berechenbar, falls ihre charakteristische Funktion
,,

, V, falls w 4 L

-C

Yftü):= <

^ ^

falls u;€L

LOOP-berechenbar ist. Sind LOOP-berechenbare Sprachen unter Komplement abgeschlossen?

Fortsetziine nächste Seite!

Herbst 2017

Einzelprüfungsnuiiuner: 46115

Seite: 5

Aufgabe 6:

(2,4)-Bäume
a) Gegeben sei der folgende Mehrwegsudibaum T\:
20

Ö Ö

Ö Ö

Ist Ti ein (2,4)-Bamn? Begründen Sie Ihre Antwort!

b) Gegeben sei der folgende (2,4)-Bamn T:

Ö Ö

Ö Ö

O Ö
Ö
O

Fügen Sie in T nacheinander die Schlüssel 7, 18 und 16 ein, so dass nadi jedem Einfügeschritt

wieder ein (2,4)-Baum entsteht. Zeichnen Sie dabei jeweils die so entstandenen (2,4)-Bäume
T2 bis T4 nach jeder Einfügeoperation und geben Sie an, welche Operationen Sie verwendet
haben.

c) Löschen Sie nun aus T4 nacheinander die Schlüssel 15,10 und 8,so dass nach jedem Löschschritt
wieder ein (2,4)-Baum entsteht. Zeichnen Sie dabeijeweils die so entstandenen (2,4)-Bäimie Ts
bis T7 nach jeder Löschoperation und geben Sie an, welche Operationen Sie verwendet haben.

d) Wie ist die Höhe eines (2,4)-Baums definiert? Welche Höhe hat T??

e) Geben Sie an, welche Höhe ein (2,4)-Baum mit n Einträgen minimal und Tnfl.yiTnfl.1 haben kann
imd begründen Sie Ihre Antwort.

Fortsetznner nächste Seite!

Herbst 2017

Einzelprüfungsnummer: 46115

Seite: 6

Aufgabe 7:
Durchmustern von Graphen
Wir betrachten den Algorithmus zur Tiefensuche von einem Knoten v in einem ungerichteten
Graphen G:

DfsRec(G,v)
Input : Graph G =(V,E) und ein Knoten v eV
1 begin
2

3
4
5

6
7
8
9

10

setVertexLabel(u,H);
forall the e G G.incidentEdges{v) do
if getEdgeLabel{e)= U_ then
w
G.oppositeVertex{v,e)-,
if getVertexLabel{w)= U_ then
setEdgeLabel(e,D);
DfsRec(G,u;);
eise

setEdgeLabel{e,B);

Wir nehmen an, dass vor dem ersten Aufruf von DfsRec alle Knoten xmd Kanten von G mit U_
markiert wurden.

a) Geben Sie für den Graphen G in folgender Abbildung die DFS-Traversierung der Knoten an,
beginnend bei Knoten 1. Die Reihenfolge, in der die Nachbarn eines Knotens in der

Adjazenzliste gespeichert sind, entspricht ihrer aufsteigenden Nummerierung (z.B.
sind die Nachbarn des Knotens 1 in der Reihenfolge 2,4,5 gespeichert).

- Zeichnen Sie dazu einen Richtungspfeil an jede besuchte Kante um anzuzeigen, von wel
chem Knoten sie besucht wurde.

- Nummerieren Sie die Kanten in der Reihenfolge in der sie besucht wurden, und

- geben Sie für jede Kante die Markierung an (sofern sie sich von U_ unterscheidet).
Hinweise zu dieser Aufgabe:

- Achten Sie darauf, die zeitliche Abfolge Ihrer Zeichnungen zu dokumentieren!
- Die Markierung U brauchen Sie nicht anzugeben.

Fortsetziinff nächste Seite!

Herbst 2017

Einzelprüfungsnximmer: 46115

Seite: 7

b) Zeichnen Sie den Rekursionsbaum für den Aufruf DfsRec(G,1). Geben Sie für jeden Knoten
im Rekursionsbaum an

- wie der Graph G zum Zeitpunkt des AufruEs markiert ist,
- imd wie der Graph markiert ist, wenn der Aufiruf beendet ist.

Nummerieren Sie die Knoten des Rekursionsbaums gemäß der zeithchen Reihenfolge der ent
sprechenden Aufrufe.

-8

Einzelprüfungsnummer: 46115

Herbst 2017

Seite: 8

Thema Nr. 2

(Aufgabengruppe)
Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!
Aufgabe 1:
Reguläre Sprachen

a) Sei E ={a,b,c} und Li die Sprache aller Wörter über E, die mit ab beginnen, mit cb enden
imd ansonsten kein weiteres TeUwort cb enthalten.

Geben Sie einen endhchen Automaten an, der Li akzeptiert.

b) Gegeben sei der unten aufgeführte endUche Automat A2, welcher die Sprache L2 = L{A2)
akzeptiert.

Start —>

90

i) Geben Sie einen regulären Ausdruck für L2 an.
ü) Geben Sie einen deterministischen endhchen Automaten an, der die Sprache L2 akzep
tiert.

c) Zeigen Sie, dass es für jede nicht-reguläre Sprache L3 eine nicht-reguläre Sprache L3 gibt, für
die 1/3 n I/3 regulär ist.
d) Zeigen Sie mit dem Pumping-Lenuna für reguläre Sprachen, dass die Sprache

1,4 = {a^b> \i,j€NAi<j} nicht regulär ist.

Fortsetziine nächste Seite!

Einzelprüfungsnummer: 46115

Herbst 2017

Seite: 9

Aufgabe 2:
Kontextfreie Sprachen

a) Sei E — {a,6,c} und Li C S* mit Li =

\%j € N}.

i) Geben Sie eine kontextfreie Grammatik für die Sprache Li an.
ii) Geben Sie eine kontextfreie Sprache L[ an, sodass Li D L\ nicht kontextfrei ist.

b) Gegeben sei die kontextfreie Grammatik G2 = (y,S,P,5) mit Sprache L2 = L{G2), wobei
V ={A,B,C,S,T,U} imd S = {o,b,c}. P bestehe aus den folgenden Produktionen:
S

BS \UG

A —fl

T-^UB\ AG

U-^AT

B^b

C —^ c

i) Zeigen Sie 6oocc € 1/2ii) Folgende Tabelle entsteht durch Anwendimg des CYK-Algorithmus für das Wort aacb.

Übernehmen Sie die Tabelle auf Ihre Bearbeitung und vervollständigen Sie die fehlenden

^
)2,2(
Q
(3,3)
.
ß
(4,4)
A
;
(1,1)

(2,3)
0
(3,4)
.
(1.2)

(1,3)
(2,4)
.

1—t

Einträge (1,3),(2,4) und (1,4)!

a

iii) Wie entnehmen Sie der Tabelle, dass aacb ^ L2 gilt?
iv) Für ein X € V" sei Gx die Grammatik {V,H,P,X). Wie entnehmen Sie obiger Tabelle
ein X e V, so dass aadb € L{Gx) gilt?

Fortsetzune nächste Seite!

Herbst 2017

Einzelprüfungsnummer: 46115

Seite: 10

Aufgabe 3:
Dynamische Programmierung

Die Methode pKR berechnet die n-te Primzahl (n > 1) kaskadenartig rekursiv und äußerst ineffi
zient:

long pKR(int n) {
long p = 2;
if (n >= 2) {

p = pKR(n - 1); // beginne die Suche bei der vorhergehenden Primzahl
int i = 0;
do {

P++; // pruefe, ob die jeweils naechste Zahl prim ist, d.h. ...
for (1=1; i < n && p % pKR(i) != 0; i++) {
} // pruefe, ob unter den kleineren Primzahlen ein Teiler ist
} while (i != n); // ... bis nur noch 1 und p Teiler von p sind
}

return p;
}

Überführen Sie pKR mittels dynamischer Programmierung (hier also Memoization) und mit

möglichst wenigen Änderungen so in die linear rekursive Methode pLR, dass
pLR(n, new long[n + 1]) ebenfalls die n-te Primzahl ermittelt:
private long pLR(int n, long[] ps) {
ps[l] = 2;

Fortsetziine nächste Seite!

Einzelprüfungsnummer: 46115

Herbst 2017

Seite: 11

Aufgabe 4:

Streuspeicherung - Hashing

Gegeben seien die folgenden Schlüssel k zusammen mit ihren Streuwerten h{k):
k

A

B

C

D

E

F

G

h{k)

1

3

3

3

2

3

3

Fügen Sie die Schlüssel k in alphabetischer Reihenfolge mit der Streufunktion h{k)in eine Streutar

belle nach folgendem Muster ein. Verwenden Sie geschlossenes Hashing mit Beh^tergröße b=2
imd lösen Sie Kollisionen durch lineares Sondieren mit Schrittweite c=H-2 auf.
Bücket ►

0

1

2

3

4

erster

Schlüssel:

y

zweiter
Schlüssel:

Aufgabe 5:
Binäre Suche

Im Folgenden sollen Sie einen Schlüssel t in einem Feld (Array) ts mittels binärer Suche lokali
sieren. Für die Schlüssel vom Typ T gibt es zwei Vergleicher cl bzw. c2 und das Feld ts ist so
sortiert, dass:

Vi < j : ts[i] -<ci ts[j] V {ts[i] =ci ts[j] A ts[i]

tsfj])

Beispiel: Tupel T ;= (String^ Integer), cl vergleicht Strlngs, c2 vergleicht Integers
(AuL>,42)

(AuD,666)

{AuD, 666)

(PFP,41)

{PFP,6m)

{PFP,mi)

Hinweis zur API der Methode int coinpare(T ol, T o2) im Interface Comparator<T>:

Compares its two arguments for order. Retums a negative integer, zero, or a positive integer as
the first argument is less than, equal to, or greater than the second.

Ergänzen Sie die iterative Methode suche so, dass sie den Index von t in ts mit einer Lauf

zeit von 0{log{ts.length)) zurückgibt, falls t in ts vorkommt, andernfalls sei ihr Ergebnis —1:
<T> int suche(T[] ts, T t, Comparator<T> cl, Comparator<T> c2)
int a = 0, m, z = ts.length - 1; // Anfang, Mitte, Ende

{

Fortsetzune nächste Seite!

Einzelprüfungsniimmer: 46115

Herbst 2017

Seite: 12

Aufgabe 6:
Halden - Heaps

Gegeben sei folgende Feld-Einbettung (Array-Daxstellung) einer Min-Halde:
0

1

0

2

2

3

4

5

6

7

6

5

4

7

8

9

9

10

11

10 11 12

00
a) Stellen Sie die Halde graphisch als (ünks-vollständigen) Baum dar.
b) Entfernen Sie das kleinste Element (die Wurzel 0) aus der obigen initialen Halde, stellen Sie
die Haldeneigenschaft wieder her und geben Sie nur das Endergebnis in Felddarstellimg an.

c) Fügen Sie nun den Wert 1 in die obige initiale Halde ein, stellen Sie die Haldeneigenschaft
wieder her imd geben Sie nur das Endergebnis in Felddarstellung an.
Aufgabe 7:
Sortieren

a) Führen Sie „Sortieren durch Einfügen'''' lexikographisch aufsteigend und in-situ (inplace) so in einem Schreibtischlauf auf folgendem Feld (Array) aus, dass glei
che Elemente ihre
00 relative Abfolge jederzeit beibehalten (also dass z.B. "Ai" stets
vor "A2" im Feld steht). Jede Zeüe stellt den Zustand des Feldes dar, nachdem
das jeweils nächste Element in die Endposition verschoben wurde. Der bereits sor

tierte Teilbereich steht vor |||. Gleiche Elemente tragen zwecks Unterscheidung ihL

Ai

Bi

F

A2

B2

b) Ergänzen Sie die folgende Methode so, dass sie die Zeichenketten im Feld a lexikographisch
aufeteigend durch Einfügen sortiert. Sie muss zum vorangehenden Ablauf passen, d.h. sie
muss iterativ sowie in-situ (in-place) arbeiten imd die relative Reihenfolge gleicher Elemen
te jederzeit beibehalten. Sie dürfen davon ausgehen, dass kein Eintrag im Feld null ist.
void sortierenDurchEinfuegen(String[] a) {
// Hilfsvariable:

String tmp;