Prüfungsteilnehmer '.  Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Kennwort: __________ Herbst A6 1 1 5

2014

Arbeitsplatz-Nr.:

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: 8

Bitte wenden!
Herbst 2014 Einzelprüfungsnummer: 46115 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:

Sei L die Menge der nicht-leeren Wörter über dem Alphabet {a,b,c}, bei denen das erste und das
letzte Zeichen verschieden sind.

a) Geben Sie einen regulären Ausdruck an, der L beschreibt.

b) Geben Sie einen deterministischen endlichen Automaten A an mit L(A) = L. Hier reicht z. B.
das Zustandsdiagramm.

Aufgabe 2:
Sei L = {a™b"c"d™ | n,m > 1}.

a) Geben Sie eine textuelle Beschreibung für Z der Form „L besteht aus allen Wörtern, die...

b) Zeigen oder widerlegen Sie, dass L regulär ist.
Begründen (Beweisen) Sie Ihre Antwort durch die Angabe einer entsprechenden Beschreibung
für Z oder zeigen Sie, dass L nicht regulär sein kann.

Aufgabe 3:

Zeigen Sie, cess es zu jedem deterministischen endlichen Automaten (DFA) A einen DFA B gibt
mit L(B) = X* — L(A), d.h., B erkennt das Komplement von A.

Aufgabe 4:

Zeigen Sie, dass die Sprache L = {a*b'a™b™a"b" | k,n,m > 1} kontextfrei ist.

Aufgabe 5:

Geben Sie eine Turingmaschine M an, die die Sprache L = {ar” |n > 1} erkennt und beschreiben
Sie in Worten, wie Ihre Turingmaschine arbeitet.
Tipp: n? ist die Summe der ungeraden Zahlen von 1 bis 2n — 1.

Aufgabe 6:
Fügen Sie nacheinander die Zahlen 10, 4, 20, 12, 5, 7, 1, 2, 8, 9

a) in einen leeren binären Suchbaum ein und zeichnen Sie den Suchbaum.

b) in einen leeren AVL Baum ein.
Beschreiben (zeichnen) Sie den AVL-Baum nach dem Einfügen von 5 und am Ende.
Beschreiben Sie, wann ggf. rotiert werden muss, und geben Sie die Rotationen an.

Fortsetzung nächste Seite!
Herbst 2014 oo. Einzelprüfungsnummer: 46115 Seite: 3

Aufgabe 7:

In einen bzgl. < angeordneten leeren Min-Heap werden nacheinander

a) die Zahlen 1, 18, 3, 20, 22, 7, 30, 26, 16 eingefügt.
Geben Sie den Min-Heap vor und nach dem Einfügen von 16 an.

b) Anschließend wird mit deletemin() die 1 gelöscht.
Beschreiben Sie, wie das realisiert wird, und geben Sie den Heap danach an.

Aufgabe 8:

Führen Sie auf dem folgenden ungerichteten Graphen G eine Tiefensuche ab dem Knoten s aus.
Unbesuchte Nachbarn eines Knotens sollen dabei in alphabetischer Reihenfolge abgearbeitet werden.

Die Tiefensuche soll auf Basis eines Stacks implementiert werden.

Geben Sie die Reihenfolge der besuchten Knoten, also die dfs-number der Knoten, und den Inhalt
des Stacks in jedem Schritt an.

| Fortsetzung nächste Seite!
Herbst 2014 Einzelprüfungsnummer: 46115 Seite: 4

Aufgabe 9:
. Berechnen Sie einen minimalen Spannbaum im Graphen G.

Markieren Sie die zum Spannbaum gehörenden Kanten.
Welchen Wert hat der Spannbaum?

Herbst 2014 — Einzelprüfungsnummer: 46115 Seite: 5:

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1:

Reguläre Sprachen I

a) Sei © = {a,b}. Für ein w € D* und x € % bezeichnen wir mit |w|, die Anzahl der x in w. Sei
L = {w € D* | |w|. ungerade}.
i) Geben Sie einen regulären Ausdruck a mit L(a@) = L an.

ii) Eine Grammatik heißt linkslinear, wenn es für jede Produktion Nichtterminale A, B und
ein Terminalsymbol x gibt, so dass die Produktion die Form A — Bz oder A — e hat.
Geben ‘Sie eine linkslineare Grammatik für die Sprache L an.

b) Geben Sie einen deterministischen endlichen Automaten an, der die gleiche Sprache erkennt,
wie der unten aufgeführte nichtdeterministische Automat. Erläutern Sie, wie Ihre Konstruktion
mit dem ursprünglichen Automaten zusammenhängt.

0,1

Aufgabe 2:
Reguläre Sprachen II

a) Erläutern Sie kurz, warum reguläre Sprachen unter Schnitt abgeschlossen sind!

Sei nun 3 = {a,b,c}. Sie dürfen als gegeben annehmen, dass die Sprache Ly = {a’b! | i € IN} nicht
regular ist.

b) Ist Ly = {atb'co) | 1,7 € No} regulär? Zeigen Sie, warum (nicht)!
c) Ist L. = {a'b’c* | i,9,k € No} regulär? Zeigen Sie, warum (nicht)!

Fortsetzung nächste Seite!


Herbst 2014 Einzelprüfungsnummer: 46115 Seite: 6

Aufgabe 3:
Kontextfreie Sprachen

_ a) Geben Sie eine kontextfreie Grammatik für die folgende Sprache an:
L = {(ba)"b"a?" |n > 0,m gerade}

b) Betrachten Sie die Grammatik G2 = (No, Ue, P2,S) mit No = {S,T,U,V, W, A, B, C,D} und
= {a,b,c}, wobei P2 aus den folgenden Produktionen besteht:

S—3S8S| AV T-UU|CW|d U->UVU|ld V->TB W-TD
A-a Boob Coe D-d

Verwenden Sie den OYK-Algorithmus, um zu zeigen, dass das Wort wg = adbb nicht in L(G.)
enthalten ist.

Aufgabe 4:
Komplexitätstheorie

In einem ungerichteten Graphen G = (V,E) ist eine Clique der Größe k eine Teilmenge
V’ CV mit |V’| = k, sodass alle u, v € V’ benachbart sind, d.h. {u,v} € E.

Wir betrachten das 2-Cliquenproblem 2-CLIQUE, welches für einen ungerichteten Graphen G |
und natürliche Zahl k die Frage stellt, ob G zwei disjunkte Cliquen der Größe mindestens k enthält.

Formal ist das Problem 2-CLIQUE wie folgt definiert:

Gegeben: Ungerichteter Graph G = (V, E) und natürliche ZahlkeN.
Problem: Existieren Cliquen V;,V2 C V mit |Vi| > k, [Val > k und inv, =

a) Begründen Sie: 2-CLIQUE liegt in NP.

b) Geben Sie eine polynomielle Reduktion von CLIQUE auf 2-CLIQUE an. Das Problem
CLIQUE ist die Frage, ob ein Graph eine Clique der Größe mindestens k besitzt.

c) Zeigen Sie: 2-CLIQUE ist NP-vollständig.
. Hinweis: Sie dürfen verwenden, dass CLIQUE NP-hart ist.

Aufgabe 5:
Berechen- und Entscheidbarkeit

Sei 5 = {0,1}. Wir nehmen an, dass jedes w € %* eine Turingmaschine kodiert und bezeichnen diese Turingmaschine mit M„. Die von M, berechnete Funktion bezeichnen wir mit

Pu:

Welche der folgenden Mengen sind entscheidbar? Begründen Sie kurz.
a) L, = {w € &* | M, besitzt mindestens 13 Zustände}

b) Ly = {w € * | es gibt x, so dass Pw(z) = 01}

c) L3 = {we d* | Ine N: w = 0710}

Fortsetzung nächste Seite!
Herbst 2014 Einzelprüfungsnummer: 46115 _ Seite: 7

Aufgabe 6:
Algorithmen und Datenstrukturen

Für diese Aufgabe nehmen wir eine Datenstruktur für Knoten in Binärbäumen an: Ein
Knoten node besitzt Zeiger auf sein linkes bzw. rechtes Kind node.left bzw. node.right sowie einen
Wert node.value € N. Zeiger auf nil markieren Blätter.

Wir zeichnen Knoten als Kreise, in welche wir die Werte schreiben. Optional geben wir den Namen
des Knoten über dem Kreis an. Pfeile symbolisieren Zeiger auf Kinder. Der Finfachheit halber
ignorieren wir Blätter.

Im nachfolgend abgebildeten Baum gilt zum Beispiel x5.left = nil, x5.right = x6 und x5.value = 5.

xl

_ Die Methode print(n) gibt die natürliche Zahl n aus. Nachfolgend abgebildeter Pseudocode liefert
mit Aufruf von traverse(x1) die Ausgabe 1,2,3,4,5,6. .

procedure traverse(node) {
- print node.value
if (node.left Z nil)
traverse (node.left)
if (node.right ¥ nil)
traverse (node.right)
}

a) Binäre Suchbäume:

i) Modifizieren Sie die Werte im oben abgebildeten Baum so, dass er einen binären Suchbaum
für die Werte {1,2,3,4,5,6} darstellt. (Zeichnen Sie diesen Baum!)

ii) Geben Sie eine Pseudocode-Implementierung für procedure contains(x, n) an, welche true
zurückliefert, falls sich der Wert n in dem binären Suchbaum mit Wurzelknoten x befindet,
und false andernfalls.

A

ii) Wie hangt die Laufzeit Ihrer Implementierung mit der Hohe des Suchbaums zusammen?
Hinweis:, Die Hohe ist die Anzahl der Knoten auf einem langsten Pfad zu einem Blatt, im
obigen Beispielbaum 3

iv) Wie viele Knoten kann ein binärer Suchbaum der Höhe n maximal enthalten? Wie viele
minimal?

Fortsetzung nächste Seite!
Herbst 2014 Einzelprüfungsnummer: 46115 Seite: 8

b) Baumtraversierung:

i) Zeichnen Sie einen Baum, der sich strukturell vom oben. abgebildeten Baum unterschei- .
det, für dessen Wurzel allerdings traverse (wie im oben gegebenen Beispiel) ebenfalls die
Ausgabe 1, 2,3, 4,5, 6 liefert.

ii) Modifizieren Sie traverse so zu traverse_sorted, dass die Werte in einem binären Suchbaum
sortiert ausgegeben werden. Verwenden sie dabei keinen der Vergleichsoperatoren < und
>!