Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennwort: Frühjahr 461 15
Arbeitsplatz-Nr.: 2 0 1 5

Erste Staatsprüfung für ein Lehramt 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: 10

Bitte wenden!

Frühjahr 2015 Einzelprüfungsnummer 46115 Seite 2

Thema Nr. 1

Aufgabe 1: reguläre Sprachen

Gegeben sei die Sprache L.
L besteht aus der Menge aller Worte über dem Alphabet {a, b, c},
die mit a beginnen und mit b enden
und die nie zwei aufeinander folgende c’s enthalten.

(1) Geben Sie einen regulären Ausdruck für L an.
(ii) Geben Sie einen vollständigen deterministischen endlichen Automaten für L an.

Aufgabe 2: reguläre Sprachen

Gegeben sei die Sprache L= {a w | n>1, we {b,c}* und |w|=n}.
Dabei bezeichnet |w| die Länge des Wortes w.

(i) Ist L regulär? Ja oder Nein?

(ii) Beweisen Sie Ihre Antwort
- bei JA, durch Angabe eines regulären Ausdrucks oder eines endlichen Automaten,
- bei NEIN, durch das Pumping Lemma.

Aufgabe 3: Minimierung DFA

Minimieren Sie den folgenden deterministischen Automaten mit den Zuständen {0,1,2,3,4}, dem
Startzustand 0 und den Endzuständen {1,2}.
Geben Sie den minimierten DFA an.

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

Aufgabe 4: kontextfreie Sprachen

Gegeben sei die Sprache L= {a" b" c b" a"In,m> 1}

Zeigen Sie, dass L kontextfrei ist.

Aufgabe 5: kontextfreie Sprachen

Gegeben sei die Grammatik G=({S, X, A}, {a,b}, S, P) mit den

Produktionen P=-{S>AX, X>SB, S>ab,A>2aB>b}
Zeigen Sie, dass das Wort aaa bbb von G erzeugt wird.

Aufgabe 6: Berechenbarkeit und Komplexität
Gegeben sei die Sprache L= {a”c” |n >1}

Geben Sie eine Turingmachine M an, die L erkennt.
Die Eingabeworte werden durch $ (oder das Blanksymbol) abgeschlossen.

a) Beschreiben Sie in Worten, wie Ihre Turingmachine arbeitet.
b) Konstruieren Sie M durch Angabe der Befehle und kommentieren Sie, was die Befehle in Bezug
auf die Arbeitsweise von M unter a) leisten.

Aufgabe 7: O-Notation

Gegeben seien die Funktionen f:N -> N und g:N -> N, wobei
f{n) = 0.01n? +n-1 und
g(n)= 100 (n+2)2 + 30

Welche der folgenden Aussagen gilt? Beweisen Sie Ihre Angabe.
a) fin) € O(gin)) |
b) g(n) e O(fin))

Aufgabe 8: Sortieren mit Quicksort

Sortieren Sie die folgende Sequenz S (im Array oder einer Liste gespeichert) von Zahlen mit
Quicksort.

Als Pivotelement soll das jeweils erste Element gewählt werden.

Beschreiben Sie den Ablauf von Quicksort durch Angabe der Zwischenergebnisse nach jedem
Durchlauf.

Markieren Sie das jeweils gewählte Pivotelement.

S = 6, 3, 17, 2, 1, 20, 4, 9, 12,5 .

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

Aufgabe 9: AVL-Bäume

(a) Gegeben sei der folgende fehlerhafte AVL-Baum T.
Geben Sie die Fehler an.

(b) Fügen Sie in den nachfolgenden AVL Baum die 2 ein und
beschreiben Sie die dazu notwendigen Operationen (Rotationen).
Geben Sie den resultiererenden AVL Baum durch eine Zeichnung an.

J

oh Lb

Fortsetzung nächste Seite!


Frühjahr 2015 Einzelprüfungsnummer 46115 Seite 5

Aufgabe 10: Das kürzeste Wege Problem (Dijkstra-Algorithmus)

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

Berechnen Sie die kürzesten Wege vom Startknoten a zuallen anderen Knoten mit Hilfe des
Algorithmus von Dijkstra.

Frühjahr 2015 Einzelprüfungsnummer 46115 Seite 6

Thema Nr. 2

Teilaufgabe 1

Die Sprache Z über dem Alphabet % = {0, 1} enthält alle Wörter, bei denen beim Lesen von links
nach rechts der Unterschied in der Zahl der Oen und len stets höchstens 2 ist. Zum Beispiel sind
00101010 e L, aber 11011000 & ZL, denn nach dem Einlesen von 11011 beträgt der Unterschied 3.

1. Konstruieren Sie einen deterministischen endlichen Automaten für L.

2. Führen Sie auf Ihrem Automaten den Minimierungsalgorithmus durch. Möglicherweise ist Ihr
Automat bereits minimal. In diesem Fall liefert der Algorithmus nichts Neues, muss aber trotzdem
durchgeführt werden. Dokumentieren Sie Ihre Schritte geeignet.

Sei A =(Q,5,q,,£) ein nichtdeterministischer endlicher Automat fir L.Es sei w, = 11, w, =1, w,
=g,w, =0, w, =00. Machen Sie sich klar, dass der Automat jedes dieser Wörter verarbeiten können

muss und dass keine zwei dieser Wörter vom Startzustand aus in denselben Zustand führen dürfen, da
sonst auch falsche Wörter akzeptiert würden. Folgern Sie, dass der Automat mindestens fünf Zustände
haben muss. Schreiben Sie Ihre Argumentation schlüssig und vollständig auf.

Teilaufgabe 2

Die Sprache L = {a"b” | n 2 1} über dem Alphabet 3 = {a,b } ist bekanntlich kontextfrei. Im
Allgemeinen ist das Komplement zweier kontextfreier Sprachen nicht wieder kontextfrei. In diesem

speziellen Fall aber schon; wir wollen nunmehr eine Grammatik für dieses Komplement L
konstruieren.

1. Geben Sie eine kontextfreie Grammatik für Z an.

2. Begründen Sie, dass L = I, UL, UL,U {e}, wobei L = a*b* und L, = {a”b"|m>n} und
'L, = {a”b"’|m>n}.

3. Zeigen Sie nun, dass L kontextfrei ist.

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

Teilaufgabe 3: „Streuspeicherung“

Gegeben seien die folgenden Schlüssel s zusammen mit ihren Streuwerten h(s):

s [AIBICIDIE
hs) 110 1011

a) Fügen Sie A,B, C, D, E in dieser Reihenfolge mit der Streufunktion h(s) in eine Streutabelle der
Größe 5 folgender Form ein! Verwenden Sie zur Kollisionsauflésung verkettete Listen (der
zuletzt eingetragene Schlüssel steht unten):

Bucket > | (Beispiel) |0 1 112,3) 4
X

|
Y

< J@SSN|Yos

_b) Fligen Sie die Schlüssel A, B, C, D, E in dieser Reihenfolge mit der Streufunktion h(s) in eine neue
Streutabelle gleicher Größe und Form ein. Verwenden Sie zur Kollisionsauflösung diesmal aber
lineares Sondieren mit Schrittweite +2.

Bucket> !0!1|12|3|/4
Schlüssel >

c) Ergänzen Sie die Methode insertis, hs), die einen Schlüssel s mit dem zugehörigen Streuwert hs in
eine anfangs leere Streutabelle (intern hier: buckets) einfügt. Die Streutabelle realisiert die
Kollisionsauflösung mit verketteten Listen. Beachten Sie bitte, dass jeder Schlüssel höchstens
einmal in der Streutabelle vorkommen darf (d. h., ein erneutes Einfügen wird ignoriert).

class Streutabelle {
LinkedList<String>[] buckets;

Streutabelle{int size) {
buckets = new LinkedList [size];

}

void insert (String s, int hs) {
assert s != null && 0 <= hs && hs < buckets.length;

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

Hinweis: Aus der Java-API der Klasse LinkedList<E> dürfen Sie verwenden:

public Linkedlist ()

Constructs an empty list.

public boolean contains (Object 0)

Returns true if this list contains the specified element.

public void addLast(E e)

Appends the specified element to the end of this list.

Teilaufgabe 4: “Spezielle Bäume”

Ein Trie ist eine Variante eines Suchbaums. Im Folgenden.
sei jeder Kante in einem Trie implizit ein Großbuchstabe
zugeordnet. Ein Pfad durch den Baum stellt daher eine
Zeichenkette dar. Um eine Zeichenkette einzufügen, wird
sowohl die Zeichenkette als auch der Trie (vom
Wurzelknoten aus) durchlaufen. In jedem Schritt wird die
Ausgangskante des aktuellen Knotens verfolgt, die dem
nächsten Zeichen im String entspricht. Falls es eine solche
Kante noch nicht gibt, wird sie samt Zielknoten neu
angelegt. Sind alle Zeichen abgearbeitet, wird die
Zeichenkette im erreichten Knoten vermerkt. Der

exemplarisch abgebildete Trie entstand durch das Einfügen der Wörter ALM, AUD, AUF, TO und
TOP.

Gegeben ist folgender Ausschnitt der Klasse Trie, die schrittweise in einer beliebigen objektorientierten Programmiersprache Ihrer Wahl oder Pseudocode vervollständigt werden soll:

public class Trie {

// bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben:
Trie[] children = new Trie['2' - "At + 1);
String myString; // null, wenn keine Zeichenkette zu speichern ist

‘a) Implementieren Sie die iterative Methode insert(String s), die den Trie um die nötigen Knoten
erweitert und s im korrekten Knoten speichert:

void insert (String s) {
assert s != null;
for (char c : s.toCharArray(})
assert c >= 'A' && c <= '2';
Trie curr = this;

Fortsetzung nächste Seite!
Frühjahr 2015 Einzelprüfungsnummer 46115 Seite 9

b)

c)

d)

Sei n := s.length{). Welche Laufzeitkomplexität (im O-Kalkül bzw. in Landau-Notation) hat
insert(s)?

Implementieren Sie eine rekursive Methode printSorted(). Sie soll alle im Trie enthaltenen
Wörter in aufsteigender alphabetischer Reihenfolge ausgeben. Wörter, die Präfix eines anderen
Wortes sind, sollen vor dem längeren Wort ausgegeben werden (z.B. TO vor TOP).

Implementieren Sie eine rekursive Methode contains(String s), die prüfen soll, ob s im Trie
enthalten ist.

Teilaufgabe 5: „Funktionale Programmierung“

Gegeben seien gerichtete Graphen G folgender Form:

type V = Int // Knoten
type E = (V, V) // Kante: (Startknoten, Endknoten)
type G = List [E]

// Beispiel:
val graph = List ((!, -), (1, Dr (ir ©), (2, 3), Gr dr (Ce =))

Definieren Sie in einer funktionalen Sprache Ihrer Wahl (hier exemplarisch Scala) eine Funktion.
outEdges(vs, g), die parallel diejenigen Kanten in g filtert und zurückgibt, die direkt von Knoten
der Knotenliste vs zu Knoten außerhalb von vs führen. Sie dürfen die Methode contains(t: T):
Boolean von List[{T]

verwenden.

Beispiel (siehe Bild):
outEdges (List (1, 2, 3), graph) == List((2,4), (3,5))

def outEdges: (List[V], G) => List{E] = (vs, g) =>...

Fortsetzung nächste Seite!
Frühjahr 2015 Einzelprüfungsnummer 46115 Seite 10

b) Ergänzen Sie die Funktion tree (v, g), die einen beliebigen gerichteten Baum (als Kantenliste) mit
Wurzel v bestimmt, welcher alle von v aus in g erreichbaren Knoten enthält. helper({vs) bearbeitet
rekursiv (mittels outEdges) die bereits besuchten Knoten vs:

Beispiel (auch andere gerichtete Bäume möglich!): (2) (4) |
tree(3, graph) == List((3,2), (2,4), (3,5))

def tree: (V, G) => G= {(v, g) => {
 &— ©

def helper: List[V] => G = vs