Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjar Kennwort: ____________ 66115 2015 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: 7 Bitte wenden! Frühjar 2015 Einzelprüfungsnummer: 66115 - Seite: 2 Thema Nr. 1 ‘(Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Die Sprache L über dem Alphabet & = {0,1} enthält alle Wörter, bei denen beim Lesen von links nach rechts der Unterschied in der Zahl der 0en und len stets höchstens 3 ist. Also ist we L . genau dann, wenn für alle u, v mit w = wv gilt IIktlo — |ulıl < 3. Erinnerung: |w|. bezeichnet die Zahl der a’s im Wort w. a) Begründen Sie, dass L regulär ist. b) Jemand behauptet, diese Sprache sei nicht regulär und gibt folgenden “Beweis” dafür an: Wäre L regulär, so sein eine entsprechende Pumping-Zahl. Nun ist w = (01)” € L. Zerlegt man nun v= us, wÖoiu=0,r=1,v= (01)""1, so ist zum Beispiel ur’v € L, denn es ist ur’v = 011111010101. Legen Sie genau dar, an n welcher Stelle dieser “Beweis” fehlerhaft ist. c) Sei A = (Q,d,9,E) ein nichtdeterministischer endlicher Automat für L. Es sei wı = 111, we = 11, w3 = 1, ws = €, Ws = O, We = 00, w7 = 000. Machen Sie sich klar, dass der Automat jedes dieser Wörter verarbeiten können muss. Folgern Sie, dass der Automat mindestens sieben Zustände haben muss. Schreiben Sie Ihre Argumentation schlüssig und vollständig auf. d) In anderen Fällen können nichtdeterministische endliche Automaten echt kleiner sein als die besten deterministischen Automaten. Ein Beispiel ist die Sprache La = %*1% aller Wörter, deren vorletztes Symbol 1 ist. Geben Sie einen 1 nichtdeterministischen Automaten mit nur drei Zustaénden an, der [2 erkennt. e) Führen Sie auf Ihrem Automaten die Potenzmengenkonstruktion und anschließend den Minimierungsalgorithmus durch. Wie viele Zustände muss ein deterministischer Automat für La also mindestens haben? Aufgabe 2: Gegeben sind eine Menge A von Angestellten und für jede Angestellte a eine Menge F(a) von Fähigkeiten, die diese mitbringt. Außerdem gibt es eine Menge Z von Paaren von Angestellten, die nicht gut miteinander zusammenarbeiten. Für eine gegebene Menge P (“Projekt”) von Fähigkeiten soll nun entschieden werden, ob eine Teilmenge T (“Team”) der Angestellten existiert, sodass P © User F(a) und für kein Paar (a,a’) € Z sowohl a, als auch a’ in P sind. Alle Mengen sind endlich und durch explizite Aufzählung gegeben. - a) Begründen Sie, dass dieses Problem in NP liegt. b) Zeigen Sie, dass das Problem NP-vollständig ist, indem Sie (zum Beispiel) eine Reduktion von 3SAT angeben. Fortsetzung nächste Seite! Frühjar 2015 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: a) Geben Sie für jede der Chomsky-Sprachklassen I-IV eine Sprache an, die in der jeweiligen Klasse liegt, aber nicht in der nächstniedrigeren. b) Nennen Sie auch eine Sprache, die nicht einmal in der Klasse IV liegt. Aufgabe 4: In der automatischen Programmverifikation kommt folgende graphentheoretische Grundaufgabe häufig vor. Gegeben ist ein gerichteter Graph G = (V,E), zwei Teilmengen A,B C V und ein Startknoten vo € V. Ein “Lasso” ist eine Folge von Knoten vo, v1, U2,.--;Um)Um+i)--+,Un beginnend beim Startknoten mit m 9973 und M, halt bei Eingabe x} D; = {xeN| M, hält nicht bei Eingabe x} N Aufgabe 5: Gegeben seien die Standarddatenstrukturen Stapel (Stack) und Schlange (Queue) mit folgenden Standardoperationen: Stapel | Schlange Boolean Empty() | Boolean Empty() Push(Zahl e) Enqueue(Zahl e) Zahl Pop() Zahl Dequeue() Zahl Top() Zahl Head() Beim Stapel gibt die Operation Top() das gleiche Element, wie Pop() zurück, bei der Schlange gibt Head() das gleiche Element wie Dequeue() zurück. Im Unterschied zu Pop(), beziehungsweise Dequeue(), wird das Element bei Top() und Head() nicht aus der Datenstruktur entfernt. a) Geben Sie in Pseudocode einen Algorithmus Sort(Stapel 5) an, der als Eingabe einen Stapel 5 mit n Zahlen erhält und die Zahlen in S sortiert. (Sie dürfen die Zahlen wahlweise entweder aufsteigend oder absteigend sortieren.) Verwenden Sie als Hilfsdatenstruktur ausschließlich eine Schlange Q. Sie erhalten volle Punktzahl, wenn Sie außer $ und Q keine weiteren Variablen benutzen. Sie dürfen annehmen, dass alle Zahlen in 5 verschieden sind. b) Analysieren Sie die Laufzeit Ihrer Methode in Abhängigkeit von n. Aufgabe 6: Ein binäres Feld (ein Feld über den Zahlen 0 und 1) sei genau dann ein gutes Feld, wenn die Methode Boolean IstGut(Feld A) als Ausgabe true zurückgibt. Die Laufzeit von IstGut(Feld A) ist linear zu der Anzahl der Zahlen in A. Sie dürfen in den folgenden Teilaufgaben die Methode IstGut(Feld A) aufrufen. a) Geben Sie einen Algorithmus int AnzahlGute(int n) in Pseudocode an, der die Anzahl aller guten binären Felder der Länge n zurückgibt. Was ist die Laufzeit Ihres Algorithmus in Abhängigkeit von n? Fortsetzung nächste Seite! Frühjar 2015 Einzelprüfungsnummer: 66115 Seite: 6 b) Geben Sie einen iterativen Algorithmus int AnzahlGutelt(int n) in Pseudocode an, der die Anzahl aller guten binären Felder der Länge n zurückgibt, die genau zwei Einser enthalten. Die Laufzeit soll in O(n?) sein. Sie brauchen die Laufzeit nicht zu zeigen. c) Geben Sie einen rekursiven Algorithmus int AnzahlGuteRek{int n, int k) in Pseudocode an, der die Anzahl aller guten binären Felder der Länge n zurückgibt, die genau k Einser enthalten. Die Laufzeit soll in O(n()) sein. Sie brauchen die Laufzeit nicht zu zeigen. Aufgabe 7: Auf folgendem ungerichteten, gewichteten Graphen wurde der Dijkstra-Algorithmus (wie auf der nächsten Seite beschrieben) ausgeführt, doch wir wissen lediglich, welcher Knoten als letztes schwarz (black) wurde (Nr. 8) und was seine Distanz zum Startknoten (Nr. 1) ist. Die Gewichte der Kanten sind angegeben. Finden Sie zunächst den Startknoten, nummerieren Sie anschließend die Knoten in der Reihenfolge, in der sie schwarz wurden, und geben Sie in jedem Knoten die Distanz zum Startknoten an. Hinweis: Der Startknoten ist eindeutig. 1 Distanz: 4 Nr. Nr. Distanz: 9 3 Distanz: 8 Nr. 23 Nr. Distanz: 5 Distanz: 5 f 4 Nr. 3 Distanz: 1 35 i 15 Nr. 8 - Nr. Distanz: 53 Distanz: 103 Fortsetzung nächste Seite! Frühjar 2015 Einzelprüfungsnummer: 66115 Dijkstra(WeightedGraph G, Vertex s) Seite: 7 Initialize(G, s) ; S=ß; () = new PriorityQueue(V, d) ; while not Q.Empty() do u = Q.ExtractMin() ; S=SU{u}; foreach v € Adj[u| do L Relax(u, v; w); u.color = black; Initialize(Graph G, Vertex s) foreach u € V do u.color = white ; u.d = 00; s.color = gray ; s.d=0; Relax(u, v; w) if v.d> u.d+ w(u,v) then v.color = gray ; | v.d=u.d+w(u,v) ; Q.DecreaseKey(v, v.d)