Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

 

Kennzahl:

 

Frühjahr
Kennwort: 66115
2020

 

Arbeitsplatz-Nr.:

 

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

— Prüfungsaufgaben —

 

Fach: Informatik (vertieft studiert)
Einzelprüfung: Theoretische Informatik, Algorithmen
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 16

 

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

 

Thema Nr. 1
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1 (Aussagen) [24 PUNKTE]
Zeigen oder widerlegen Sie die folgenden Aussagen (die jeweiligen Beweise sind sehr kurz).
Schreiben Sie zunächst zur Aussage „Richtig“ oder „Falsch“ und dann Ihre Begründung.

(a) [6 PUNKTE] Seien L, L’ < 2* formale Sprachen. Falls L kontextfrei und L’ unentscheidbar
ist, dann ist die Vereinigung L U 2’ sicher nicht regulär.

(b) [6 PunKTE] Die Menge aller Sprachen in der Klasse NP ist abzählbar unendlich.

(c) [6 PunKTe|] Es ist unentscheidbar, ob eine vorgelegte aussagenlogische Formel durch jede
Belegung ihrer Variablen erfüllt wird.

(d) [6 PUNKTE] Angenommen es gilt P # NP, und Le NP\P ist gegeben. Dann ist es
möglich, dass L nur endlich viele Nerode-Aquivalenzklassen besitzt.

Aufgabe 2 (Reguläre Sprachen) [30 PUNKTE]

(a) [4 PUNKTE] Es sei Z C {a,b,c}* die von dem folgenden nichtdeterministischen Automaten
akzeptierte Sprache:
a,b,c a,b,c

—DO:-050 02.02.06
Beschreiben Sie (in Worten) wie die Wörter aus der Sprache L aussehen.

(b) [8 PUNKTE] Benutzen Sie die Potenzmengenkonstruktion, um einen deterministischen Au-
tomaten zu konstruieren, der zu dem Automaten aus Teil (a) äquivalent ist. (Berechnen Sie
nur erreichbare Zustände.)

(c) [3 PunKTe] Ist der resultierende deterministische Automat schon minimal? Begründen Sie
Ihre Antwort.

(d) [15 PUNKTE] Minimieren Sie den folgenden deterministischen Automaten:

 

 

 

 

 

Machen Sie dabei Ihren Rechenweg deutlich!

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

 

Aufgabe 3 (Kontextfreie Sprachen) [36 PUNKTE]

(a) [10 PUNKTE] Entwerfen Sie eine kontextfreie Grammatik für die folgende kontextfreie Spra-
che über dem Alphabet D = {a,b, c}:

L = {a"*’wuc” |n € No,2- |w|s = |vla}-

(Hierbei bezeichnet |u|, die Anzahl des Zeichens x in dem Wort u.)

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

(b) [10 PunKTeE|] Betrachten Sie die folgende kontextfreie Grammatik
G=({A,B,C,D}, {a,b,c}, P, A)
mit den Produktionen

—> AB|CD|a

— CClc

u »

— DC|CB|b

D- DBla

Benutzen Sie den Algorithmus von Cocke-Younger-Kasami (CYK), um zu zeigen, dass das
Wort abcab zu der von G erzeugten Sprache L(G) gehört.

(c) |3 PUNKTE] Finden Sie nun ein größtmögliches Teilwort von abcab, dass von keinem der vier
Nichtterminale von G ableitbar ist.

(d) [3 PUNKTE] Geben Sie eine Ableitung des Wortes abcab mit G an.

(e) [10 PUNKTE] Beweisen Sie, dass die folgende formale Sprache über Z = {a,b} nicht kon-
textfrei ist: ,
L={a"b" |neN}.

Aufgabe 4 (Entscheidbarkeit) [14 PUNKTE]

Gegeben ist das folgende Entscheidungsproblem:

Eingabe: eine (geeignet codierte) Turingmaschine M, die eine (möglicherweise partielle) Funktion
fm : N N berechnet

Aufgabe: entscheiden, ob fm sich von der Fakultätsfunktion unterscheidet

(a) [7 PuUnKTel Ist das gegebene Problem semi-entscheidbar? Begründen Sie Ihre Antwort.

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

(b) [7 PunKTe] Ist das gegebene Problem sogar entscheidbar? Begründen Sie auch hier Ihre
Antwort.

Aufgabe 5 (NP-Vollständigkeit) [16 PUNKTE]

Beweisen Sie, dass das folgende Problem N P-vollständig ist:

Eingabe: ein ungerichteter Graph mit Knotenmenge V, dessen Knoten mit den Farben Rot und
Grün gefärbt sind und eine natürliche Zahl n > 5

Aufgabe: entscheiden, ob es möglich ist, den Knoten Prioritäten zuzuordnen (d.h. Zahlen
», € {l,...,n}, ve V), so dass je zwei durch eine Kante verbundene Knoten verschie-
dene Priorität haben und die Priorität eines jeden roten Knoten höher ist als die Priorität
jedes grünen Knoten (d.h. für jeden roten Knoten u und jeden grünen Knoten v gilt p, > Dy)

Aufgabe 6 (Matrixarithmetik) : [68 PUNKTE]

Zur Erinnerung: Für zwei (quadratische) Matrizen A,B € R”*” mit A = (a, ,)ı<sijm undB=
(bi ;)1<ij<n (mit n2 1) ist

e die Summe A+ B definiert als die Matrix $ = (s; ;)Jı<ij«n mit s:; =; + bis:
e die Differenz A— B definiert als die Matrix D = (d; ;)ı<i,j<n mit d; = a; — bi,;, und

e das Pr odukt AB definiert als die Matrix P = (Pi, j)ı<i,j<n mit Pij > Vr-ı 0; 60%, (d.h. Pi,j
ist das Skalarprodukt der ö-ten Zeile von A mit der j-ten Spalte von B)..

Hinweis: In dieser Aufgabe nehmen wir an, dass n eine Zweierpotenz ist, d.h. n = 2* für eink > 0.

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

MADpDp(A, B,n)

/ Eingabe: Zwei Matrizen A, Be R"** mitn>1 und
A= (@,;j)ı<ijn und B= (b, ‚)ı<ijen Ä
N Ausgabe: Die Matrix 5S= (Si j)1<i,j<n mit $= A +B

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

(c) [4 Punkte] Geben Sie einen iterativen Algorithmus zur Multiplikation zweier n x n Matrizen
in Pseudo-Code an, der die Definition des Matrixprodukts direkt umsetzt:

MMULT(A, B,n)
/ Eingabe: Zwei Matrizen A, BE R**“* mitn>1 und
A= (ay)ı<sijn und B= (b,,)ı<i,<n
/ Ausgabe: Die Matrix P = (p,,)ı<ij<n mit P= AB

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

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

 

Wir wollen nun eine rekursive Strategie entwickeln, um für zwei Matrizen A, B e R”*” die Matrix
P e R”*" mit P = AB zu berechnen. Dazu zerlegen wir (falls n > 1 ist) A,B und P jeweils in
vier Blockmatrizen der Größe n/2 x n/2, d.h., wir schreiben

Aıı Aı2 Bıı Bı2 Pıı Pıa
A= ‚B = ‚P =

Aaı As2 Baı Ba2 Pı Pa
mit Au, Bis; Pi e Rr/2xn/2,
Mit dem Algorithmus

GETÜUPPERLEFT(X, n)

U Eingabe: Eine Matrix X = (2; j)ı1<i,j<n e Rrr mit n > 2
N Ausgabe: Die Matrix Z = (2,j)1<i,j<n/2 = Rr/2xn/2 mit ZA; Tij
1 fori=1ton/2
2 for j =1ton/2
3 u
4 return (2,;)1<ij<n/2

kann die Matrix A, aus der Matrix A bestimmt werden: Aı,ı = GETUPPERLEFT(A,n); ebenso
kann die Matrix B,,, aus der Matrix B bestimmt werden: Bıı = GETÜPPERLEFT(B,n).

(e) [2 Punkte] Bestimmen Sie die Laufzeit des Algorithmus beim Aufruf GETUPPERLEFT(A,n).

(f) [3 Punkte] Geben Sie einen Algorithmus GETUPPERRIGHT an mit dem die Matrix Aı.
(bzw. Bı.) aus der Matrix A (bzw. B) bestimmt werden kann:

GETÜUPPERRIGHT(X, n) Ä
// Eingabe: Eine Matrix X = (2; ;Jısi,j«n € R"" mitn>2
U Ausgabe: Die Matrix Z = (2 ;)ı<ijn/2 € Rr/2XR/?2 mit %i,j; = Tijtn/2

Wir nehmen an, dass uns zwei Algorithmen GETLOWERLEFT und GETLOWERRIGHT zur
Verfügung stehen für die gilt:

Asa,ı = GETLOWERLEFT(A, n),

Aoaa = GETLOWERRIGHT(A,n),
Ba,ı = GETLOWERLEFT(B,n), und
B22 = GETLOWERRICHT(B,n).

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

 

Weiterhin gibt es einen Algorithmus CoMPOSE der aus vier n/2 x n/2 Matrizen einenx n Matrix
zusammensetzt:

CoMPOSE(X1 1,X12, X21,X22,n)
N Eingabe: Vier Matrizen X11,X12,X21,X22 € R7?*"/? mitn>2

Xıı X
// Ausgabe: Die Matri 11 12
gabe: Die Matrix | Kt Kos

Man kann nun zeigen, dass gilt:

Pıı = AııBıı + Aı2Baı Pıa = AııBı2a + Aı2Ba2
Paı = AaıBı,ı + A22 Ba ı Pa = A2ıBıa + A2a2Ba.2

Auf dieser Darstellung basiert folgender Algorithmus:

MMULTR(A, B, n)
// Eingabe: Zwei Matrizen A,Be R” mitn>1 und
A= (a,;)ı<sijcn und B = (b, ;)1<ij<n
N Ausgabe: Die Matrix P = (p; s)i<i,j<n mit P= AB
fn==1
return (a1, ıbı.1)

/ Erstelle Aıı, Aı,., Aa 1, Aa € Rr/2xn/2 mit A= A 1
Ayı Ag2

Aıı = GETUPPERLEFT(A, n) |
Aıa = GETÜUPPERRIGHT(A, n)
Asa, = GETLOWERLEFT(A, rn)

Aa. = GETLOWERRIGHT(A, n)
/ Erstelle Bıı, Bı», Baı, Ba.2 E Rr/2xn/2 mit B — 5 1, |

Baı Ba2

9 Bıı = GETÜUPPERLEFT(B,n)
10 Bı2 = GETÜUPPERRIGHT(B,n)
11 Baı = GETLOWERLEFT(B,n)
12 Ba2 = GETLOWERRIGHT(B,n)
13 Pıı = MADpp(MMULTR(A, |, Bi, n/2), MMULTR(A;5», Ba1; n/2))
14 P. 12 = MADPD(MMULFR{A, |, Bi», n / 2), MMULTR(A; >, Ba», 1/ 2))
15 Pı = MADD(MMULTR (A; ı, Bı 1,n/2), MMULTR(A3,, Ba,ı,n/2))
16 P2 = MADpp(MMULTR(A; |, Bı», n/2), MMULTR(A3>, Ba», n/2))
17 4 Gib die Matrix A ne zurück

21 22

18 return CoMmPosE(P: 1; Pı2: Pa; Po2., n)

oO SI O0», © De

(g) [9 Punkte] Beweisen Sie, dass der Algorithmus MMULTR korrekt ist.

Fortsetzung nächste Seite!
Frühjahr 2020 Einzelprüfungsnummer: 66115 | Seite: 7

 

(h) [8 Punkte] Begründen Sie, dass die Laufzeit T(n) des Algorithmus beim Aufruf
MMULTR(A, B,n) folgender asymptotischer Rekursions(un)gleichung genügt:

T(n) = 8T(n/2) + O(n?) fürn >1 und T(n)=O() fürn=1.
Sie dürfen dabei annehmen, dass die Algorithmen GETUPPERLEFT, GETÜPPERRIGHT,

GETLOWERLEFT, GETLOWERRIGHT, MADD und COMPOSE so implementiert sind, dass
ihre asymptotische Laufzeit auf n x n Matrizen O(n?) ist.

(i) [9 Punkte] Wir betrachten die Rekursionsungleichung (für eine Konstante c > 0)
T(n) <8-T(n/2)+c-n?fürn>1 und T(n)<cfürn<1.
Beweisen Sie, dass daraus T(n) = O(n?) folgt.

Wir wollen eine bessere rekursive Strategie entwickeln, um zwei Matrizen zu multiplizieren. Volker
Strassen hat 1969 gezeigt, dass mit

M; := (Aıı + Aaa)(Bı,ı + Ba.) Ma := (Aa,ı + Aa2)Bı,ı
M3 := A, ı(Bı. — Ba.) Ma := Aaa(Ba.ı - Bı,ı)
M; := (A, + A12)Ba,2 Me := (Aa, — Aıı)(Bı,ı + Bi.)

Mr := (Aıa — Aaa)(Ba,ı + Ba.)

gilt, dass

P,ı=Mı+M.-M;+M7 Poa=M;s+M;
Pı=M+M; P2=Mı -M;+M;:+M

(j) [9+8 Punkte] Entwickeln Sie auf Basis dieser Identitäten einen rekursiven Algorithmus
MMuLTtVS zur Berechnung des Produktes zweier n x n Matrizen

MMULTVS (A, B, n)
// Eingabe: Zwei Matritzen A, B, e R”*? mitn 2 1 und
A = (a,,)ı<ijsnund B = (b,)ı<ij<n
// Ausgabe: Die Matrix P = (p,,)ısij<"nmit P=AB

dessen Laufzeit T(n) folgender asymptotischer Rekursions(un)gleichung genügt:

T(n) = 7: T(n/2) + O(n?) fürn >1 und T(n) = O(1) fürn =1.

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

 

Sie dürfen dabei wieder annehmen, dass die Algorithmen GETUPPERLEFT, GETÜUPPER-
RIGHT, GETLOWERLEFT, GETLOWERRIGHT, MADD und COMPOSE so implementiert
sind, dass ihre asymptotische Laufzeit auf n x n Matrizen O(n?) ist. Zudem steht Ihnen
ein Algorithmus MSuUB zur Subtraktion von Matrizen zur Verfügung:

MSUB (A, B, n)
// Eingabe: Zwei Matritzen A, B, e R”“? mitn 2 1 und
A= (a;,)ı Sij<n und B = (b,)ı SijSn
// Ausgabe: Die Matrix D = (d; )ı<;j<„mit D=A-B

Auch dessen asymptotische Laufzeit auf nx n Matrizen ist O(n?). Begründen Sie, warum die
Laufzeit Ihrer Implementierung von MMULTVS der o.g. Rekursions(un)gleichung genügt.

(k) [9 Punkte] Wir betrachten die Rekursionsungleichung (für eine Konstante c > 0)
Tvs(n) <7-Tys(n/2)+c-n? fürn>1 und Tys(n) <cfürn<1.

Beweisen Sie, dass Tys(n) = O(n!°&2 7).

Aufgabe 7 (Auftragsdisposition) [52 PUNKTE]

Gegeben sei eine Menge J = {l,...,n} von n Jobs. Jeder Job i € J hat eine Startzeit s; € R>o,
eine Endzeit f; € Rso mit fi > s; und einen Wert w, € R>o. Wir nehmen im Folgenden an, dass
alle Zeiten sı,...,$n, fi,--- , /n paarweise verschieden sind. Für eine Menge 5 C J von Jobs ist
der Gesamtwert definiert als
w(S ) = > Wi.
ieS

Eine Menge von Jobs M C J wird kompatibel genannt, falls keine zwei verschiedenen Jobs
l,m € M existieren, welche sich zeitlich überlappen. Das heißt für alle !,m e M mit ! £ m silt
dann entweder fm < sı oder fı < sm-

Gesucht ist eine Menge $ C J von kompatiblen Jobs, deren Gesamtwert w(S) marimal ist.
Diesen Wert bezeichnen wir mit OPT(J).

Wir nehmen im Folgenden an, dass die Jobs nach ihren Endzeiten f; aufsteigend sortiert sind und
setzen fo := 0. Nun betrachten wir für0 <i<n die Menge

„=4jeJf;< fi}

von Jobs, welche alle zur Zeit f; beendet sind.

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

(a) [2 Punkte] Zeigen Sie, dass Jo = ® und J; = {1,2,...,i} fürl<i<n.

Für 0 <i<n sei OPT(i) der optimale Gesamtwert für die Menge J,;, d.h.
OPT) := OPT(J,;)

(b) [1 Punkt] Welcher Zusammenhang besteht zwischen den OPT(i) und dem gesuchten Wert
OPT(J)?

(c) [2 Punkte] Was sind die Werte für OPT(0) und OPT(1)?

Sei p(j) der Job mit dem größten Index kleiner als j, welcher kompatibel mit Job 5 ist. Mit anderen
Worten, das größte k < j, für welches f; < s; gilt. Sollte ein solcher Job nicht existieren, so ist
p(j) := 0 per definitionem.

(d) [9 Punkte] Zeigen Sie, dass für © >21 gilt
OPT{ti) = max(OPT(i - 1),w +OPT(pfi))).

(e) [4 Punkte] Formulieren Sie auf Basis dieser Rekursionsgleichung einen rekursiven Algorith-
mus zur Berechnung von OPTt) in Pseudocode:

DispRec(S, F, W,i, P)
/ Eingabe: Eine Instanz des Dispositionsproblems, beschrieben durch
N die Folge $ = (sı,...,3„) der Startzeiten
N die Folge F=(fı,..., fn) der Endzeiten mit fi <---< fu
N die Folge W = (wı,...,w„) der Werte
A ein Indx0 <i<n
N die Folge P = (p(1),...,p(n))
/ Ausgabe: OPT(t)

(f) [4 Punkte] Beschreiben Sie eine Menge von n Jobs durch die Angabe der Start- und Endzeiten
S1, +. 81 Fir ---, fn für die gilt, dass für ale 1<j<oagil:p(j)=j-1.

(g) [4 Punkte] Wir betrachten nun eine Eingabe „der Länge n“ wie aus der vorigen Aufgabe
für die also gilt, dass für alle 1<j <n gilt: p(j) = j — 1. Begründen Sie, dass für so eine
Eingabe die Laufzeit T’(n) des rekursiven Algorithmus beim Aufruf DispRec($, F,W,n, P)
folgender asymptotischer Rekursionsgleichung genügt:

T(n)=2T(n-1)+9(1)
(mit T(n) = 9(1) fürn = O(1))

(h) [2+2 Punkte] Wir betrachten die Rekursionsungleichung (für eine Konstante c > 0)
T(n)>2-T(n-1)+cfün>1 wd T(n)>cfürn<i.

Beweisen Sie, dass T’(n) = N(2”).

Argumentieren Sie damit, warum eine direkte Implementierung der Rekursion im Allgemei-
nen nicht effizient ist.

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

(i) [4+3+3 Punkte] Geben Sie einen Algorithmus in Pseudocode an, der für1 <j <n die
Werte p(j) berechnet:

COMPUTEP(S, F,W)
// Eingabe: Eine Instanz des Dispositionsproblems, beschrieben durch
N die Folge $S = (sı,...,s„) der Startzeiten
N die Folge F = (fı,..., fa) der Endzeiten mit fi <---< fi
N die Folge W = (wı,...,w„) der Werte
// Ausgabe: Die Folge P = (p(1),...,p(n))

Begründen Sie, warum Ihr Algorithmus korrekt ist und analysieren Sie dessen Laufzeit.

(j) [4+6+2 Punkte] Formulieren Sie ein dynamisches Programm zur Berechnung von OPT(n)
in Pseudocode:

DispDP($, F,W, P)
/ Eingabe: Eine Instanz des Dispositionsproblems, beschrieben durch
N die Folge $ = (sı,...,s„) der Startzeiten
N die Folge F= (fı,..., fn) der Endzeiten mit fi <---<f,
N die Folge W = (wı,...,w„) der Werte
N die Folge P = (p(1),...,p(n))
/ Ausgabe: OPT(n)

Begründen Sie, warum Ihr Algorithmus korrekt ist und analysieren Sie dessen Laufzeit.

-11-
Frühjahr 2020 Einzelprüfungsnummer: 66115 Seite: 11

 

Thema Nr. 2
(Aufgabengruppe)

Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten!

Aufgabe 1 (Aussagen) [18 PUNKTE]

Im Folgenden seien L und L’ formale Sprachen. Zeigen oder widerlegen Sie die folgenden Aussagen
(die jeweiligen Beweise sind sehr kurz).

Schreiben Sie zunächst zur Aussage “Richtig” oder “Falsch” und dann Ihre Begründung.

(a) [6 Punkte] Sind Z und L’ regulär, so ist auch L \ L’ regulär.
(b) [6 Punkte] Sind Z und L’ kontextfrei, so ist auch ZL \ L’ kontextfrei.

(c) [6 Punkte] Ist Z entscheidbar und L’ semi-entscheidbar, so ist L \ L’ semi-entscheidbar.

Aufgabe 2 (Automatentheorie und reguläre Sprachen) [35 PUNKTE]

Betrachten Sie den regulären Ausdruck @ = (OU 1)*(00 U 11)(0 U1) und die zugehörige Sprache
A=Lf(a).
(Alternative Schreibweise & = (0 + 1)*(00+11)(0+1).)

(a) [3 Punkte] Beschreiben Sie Gestalt der Wörter der Sprache A in Worten.

(b) [5 Punkte] Geben Sie einen nicht-deterministischen endlichen Automaten M mit L(M) =
L(c) an.

(c) [12 Punkte] Überführen Sie den Automaten M aus Teilaufgabe (b) mittels der Teilmengen-
konstruktion in einen deterministischen endlichen Automaten M’ mit L(M’) = L(M). Eine
Darstellung des Automaten in Tabellenform ist ausreichend.

(d) [12 Punkte] Betrachten Sie die zur Sprache A gehörende Myhill-Nerode-Relation =, und
die folgenden Wörter:
wo = 000, wı = 001, wa = 010, wa = 011, wı = 100, ws = 101, we = 110, wz = 111

Zeigen Sie, dass die Wörter wo, ..., w7 paarweise nicht äquivalent sind, also in verschiedenen
Aquivalenzklassen von =4 liegen.

Hinweis: Es ist nicht nötig alle 23 möglichen Paare von Wörtern einzeln zu betrachten;
überlegen Sie, wie jeweils mehrere Paare von Wörtern gleichzeitig betrachtet werden können.

(e) [3 Punkte] Was folgt aus Aufgabenteil (d) für die Anzahl der Zustände eines deterministi-
schen endlichen Automaten, der A erkennt”? Begründen Sie Ihre Antwort.

Fortsetzung nächste Seite!
Frühjahr 2020 Einzelprüfungsnummer: 66115 Seite: 12

 

Aufgabe 3 (Kontextfreie Sprachen) [20 PUNKTE]

(a) [4 Punkte] Ist die folgende Sprache Lı = {a"**b*t! |n > 2} über dem Alphabet % = {a,b}
kontextfrei?

Falls ja, geben Sie eine kontextfreie Grammatik für L, an, falls nein, eine kurze Begründung
(ein vollständiger Beweis ist hier nicht gefordert).

(b) [12 Punkte] Geben Sie einen Kellerautomaten (PDA) formal an, der die Sprache L2 =
{wıwaw3 | wı,wa,w3 € D*\ {A} und wı = wäY} € CFL über dem Alphabet % = {0,1}
akzeptiert.

Dabei bezeichnet X das leere Wort und w3° bezeichnet das Wort ws rückwärts gelesen. Bei
Akzeptanz einer Eingabe soll sich der PDA in einem Endzustand befinden und der Keller
geleert sein.

(c) [4 Punkte] Beschreiben Sie in Worten die Arbeitsweise Ihres PDA aus Aufgabenteil (b).

Aufgabe 4 (Berechenbarkeitstheorie) [27 PUNKTE]

Sei A= {{M) | M ist Turingmaschine, die bei Eingabe 101 hält }. Dabei bezeichnet (M) die
Gödelnummer der Turingmaschine M.

(a) [12 Punkte] Zeigen Sie, dass A unentscheidbar ist.
(b) [5 Punkte] Zeigen Sie, dass A semi-entscheidbar ist.
(c) [10 Punkte] Ist das Komplement A° von A entscheidbar? Ist es semi-entscheidbar? Begründen

Sie Ihre Antworten.

Hinweis: Sie können die Aussagen aus Teilaufgabe a) und b) verwenden, auch wenn Sie sie
nicht bewiesen haben.

Aufgabe 5 (Komplexitätstheorie) [20 PUNKTE]

Sei G = (V, E) ein ungerichteter Graph. Eine 2-Kreisüberdeckung von G besteht aus zwei einfachen
Kreisen C| und Ca in G, sodass jeder Knoten von G in mindestens einem der Kreise C\ oder O5
enthalten ist.

Das Problem 2-KREISÜBERDECKUNG besteht darin, für einen gegebenen Graphen G = (V, E) zu
entscheiden, ob G eine 2-Kreisüberdeckung besitzt.

(a) (4 Punkte] Geben Sie eine 2-Kreisüberdeckung für den folgenden Graph an.

 

Fortsetzung nächste Seite!
Frühjahr 2020 Einzelprüfungsnummer: 66115 Seite: 13

 

(b) [6 Punkte] Zeigen Sie, dass das Problem 2-KREISÜBERDECKUNG in N P liegt.

(c) [10 Punkte] Zeigen Sie, dass das Problem 2-KREISÜBERDECKUNG N P-vollständig ist.

Hinweis: Sie können ohne Beweis benutzen, dass das Problem HAMILTONKREIS, das darin
besteht zu entscheiden ob ein gegebener Graph einen einfachen Kreis besitzt, der alle Knoten
enthält, NP-schwer ist.

Aufgabe 6 (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 © — 1 schon sortiert ist. Dann
speichert Insertion-Sort das :-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 7 (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: 66115 Seite: 14

 

 

 

 

Nr. 8
. Nr.
Distanz: 11 -
15 21; Distanz:
Nr. 7
Distanz: 6
\ 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)

=

= new PriorityQueue(V, d)

hile not Q.Empty() do

. u = Q.ExtractMin()
S=SUuf{u}
foreach v € Adj[u] do

| Relax(u,v, w)

_ u.color = black

 

 

 

 

Initialize(Graph G, Vertex s)

foreach vweV do
u.color = white
u.d = 00

 

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: 66115 Seite: 15

 

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

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

 

Tr
e blau
_ —ä u a —- ii --— dir .————-
x-Achse a2 A rot

 

Die Eingabe wird in einem Feld A übergeben. Jeder Punkt Alö] mit 1<i<n hat eine
x-Koordinate Alil.x und eine Farbe Alil.color € { rot, blau }. Das Feld A ist nach x-Koordinate
sortiert, d.h. es gilt A[1].x < A[2]l.x <--- < Aln].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(r) Zeit berechnen kann. (Ihr Algorithmus darf also insbesondere nicht Laufzeit
O(n) haben.)

Aufgabe 9 (Heaps) [20 PUNKTE]

Sei H ein Max-Heap, der n Elemente speichert. Für ein Element v in H 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 Jr 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 ZH’ ein Feld der Länge n. Geben Sie einen Algorithmus an, der in Linearzeit
testet, ob H’ ein Max-Heap ist.

Fortsetzung nächste Seite!
Frühjahr 2020 Einzelprüfungsnummer: 66115 Seite: 16

 

Aufgabe 10 (Binärbäume) [30 PUNKTE]

Sei B ein binärer Suchbaum. In jedem Knoten v von B wird ein Schlüssel v.key € N gespeichert
sowie Zeiger v.left, v.right und v.parent auf sein linkes Kind, auf sein rechtes Kind und auf seinen
Elternknoten. Die Zeiger sind nel, wenn der entsprechende Nachbar nicht existiert. Für zwei Knoten
u und v ist wie üblich der Abstand die Anzahl der Kanten auf dem kürzesten Pfad von uw nach v.

Für einen Knoten w von B sei B(w) der Teilbaum von B mit Wurzel w. Für zwei Knoten u und v
von B ist w ein gemeinsamer Vorfahre, wenn u und v in B(w) liegen. Wir suchen den niedrigsten
gemeinsamen Vorfahren ngV(u,v) von u und v, also einen gemeinsamen Vorfahren w, so dass für
jeden Vorfahren w’ von u und v gilt, dass w in B(w’) liegt. Wir betrachten verschiedene Szenarien,
in denen Sie jeweils den niedrigsten gemeinsamen Vorfahren von u und v berechnen sollen.

(a) [10 Punkte] Wir bekommen u und v als Zeiger auf die entsprechenden Knoten in B gelie-
fert. Beschreiben Sie in Worten und in Pseudocode einen Algorithmus, der den niedrigsten
gemeinsamen Vorfahren von u und v berechnet. Analysieren Sie die Laufzeit Ihres Algorith-
mus.

(b) [10 Punkte] Wir bekommen u und v wieder als Zeiger auf die entsprechenden Knoten in B
geliefert. Seien d, und d, die Abstände von u bzw. v zum niedrigsten gemeinsamen Vor-
fahren von u und v. Die Laufzeit Ihres Algorithmus soll O(max{d,,d,}) sein. Dabei kann
Ihr Algorithmus in jedem Knoten v eine Information v.info speichern. Skizzieren Sie Ihren
Algorithmus in Worten.

(c) [10 Punkte] Wir bekommen die Schlüssel u.key und v.key. Die Laufzeit Ihres Algorithmus
soll proportional zum Abstand der Wurzel von B zum niedrigsten gemeinsamen Vorfahren
von u und v sein. Skizzieren Sie Ihren Algorithmus in Worten.

vr