Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

 

Kennzahl:

 

Frühjahr
Kennwort: 46 1 1 5
2020

 

Arbeitsplatz-Nr.:

 

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

— Prüfungsaufgaben —

 

Fach: Informatik (Unterrichtsfach)
Einzelprüfung: Theoretische Informatik/Algorithmus/Datenstrukturen
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 10

 

Bitte wenden!
Frühjahr 2020 Einzelprüfungsnummer: 46115 Seite: 2

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1 (Reguläre Sprachen) [35 PUNKTE]

(a) [4 Punkte] Betrachten Sie die formale Sprache Z < {0,1}* aller Wörter, die 01 oder 110 als
Teilwort enthalten.

Geben Sie einen regulären Ausdruck für die Sprache L an.

(b) [10 Punkte] Entwerfen Sie einen (vollständigen) deterministischen endlichen Automaten, der
die Sprache L aus Teilaufgabe (a) akzeptiert. (Hinweis: es werden nicht mehr als 6 Zustände
benötigt.)

(c) [15 Punkte] Minimieren Sie den folgenden deterministischen endlichen Automaten:

 

 

 

 

Machen Sie dabei Ihren Rechenweg deutlich!

(d) [6 Punkte] Ist die folgende Aussage richtig oder falsch? Begründen Sie Ihre Antwort!

„Zu jeder regulären Sprache L über dem Alphabet D gibt es eine Sprache L’ C 2*, die L
enthält (d.h. L C L’) und nicht regulär ist.“

Aufgabe 2 (Kontextfreie Sprachen) [32 PUNKTE]

(a) [4 Punkte] Betrachten Sie die formale Sprache L über dem Alphabet U = {a,b,c} aller
Wörter wv mit w € {a,b}* und v e {b,c}* so dass w = b*a” und v = (cb)*
fürn, kENo.
(eben Sie zwei Wörter über % an, die in L enthalten sind und zwei Wörter, die nicht in L
enthalten sind. Die Wörter sollen mindestens Länge 5 haben.

(b) [10 Punkte] Geben Sie eine kontextfreie Grammatik für die Sprache L an.

Erklären Sie den Zweck der einzelnen Nichtterminale (Variablen) und der Grammatikregeln
Ihrer Grammatik.

(c) [2 Punkte] Geben Sie für eines Ihrer beiden Wörter aus Teilaufgabe (a), das in Z enthalten
ist, einen Ableitungsbaum des Wortes mit Ihrer Grammatik aus Teilaufgabe (b) an.

(d) [10 Punkte Beweisen Sie, dass die Sprache L aus Teilaufgabe (a) nicht regulär ist.

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

 

(e) [6 Punkte] Ist die folgende Aussage richtig oder falsch? Begründen Sie Ihre Antwort!

„Wenn L eine kontextfreie und L’ eine Sprache aus der Klasse P ist, dann ist die Konkate-
nation LL’ wieder kontextfrei.“

Aufgabe 3 (Entscheidbarkeit) [23 PUNKTE]

(a) [8 Punkte] Betrachten Sie das folgende Entscheidungsproblem:

Eingabe: eine (geeignet codierte) Turingmaschine M

Aufgabe: entscheiden, ob die Turingmaschine M auf jedes Eingabewort nach höchstens 42
Schritten hält.

Ist dieses Problem entscheidbar? Begründen Sie Ihre Antwort.

(b) [15 Punkte] Beweisen Sie mit Hilfe eines Reduktionsbeweises, dass das folgende Problem
nicht entscheidbar ist:

Eingabe: zwei (geeignet codierte) Turingmaschinen Mı, Ma sowie ein Eingabewort w
Aufgabe: entscheiden, ob M} auf Eingabewort w hält und Ma auf w nicht hält.

Aufgabe 4 (Korrektheit von Algorithmen) [26 PUNKTE]

Wir betrachten den nachstehenden Algorithmus:

MINSUFFIXAVERAGE(All..n])

// Eingabe: Ein Feld A vonn >1 Zahlen
N Ausgabe: mMinı<i<n Mir) DE Alk]
[0] =
a[0] = 0
for s= n downtol

=n-s+H1l

—s)-all-1]+Als
al

bl! = min(bli - 1],all])
return bln]

-)19) cr PO DN Mr

(a) [3 Punkte] Begründen Sie, dass der Wert der Variablen ! der Nummer des aktuellen Schlei-
fendurchlaufs entspricht (wenn wir mit dem Zählen der Schleifendurchläufe bei 1 beginnen).

Wir wollen beweisen, dass der Algorithmus korrekt ist, d. h., dass er für die Eingabe All,...,n]
den Wert

1<ien ( —i+ (n-i+1)& > Alk)

zurückgibt. Für 1<I<n seien dazu folgende Werte definiert

n

1
u DA md de, a an

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

 

Wir wollen durch Induktion zeigen, dass für alle 1<!<n die Aussage
Aı : Nach dem I-ten Durchlauf der Schleife ist all] = a,
gilt.
(b) [2 Punkte] Führen Sie den Induktionsanfang ! = 1 aus.
(c) [8 Punkte] Führen Sie den Induktionsschritt -1—!(für1<I<n) aus.
Wir wollen als nächstes durch Induktion zeigen, dass für alle 1<!<n die Aussage

B, : Nach dem I!-ten Durchlauf der Schleife ist b[!] = b;
gilt.

(d) [2 Punkte] Führen Sie den Induktionsanfang ! = 1 aus.

(e) |9 Punkte] Führen Sie den Induktionsschritt -1— 1! (füri<I!<n) aus.
Hinweis: Verwenden Sie das Resultat aus der vorigen Aufgabe: all] = a; für alle1<I!<n.

(f) [2 Punkte] Folgern Sie, dass der Algorithmus MINSUFFIX AVERAGE korrekt ist.

Aufgabe 5 (Naive Polynomarithmetik) 15 PUNKTE]

In den folgenden Aufgaben nehmen wir an, dass ein Polynom

A= > a2 € Ze]

O<SI<n

vom Grad < n im Rechner durch ein Array K4l0,...,n — 1] mit Kıls] = a, dargestellt wird.

(a) [3 Punkte] Geben Sie einen Algorithmus zur Addition zweier Polynome in Pseudo-Code an:

PADD(A, B,n)
/ Eingabe: Zwei Polynome A, B € Z[x] vom Grad kleiner n mit
N A=Yocimn ur und B= osicn Dir’

# Ausgabe: Das Polynom C = Ygc;, Ga’ mit CO=A+B

(b) [2 Punkte] Bestimmen Sie die Laufzeit Ihrer Implementierung beim Aufruf PApp(A, B,n).
(c) [4 Punkte] Geben Sie einen Algorithmus zur Multiplikation zweier Polynome in Pseudo-Code

an:
PMULT(A, B,n)
# Eingabe: Zwei Polynome A, B & Z[x] vom Grad kleiner n mit
N A= osien a,r® undB= o<ien b,x?
# Ausgabe: Das Polynom O = Y)g<;n_ı 42° mit C = AB

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

(d) [2 Punkte] Bestimmen Sie die Laufzeit Ihrer Implementierung beim Aufruf PMULT(A, B,n).

(e) [2 Punkte] Beschreiben Sie einen Algorithmus PMULTAMONOM(A, B,n) der © = AB in
O(n) Zeit berechnet, falls A ein Monom (d. h. ein Polynom von der Form a,x" mit k < n)
ist.

(f) [2 Punkte] Bestimmen Sie die Laufzeit Ihrer Implementierung beim Aufruf
PMULTAMOonNOM(A, B,n).

Aufgabe 6 (Münzwechseln) 49 PUNKTE]

Gegeben sei eine feste Menge D = {dı,...,‚d„} von m > O natürlichen Zahlen 1=dı <---< dm;
die wir Münzwerte nennen.

(a) [1 Punkt] Begründen Sie, dass sich jede Zahl se Nin der Form

m
= Da-d
i=1
mit c,€ N. schreiben lässt.
Wenn m
5 = > GG di,
i=1
so nennen wir die Folge C = (cı,...,cm) der Länge m eine Darstellung von s (bezüglich der

Münzwerte D). Wir interpretieren dies so, dass sich (der Geldwert) s mithilfe der m verschiedenen
Münzwerte die uns zur Verfügung stehen, wechseln lässt: Wenn wir für 1 << m gerade c;
Münzen vom Wert d; nehmen, erhalten wir insgesamt s. Den Wert

cost(C) := 5 G;

ı=1

nennen wir die Kosten der Darstellung C. Die Kosten einer Darstellung von s zählen also einfach
nur, wie viele Münzen wir insgesamt benötigen, um s gemäß C zu wechseln.

*

Wir suchen eine Darstellung C* = (c$,...,c},) von s mit minimalen Kosten (d. h. wir wollen
möglichst wenige Münzen verwenden). So eine Darstellung von s nennen wir optimal, ihre Kos-
ten bezeichnen wir mit OPT(s) := OPT(C*); für s < 0 definieren wir (zur Vereinfachung der
Notation) OPT(s) := x.

(b) [3 Punkte] Was ist der Wert OPT'(0)? Was sind die Werte OPT(d;) für 1<i<m?

(c) [5 Punkte] Sei C* = (c},...,c#,...,c},) eine optimale Darstellung vons >O0mit >1
für ein 1 < i < m. Beweisen Sie, dass dann C := (c},...,c — l,...,c},) eine optimale
Darstellung von (s — d,) ist.

(d) [6 Punkte] Beweisen Sie, dass für s > 0
OPT(s)=1+ min OPT(s - d,).

Fortsetzung nächste Seite!
Frühjahr 2020 Einzelprüfungsnummer: 46115 | Seite: 6

 

(e) [5 Punkte] Formulieren Sie auf Basis der Rekursionsgleichung aus Teilaufgabe (d) einen
rekursiven Algorithmus zur Berechnung von OPT(s) in Pseudocode:

CHANGEREC (s, D)

/! Eingabe: Eine Instanz des Münzwechselproblems, beschrieben durch
// den Zielwert s>O und

/!  dieFolge D= (d,,....,‚dm) der Münzwerte mit 1 = di <...< dan
// Ausgabe: OPT (s)

(f) [4 Punkte] Wir betrachten nun die Menge D = {1,2} von Münzwerten. Begründen Sie, dass
für dieses D die Laufzeit T(s) des rekursiven Algorithmus beim Aufruf CHAnGEREC(s, D)
folgender asymptotischer Rekursionsgleichung genügt:

T(s)=T(s-1)+T(s-2)+0(1)
(mit T(s) = O(1) für s=O(1))

(s) [6+2 Punkte] Wir betrachten die Rekursionsungleichung (für eine Konstante c > 0)
T(s)>T(s-1)+T(s-2)+cfürs>1 und T(s) >cfürs<li.

Beweisen Sie, dass T(s) = (v2).

Argumentieren Sie damit, warum eine direkte Implementierung der Rekursion von
CHANGEREC im Allgemeinen nicht efhzient ist.

(h) [6+8-+3 Punkte] Formulieren Sie ein dynamisches Programm zur Berechnung von OPT(s)
in Pseudocode:

CHANGEDP (s, D)

// Eingabe: Eine Instanz des Münzwechselproblems, beschrieben durch
// den Zielwert s>0 und

// die Folge D= (d,,.....,‚dn) der Münzwerte mit 1 = di <...< da
// Ausgabe: OPT (s)

Begründen Sie, warum Ihr Algorithmus korrekt ist und analysieren Sie die dessen Laufzeit.
Frühjahr 2020 Einzelprüfungsnummer: 46115 Seite: 7

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1 (Automatentheorie und reguläre Sprachen) [44 PUNKTE]

Gegeben seien die beiden folgenden deterministischen endlichen Automaten
Mı = (Qı, {a, b}, 61,21; Fi) und M; — (Q>, {a, b}, ö9, 9; F3).

 

(a) [16 Punkte] Konstruieren Sie den Produktautomaten M3 mit L(M3) = L(Mı)N L(M;)

(b) [6 Punkte] Welche Veränderungen an Ihrem Automaten M3 sind nötig, um einen Automaten
M; zu erhalten, mit L(M3) = L(Mı}) \ L(M3)?

Hinweis: Eine explizite Angabe des modifizierten Automaten, etwa in Form eines Zu-
standsübergangsdiagramms, ist nicht erforderlich.

(c) [16 Punkte] Geben Sie einen regulären Ausdruck «a mit L(a) = L(Mı) an. Gehen Sie syste-
matisch vor und dokumentieren Sie Ihr Vorgehen geeignet.

(d) [6 Punkte] Gibt es zwei nicht reguläre Sprachen L, und Lz deren Schnitt Lı N La regulär
ist? Begründen Sie Ihre Antwort.

Aufgabe 2 (Turingmaschinen) [30 PUNKTE]

Ziel dieser Aufgabe ist es, eine deterministische 1-Band-Turingmaschine zu konstruieren, die für
jedes Eingabewort w € {a,b}* das Wort w#w berechnet und dann hält. Dabei ist # ein Platz-
haltersymbol, das nicht im Eingabewort vorkommt.

(a) [8 Punkte] Beschreiben Sie das Vorgehen einer solchen Turing-Maschine in Worten.

(b) [18 Punkte] Geben Sie ein Zustandsübergangsdiagramm einer Turingmaschine an, die diese
Berechnung durchführt.

(c) [4 Punkte] Dokumentieren Sie, welche Zustände Ihrer Turingmaschine Ihre Schritte aus
Teilaufgabe (a) implementieren.

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

 

Aufgabe 3 (Berechenbarkeitstheorie) [16 PUNKTE]

Für ein Wort w € &* bezeichne w” das Umkehrwort, das aus w entsteht, indem man die Zeichen-
folge umdreht. Für eine beliebge Sprache A bezeichne A” = {w” | w € A} die Umkehrsprache.

Angenommen, A ist unentscheidbar (= nicht rekursiv). Zeigen Sie, dass dann auch A” unent-
scheidbar ist.

Aufgabe 4 (Sortieren) |9 PUNKTE]

Ein bekanntes Sortierverfahren ist Insertion-Sort, ein inkrementeller Algorithmus. Insertion-Sort
geht im i-ten Durchlauf davon aus, dass das Teilfeld bis zur Stelle z — 1 schon sortiert ist. Dann
speichert Insertion-Sort das i-te Element des gegebenen Feldes zwischen, um es an der korrekten
Stelle im schon sortierten Teilfeld einzufügen.

(a) [3 Punkte] Analysieren Sie, wie viele Schlüsselvergleiche Insertion-Sort im besten und im
schlechtesten Fall benötigt, um ein Feld von n verschiedenen Zahlen zu sortieren. Geben Sie
jeweils die genaue Anzahl an.

(b) [6 Punkte] Sei nun die Eingabe ein Feld mit den Zahlen 1,2,...,n in zufälliger Reihenfolge.
Schätzen Sie asymptotisch scharf ab, wie viele Schlüsselvergleiche Insertion-Sort in diesem
Fall vornimmt.

Tipp: Gehen Sie davon aus, dass n durch 4 teilbar ist. Betrachten Sie der Einfachheit halber
nur die Elemente im letzten Viertel des Feldes. Wie weit müssen manche (wie viele?) dieser
Elemente nach links wandern?

Aufgabe 5 (Dijkstras Algorithmus) [21 PUNKTE]

Auf folgendem ungerichteten Graphen wurde Dijkstras Algorithmus (wie unten beschrieben) aus-
geführt, doch wir wissen lediglich, welcher Knoten als letztes schwarz (black) wurde (Nr. 8) und
was seine Distanz zum Startknoten (Nr. 1) ist. Die Gewichte der Kanten sind angegeben.

Finden Sie den Startknoten, nummerieren Sie die Knoten in der Reihenfolge, in der sie schwarz
wurden und geben Sie in jedem Knoten die Distanz zum Startknoten an!

Markieren Sie die Kanten, die zu dem Kürzesten-Wege-Baum gehören, den Dijkstras Algorithmus
ausgibt.

Der Startknoten ist eindeutig!

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

 

 

 

 

Nr. 8 1 Nr.
15 ae Distanz:
Nr. 7
Distanz: 6
istanz: 10
Nr. 2
10
5 Distanz: Nr.
Distanz:
16
Nr 18 6 Nr
Distanz: Distanz:
5 Nr. 8
Distanz:

Dijkstra(Graph G, Edgeweights w, Vertex s)

 

Initialize(G, s)
S=9
Q = new PriorityQueue(V, d)
while not Q.Empty() do
u = Q.ExtractMin()
S=SUuU{u}
foreach v € Adj[u] do
| Relax(u,v, w)

u.color = black

 

 

 

 

Initialize(Graph G, Vertex s)

 

foreach uveV do
u.color = white
ud=&

s.color = gray
s.d=0

 

 

 

Relax(Vertex u, Vertex v, Edgeweights w)

 

if v.d>u.d+ w(u,v) then
v.color = gray

v.d=u.d+ w(u,v)
@Q.DecreaseKey(v, v.d)

 

 

 

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

 

Aufgabe 6 (Nächstes rot-blaues Paar auf der x-Achse) [40 PUNKTE]

(segeben seien zwei nichtleere Mengen R und B von roten bzw. blauen Punkten auf der x-Achse.
Gesucht ist der minimale euklidische Abstand d(r, b) über alle Punktepaare (r,b) mitr € R und
be B. Hier ist eine Beispielinstanz:

r
e blau
- — A —a— —— 04
x-Achse do “rot

 

 

Die Eingabe wird in einem Feld A übergeben. Jeder Punkt Al) mit 1<i<n hat eine r-
Koordinate Ali].x und eine Farbe Alil.color € { rot, blau }. Das Feld A ist nach x-Koordinate
sortiert, d.h. es gilt A[1].x < Al2].x < --- < Alnl.x, wobein = |R| + |B|.

(a) [10 Punkte] Geben Sie in Worten einen Algorithmus an, der den gesuchten Abstand in O(n)
Zeit berechnet.

(b) [10 Punkte] Begründen Sie kurz die Laufzeit Ihres Algorithmus.

(c) [10 Punkte] Begründen Sie die Korrektheit Ihres Algorithmus.

(d) [10 Punkte] Wir betrachten nun den Spezialfall, dass alle blauen Punkte links von allen
roten Punkten liegen. Beschreiben Sie in Worten, wie man in dieser Situation den gesuchten
Abstand in o(n) Zeit berechnen kann. (Ihr Algorithmus darf also insbesondere nicht Laufzeit
O(n) haben.)

Aufgabe 7 (Heaps) [20 PUNKTE]

Sei H ein Max-Heap, der n Elemente speichert. Für ein Element v in Ä sei h(v) die Höhe von v,
also die Länge eines längsten Pfades von v zu einem Blatt im Teilheap mit Wurzel v.

(a) [6 Punkte] Geben Sie eine rekursive Definition von h(v) an, in der Sie sich auf die Höhen
der Kinder v.left und v.right von v beziehen (falls v Kinder hat).

(b) [8 Punkte] Geben Sie eine möglichst niedrige obere asymptotische Schranke für die Summe
der Höhen aller Elemente in H an, also für $_,czr h(v) und begründen Sie diese.
Tipp: Denken Sie daran, wie man aus einem beliebigen Feld einen Max-Heap macht.

(c) [6 Punkte] Sei 7’ ein Feld der Länge n. Geben Sie einen Algorithmus an, der in Linearzeit
testet, ob H’ ein Max-Heap ist.

ee