Prüfungsteilnehmer _Prüfungstermin_ Einzelprüfungsnummer Kennzahl: Kennwort: Frühjahr | m 46115 Arbeitspistz-Nr.; | 2010 , Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen | — Prüfungsaufgaben — Fach: Informatik (Unterrichtsfach) Einzelprüfung: Theoret. Informatik, Algorith./Datenstr Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 6 Bitte wenden! Frühjahr 2010 Einzelprüfungsnummer 46115 Seite 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! 1. Betrachten Sie über dem Alphabet 3 = {a,b} die Sprache L, die durch folgendes Regelsystem vollständig gegeben ist: - Das Wort a gehört zu L. - Gehört ein Wort w zu L und endet w mit einem a, so gehört auch wb zu L, d.h. für u€ D* gilt uae LD => uadbe L. - Gehört w zu L, so gilt auch ww € L. - Folgen in einem Wort w € L drei a’s unmittelbar aufeinander, so gehört auch das Wort zu L, das man aus w erhält, wenn man aaa durch b ersetzt, d.h. für u,v € D* gilt uaaay € L => ubv € L. - Folgen in einem Wort w € L zwei b’s unmittelbar aufeinander, so gehört auch das Wort zu L, das man aus w erhält, wenn man bb streicht, d.h. für u,v € X* gilt ubbu € LD => uv € L. Beispielsweise gehört das Wort baab zu L, was man an der Ableitung ataat aaaat ba + bab + babbab + baab , sieht. Da das Regelsystem sowohl verlängernde als auch verkürzende Regeln enthält, ist die Zugehörigkeit eines Worte w € C* zur Spache L scheinbar nicht einfach zu entscheiden. Da das Regelsystem keine reguläre Grammatik ist, ist auch nicht klar, ob die Sprache L regulär ist, a) Zeigen Sie, dass alle Wörter w€ L die Eigenschaft haben: (*) Die Anzahl |w|, der Vorkommen von a in w ist nicht durch 3 teilbar. b) Tatsächlich charakterisiert die Eigenschaft (*) die Sprache L, d.h. es gilt L= {we 2*; 34 |w|a}. Verwenden Sie diese Aussage (die Sie nicht beweisen sollen!), um einen minimalen _ vollständigen DFA zu konstruieren, der die Sprache L akzeptiert. .c) Beweisen Sie, dass Ihr Automat tatsächlich minimal ist! 2. Betrachten Sie die Funktion des ganzzahligen Quadratwurzelziehens: - sort :N>N:x+ |ye| a) Geben Sie ein Programm für sqrt in einer Ihnen geläufigen Programmiersprache an. ) b) Geben Sie ein WHILE-Programm für sqrt an. c):Geben Sie ein LOoP-Programm für sqrt an. ) d) Zeigen Sie, dass sqrt eine primitiv-rekursive Funktion ist, indem Sie eine entsprechende | Definition angeben. - Fortsetzung nächste Seite! nn een Frühjahr 2010 Einzelprüfungsnummer 46115 Seite 3 Hinweise: - Sie können, falls Ihnen das hilfreich erscheint, die Tatsache verwenden, dass 1+ 3+5+ | + (2n ~1) = n? ist. - = bezeichnet die größte ganze Zahl, die kleiner oder gleich x ist, also z.B. [3,1] = 3. 3: Beweisen oder widerlegen Sie die folgenden Behauptungen über Sprachen A, B C &*. AAB = (A \ B) U(B \ A) bezeichne dabei die symmetrische Mengendifferenz. a) Sind A und B regular, so ist auch AAB regular. b) Sind A und B kontextfrei, so ist auch AAB kontextfrei. c) Sind A und B entscheidbar, so ist auch AAB entscheidbar. d) Sind A und B partiell-entscheidbar, so ist auch AAB partiell-entscheidbar. .e) Sind A-und B polynomiell-entscheidbar, so ist auch AAB polynomiell-entscheidbar. 4, ALICE und Bos verfügen jeder über einen DFA über dem Alphabet © = {0,1}. Der Automat von ALICE sei X, der Automat von Bos sei B. Beide Automaten haben die gleiche Anzahl n von Zuständen. ALICE und BoB wollen die Frage klären, ob es ein Wort w € %* gibt, das von beiden Automaten akzeptiert wird. ALICE argumentiert: “Diese Frage können wir gar nicht entscheiden, denn dafür: müssten wir unendlich: viele Wörter aus &* durchprobieren.” BoB hält dem entgegen: “Das geht doch ganz einfach: Wenn ein Automat: n Zustände hat, können alle akzeptierenden Zustände in höchstens n — 1 Schritten erreicht werden. Es genügt also, Wörter der Länge < n zu testen, ob eines von ihnen von beiden Automaten Q und B akzeptiert wird.” Kommentieren Sie die beiden Aussagen! Sollten Sie weder ALICE noch BoB zustimmen, so . zeigen Sie einen Weg auf, die Frage zu beantworten. Geben Sie ein Entscheidungsverfahren an oder weisen Sie nach, dass es sich um ein unentscheidbares Problem handelt: Fortsetzung nächste Seite! n Frühjahr 2010 \ Einzelprüfungsnummer 46115 = Seite 4 5. "Datenstrukturen und Algorithmen: Binäre Suchbäume und AVL-Bäume - a) b) c) a Geben Sie jeweils eine Definition für binäre Suchbäume und A VL-Bäume an. Zeichnen Sie einen AVL-Baum, der die folgenden Schlüssel enthält: 1 1,1, 5, 37, 17, 29, 31, 3. Welche Zeitkomplexitat haben die Operationen Einfügen, Löschen und Suchen auf AVL-Bäumen? Begründen Sie Ihre Antwort. — Implementieren Sie die Datenstruktur AVL-Baum mit Schlüsseln vom Typ int (für Java oder entsprechende Datentypen für die anderen Programmiersprachen) in entweder Java, C++, Smalltalk oder Eiffel. Ihre Implementierung muss als einzige Operation die Methode suche bereitstellen, die einen Schlüssel als Parameter bekommt und - true zurückliefert, wenn der gesuchte Schlüssel im Baum enthalten ist, - ‚ansonsten false. Ihre Implementierung muss keine Konstruktoren oder andere Methoden zur Initialisierung bereitstellen. Desweiteren soll die Implementierung nur Schlüsselknoten - berücksichtigen. Kommentieren Sie Ihre Implementierung ausführlich. Geben Sie an, welche Programmiersprache Sie gewählt haben. Frühjahr 2010 Einzelprüfungsnummer 46115 Bu . Seite 5 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! 1. Gegeben ist die folgende Sprache L1 über dem Alphabet © = {a,b}: Il = {we%\* | die Anzahl der a in w ist gerade und b kommt in w genau einmal vor}. a) Geben Sie einen deterministischen endlichen Automaten an, der die Sprache L1 akzeptiert. b) Geben Sie einen regulären Ausdruck an, der die Sprache L1 beschreibt. Die folgende Sprache L2 ist eine Erweiterung von LI: 12 = {we =* | die Anzahl der a in w ist gerade und die Anzahl der bin w ist ungerade}. | c) Geben Sie einen deterministischen endlichen Automaten an, der die Sprache L2 akzeptiert. d) Geben Sie eine rechtslineare Grammatik an, die die Sprache L2 erzeugt. 2. Gegeben ist die folgende Sprache L über dem Alphabet © = {0,1}: L = [we | wFfew enthält gleich viele 0-en wie l-en und in jedem Anfangswort von w kommen mindestens soviele 0-en wie 1-en vor}. a) Geben Sie alle Wörter w € L mit Länge |w] < 4 an. b) Geben Sie eine kontextfreie Grammatik an, die die Sprache L erzeugt. c) Zeigen Sie, dass L nicht regulär ist. Der Beweis kann ohne Anwendung .des Pumping Lemmas unter Verwendung der beiden folgenden Tatsachen geführt werden: i) Der Durchschnitt zweier regulärer Sprachen ist regulär. ii) Die Sprache L’ = {0/1} | j > 0} ist nicht regulär. Pn oR mE Ry Netter Wir betrachten nun für alle natürlichen Zahlen n € N die folgenden Teilsprachen L, von L: | In = fweL| in jedem Anfangswort von w kommen höchstens n mehr 0-en vor als I-en}. : non, d) Für alle natürlichen Zahlen n ist L, regulär. Zeigen Sie dies für den Faln=3. | e) Wie kann man aus den Tatsachen, dass D nicht regular ist und Ly, für alle n eN regulär ist, schließen, dass die Vereinigung abzählbar unendlich vieler regulärer Mengen nicht notwendigerweise regulär ist? 3. Zeigen Sie, dass die Funktion f: N — N, mit f({n) = 2 div 2 für allen € N, primitiv rekursiv ist. Dabei bezeichnet n div 2 die. ganzzahlige Division durch 2. Beim Beweis ist das Schema der primitiven Rekursion zu verwenden, d.h. es sind geeignete primitiv rekürsive Funktionen g: NN undh:N 2 N anzugeben, so dass gilt: f(0)=9,f(n+1) = A(n, f(n)) fir alle n € N. Es kann vorausgesetzt werden, dass die Multiplikation und die Fallunterscheidung, ob eine natürliche Zahl gerade ist oder nicht, primitiv rekursiv sind. Fortsetzung nächste Seite! Frühjahr 2010 Einzelprüfungsnummer 46115 Seite 6 4. Entscheiden Sie, welche der folgenden Aussagen richtig und welche falsch sind und geben Sie jeweils eine kurze Begründung für Ihre Antwort an. Unter einer totalen Funktion wird im Folgenden, wie üblich, eine auf allen Argumenten definierte Funktion verstanden. a) Jede u-rekursive totale Funktion ist primitiv rekursiv. - b) Jede primitiv rekursive Funktion ist eine totale u-rekursive Funktion. c) Das Komplement jeder primitiv rekursiven Teilmenge M der natürlichen Zahlen ist primitiv rekursiv. (Eine Menge heißt primitiv rekursiv, wenn ihre charakteristische Funktion primitiv rekursiv ist.) d) Das Komplement jeder entscheidbaren Teilmenge M der natürlichen Zahlen ist entscheidbar. e) Das Komplement. jeder rekursiv aufzihlbaren Teilmenge M der natürlichen Zahlen ist rekursiv aufzählbar. 5. a) Beschreiben Sie die Datenstruktur HEAP, insbesondere die zugehörigen Operationen, Aufbau und Update einschließlich Aufwandsbetrachtungen. b) Stellen Sie mindestens zwei unterschiedliche Sortierverfahren einander gegenüber und vergleichen Sie diese Verfahren mit Heap-Sort. -c) Beschreiben Sie die Suchstrategie „Tiefensuche (Depth First Search)“ und zeigen Sie Anwendungen auf bei der Bestimmung von Zusammenhangskomponenten in Graphen.