Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 66115 2018 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Theoret. Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 12 Bitte wenden! Herbst 2018 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’ C %* formale Sprachen. Falls L regulär und L’ semi-entscheidbar (= rekursiv aufzählbar) ist, dann ist der Durchschnitt LM L’ regular. (b) [6 PUNKTE] Die Menge aller semi-entscheidbaren (= rekursiv-aufzählbaren) Sprachen ist überabzählbar unendlich. (c) [6 PUNKTE] Angenommen es gilt P # NP. Dann ist jede formale Sprache Le NP\P sicher nicht regulär. (d) [6 PUNKTE] Das Halteproblem liegt in der Klasse NP. Aufgabe 2 (Reguläre Sprachen) [35 PUNKTE] (a) [10 PUNKTE] Es sei ZL C {5,7}* die von dem folgenden nichtdeterministischen Automaten akzeptierte Sprache. Geben Sie einen Automaten für das Komplement {5,7}*\ L der Sprache L an. 5,7 90:30 O=@® (b) [15 PUNKTE] Minimieren Sie den deterministischen Automaten A= ({g,7, 5,¢, u, v}, {0, 1}, 6,9, {¢, 5, u}) mit der folgenden tabellarisch gegebenen Zustandsüberführungsfunktion: 6/01 q\s v ulr q vir ft Machen Sie dabei Ihren Rechenweg deutlich. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 3 (c) [10 PunKTe] Beweisen Sie, dass die folgende formale Sprache über % = {a,b} nicht regulär ist: L = {b"a” | 2n # m} Aufgabe 3 (Kontextfreie Sprachen) [25 PUNKTE] (a) [10 PunKTe] Entwerfen Sie eine kontextfreie Grammatik für die folgende kontextfreie Sprache über dem Alphabet © = {a, b,c}: L={w*y|keN,|w|.= |ula}. (Hierbei bezeichnet |u|, die Anzahl des Zeichens x in dem Wort u, und es gilt 0 e N.) Erklären Sie den Zweck der einzelnen Nichtterminale (Variablen) und der Grammatikregeln Ihrer Grammatik. (b) [10 PUNKTE] Betrachten Sie die folgende kontextfreie Grammatik G = ({S, X,Y, Z}, {z, y}, P, S) mit den Produktionen P: +> ZX|y S X + ZS|SS\z2 Y +> SX|YZ Z > XX|XS Benutzen Sie den Algorithmus von Cocke-Younger-Kasami (CYK) um zu zeigen, dass das Wort zzzyr zu der von G erzeugten Sprache L(G) gehört. (c) [d PUNKTE] Geben Sie eine Ableitung des Wortes zzryx mit G an. Aufgabe 4 (Entscheidbarkeit) [36 PUNKTE] (a) [8 PUNKTE] Benutzen Sie den Satz von Rice um zu beweisen, dass das folgende Problem nicht entscheidbar ist: Eingabe: eine (geeignet codierte) Turingmaschine M, die eine (möglicherweise partielle) Funktion fv : N— N berechnet; Aufgabe: entscheiden, ob esein ne N mit fu(n) = 42 gibt. (b) [8 PUNKTE] Zeigen Sie, dass das Problem aus (a) semi-entscheidbar (= rekursiv-aufzählbar) ist. (c) [20 PUNKTE] Zeigen Sie mit Hilfe einer Reduktion, dass das folgende Problem nicht entscheidbar ist: Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 4 Eingabe: zwei (geeignet codierte) Turingmaschinen M, und Ms; Aufgabe: entscheiden, ob für jedes Eingabewort w Mı gestartet auf w genau dann hält, wenn Ma gestartet auf w hält. (Für die Reduktion kann benutzt werden, dass das Problem zu entscheiden, ob eine gegebene Turingmaschine auf jedes Eingabewort hält, unentscheidbar ist.) Aufgabe 5 (AVL Bäume) [54 PUNKTE] Hinweis: Wir betrachten in dieser Aufgabe binäre Suchbäume, bei denen jeder innere Knoten genau zwei Kinder hat. Schlüssel werden nur in den inneren Knoten gespeichert - die Blätter speichern keinerlei Informationen. 9.1 9.2 9.3 5.4 9.0 9.6 [2 PUNKTE] Welche Eigenschaften muss ein binärer Suchbaum haben, damit er ein AVLBaum ist? [8 PUNKTE] Mit n(h) bezeichnen wir die minimale Anzahl innerer Knoten eines AVL-Baums der Höhe Ah. (a) [2 PUNKTE] Begründen Sie, dass n(1) = 1 und n(2) = 2. (b) [3 PUNKTE] Begründen Sie, dass n(h) = 1+ n(h — 1) +n(h— 2). (c) [3 PUNKTE] Folgern Sie, dass n(h) > 2271. [2 PUNKTE] Warum ist die Héhe jedes AVL-Baums mit n inneren Knoten O(logn)? [16 PUNKTE] Fügen Sie die Elemente (45, 16,79, 31,51,87,49,61) in der angegebenen Reihenfolge in einen anfangs leeren binären Suchbaum ein (ohne Rebalancierungen). Zeichnen Sie den resultierenden Suchbaum nach jeder Einfügeoperation. [2 PUNKTE] Ist der resultierende Suchbaum aus Teilaufgabe 5.4 ein AVL-Baum? Begründen Sie Ihre Antwort. [12 PUNKTE] Das Einfügen in einen AVL-Baum funktioniert (zunächst) wie beim binären Suchbaum durch Erweitern eines äußeren Knotens w: vor dem Einfügen von 54 nach dem Einfügen von 54 Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 5 9.7 9.8 9.9 5.10 Anschließend wird die AVL-Baum Eingenschaft (falls notwending) durch eine (Doppel-)Rotation wiederhergestellt: Wenn z der erste Knoten auf dem Pfad P von w zur Wurzel ist, der nicht balanciert ist, y das Kind von z auf P und r das Kind von y auf P, und wenn (a, b,c) die Inorder-Reihenfolge von x, y, 2 ist, dann führen wir die Rotation aus, die benötigt wird, um b zum obersten Knoten der drei zu machen. Die folgende Illustration zeigt den Fall, dass key(y) < key(x) < key(z), d.h. (a,b,c) = (y,x,z), wobei w ein Knoten in Ty ist. Sei Ah die Höhe des Teilbaums 73. Für i = 0,1,2 sei h; die Höhe des Teilbaums T; und für v = 2,y,z sei h, die Höhe des Teilbaums mit der Wurzel v vor der Restrukturierung. Begründen Sie, dass (a) [2 PUNKTE] ho = h (b) [2 PUNKTE] hy =h—-1 (c) [2 PUNKTE] hg =A (d) [2 PUNKTE|] h, =h+1 (e) [2 PUNKTE| hy =h+2 (f) [2 PUNKTE] h, =h+3 [3 PUNKTE] Welche Höhe haben die Teilbäume mit den Wurzeln x, y, z nach der Restrukturierung? Begründen Sie Ihre Antworten. [4 PUNKTE] Begründen Sie, dass die oben gezeigte Doppelrotation die AVL-BaumEigenschaft wiederherstellt. [3 PUNKTE] Beschreiben Sie, wie ein binärer Baum der Höhe h in einem Array repräsentiert werden kann. Wie viel Speicherplatz ist für so eine Darstellung erforderlich? [2 PUNKTE] Warum verwendet man bei der Implementierung von AVL-Bäumen eine verzeigerte Struktur und nicht eine Array-basierte Repräsentation? Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 6 Aufgabe 6 (Ein Spiel mit Zahlen) [51 PUNKTE] Wir spielen folgendes Spiel: Gegeben sei eine Folge S = (2,...,2%,) von n Zahlen. In einer Runde dürfen wir in 5 zwei beliebige benachbarte Zahlen xx, £k+ı entfernen und durch die Zahl 2-(2&k + Zk+ı) ersetzen, ohne die Reihenfolge der anderen Zahlen in 5 zu verändern. Wir erhalten so eine neue Folge S’ = (x},...,2;,_,) von n — 1 Zahlen, wobei x, = 2; für 1 (6,14,6,3) — (6,14,18) — (40,18) — (116). Ein Spiel können wir auch als eine Klammerung der Elemente von 5 interpretieren: Anstatt in einer Runde xz, 2,41 zu entfernen und durch 2 - (x, + 2,41) zu ersetzen, ersetzen wir die beiden Zahlen durch den geklammerten Ausdruck (2% * 2,41). In unserem Beispiel sieht das so aus: (2,1,3,4,1,2,3) — ((2*1),3,4,1,2,3) > ((2*1),3,4, (1*2),3) — ((2 * 1), (3 * 4), (1 * 2) * 3) > ((2*1),(3*4),((1*2) *3)) — (((2 * 1) * (3 * 4)), (1 * 2) *3)) ((((2 * 1) * (3 * 4)) « ((1 * 2) *3))). Nach n — 1 Runden entsteht ein Klammerausdruck K auf den Elementen von S. Wenn wir den Operator * definieren als xy := 2- (x+y), dann ist der Wert w(K) dieses letzten Klammerausdrucks gerade der Gewinn des Spiels: w((((2 * 1) * (3 * 4)) « ((1 * 2) * 3))) = 116. Einen Klammerausdruck der den größten Gewinn erzielt nennen wir optimal. Für 1L 1 (mit T(1) = @(1)) Begründen Sie, dass dem so ist. [6 PUNKTE] Finden Sie eine (möglichst kurze) Eingabefolge $ an der deutlich wird, dass sich die Teilprobleme der Rekursion zur Berechnung von W(1,n) überlappen. Illustrieren Sie das Phänomen, indem Sie den Rekursionsbaum zeichnen und die mehrfach berechneten Teilprobleme markieren. | [3 PUNKTE] Begründen Sie, dass T(n) = 2T(n — 1) + Q(1) fir n > 1. [4 PUNKTE] Begründen Sie, dass T(n) = 0(2"). [4 PUNKTE] Wie sieht eine Reihenfolge aus, in der die W(i, 7) bottom-up berechnet werden können, die mit obiger Rekursionsgleichung kompatibel ist? Begründen Sie Ihre Antwort. [6 PUNKTE] Geben Sie ein dynamisches Programm WINGAMEDP(S) in Pseudocode an, das den Wert W(1,n) in polynomieller Zeit berechnet. Hinweis: Wenn Sie die vorige Aufgabe nicht lösen konnten, verwenden Sie die lexikographische Reihenfolge zur bottom-up Berechnung der W(i, 7). [6 PUNKTE] Begründen Sie, warum Ihr Algorithmus in Teilaufgabe 6.8 korrekt ist. [4 PUNKTE] Bestimmen Sie die asymptotische Laufzeit und den Speicherplatzbedarf Ihres Algorithmus aus Teilaufgabe 6.8 möglichst genau. Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 8 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1 (Reguläre Sprachen) [22 PUNKTE] (a) [6 PUNKTE] Geben Sie alle Nerode-Äquivalenzklassen von L((aa)*) über dem Alphabet {a, b} an. Geben Sie für jede Klasse 3 Wörter an, die zu dieser gehören. (b) [6 PunKTE] Geben Sie einen DEA mit maximal 4 Zuständen an, zu dem es keinen äquivalenten DEA mit höchstens einem akzeptierenden Zustand gibt. Verwenden Sie ein Alphabet mit höchstens zwei Symbolen. Warum erfüllt Ihr DEA diese Eigenschaft? (c) [10 PUNKTE] Ist L, = {ab |i+5j =} U L((a+ c)*) U L((b+c)*) eine reguläre Sprache? Geben Sie einen Beweis für Ihre Antwort. Um Regularität zu zeigen reicht die Angabe eines Automaten oder regulären Ausdrucks, der die Sprache akzeptiert. Aufgabe 2 (Kontextfreie Sprachen) [22 PUNKTE] (a) [6 PUNKTE] Entscheiden Sie mit Hilfe des CYK-Algorithmus, ob das Wort acbaabaa in der Sprache der nachfolgenden Grammatik enthalten ist. S—+c|BA A-alb!CB B-AA|AS CSA (b) [4 PUNKTE] Seien L; und Le kontextfreie Sprachen. Ist Li U La eine entscheidbare Sprache? Ist Ly M La eine entscheidbare Sprache? Begründen Sie Ihre Antworten. (c) [6 PunKTe] Sei L3 die Komplementsprache von L = {a"b"c” | n € N} über Alphabet {a,b,c}, d.h., Lz = {we {a,b,c}* | w& L}. Ist Lz kontextfrei? Geben Sie einen Beweis für Ihre Antwort. Um Kontextfreiheit zu zeigen reicht die Angabe eines Automaten oder einer Grammatik, die die Sprache akzeptiert. Bitte erläutern Sie dann Ihre Konstruktionsidee. Sie müssen nicht formal beweisen, dass Ihr Automat oder Ihre Grammatik korrekt ist. (d) [6 PUNKTE] Sei L, die Sprache {a™ | n e N} über Alphabet {a}. Ist L4 kontextfrei? Geben Sie einen Beweis für Ihre Antwort. Um Kontextfreiheit zu zeigen reicht die Angabe eines Automaten oder einer Grammatik, die die Sprache akzeptiert. Bitte erläutern Sie dann Ihre Konstruktionsidee. Sie müssen nicht formal beweisen, dass Ihr Automat oder Ihre Grammatik korrekt ist. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 9 Aufgabe 3 (Entscheidbarkeit) [16 PUNKTE] Wir bezeichnen mit M„ die Turingmaschine, die von einem Wort w kodiert wird. (a) [8 PUNKTE] Ist die Sprache {w | M„ hält auf jeder Eingabe nach maximal 42 Schritten an} entscheidbar? (b) [8 PUNKTE] Ist die Sprache {w | M, halt auf Eingabe e nach einer geraden Anzahl von Schritten an} entscheidbar? Beweisen Sie Ihre Antwort. Aufgabe 4 (Komplexität) [10 PUNKTE] Wir betrachten ungerichtete Graphen G = (V, E), wo E eine Teilmenge E. hat, die wir exklusive Kanten nennen. Eine beschränkte Überdeckung von G ist eine Teilmenge U von V, so dass - jeder Knoten einen Nachbarknoten in U hat oder selbst in U liegt (für jeden Knoten u e V\U gibt es einen Knoten v € U mit (u,v) € E) und - für jede exklusive Kante (u,v) € E. genau einer der Knoten u, v in U liegt. Betrachten Sie nun die folgenden Entscheidungsprobleme: 3SAT Gegeben: Aussagenlogische Formel p in 3KNF Gefragt: Hat o eine erfüllende Belegung? BÜ Gegeben: Graph G = (V, E), exklusive Kantenmenge E. CE undkeN Gefragt: Hat G eine beschränkte Überdeckung U mit |U| < k? Beweisen Sie, dass BÜ NP-vollständig ist. Sie dürfen dabei annehmen, dass 3SAT NP-vollständig ist. Aufgabe 5 (Studienzeitoptimierung) [45 PUNKTE] Für den Bachelorstudiengang Informatik an Ihrer Hochschule werden die Module als Knoten eines gerichteten Graphen G = (V, E) modelliert. Es führt eine Kante (u,w) von Modul u zu Modul w genau dann, wenn der (erfolgreiche) Abschluss von Modul u notwendige Voraussetzung für die Teilnahme an Modul w ist. Der Einfachheit halber machen wir zwei Annahmen: Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 10 1. Jedes Modul dauert genau ein Semester. 2. In jedem Semester werden alle Module des Studiengangs angeboten. Wenn k die Länge des längsten Pfades in G ist, dann ist die Mindeststudiendauer k +1 Semester. Ihre Aufgabe ist es nun, den längsten Pfad in G zu berechnen und dafür einen möglichst eflizienten Algorithmus zu entwickeln. Zunächst folgen einige Tipps, dann drei Fragen als Vorüberlegung. Anschließend geht es zur Implementierung. Tipps: 1. Der Graph ist zyklusfrei. 2. Der Graph ist kein gerichteter Wald, d.h. es kann Knoten geben, die mehrere Vorgänger haben. (a) [5 PUNKTE] Von welchen Knoten aus sollte die Suche nach dem längsten Pfad beginnen? Begründen Sie Ihre Antwort. (b) [5 PUNKTE] Beschreiben Sie, wie man induktiv für einen beliebigen Knoten v die Länge des längsten Teilpfades bis zu diesem Knoten aus der maximalen Pfadlänge zu allen Vorgängerknoten berechnen kann. Beschreiben Sie die Umstände der Induktionsverankerung. (c) [5 PUNKTE] Welches ist eine sinnvolle Reihenfolge, in der die Knoten von G bei der Durchführung des Algorithmus abgearbeitet werden? Begründen Sie Ihre Antwort. (d) |25 PUNKTE] Formulieren Sie einen Algorithmus, der Ihnen die minimale Studiendauer berechnet. Geben Sie zudem die asymptotische Laufzeit Ihres Algorithmus mittels O-Notation an. (e) [5 PUNKTE] Wie ändert sich die Problemstellung, wenn es Module gibt, die nur im Sommer- bzw. nur im Wintersemester angeboten werden? Müssen Sie den Algorithmus dafür abändern? Begründen Sie Ihre Antwort. (Annahme: Das Studium kann sowohl zum Sommersemester als auch zum Wintersemester aufgenommen werden.) Aufgabe 6 (Backtracking) [30 PUNKTE] Ein sehr bekanntes Optimierungsproblem ist das sogenannte Rucksackproblem: Gegeben ist ein Rucksack mit der Tragfähigkeit B. Weiterhin ist eine endliche Menge von Gegenständen mit Werten und Gewichten gegeben. Nun soll eine "Teilmenge der Gegenstände so ausgewählt werden, dass ihr Gesamtwert maximal ist, aber ihr Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 11 Mathematisch exakt kann das Rucksackproblem wie folgt formuliert werden: Gegeben ist eine endliche Menge von Objekten U. Durch eine Gewichtsfunktion w : U + R* wird den Objekten ein Gewicht und durch eine Nutzenfunktion v : U — R* ein festgelegter Nutzwert zugeordnet. Des Weiteren gibt es eine vorgegebene Gewichtsschranke B € R*. Gesucht ist eine Teilmenge K CU, die die Bedingung Y,.x w(u) < B einhält und die Zielfunktion Y,.x v(u) maximiert. Das Rucksackproblem ist NP-vollständig (Problemgröße ist die Anzahl der Objekte), sodass es an dieser Stelle wenig Sinn macht, über eine effiziente Lösung nachzudenken. Lösen Sie das Rucksackproblem daher mittels Backtracking und formulieren Sie einen entsprechenden Algorithmus. Gehen Sie davon aus, dass die Gewichtsschranke B sowie die Anzahl an Objekten N beliebig, aber fest vorgegeben sind. Das Programm soll folgende Ausgaben liefern: 1. Maximaler Nutzwert, der durch eine Objektauswahl unter Einhaltung der Gewichtsschranke B erreicht werden kann. 2. Das durch die maximierende Objektmenge erreichte Gesamtgewicht. 3. Diejenigen Objekte (Objektnummern) aus U, die zur Maximierung des Nutzwerts beigetragen haben. Aufgabe 7 (O-Nation) [20 PUNKTE| (a) Beweisen Sie die folgenden Aussagen formal nach den Definitionen der O-Notation oder widerlegen Sie sie. i. [5 PUNKTE] O(n - log. n) C O(n- (logy n)*) ii. [5 PUNKTE] 2"*1 € O(2”) (b) Bestimmen Sie eine asymptotische Lösung (in 8-Schreibweise) für die folgende Rekursionsgleichung: [10 PunKTE] T(n)=4:T(3)+n? Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 66115 Seite: 12 Aufgabe 8 (Sortierverfahren) [25 PUNKTE] Gegeben sei das folgende Feld A mit 7 Schlüsseln: [15, 4, 10, 7, 1,8, 10] (a) [10 PUNKTE] Sortieren Sie das Feld mittels des Sortierverfahrens Bubblesort. Markieren Sie jeweils, welche zwei Feldwerte verglichen werden und geben Sie den Zustand des gesamten Feldes jeweils neu an, wenn Sie eine Vertauschung durchgeführt haben. (b) [10 PunKTe] Sortieren Sie das Feld mittels des Sortierverfahrens Selectionsort. Markieren Sie jeweils, welche zwei Feldwerte verglichen werden und geben Sie den Zustand des gesamten Feldes jeweils neu an, wenn Sie eine Vertauschung durchgeführt haben. (c) [5 PUNKTE] Vergleichen Sie beide Sortierverfahren hinsichtlich ihres Laufzeitverhaltens im best case. Welches Verfahren ist in dieser Hinsicht besser, wenn das zu sortierende Feld anfangs bereits sortiert ist? Begründen Sie Ihre Antwort.