Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: Frühjahr

m 66115
Arbeitsplatz-Nr.: 2013

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

nzahl der Druckseiten dieser Vorlage: 9

Bitte wenden!
Frühjahr 2013 - Einzelprüfungsnummer 66115 Seite 2

Thema Nr. 1

Aufgabe 1 Endliche Automaten und reguläre Sprachen

Gegeben sei folgender nicht-deterministischer endlicher Automat M:

M = (4402912 90993294 $5, {0,1}, {40}. {44 ))

mit dem Eingabealphabet & = {0,1}, dem Startzustand g,, dem Endzustand q, und der
Übergangsfunktion 6 definiert durch

5 (qo,0) = {qo. qi}.
ö (q0,1) = {qo},
5 (q,1) = {a},
ö (92,1) = {3},
5 (93,0) = {ga};
ö (q3,1) = {qo},

5 (94,0) = 8 (94, =iga}

a) Geben Sie einen regulären Ausdruck für die von M akzeptierte Sprache L(M) an.
b) Geben Sie eine reguläre, &-freie Grammatik G an, die die Sprache Z(M) erzeugt.

c) Wandeln Sie den nicht-deterministischen endlichen Automaten M durch
Teilmengenkonstruktion in einen deterministischen endlichen Automaten N um und
minimieren Sie den Automaten N bzw. weisen Sie nach, dass der Automat N bereits
minimal ist.

Fortsetzung nächste Seite!
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 3

Aufgabe 2 Kontextfreie Grammatiken

Gegeben sei die Grammatik G = (V,%,P,S) mit V= {S, A, B, C}, & = {a,b}, dem Startsymbol S
und

P = {S—AB,S CS ABC ABB, A >a B>AG Bob, C>AAC > BA}.
L = L(G) ist die von G erzeugte Sprache.

a) Zeigen Sie, dass G mehrdeutig ist.

b) Entscheiden Sie mithilfe des Algorithmus von Cocke, Younger und Kasami (CYK), ob das
Wort w= babaaa zur Sprache L gehört. Begründen Sie Ihre Entscheidung.

e) Geben Sie eine Ableitung für w= babaaa an.

Aufgabe 3 Turing-Maschinen

Konstruieren Sie eine deterministische Turing-Maschine M, die die Sprache
L=L(y)mity=(01110)*

entscheidet.
Geben Sie die Übergangsfunktion als Tabelle an und erläutern Sie die Bedeutung der Zustände in
der von Ihnen konstruierten Maschine.

Aufgabe 4 Algorithmen

Die Potenz y einer Zahl x für zwei Zahlenx undy (yeN, xeZ) kann als fortgesetzte
Multiplikation realisiert werden:

y_ __¢ xx" fallsy > 0
x =exp(x, y)={ 1 falls y =0

a) Schreiben Sie eine rekursive Implementierung für diese Funktion in einer
Programmiersprache Ihrer Wahl.

b) Implementieren Sie diese Funktion nun in der Programmiersprache Ihrer Wahl in iterativer
Form.

c) Geben Sie für beide Algorithmen jeweils die Speicher- und Laufzeitkomplexität an.

Fortsetzung nächste Seite!
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 4

Aufgabe 5 Doppelt verkettete Listen und Sortieralgorithmen

a) Implementieren Sie in einer objektorientierten Programmiersprache Ihrer Wahl eine
doppelt verkettete Liste für ganze Zahlen. Jedes Listenelement soll die Methoden get ()
und set () der Attribute value, predecessor und successor enthalten.

b) Implementieren Sie die Methoden head () undtail(), die das erste und letzte Element
der Liste ausgeben.

c) Implementieren Sie eine Methode sort (), die die Liste nach den Werten von value
aufsteigend sortiert.

d) Welche Komplexität hat Ihr Sortieralgorithmus beim Sortieren der doppelt verketteten Liste
aus c jeweils im besten und schlechtesten Fall?

Aufgabe 6 Streutabellen (Hash-Tables)

Um die URL (zum Beispiel google.de) und die zugehörige IP des Servers (hier 173.194.69.9)
zu verwalten, werden Streutabellen verwendet, die eine bestimmte Zone von Adressen
abbilden. Die Streutabellen werden als zwei dynamische Arrays (in Java: ArrayLists) realisiert.
Kollisionen innerhalb einer Zone werden ebenfalls in dynamischen Arrays verwaltet.

google.de Index 0 Streuwert 0 Streuwert 0 173.194.69.9 Index 0
hayern.de Index 0 Streuwert 1 N Streuwert 7 195.200 7 A Index 0
u
Bunensuersen & beeen tees
facebook.com | Index 0 . 69.171.229.1 index 0
Streuwert 45 Streuwert 45 -
omx.nei Index 1 213.165.64.7 Index 1

Um zu einer URL die IP zu finden, berechnet man zunächst mittels der Funktion hash() den
entsprechenden Streuwert, entnimmt dann den Index der Tabelle URL und sucht schließlich an
entsprechender Stelle in der Tabelle IP die IP-Adresse.

Fortsetzung nächste Seite!
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 5

a) Erläutern Sie am vorgestellten Beispiel, wie ein Hash-Verfahren zum Speichern großer

Datenmengen prinzipiell funktioniert und welche Voraussetzungen und Bedingungen daran
geknüpft sind.

b) Nun implementieren Sie Teile dieser IP- und URL-Verwaltung in einer objektorientierten
Sprache Ihrer Wahl. Verwenden Sie dabei die folgende Klasse (die Vorgaben sind in der
Sprache Java gehalten):

class Zone {
private ArrayList<ArrayList<String>> urlList =
new ArrayList<ArrayList<String>>();
private ArrayList<ArrayList<String>> ipList =
new ArrayList<ArrayList<String>>();
public int hash(String url) {/* calculates hash-value h, >=0 */}

i) Prüfen Sie in einer Methode boolean exists(int h) der Klasse zone, ob bereits
mindestens ein Eintrag für einen gegebenen Streuwert vorhanden ist. Falls n größer ist
als die derzeitige Größe der Streutabelle, existiert der Eintrag nicht.

ii) Die Methode int getIndex (string url, ArrayList<String> urlList) soll den
Index einer URL in der Kollisionsliste berechnen. Ist die URL in der Kollisionsliste
nicht vorhanden, soll -1 zurückgeliefert werden.

iii) Ergänzen Sie die Klasse Zone um eine Methode string lookup (String url), die in
der Streutabelle die IP-Adresse zur url zurückgibt. Wird eine nicht vorhandene
Adresse abgerufen, wird eine Fehlermeldung zurückgegeben.
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 6

Thema Nr. 2

1. Es bezeiche G = (V,T, P, A) die kontextfreie Grammatik mit dem Variablenalphabet YV =
{A,B}, dem Terminalalphabet T = {a,b}, dem Startsymbol A und der Menge P von
Produktionen:

P={A-aBa|bBa, B—aBa|bBa|A}

wobei X für das leere Wort steht.

(a) Welches ist die von .G generierte Sprache L(G)? Geben Sie eine Beschreibung von
L(G), die nicht anf die Grammatik G Bezug nimmt. Beweisen Sie Ihre Behauptung!

(b) Zeigen Sie dass die Sprache L(G) nicht regular ist.

(c) Transformieren Sie die Grammatik G in eine äquivalente Grammatik G’ in ChomskyNormalform und geben Sie in G’ eine Linksableitung für das Wort ab?a? an.

2. Es sei 5 = {0,1}. Das Alphabet X2q bestehe aus allen Paaren von Elementen aus D,
geschrieben als Spaltenvektoren der Länge 2 über 2, also

= {8)0).£)-6)

Ein Wort w = wywe...Wn © LF mit w;= 5. 1<i<sn, kann aufgefasst werden als ein
T

Paar (x,y) € 5” x D” mit x = a102...0n, y= yiye---Yn, dh.
fol [ay] Tae ia

w= l= (el eld

Jedes Wort a = 4102...Qn-10n € &” stellt die natürliche Zahl
ex bin(a) = a, 27-1 4 aq- 27-7 +e + 1:24 m

dar (binäre Zahldarstellung).

(&) Die Sprache der “Multiplikation mit 3” ist
M3 = f w= [| € D5; bin(y) =3 -vin(e)}
eo LW
Es gilt also beispielsweise
0011 oj fol fay [a o11] — fol fa] fa
[ios] = [fl fo El eo] = LI [al ¢**
Zeigen Sie, dass die Sprache M3 regular ist.
Hinweis: Sie können - falls Ihnen das hilfreich erscheint — hier die Tatsache verwenden,

dass eine Sprache L genau dann regulär ist, wenn die gespiegelte Sprache L® =
{w® ; w € L} regular ist. Dabei ist (wıw2...Wn-ıUn)* = Unln-ı.- -Waun.

(b) Zeigen Sie, dass die Sprache

[-Flen-r)

nicht regulär ist.

Fortsetzung nächste Seite!
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 7

3. Es sei X = {z1,20,...,2n} eine Variablenmenge und es bezeichne AL(X) die Menge der
aussagenlogischen Formeln über X mit Konnektiven für die Konjunktion (A), die Disjunktion (V) und die Negation (3). Es bezeichne Sat(X) die Menge der erftillbaren Formeln
und Taut(X) die Menge der Tautologien aus AL(X). Eine aussagenlogische Formel heisse
2-erfüllbar, wenn es mindestens zwei verschiedene Bewertungen ihrer Variablen gibt, die
diese Formel wabr machen. Sate{X) bezeichne die Menge der 2-erfüllbaren aussagenlogischen Formeln über X.

(a) Geben Sie eine induktive Definition für AL(X') in Form einer Grammatik an.
(b) Geben Sie für den Fall X = {zı,29,x3} Beispiele für Formein folgender Art an:

i. eine Formel Fi, die unerfüllbar ist, d.h. F} € AL(X) \ Sat(X);
ii.  eine Formel Fr, die erfüllbar, aber nicht 2-erfüllbar ist,
d.h. Fy € Sat{X) \ Satz(X);
iii. eine Formel F3, die 2-erfüllbar ist, aber keine Tautologie,
d.h. F3 € Sata(X) \ Taut(X);
iv. eine Tautologie Fy, d.h. Fy € Taut(X).

(c) Zeigen Sie, dass die Frage nach der Zugehérigkeit einer Formel zu Sate(X) (für beliebige
Variablenmengen X) ein NP-vollständiges Problem ist. Konstruieren Sie hierfür eine
polynomielle Reduktion zwischen dem bekannten Erfüllbarkeitsproblem Sat und dem
Sat2-Problem, die dies beweist.

Falls Sie die verlangte Reduktion nicht finden, so geben Sie möglichst genau an, aus
welchen Daten eine solche besteht und was zu beweisen wäre.

Hinweis: Verwenden Sie zur Formulierung von Algorithmen bzw. Datentypen eine
gängige höhere Programmiersprache oder einen entsprechenden Pseudocode. Erläutern
Sie Ihre Lösung ausgiebig durch Kommentare.

Fortsetzung nächste Seite!
Frühjahr 2013 Einzelprüfungsnummer 66115 Seite 8

Aufgabe 4

Für das bekannte rekursive Sortierverfahren Mergesort soll eine nicht-rekursive Variante
nrMergesort entwickelt werden. Die Grundidee des Verfahrens besteht dabei darin, auf den
rekursiven Abstieg zu verzichten und davon auszugehen, dass zu Beginn sortierte
einelementige Listen hintereinander in einem Feld vorliegen. Im Verlauf des Verfahrens
werden immer länger werdende, sortierte Teillisten miteinander solange gemischt, bis die
gesamte Liste sortiert ist.

a) Geben Sie eine Implementierung des nicht-rekursiven Mergesort-Verfahrens an, welche
zwei Felder verwendet.

b) Werden bei diesem Verfahren die gleichen Mischoperationen ausgeführt, wie beim
rekursiven Mergesort? Begründen Sie Ihre Antwort.

c) Ist folgende Behauptung wahr oder falsch: Die Laufzeit von Mergesort (rekursive

Variante) hängt nicht vom Wert der Schlüssel in der Eingabedatei ab. Begründen Sie Ihre
Antwort.

Fortsetzung nächste Seite!
Seite 9

Frühjahr 2013 Einzelprüfungsnummer 66115

Aufgabe 5

Drei Missionare und drei Kannibalen befinden sich am Ufer eines Flusses und möchten diesen
überqueren. Dazu steht ihnen ein Boot zur Verfügung, das ein oder zwei Personen befördern
kann. Verbleiben an einem Ufer mehr Kannibalen als Missionare, so werden die Missionare
verspeist. Die Frage besteht nun darin, wie alle Personen unversehrt auf die andere Seite des
Flusses gelangen.

Im Anfangszustand befinden sich alle Personen und das Boot auf einer Seite des Flusses.
Nehmen Sie an, es sei die linke Seite des Flusses. Im Zielzustand befinden sich alle Personen
und das Boot auf der anderen Seite des Flusses. Jeden Zustand kann man durch folgendes
Fünftupel beschreiben:

Missionareyngs X Kannibalen;;„xs X Missionareyeens X Kannibalenyechıs X Boolposition

Dabei werden die Elemente für Missionare und Kannibalen durch natürliche Zahlen und die
Bootsposition durch einen der Strings „links“ oder „rechts“ modelliert. Der Anfangszustand
wäre somit also (3, 3, 0, 0, » links") und der Zielzustand (0, 0, 3, 3, „rechts‘“).

Schreiben Sie Algorithmen zur Lösung dieses Suchproblems und retten Sie die Missionare!
Es ist empfehlenswert (aber nicht zwingend), hierzu eine funktionale Programmiersprache zu
verwenden. Gehen Sie im Einzelnen vor, wie folgt:

a.) Schreiben Sie eine Funktion, die alle möglichen Überfahrten von links nach rechts
oder umgekehrt modelliert, d. h. die zu einem gegebenen Zustand die Liste der
möglichen Folgezustände im Sinne der o. g. Regeln berechnet. Gehen Sie dazu von
allen möglichen Überfahrten aus und überprüfen Sie für jede konkrete Überfahrt
mittels einer geeigneter Funktion, ob diese zu einem zulässigen Zustand führt.
Zustände, die die Missionare nicht überleben, gelten im Sinne des Rettungsvorhabens
ebenfalls als nicht zulässig. Nicht zulässige Zustände werden nicht in die Liste der
möglichen Folgezustände eingefügt.

b.) Geben Sie eine Funktion an, die feststellt, ob ein Zyklus vorliegt, d. h. ob ein Zustand
in einer Liste bereits besuchter Zustände schon enthalten ist.

c.) Verwenden Sie Ihre Ergebnisse aus a.) und b.), um eine Funktion anzugeben, die
dieses Suchproblem mittels Breitensuche löst. (Sie können die Funktionen aus a.) und
b.) hier auch dann verwenden, wenn Sie diese Teilaufgaben nicht vollständig gelöst
haben.) Die Funktion erhält als Eingabe einen Start- und einen Zielzustand und liefert
als Ergebnis die erste gefundene Liste von Zuständen, die das Problem löst.