Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: _ Herbst 46115 2015 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: 9 Bitte wenden! Herbst 2015 Einzelprüfungsnummer: 46115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Die Sprache L über dem Alphabet © = {a,b} enthält alle Wörter, die das Wort baab oder das Wort abba oder beide enthalten. Z.B. ist baababb € L, aber babababa ¢ L. 1. Geben Sie einen regulären Ausdruck für L an. 2. Konstruieren Sie einen nichtdeterministischen endlichen Automaten mit höchstens 8 Zuständen für L. 3. Konstruieren Sie einen deterministischen Automaten für Z mit der Potenzmengenkonstruktion. Sie dürfen sich wie üblich auf die erreichbaren Zustände beschränken. 4. Konstruieren Sie den Minimalautomaten für L. Sie können entweder das übliche Verfahren anwenden und Ihre Schritte geeignet dokumentieren, oder aber den Minimalautomaten direkt angeben und geeignet begründen, dass es sich um den richtigen Automaten handelt. Aufgabe 2: Beim Postschen Korrespondenzproblem (PCP) ist bekanntlich eine Liste von Paaren (u1,U1),---, (Un, Un) mit u,v; € X* für ein Alphabet U gegeben. Zum Beispiel (u1,vı) = (b, bab) und (u2, v2) = (ba, aa) und (ug, v3) = (abb, bb), wobei hier also n = 3 und D = {a,b} sind. Gefragt ist, ob es eine Indexfolge 71, i2,...,in mit 7, T set: AAxintx T > AA size: AA > int delete: AAx int > AA axs size(create) =0 get(create, i) = null delete(create, i) = create end AA b) Ergänzen Sie die fehlenden Methoden so, dass die folgende Klasse genau das Verhalten des obigen adt wiedergibt. Sie dürfen dabei keine anderen Datenstrukturen verwenden, also insbesondere auch keine HashMap aus der Java-API. public class AA { private int key; private T value; private AA tail; private AA(int key, T value, AA tail) { this.key = key; this.value = value; this.tail = tail; } public static AA create() { return new AA(@, null, null); } // TODO: Code hier ergaenzen Fortsetzune nachste Seite! Herbst 2015 Einzelprüfungsnummer: 46115 Seite: 6 Aufgabe 3: “Bäume % a) Fügen Sie die Zahlen 83, 85, 67, 72, 69 in der gegebenen Reihenfolge i) in einen linksvollständigen Binärbaum bzw. i) in einen binären Suchbaum ein. Stellen Sie jeweils nur das Endergebnis dar. b) Fügen Sie 77 in jeden der folgenden AVL-Bäume ein und führen Sie anschlieRend bei Bedarf die erforderliche(n) Rotation(en) aus. ZeichnenSie den Baum zunächst unmittelbar nach dem Einfügen und anschließend im Endzustand nach den Rotationen. c) Traversieren Sie den folgenden Baum in der jeweils angegebenen Art (Abstieg zuerst im linken Teilbaum) und geben Sie dabei die Knoten in der entsprechenden Reihenfolge aus: i) in-order il) post-order d) Löschen Sie den Knoten 70 aus dem folgenden binären Suchbaum und ersetzen Sie ihn dabei durch einen geeigneten Wert aus dem linken Teilbaum. Zeichnen Sie nur den Endzustand: Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 46115 Seite: 7 Aufgabe 4: “Formale Verifikation - Induktionsbeweis“ Gegeben sei die folgende Methode £unction: double function(int n) { if (n == 1) return 0.5 * n; else return 1.8 / (n * (n + 1)) + function(n - 1); } Beweisen Sie folgenden Zusammenhang mittels vollständiger Induktion: Vn > 1: function (n) = f(n)mit f(n) =1- Br Hinweis: Eventuelle Rechenungenauigkeiten, wie z. B. in Java, bei der Behandlung von Fließkommazahlen (z. B. double) sollen beim Beweis nicht berücksichtigt werden — Sie dürfen also annehmen, Fließkommazahlen würden mathematische Genauigkeit aufweisen. Fortsetzune nächste Seitel Herbst 2015 Einzelprüfungsnummer: 46115 Seite: 8 Aufgabe 5: Sei D = {a,b}, sei INg = {0,1,2,...}. a) Sei Lı = {w € D* | w enthält mehr a’s als b’s} . Beispiele: aba € Lı, bbbaabaabaa € L\,a € Lı. Zeigen Sie, dass L} kontextfrei ist, indem Sie die Arbeitsweise eines Kellerautomaten beschreiben, der L, akzeptiert. b) Formulieren Sie das Pumping-Lemma für reguläre Sprachen: „Sei L eine reguläre Sprache über dem Alphabet %. Dann gibt es...“ c) Zeigen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die Sprache L, nicht regulär ist. Aufgabe 6: a) Sim e IN, = {0,1,2,...}. Definieren Sie formal die Menge H„ der Gödelnummern der Turing-Maschinen, die gestartet mit m halten. b) Gegeben sei das folgende Problem E: - Entscheide, ob es für die deterministische Turing-Maschine M mit der Gödelnummer (M) mindestens eine Eingabe w € INy gibt, so dass w eine Quadratzahl ist und die Maschine M gestartet mit w hält. Zeigen Sie, dass E nicht entscheidbar ist. Benutzen Sie, dass H,„, aus (a) für jedes m € INg nicht entscheidbar ist. c) Zeigen Sie, dass das Problem E aus (b) partiell-entscheidbar (= rekursiv aufzählbar) ist. Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 46115 Seite: 9 Aufgabe 7: a) Gegeben sei der folgende nichtdeterministische endliche Automat N: € bezeichnet das leere Wort. Konstruieren Sie zu N mit der Potenzmengen-Konstruktion einen äquivalenten deterministischen endlichen Automaten A. Zeichnen Sie nur die vom Startzustand erreichbaren Zustände ein, diese aber alle. Die Zustandsnamen von A müssen erkennen lassen, wie sie zustande gekommen sind. Führen Sie keine „Vereinfachungen“ durch! Hinweise: - {go} ist nicht der Startzustand des deterministischen endlichen Automaten. - In einem deterministischen endlichen Automaten darf es keine e-Übergänge geben, und es muss an jedem Zustand für jedes Zeichen einen Übergang geben. b) Geben Sie einen regulären Ausdruck «{N) für die Sprache, die der nichtdeterministische endliche Automat N aus (a) akzeptiert, an. c) Beweisen oder widerlegen Sie die folgende Behauptung. Beh.: Es gibt reguläre Sprachen L, die mindestens eine echte Teilmenge U enthalten, so dass U nicht regular ist.