Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 661 1 z 2011 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: 6 Bitte wenden! Herbst 2011 Einzelprüfungsnummer 66115 Seite 2 Thema Nr. 1 Aufgabe 1: Automatentheorie 1.1 Reguläre Sprachen und Endliche Automaten Gegeben ist die Grammatik G = ({S, A, B, C}, {a,b}, ®, S) mit ®={ Sad |bB |a|b| e, A— aC | bB |b, B— aA [dC |a, C— aC | bC}. a) Konstruieren Sie einen DFA M mit L(M) = L(G). b) Welche Sprache erzeugt die Grammatik G? 1.2 Minimierung Gegeben seien die beiden folgenden deterministischen endlichen Automaten MI und M2: 0 0 0,1 a) Zeigen Sie, dass M, und M minimal sind. b) Bilden Sie einen DFA M, der die Sprache (M7) NL(M) akzeptiert. c) Welche Sprache akzeptiert der Automat M? Geben Sie einen regulären Ausdruck , an, der diese Sprache beschreibt, so dass y möglichst wenig Zeichen aus {0; 1} enthält. Aufgabe 2: Formale Sprachen 2.1 Bestimmung der Grammatiktypen Bestimmen Sie für die folgenden drei Sprachen jeweils den restriktivsten Typ einer Grammatik, die diese Sprache erzeugt, und geben Sie eine entsprechende Grammatik an (n,kE N). L={dca In > 0} Ly, = {a"b' ca” | n>0,k>1} L;= {ab"a"*|n>1,k>1} 2.2 Pumping Lemma Wählen Sie eine nicht-reguläre Sprache aus Teilaufgabe (2.1) aus und beweisen Sie mit Hilfe des Pumping Lemma, dass diese nicht regulär ist. Fortsetzung nächste Seite! Herbst 2011. Einzelprüfungsnummer 66115 Seite 3 23 Eindeutige Grammatik Es sei folgende Grammatik G = (Vy, V7, ®, S) mit Vy = {S, T},Vr = {a,b} und @={S—aT, S—aTbT, T—aT, T>aTbT, T>E} gegeben. a) Zeigen Sie, dass die Grammatik mehrdeutig ist. b) Welche Sprache wird von dieser Grammatik erzeugt? c) Geben Sie eine eindeutige, €-freie Grammatik an, die dieselbe Sprache erzeugt. Aufgabe 3: Berechenbarkeit 3.1 Rekursive Aufzählbarkeit Sei U eine beliebige entscheidbare Menge und W C U. Zeigen Sie, dass W genau dann entscheidbar ist, wenn W und U\W rekursiv aufzählbar sind. 3.2 Entscheidbarkeit Beweisen Sie: Wenn eine nicht-leere Menge MCN eine monoton wachsende Aufzählungsfunktion ay besitzt, ist M entscheidbar. Aufgabe 4: Komplexität 4.1 O-Notation Formulieren Sie möglichst einfache Algorithmen mit den folgenden asymptotischen Laufzeitkomplexitäten: a) O(n’) b) O(log n) c) O(n log n) . Versuchen Sie, die Komplexität durch geeignete Schachtelung von Schleifen zu erreichen. Erläutern Sie Ihre Lösungen. Eine Verwendung der Ausdrücke der asymptotischen Laufzeitkomplexität als Grenzen für Laufvariablen ist nicht zulässig. Fortsetzung nächste Seite! Herbst 2011 Einzelprüfungsnummer 66115 Seite 4 4.2 Algorithmen Beachten Sie folgenden Algorithmus: int vectorSum(int[] vector) { int n = vector.length; int sum = 0; for (int 1 = 0; i 1} über dem Alphabet {a, b}. a) Beweisen Sie, dass E kontextfrei ist. b) Beweisen Sie, dass E nicht regulär ist. Aufgabe 6: Beweisen Sie, dass folgende Menge in NP liegt. F={(a,b,c,d) € N‘ | dx, y € N mit ax’y + bx’ + cxy = a} Fortsetzung nächste Seite! Herbst 2011 Einzelprüfungsnummer 66115 _ Seite 6 Aufgabe 7: Geben Sie zwei Sortierverfahren an, deren asymptotische Worst-Case-Laufzeit sinkt, wenn die zu sortierenden Daten (über die ansonsten nichts bekannt ist) schon sortiert sind. Aufgabe 8: Sei G=(V, E) ein ungerichteter Graph. Ein Matching (oder eine Paarung) in G ist eine Teilmenge M der Kantenmenge E, so dass keine zwei Kanten in M zum selben Knoten inzident sind. Sei nun w: E— R»o eine Abbildung, die den Kanten von G ein positives Gewicht zuordnet. Dann ist ein Matching Mop: ein schwerstes (oder gewichtsmaximales) Matching, falls w(M opt): "dee Mopı W(E) maximal unter allen Matchings in G ist. Professor Ydeerg schlägt vor, ein schwerstes Matching wie folgt zu berechnen. Man sortiere erst die Kanten nach Gewicht. Solange es noch Kanten gibt, nehme man eine schwerste Kante {u, v} ins Matching und lösche alle (verbliebenen) Kanten, die zu u oder v inzident sind. a) Zeigen Sie, dass Professor Ydeergs Algorithmus zwar immer ein Matching liefert — aber nicht immer ein schwerstes. b) Nun behauptet Professor Ydeerg, dass sein Algorithmus immer ein Matching liefert, das wenigstens halb so schwer wie ein schwerstes Matching ist. Beweisen Sie seine Behauptung. Betrachten Sie dazu einen Graphen G und ein schwerstes Matching Moin G. Was passiert, wenn Professor Ydeergs Algorithmus eine Kante {w, v} auswählt und die zu z und v inzidenten Kanten löscht? c) Welche Laufzeit hat der Algorithmus in Abhängigkeit von der Anzahl n der Knoten und der Anzahl m der Kanten von G? d) Kann man diese Laufzeit verbessern, wenn man weiß, dass die Gewichtsfunktion w die Kantenmenge E in die Menge {1, 2, ..., m} abbildet? Aufgabe 9: Sie verwalten eine Menge $ von natürlichen Zahlen und müssen immer wieder für ein gegebenes Intervall [a, b] (mit a, be N) alle Zahlen in S/O [a, 5] liefern. a) Angenommen, die Menge $ ändert sich nicht, wie würden Sie S vorverarbeiten, um Anfragen ausgabesensitiv bearbeiten zu können? Mit anderen Worten, Sie sollen durch die Vorverarbeitung erreichen, dass die Anfragezeit nicht nur von der Anzahl n der Elemente i in S, sondern auch von der Größe k der Ausgabe abhängt. Stellen Sie sicher, dass die Anfragezeit Tquery\(n, k) sublinear von n abhängt. Die Abhängigkeit von k sollte linear sein. Wie lange dauert Ihre Vorverarbeitung? b) Nehmen wir nun an, dass sich die Menge S im Lauf der Zeit ändert. Das heißt, Sie möchten eine dynamische Datenstruktur RangeSet anbieten, die neben obiger Anfrage auch das Einfügen und Löschen von Zahlen erlaubt. Entwerfen Sie RangeSet, so dass die Laufzeiten aller drei Operationen sublinear von der aktuellen Größe n von S abhängen. Die Anfragezeit soll darüber hinaus wieder linear von k abhängen. c) Eine andere Art von Anfrage soll die Summe der Zahlen in S liefern, die in einem gegebenen Intervall [a, 5] liegen. Beschreiben Sie eine dynamische Datenstruktur, die diese Art von Anfragen sowie Einfügen und Löschen in O(log n) Zeit zulässt.