Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:
Frühjahr
Kennwort: —_ 46 1 1 5
2018

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 2018 Einzelprüfungsnummer: 46115 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1: Reguläre Ausdrücke

Gegeben sei die Sprache L. L besteht aus der Menge aller Worte über dem Alphabet 3 = {0,1,2},
die mit 0 beginnen und bei denen das vorletzte und das letzte Zeichen übereinstimmen.

a) Geben Sie alle Worte bis zur Länge vier von L an.
b) Zeigen Sie durch Angabe eines regulären Ausdrucks, dass die Sprache L regulär ist.

c) Konstruieren Sie (graphisch) einen nichtdeterministischen endlichen Automaten ohne Spontanübergänge (= e-Kanten), der L akzeptiert.

Aufgabe 2: Komplexitätsklassen

a) Definieren Sie die Komplexitätsklassen P und NP.
b) Warum gilt P C NP?

Aufgabe 3: Turingmaschinen

Gegeben sei die Sprache L = {a"b?"|n > 1}.

a) Geben Sie eine Turingmaschine M an, die L erkennt. Die Eingabeworte sind durch die Sonderzeichen € vorne und $ hinten begrenzt.

b) Beschreiben Sie in Worten, wie Ihre Turingmaschine arbeitet.

c) Konstruieren Sie M durch Angabe der Befehle und kommentieren Sie, was die Befehle in
Bezug auf die Arbeitsweise von M unter a) leisten.

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

Aufgabe 4: Pumping-Lemma
Das Pumping-Lemma für reguläre Sprachen ist bekanntlich folgendermaßen definiert:

Satz (Pumping-Lemma)
- LEREG> (3keNoVwel:|w|2k= 3 Zerlegung w = xyz mit
1. y!2ı
2. |xy|<k
3. Vie No: xy'ze L)

Zeigen Sie damit, dass die Sprache L = {a”b"*3|n > 2} nicht regular ist.

Aufgabe 5: Mastertheorem
Der Hauptsatz der Laufzeitfunktionen ist bekanntlich folgendermaßen definiert:

Satz (Mastertheorem)

- Sei T(n) = 17 © OC) fallsnsk ne keN,a21undb>1
a-T(z)+g(n), sonst
- Dann gilt
1. g(n) e O(n'& °-€) für ein e>0 = T{n)e O(n'%b?)
2. g(n)e S{n&*) > T(n) e ©(n'%b® .jogn)= ©(g(n)-logn)

3. g(n) € 2(n8o4*) für ein e>O und
a-g(#)<c-g(n) für fast alle n und ein ce mitü<c<1
=» T(n)e ©(g{r))

Sei nun folgende Funktion für die Anzahl an Schritten eines Algorithmus auf der Eingabegröße n
gegeben:

T(n) = 4 T(n/2) + 2n log5(n) + 7n.

Ordnen Sie T(n) einem der drei Fälle des Mastertheorems zu. Beweisen Sie, dass T(n) die Voraussetzungen des Falles erfüllt und geben Sie die resultierende Laufzeitkomplexität von T(n) an.

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

Aufgabe 6: Sortieren

a)

b)

Gegeben ist das folgende Array von Zahlen:

[13, 4, 7, 32, 27, 11, 6, 17, 2]

Sortieren Sie das Array mittels Mergesort aufsteigend von links nach rechts. Das Aufteilen
einer Liste soll in der Mitte erfolgen und, falls notwendig, die zweite Liste ein Element länger
sein als die erste. Listen der Länge zwei dürfen durch direkten Vergleich sortiert werden. Geben Sie die Eingabe und das Ergebnis jedes (rekursiven) Aufrufs an. Geben Sie abschließend
die sortierte Liste an.

Beantworten Sie folgende Fragen jeweils ohne Begründung oder Beweis.

(i) Welche Worst-Case-Laufzeit (O-Notation) hat Mergesort für n Elemente?
(ii) Welche Laufzeit hat Mergesort für n Elemente im Best-Case?

(iii) Kann basierend auf paarweisen Vergleichen von Werten schneller

(Laufzeitkomplexität) als Mergesort sortiert werden?

Aufgabe 7: Kürzeste Wege

a)

Berechnen Sie mithilfe des Algorithmus von Dijkstra die kürzesten Wege vom Knoten s zu
allen anderen Knoten im folgenden aufgezeichneten Graphen G.

Erstellen Sie dazu eine Tabelle mit zwei Spalten und stellen Sie jeden einzelnen Schritt des
Verfahrens in einer eigenen Zeile dar. Geben Sie in der ersten Spalte den jeweils als nächstes
fertigzustellenden Knoten v (wird sog. “schwarz”) als Tripel (v, p, 6) mit v als Knotenname,
p als aktueller Vorgängerknoten und ö als aktuelle Distanz von s zu v über p an. Führen
Sie in der zweiten Spalten alle anderen bisher erreichten Knoten v ebenfalls als Tripel (v, p,
6) auf, wobei diese sog. “grauen Randknoten” in folgenden Durchgängen erneut betrachtet
werden müssen. Zeichnen Sie anschließend den entstandenen Wegebaum, d.h. den Graphen
G, in dem nur noch diejenigen Kanten vorkommen, die Teil der kürzesten Wege von s zu
allen anderen Knoten sind.

Fortsetzung nächste Seite!
Frühjahr 2018 Einzelprüfungsnummer: 46115 Seite: 5

b) Nehmen Sie jetzt an, dass die Kantengewichte auch negativ sein können. Geben Sie ein kleines
Beispiel (max. 3 Knoten) an und machen Sie daran deutlich, dass der Dijkstra-Algorithmus
dann falsche Ergebnisse liefern kann.

Aufgabe 8: Spannbaum

a) Berechnen Sie mithilfe des Algorithmus von Prim ausgehend vom Knoten s einen minimalen
Spannbaum des ungerichteten Graphen G, der durch folgende Adjazenzmatrix gegeben ist:

siaıb/[c|dje| f|gıh
s/-|- 13|)-|- 1 7|I-|I-] -
aj-}| - | - |}O);8] - J11|-| -
bi3]- |] - |-];5] - | 101-4] -
e/-|0j),- ]7-1-}- 1} 1 ]-] -
dj-{ 8} 5i/-];-|2},3]- ] 6
e|7],- }|- 1-72] - | - |- {11
t|- ılılıla)- | - |7|-
g|l-I-1I-|-|I-1- | 71-14
hj-|-|-1-]6]41} - [44 -

Erstellen Sie dazu eine Tabelle mit zwei Spalten und stellen Sie jeden einzelnen Schritt des Verfahrens in einer eigenen Zeile dar. Geben Sie in der ersten Spalte denjenigen Knoten v, der vom
Algorithmus als nächstes in den Ergebnisbaum aufgenommen wird (dieser sog. “schwarze” Knoten
ist damit fertiggestellt) als Tripel (v, p, 6) mit v als Knotenname, p als aktueller Vorgängerknoten
und 6 als aktuelle Distanz von v zu p an. Führen Sie in der zweiten Spalte alle anderen vom aktuellen Spannbaum direkt erreichbaren Knoten v (sog. “graue Randknoten”) ebenfalls als Tripel
(v, p, 6) auf. Zeichnen Sie anschließend den entstandenen Spannbaum und geben Sie sein Gewicht
an.

b) Welche Worst-Case-Laufzeitkomplexität hat der Algorithmus von Prim, wenn die grauen
Knoten in einem Heap nach Distanz verwaltet werden? Sei dabei n die Anzahl an Knoten
und m die Anzahl an Kanten des Graphen. Eine Begründung ist nicht erforderlich.

c) Beschreiben Sie kurz die Idee des alternativen Ansatzes zur Berechnung eines minimalen
Spannbaumes von Kruskal.
Frühjahr 2018 Einzelprüfungsnummer: 46115 Seite: 6

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:

Gegeben sei der nichtdeterministische endliche Automat N = (Q, {0,1}, 6,90, F) mit
Q = {A,B,C}, = A, F = {C} und

a) Wenden Sie die Potenzmengenkonstruktion an, um einen deterministischen endlichen Automaten für die Sprache L(N) zu erhalten.

b) Beweisen oder widerlegen Sie: für reguläre Ausdrücke a, ß gilt:
L((a|ß)*) = L(a*|ß*)

c) Für eine gegebene Sprache L C {a,b,c}* sei replace(L) die Sprache bestehend aus genau den
Wörtern, die entstehen, wenn in jedem Wort aus L jedes Vorkommen von c durch ab ersetzt
wird.

Beispiel: replace({a, c, ba, ab, abc, cab}) = {a, ab, ba, abab}
i) Zeigen Sie: Wenn L regular ist, ist auch replace(Z) regular.
ii) Widerlegen Sie: Wenn replace(L) regulär ist, ist auch L regular.

Aufgabe 2:

a) Zeigen Sie: Die Sprache {(ba)"b(ab)” | n € N} ist regular.

b)  Zeigen Sie, dass {a'c/b**c* | i, j,k € N} kontextfrei ist, indem Sie eine geeignete kontextfreie
Grammatik angeben.

c) Gegeben sei die kontextfreie Grammatik G = (V,D,P,S) mit Sprache L(G), wobei V =
{S,X,Y} und © = {a,b,c,d,e}. P bestehe aus den folgenden Produktionen:

S—+X|SbY X + dSela Y>X|YcX

Bringen Sie G in Chomsky-Normalform.

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

Aufgabe 3:
a) Ein AVL-Baum ist stets ein binärer Suchbaum. Geben Sie informell die zentrale Eigenschaft
von AVL-Bäumen an, die an jedem Knoten erfüllt ist.

b) Fügen Sie nacheinander die folgenden Zahlen in einen anfangs leeren AVL-Baum ein: 5, 7, 9,
12, 15.

Zeichen Sie den Baum nach jedem Einfügen und nach jeder Rotation.

c) In welcher Reihenfolge können die Zahlen 1, 2, 3, 4, 5, 6, 7, 8, 9 in einen anfangs leeren
AVL-Baum eingefügt werden, sodass keine Rotationen stattfinden? Geben Sie eine mögliche
Reihenfolge an und zeichnen Sie den daraus resultierenden AVL-Baum.

Aufgabe 4:

Sei G der folgende Graph.

OO
©)

a) Bestimmen Sie mithilfe des Dijkstra-Algorithmus den Kürzeste-Wege-Baum im ungerichteten
Graph G, ausgehend vom Knoten a. Geben Sie die Einzelschritte Ihrer Berechnung, inklusive
der aktuellen Warteschlange, tabellarisch an. Zeichnen Sie den resultierenden Baum.

Fortsetzung nächste Seite!
Frühjahr 2018 Einzelprüfungsnummer: 46115 Seite: 8

d)

Ihre Tabelle sollte wie folgt beginnen:

a b ce d e f Warteschlange

0 co ww m oo a

Der Algorithmus von Prim ist ein Algorithmus zur Bestimmung des minimalen Spannbaums
in einem Graphen. Geben Sie einen anderen Algorithmus zur Bestimmung des minimalen
Spannbaums an.

Führen Sie den Algorithmus von Prim schrittweise auf G aus. Ausgangsknoten soll der Knoten
a sein.

Ihre Tabelle sollte wie folgt beginnen:

a b c d e f Warteschlange

0 www wo o a

Die Einträge der Tabelle geben an, wie weit der angegebene Knoten vom aktuellen Baum
entfernt ist.

Erklären Sie, warum der Kürzeste-Wege-Baum und der minimale Spannbaum nicht notwendigerweise identisch sind.

Aufgabe 5:

Eine S-Bahnstrecke mit n Stationen wird von einer Linie von Anfang bis Ende befahren. Wegen
der vielen Haltepunkte ist die Fahrzeit sehr lang. Daher soll eine Expresslinie eingerichtet werden.
Diese hält nicht an allen Stationen und kann dadurch die Fahrzeit erheblich verkürzen.

Einige Haltestellen werden als Expresshaltestellen ausgewählt und die Expresslinie hält nur an
diesen Punkten. Durch eine geeignete Kombination an normalen Zügen und Expresszügen kann
ein Nutzer seine Fahrzeit minimieren (die Fahrzeit ist hier die Gesamtzahl der Stopps des Nutzers
- insbesondere vernachlässigen wir hierbei die Zeit für das eventuelle Wechseln eines Zuges).

Ziel ist es, dass jeder Nutzer eine Fahrzeit von höchstens O(,/n) hat. Finden Sie eine geeignete
Verteilung der Expresshaltestellen. Beschreiben Sie, wie ein Nutzer effizient von Haltestelle i zu
Haltestelle 5 fährt. Begründen Sie die daraus resultierende (asymptotische) Worst-Case-Fahrzeit.