Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl. Frühjahr Kennwort: 2009 66115 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: 9 Bitte wenden! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1 Ordnen Sie die folgenden formalen Sprachen bestmöglich in die Chomsky-Hierarchie ein, und geben Sie eine ausreichende Begründung dafür, dass die jeweilige Sprache in der von Ihnen genannten Hierarchiestufe liegt und in keiner niedrigeren eingeordnet werden kann! 1. L i ={anbnanIn> 2. L2 = anbman 1} > 1,n > 1} 3. L3= { a n b m ^ m>1, n> 1} 4. L4 = Die Menge aller Dezimaldarstellungen von Vielfachen von 3 5. L5 = Die Menge aller terminierenden Java-Programme 6. L6 ={tvc{a,b}lw enthält mindestens 4 Vorkommen von Aufgabe 2 Wir betrachten den deterministischen Automaten (E, Z, zo , 6, F), wobei E = {0,1} und Z = {E,0, 1,00,01,10,11} und zo = E und F = {10} und die Zustandsüberführungsfunktion 6 schematisch durch die folgenden Gleichungen gegeben ist: 6(E, x) = x 6(x y) = xy 6(xy,z) -=- yz wobei x,y,z E {0,1}. Es gilt also zum Beispiel 6(0,1) = 01 und 6(01,1) = 11. Lassen Sie sich nicht dadurch verwirren, dass die Zustände hier Wörter sind. I. Zeichen Sie den Automaten als Diagramm! 2. Geben Sie einen möglichst kurzen regulären Ausdruck für die erkannte Sprache L an! 3. Wenden Sie den Minimierungsalgorithmus auf den Automaten an und berechnen Sie so den Minimalautomaten! 4. Geben Sie die Äquivalenzklassen der Myh,ill-Nerode Äquivalenzrelation als reguläre Ausdrücke an! Hinweis: Die Myhill-Nerode Äquivalenz ist er(Vw : uw E L <# vw E L). klärt durch u v ti Tipp: Die Vereinigung aller Klassen muss {0,1}* ergeben. Fortsetzung nächste Seite! Frühjahr 2009 Seite: 3 Einzelprüfungsnummer: 66115 Aufgabe 3 Welche der folgenden Aussagen trifft zu, welche nicht? Begründen Sie jeweils Ihre Antwort durch Beweis oder Gegenbeispiel! Natürlich dürfen Sie sich auf allgemein bekannte Lehrsätze und den Informatikduden beziehen. I. Ist eine Sprache L rekursiv aufzählbar, so ist sie auch entscheidbar. 2. Ist eine Sprache auf das Halteproblem reduzierbar, so ist sie rekursiv aufzählbar. 3. Die rekursiv aufzählbaren Sprachen sind unter Vereinigung und Durchschnitt abgeschlossen. 4. Die rekursiv aufzählbaren Sprachen sind unter Komplement abgeschlossen. 5. Es ist unentscheidbar, ob eine Turingmaschine M bei leerer Eingabe im Verlaufe der Berechnung eine Konfiguration erreicht, die grösser als 17 ist. Tipp: Es gibt nur eine feste Zahl von Konfigurationen der Grösse 17 oder kleiner. Fortsetzung nächste Seite! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 4 Aufgabe 4 Hier finden Sie Pseudocode s für den Dijkstra-Algorithmus in der Notation des Informatikdudens. Insbesondere ist R eine Prioritätsschlange mit DH als Schlüssel. Der Algorithmus berechnet die kürzesten Entfernungen vorn Startknoten s in einem gerichteten Graphen G = (V, E) mit nichtnegativen Kantengewichten d(.,.). Der Aufruf deletemin(R,v) weist den kleinsten Eintrag von R der Variablen v zu und entfernt ihn aus R. setze D[v] = oo für alle Knoten v; D[s] := 0; R := V while R 0 do deletemin(R, v); for all Knoten w mit (v,w) E E do h := D[v] + d(v, w); if h < D[w] then D[w] h; decreasekey(R,w); I. Arbeiten Sie den Algorithmus für folgende Eingabe ab und dokumentieren Sie die Schritte geeignet! V = 1s, u, v, x, - = {(s, u) , (s, x), (u, x), (x, u), (u, v), (x, y) , (x, v) , (v, y) , (y, v) , (y, s)} = 5, d(u, x) = 2, d(x , Lt) = 3, d(u , v) = 1, d(s , u) = 10 d = 6, d(y, s) = 7 = 4, d(y, d(x , y) = 2, d(x , = 9, d(v, - 2. Der syldawische Informatiker W. E. ARTSKJID schlug 2007 vor, beim Abarbeiten eines Knotens v jeweils die Menge M {v1, . , vk } derjenigen Knoten in R zu bilden, deren D-Wert während der Abarbeitung von v verringert wurde. Aus dieser Menge M wird nun der Knoten mit dem kleinsten D-Wert gesucht und als nächstes abgearbeitet. Sollte die Menge M leer sein, so wird wie üblich verfahren, es wird also der Knoten aus R mit kleinstem D-Wert als nächstes abgearbeitet. Geben Sie Pseudocode für den so modifizierten Algorithmus an! Geben Sie ein konkretes Beispiel dafür, dass der modifizierte Algorithmus bisweilen unkorrekte Ergebnisse liefert! Sie müssen dazu den entsprechenden Eingabegraphen mit Kantengewichten skizzieren und den Lauf des modifizierten Algorithmus auf dieser Eingabe geeignet dokumentieren. 1 Die Version der Informatikdudens enthält eine hier störende Ungenauigkeit, welche es im Prinzip erlaubt, bereits abgearbeitete Knoten wieder in die Prioritätsschlange aufzunehmen. -5 Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 5 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Formale Sprachen und Automatentheorie a) Wir betrachten die Sprache L über der Zeichenmenge T = {a, b}, die das Wort abab als Teilwort enthalten. i) Geben Sie einen regulären Ausdruck an, der L beschreibt. ii) Geben Sie eine reguläre, rechtslineare Grammatik an, die L erzeugt. iii) Geben Sie eine Ableitung des Wortes aababbb an. b) Gegeben sei der reguläre Ausdruck: [011(01*01* 11*. Wandeln Sie diesen regulären Ausdruck in einen nichtdeterministischen endlichen Automaten um. c) Gegeben sei der endliche, nichtdeterministische Automat A = (S, T, s o , 6) S = mit {so, S1 S2, S3}, T = {a, b}, Z = {s 2 , 53} mit der Übergangsfunktion 6 gemäß untenstehendem Diagram. a, b a, b i) Konstruieren Sie einen äquivalenten, deterministischen, endlichen Automaten. ii) Minimalisieren Sie den endlichen Automaten. Fortsetzung nächste Seite! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 6 d) Eine Turing-Maschine D, die natürliche Zahlen in Strichdarstellung halbiert (ganzzahlige Division durch 2), mit Eingabealphabet T = { I } soll in mehreren Schritten entwickelt werden. i) Definieren Sie eine Turing-Maschine L mit Eingabealphabet T, die den Kopf zum nächsten leeren Bandfeld nach links (mindestens um ein Feld) bewegt und die Bandbeschriftung nicht ändert. L setzt voraus, dass der Kopf auf einem leeren Bandfeld steht (Beispiel für Startkonfiguration: #111#). Stellen Sie die Übergangsrelation von L in Form einer Tabelle und in Form eines erweiterten, endlichen Automaten dar. Hinweis: Ein erweiterter, endlicher Automat ist ein endlicher Automat, dessen Zustandsübergänge neben der gelesen Eingabe mit der geschriebenen Ausgabe und der Lese/Schreibkopfbewegung annotiert sind. ii) Definieren Sie analog zu i) eine Turing-Maschine R, die den Kopf zum nächsten leeren Bandfeld nach rechts bewegt. Geben Sie eine vollständige Berechnung von R zur Startkonfiguration #111# an. iii) Geben Sie nun unter Verwendung von L und R eine Turing-Maschine D (für die ganzzahlige Division durch 2 einer Strichzahl) in Form eines erweiterten, endlichen Automaten an. D setzt voraus, dass der Kopf auf dem ersten leeren Bandfeld rechts von der Eingabe steht. Beispielberechnung: (###111#) --›* (#1# # # # #) Aufgabe 2: Berechenbarkeit a) Gegeben sei die Funktion f : N oN 0 mit f (x) x — 1 wobei '—' definiert ist als Subtraktion über den natürlichen Zahlen mit der Besonderheit, dass a — b = 0 ergibt, falls a < b. i) Zeigen Sie, dass die Funktion f Einband-Turing-berechenbar ist, indem Sie eine solche Turing-Maschine angeben. x sei dabei wieder in Strichdarstellung gegeben. Der Kopf beginnt rechts. ii) Nennen Sie zwei weitere Modelle für Berechenbarkeit. iii) Was besagt die Church These im Hinblick auf die obigen Modelle? b) i) Begründen Sie, dass die Menge der Primzahlen entscheidbar ist. ii) Zeigen Sie folgende Eigenschaften für entscheidbare Mengen: - Jede endliche Menge, einschließlich der leeren Menge, ist entscheidbar. - Das Komplement einer entscheidbaren Menge ist entscheidbar. c) Sei A C N 0 . i) Geben Sie die Definition für rekursive Aufzählbarkeit dieser Menge an. ii) Zeigen Sie, dass eine Menge A genau dann entscheidbar ist, wenn A und A rekursiv aufzählbar sind. Fortsetzung nächste Seite! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 7 Aufgabe 3: Komplexität a) Die folgenden Fragen beziehen sich auf nichtdeterministische Turing-Maschinen. i) Geben Sie eine Definition in üblicher Tupelschreibweise an. ii) Erarbeiten Sie die wesentlichen Unterschiede zu einer deterministischen Turing-Maschine. iii) Was bedeutet die Klasse N P? b) Gegeben sei das SOS (Sum of Subset) - Problem SOS := b) (a 1 , ..., : m, ..., b E No und es existieren c l , ..., en, E {0, 1} mit =ici 7i,n - az b i) Zeigen Sie, dass das SOS - Problem in polynomialer Zeit auf einer nichtdeterministischen Maschine entscheidbar ist (verwenden Sie dazu ein geeignetes übliches nichtdeterministisches Berechnungsmodell in dem Arrays als primitive Datenstruktur vorhanden sind). ii) Gegeben sei das NP-vollständige Problem TS', eine Variante des "Travelling Salesperson" Problems: TS' (m, M, k) : m, k E N 0 , M : {1, 2, ...,m} 2 --> und es existiert eine Permutation 7r mit Eni l M(7r(i),7r(i + 1)) + M(7r(m),7v(1)) k } Zeigen Sie damit, dass das obige SOS-Problem ebenfalls ein NP-vollständiges Problem ist. Aufgabe 4: Effiziente Algorithmen und Datenstrukturen a) Die Ausdrücke O(.) und Q(.) sind gebräuchliche Notation in der Informatik. i) Wie sind sie jeweils definiert? ii) Benennen Sie die wesentlichen Unterschiede. Fortsetzung nächste Seite! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 8 iii) Geben Sie in O(.)-Notation die Berechnungskomplexität in Abhängigkeit von a und b für folgenden Algorithmus an: function fastmult(a,b); begin ACO] := 1; B[0] := a; j := 0; while (A[j] <= b) do begin A[j+1] := (A[j] + A[j]); B[j+1] := (B[j] + B[j]); j := +1) end; c := 0; > 0) do begin while j := (j-1); if (A[j] <= b) then begin b := - A[j]); c := (c + BEjl) end end; fastmult := c; end iv) Zeigen oder widerlegen Sie: 2n+ 1 = 0(2n)? 22n = 0(2n)? b) Gegeben sei der Graph G: Somit ist die Adjazenzmatrix von G die Matrix D o : / c>o Do 1 3 oo oo 1 1 oo 00 Fortsetzung nächste Seite! Frühjahr 2009 Einzelprüfungsnummer: 66115 Seite: 9 Um den kürzesten Pfad in diesem gewichteten, gerichteten Graphen zu finden, setzen wir den Floyd-Warshall-Algorithmus ein: n := rows[D o ] for k 1 tO n do fori e— 1 to n do for j 1 to n do D k[i][j] min( D k -i[i][j] D k _ i[i][k] D k _i[k][j]) return D n i) Führen Sie den Floyd-Warshall Algorithmus auf der den Graphen G repräsentierenden Matrix D o aus. Stellen Sie dabei die Zwischenergebnisse der Matrizen D 1 und D2 sowie das Ergebnis D3 in Matrixform dar. ii) Auf welchen gewichteten, gerichteten Graphen berechnet der Floyd-Warshall-Algorithmus genau die transitive Hülle?