Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: —— _ —_ Herbst 66 1 1 5 2007 | 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: 5 Bitte wenden! Herbst 2007 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 Hinweis: Die einzelnen Teilaufgaben bauen oftmals aufeinander auf, sind aber im Prinzip in beliebiger Reihenfolge lösbar. Sie dürfen hierbei die Angaben und Ergebnisse früherer Teilaufgaben uneingeschränkt zur Lösung späterer Teilaufgaben verwenden! Außerdem dürfen Sie Tatsachen aus dem Informatik-Duden ohne weitere Begründung als bekannt voraussetzen. Aufgabe 1: Ordnen Sie die folgenden formalen Sprachen bestmöglich in die Chomsky-Hierarchie ein und geben Sie eine ausreichende Begründung an: a) Ly = {a"b"a" | n > 1} b) La sei die Menge aller terminierenden Java-Programme. c) Lz sei die Menge aller vollständig und korrekt geklammerten arithmetischen Ausdrücke in den Variablen a und b mit den Operationen + und x. Zur Illustration: ((a + (b+ a)) x a) € Ls, ((a+b+)a)) x b & Lz (nicht korrekt geklammert), a x (b+5)) € Ls (nicht vollsténdig geklammert). d) Ls = {w € {a, b}* |w enthalt mindestens 4 Vorkommen von a}. e) Ls = {a"b"$w | n> 1 und w € {a, b}*} Aufgabe 2: Geben Sie zu dem nichtdeterministischen endlichen Automaten in der Abbildung einen äquivalenten deterministischen Automaten an. Ist Ihr Automat minimal? Falls nein, so geben Sie mindestens ein Paar von Zuständen an, die zu einem einzigen Zustand zusammengefasst werden können. Falls ja, so geben Sie für mindestens drei Zustandspaare Ihrer Wahl jeweils eine Begründung dafür, dass diese nicht zusammengefasst werden können. Abbildung: ein nichtdeterministischer endlicher Automat mit 3 Zuständen Fortsetzung nächste Seite! Herbst 2007 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: Für eine (deterministische) Turingmaschinge T = (J, >>, Q,6,q0, F,b) und ein Wort w € >> ist die partielle Funktion TIME-(w) definiert als die Anzahl von Arbeitsschritten, die T bei Eingabe w ausführt. Falls T bei Eingabe w nicht halt, ist TIME7(w) = 1, also undefiniert. Im Folgenden sei >, = {0,1} fest; das leere Wort wird wie üblich mit e bezeichnet. Die Busy-Beaver Funktion BB(n) ist definiert als BB(n) := max {TIMEr(e) | Turingmaschine T hat höchstens n Zustände und hält auf leerer Eingabe } a) Das Halteproblem bei leerer Eingabe ist die Menge Ho = {T | TIMEr(e) # 1}. Bekanntlich ist Ho unentscheidbar. Geben Sie eine Reduktion des Graphen von BB, also der Menge G = {(n,b) |b =BB(n)} auf Ho an. b) Zeigen Sie durch Widerspruch: BB({n) wächst schneller als jede berechenbare Funktion, d. h. für jede berechenbare Funktion f:N— N gilt: BB(n) € O(f{n)). Aufgabe 4: Wrestling ist ein Showkampf, bei dem es zwei Arten von Teilnehmern gibt: Gute und böse Wrestler. Wer gut und wer böse ist, wird von den Organisatoren vorab festgelegt, die Wrestler haben sich dann entsprechend zu kleiden und zu benehmen. Zwischen manchen Wrestlern bestehen persönliche Rivalitäten und um die Kämpfe zusätzlich anzuheizen, ist man bestrebt, die Einteilung in Gute und Böse so vorzunehmen, dass es keine Rivalitäten zwischen zwei Guten oder zwischen zwei Bösen gibt, sondern nur zwischen „Gut“ und „Böse“. Helfen Sie dem Management, indem Sie einen effizienten Algorithmus entwerfen, der entscheidet, ob solch eine Einteilung existiert und sie ggf. berechnet. Gegeben ist hierbei eine Menge von W Wrestlern repräsentiert durch {1,....W} und einer Liste von R Paaren einander rivalierender Westler. „Effizient“ bedeutet hier, dass die Laufzeit O(W + R) sein muss. Beschreiben Sie Ihre Lösung in Pseudocode oder einer Programmiersprache Ihrer Wahl. Beispiel: Bei drei Westlern {1,2,3} und Rivalitäten zwischen 1,2 sowie 1,3 könnte man 1 als „gut“ und 2,3 jeweils als „böse“ einteilen. Besteht zusätzlich noch eine Rivalität zwischen 2 und 3, so existiert keine Lösung. Hinweis: Bauen Sie Ihren Algorithmus auf einem geeigneten Verfahren zum Durchlaufen von (ungerichteten) Graphen auf. Herbst 2007 Einzelprüfungsnummer: 66115 Seite: 4 Thema Nr. 2 Aufgabe 1: Gegeben sei der nichtdeterministische endliche Automat M mit dem Alphabet ) = {a,b}, der Zustandsmenge {2p, 21,22, 23}, Anfangszustand zo, Endzustand {z3} und der Überführungsfunktion 6 mit: 6(20,@) = {21 2} ö(z1,b) = {20,21}; ö(22,a) = {22,28}, | 6(20, 6) = 6(21, a) = 6(22, 6) = 6(23, a) = 6(23,6) =O L(M) sei die von M akzeptierte Sprache. a) Gelten folgende Aussagen? i) Es gibt Zeichenreihen in L(M), die genauso viele a’s enthalten wie b’s. ii) Jede Zeichenreihe in L(M), die mindestens vier b’s enthält, enthält auch mindestens vier a’s. Begründen Sie Ihre Antworten. b) Geben Sie eine regulare (Typ-3-)Grammatik an, die L(M) erzeugt. c) Beschreiben Sie L(M) durch einen regulären Ausdruck. d) Konstruieren Sie aus M mit der Potenzmengen-Konstruktion (und entsprechender Begründung) einen deterministischen endlichen Automaten, der L(M) akzeptiert. Aufgabe 2: Für beliebiges m € N sei L„ die Sprache Lm = {a!b"a!b” € {a,b}* ke N}. a) Beweisen Sie: L3 ist nicht regulär. b) Ist L„ für jedes m € N nicht regulär? Begründen Sie Ihre Antwort. c) Geben Sie die allgemeine Form einer kontextfreien (Typ-2-)Grammatik an, die Lm (für beliebiges m) erzeugt. d) Ist jede der Sprachen L,, mit einer deterministischen Turing-Maschine mit einer Zeitkomplexitat O(n) entscheidbar (n ist die Lange der jeweiligen Eingabe)? Begründen Sie Ihre Antwort. Aufgabe 3: Es seien 5~ ein Alphabet, L,; und La zwei Sprachen über 5°. € bezeichne die leere Zeichenreihe. Gelten folgende Aussagen? Begründen Sie Ihre Antworten. a) Ist Ly kontext-sensitiv (Typ-1), so ist die Sprache L={we Sow ¢ Lyund w # €} entscheidbar. Fortsetzung nächste Seite! Herbst 2007 Einzelprüfungsnummer: 66115 Seite: 5 b) Wird L, von einem linear beschränkten Automaten M mit Zustandsmenge Z und Endzustandsmenge E akzeptiert, so akzeptiert der linear beschränkte Automat M’, der aus M entsteht, wenn man E durch Z\E ersetzt, die Sprache Y*\Lı. c) Sind Lı und Z, entscheibar, so ist auch die Sprache Ly ° La = {w wa € Sows E Ly, We € Lo} entscheidbar. d) Ist L, entscheibar und La semi-entscheidbar, so ist die Funktion f : 5°>* — )>* mit undefiniert sonst iw) = ‘ falls w ¢ Ly N Le berechenbar. e) Sind sowohl /, als auch L, mit einer deterministischen Turing-Maschine mit polynomieller Zeitkomplexität entscheidbar, so gilt dies auch für Lı\ La. Aufgabe 4: a) Beschreiben Sie kurz allgemein die Wirkungsweise des Sortier-Algorithmus Heapsort. b) Welche Zeitkomplexität hat Heapsort? Begründen Sie Ihre Antwort. c) Beschreiben Sie konkret die einzelnen Schritte, die durchgeführt werden, wenn die Zahlenfolge 13, 8, 25, 3, 9, 20, 5, 21 mit Heapsort aufsteigend sortiert wird. Geben Sie dabei die jeweiligen Heapstrukturen sowohl als Baum als auch in ihrer üblichen Darstellung als Feld an.