Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 66 1 12 2006 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie, Komplexität, Algorith. Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 7 Thema Nr. 1 1. Spracheindeutigkeit Gegeben sei folgende Grammatik: G:({S},{4.2,y,z},{9 > S+5,9 > 2,9 > 2,5 — y},S) 1.1. Welche Sprache Z wird von G erzeugt (ohne Beweis)? 1.2. Beweisen oder widerlegen Sie: Die Grammatik G ist eindeutig. 1.3. Ist die Sprache Z eindeutig? Begründen Sie Ihre Antwort. 2. Chomsky-Hierarchie Gegeben sei die folgende Grammatik: G = ({5,M},{2,#},{5 — SM2,5 > #,2M > M2,#M — zu #,},5) Fortsetzung nächste Seite! Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 2 2.1. Welchen Typ (Namen und Nummer in der Chomsky-Hierarchie) hat die Grammatik G? 2.2. Welche Sprache L wird von G erzeugt (ohne Beweis)? 2.3. Zu welchen Sprachtypen gehört die Sprache Z und zu welchen gehört sie nicht? Zitieren Sie, soweit möglich, die Chomsky-Hierarchie. Geben Sie an der entscheidenden Stelle eine erzeugende Grammatik an und benutzen Sie das entsprechende Pumping-Lemma. 3. Turing-Maschinen Eine deterministische Turingmaschine ist ein Tupel (9; Dol OG By F). Dabei ist Q die endliche Zustandsmenge, ) das endliche Eingabealphabet, T' das endliche Bandalphabet, 6:QxT— QxTx{L,R,N} die Übergangsfunktion, q, € Qder Startzustand, B das Blanksymbol und FC Q eine Menge von Endzuständen. Eine solche, deterministische Turingmaschine liest also in jedem Schritt das aktuelle Zeichen unter dem Schreib-/Lesekopf, entscheidet abhängig vom aktuellen Zustand und dem gelesenen Zeichen welches neue Zeichen geschrieben, in welchen Folgezustand übergegangen und ob dabei der Schreib-/Lesekopf nach rechts (R), nach links (Z) oder gar nicht (N) bewegt werden soll. Sei nun > = (0,1) und T = (0,1, B). Konstruieren Sie eine Turingmaschine, welche eine Zahl ungleich Null in Binärdarstellung um Eins dekrementiert und die Zahl Null ggf. unberührt lässt. Beachten Sie dabei die folgenden Vorgaben: Auf dem Band steht die gegebene Zahl in Binärdarstellung mit dem niederwertigsten Bit ganz rechts. Führende Nullen sind zugelassen. Beispiel für die Dezimalzahl 13: BB00001101BB. Der Schreib-/Lesekopf steht zu Beginn der Verarbeitung auf dem ersten B links von der Eingabe und soll auch am Ende wieder dort stehen. Schreiben Sie die Übergangsfunktion 6 in Tabellenform nieder, pro Zustand eine Spalte, pro Zeile ein Bandsymbol und dann in jeder Zelle den Folgezustand, das zu schreibende Zeichen sowie die Kopfbewegung. 4. Endliche Automaten Gegeben sei folgender nichtdeterministischer, endlicher Automat A, : A, u (3 5, % {a,}) Q = [9,99,4,9,:4,} = {a,b} dc (Qx2)xQ, &= {((ds)14,) s((dos) 4%) ((4»®)>45) ((4as®) +44)» ((0,14),44)s((2us4)>4)s((4s14)>44)s((2»4)>%)} Fortsetzung nächste Seite! Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 3 4.1. Stellen Sie den Automaten A, graphisch dar. 4.2. Beschreiben Sie die vom Automaten A, akzeptierte Sprache durch einen regulären Ausdruck (ohne Beweise). 4.3. Konstruieren Sie aus A, einen äquivalenten, deterministischen, endlichen Automaten A, und stellen Sie ihn graphisch dar. 4.4. Ist der in 4.3. konstruierte Automat minimal? Begründen Sie Ihre Antwort. Ist der Automat noch nicht minimal, so geben Sie den Minimalautomaten in graphischer Form an. 5. Komplexitätstheorie Sei RUCKSACK = {(A.gw, G,W) |Aendliche Menge, g :Am NwA>NGEeNWe n} und RUCKSACK* = [isso rvexsack ip CA: lg) SGA we) > "). acB acB Das Rucksackproblem besteht darin, für ein gegebenes Tupel x = (A,g,w,G,W) € RUCKSACK zu entscheiden, ob € RUCKSACK™ gilt. Sei TEILE = {ala @ Nendlich} und TEILE* = ja € TEILE be CA: y= i beB bEA\B Das Teileproblem besteht darin, für eine gegebene Menge A € TEILE zu entscheiden, ob A € TEILE* gilt. Das Teileproblem ist NP-vollständig. 5.1. Beschreiben Sie einen nichtdeterministischen Algorithmus zur Lösung des Rucksackproblems in polynomieller Zeit abhängig von der Länge der Eingabe. 5.2. Zeigen Sie, dass das Teileproblem polynomiell auf das Rucksackproblem reduziert werden kann TEILE" <,, RUCKSACK". 5.3. Schließen Sie daraus formal die NP-Vollständigkeit des Rucksackproblems. Fortsetzung nächste Seite! Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 4 6. Verifikation Gegeben ist folgender Algorithmus welcher verifiziert werden soll: = y=0 z=0 while (z < 7 —-1) { y=y+tz+z+l z=z+1 [[tud= 6.1. Geben Sie die Bedingungen an, welche nach dem Ablauf der while-Schleife für das Prädikat Q gelten und geben Sie die Schleifeninvariante an. Begründen Sie Ihre Antwort. 6.2. Führen Sie für diesen Algorithmus eine Verifikation durch, wobei die einzelnen Beweisschritte mit den Regeln der axiomatischen Semantik ausführlich zu beschreiben und zu begründen sind. Rekursion und Iteration 7.1. Es gibt zwei Möglichkeiten die Fakultät F: N* — N* ‚mit F(n) = IE zu berechnen. i=l Zum einen kann sie iterativ und zum anderen rekursiv berechnet werden. Geben Sie für jede der Möglichkeiten jeweils eine Methode in einer höheren Programmiersprache an. 7.2. In der Linearen Algebra ist die Determinante eine Funktion, die jeder quadratischen Matrix eine Zahl zuordnet. Zum Beispiel hat die 2x2-Matrix ab ab) A= ed die Determinante det (A) = d= ad — be. Allgemein wird die Determinante einer n x n Matrix berechnet, indem aus einer gewählten Zeile i jedem Element a, „,...a,, eine Untermatrix A, gebildet wird. Die Untermatrix A, entsteht aus A durch Streichen der i-ten Zeile und j-ten Spalte. Für die Determinante von A gilt: det(A) =) \(-1)* a, -det(A,). j=l Schreiben Sie eine rekursive Funktion in einer höheren Programmiersprache, welche die Determinante der Matrix A bestimmt. Die Funktionsdeklaration könnte in C wie folgt aussehen: float det (oat IL] Matrix, int dimension) Fortsetzung nächste Seite! Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 5 8. Listen, Bäume, Komplexität 8.1. 8.2. 8.3. Nennen Sie den Aufwand von sortierten Listen, balancierten Suchbäumen und sortierten Arrays in Bezug zueinander bei der Speicherung von n Elementen für die Operationen Element finden und Element einfügen bzw. löschen. Geben Sie ebenfalls den zusätzlichen Speicherbedarf für die Verwaltung der Datenstrukturen an. Kriterium Listen Bäume Arrays Element finden Element einfügen bzw. löschen zusätzlicher Speicherbedarf Gesucht ist ein nicht notwendigerweise balancierter binärer Suchbaum, bei welchem in jedem Knoten eine Zahl n € N gespeichert ist. Für jeden Knoten gilt, dass alle Knoten, welche an seinem linken (rechten) Ast hängen, kleinere (größere) Elemente als n gespeichert haben. Ferner gibt es in dem Suchbaum keine doppelten Elemente n. Geben Sie eine Methode insert (n ) zum Einfügen und eine Methode search (n) zum Suchen eines Elementes an. Fügen Sie mit der Methode insert ( n ) die Elemente 5, 14, 2, 8, 14, 7 in einen leeren Baum ein und geben Sie den Baum nach jedem Einfügen eines Elementes an. Im Weinkeller eines grausamen Königs befinden sich n wertvolle Weinflaschen. Seine Wächter haben einen Hexer gefangen genommen, der genau eine Flasche vergiftet hat. Unglücklicherweise wissen sie nicht welche, Das Gift ist jedoch so stark, dass man sogar dann sterben würde, wenn man den Wein aller Flaschen vermischt und davon kostet. Allerdings wirkt das Gift so langsam, dass man erst einen Monat später daran erkrankt. Mit welcher Methode könnte der König innerhalb eines Monats feststellen, welche Flasche vergiftet ist und dabei höchstens O(log n) Vorkoster einsetzen? Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 6 Thema Nr. 2 Teilaufgabe I Wir fixieren das Alphabet > = {0,1} und definieren ZL C 0° durch L = {w| in w kommt genau einmal das Teilwort 0010 vor } 1. Zeigen Sie, dass L regular ist! 2. Geben Sie die Aquivalenzklassen der Myhill-Nerode Äquivalenz von Z durch Repräsentanten an, (Diese Aquivalenz ist definiert durch ~, y > Vu.cu € L & yu € L 3. Zeichnen Sie den Minimalautomaten für L. Teilaufgabe II Sei 7, das Alphabet {0,1}". Ein Buchstabe in D, ist also ein n-Tupel von Oen und len; das Alphabet I, hat 2" Buchstaben. Ist w € I, so bezeichne w,das Wort über), das aus den ersten Komponenten der Buchstaben in w besteht, formal also w, = f(w)für den durch f (2, )) =x, definierten Homomorphismus f. Analog definiert man w,,w,,etc. Also gilt für w= (0,1,1)(1,1,0)(0,0,1)(1,1,1), dass w, = 0101,w, = 1101,w, = 1011. Für w € yi bezeichne num (w) € N die Bedeutung von w aufgefasst als von rechts nach links gelesene Binärdarstellung. Also num (10110000) = 13. Die "Inverse" (bis auf Nullen am Ende) von num bezeichnen wir mit bin, also bin(19) = 11001. 1. Zeigen Sie, dass L= {w ED, num (w,) = num (w,) +num (w,)} regular ist. 2. Für veD undve)D) sei (u,v) € >, _ das durch leo \- x (laul, ful) num (u, a = num (u) num (u,v a= = num (», ) eindeutig definierte Wort. Sei LC D, regulär. Es sei r= {w ED)! esexistiertn € N, sodass (bin (n),w) € L} Zeigen Sie, dass L’ regular ist. 3. Programmieren Sie die vier Funktionen bin, num, w ++ w, und u,v ++ (u,v) in einer funktionalen Programmiersprache Ihrer Wahl oder Pseudocode. Zur Beachtung: das möglicherweise erforderliche Auffüllen von v mit Nullen bei der Berechnung von (u, v) beinhaltet eine gewisse Schwierigkeit, da v € D, für beliebiges n. Es bietet sich an, die Tupel als Listen zu implementieren. Programmieren Sie auch eine boole'schwertige Funktion, die die Zugehörigkeit zur in 1) definierten Sprache prüft. Fortsetzung nächste Seite! Frühjahr 2006 Einzelprüfungsnummer: 66112 Seite: 7 Teilaufgabe III Es soll ein Mühlespiel programmiert werden. Die beiden Spieler sollen abwechselnd mit der Maus Züge wählen; das Programm soll überprüfen, ob ein Zug erlaubt ist und das Ergebnis des Zuges auf dem Bildschirm anzeigen. 1. Skizzieren Sie einen objektorientierten Entwurf für diese Aufgabenstellung in Form eines Klassendiagramm (in UML o.ä.). Ihr Diagramm sollte nicht weniger als fünf Klassen haben und neben den Beziehungen der Klassen untereinander auch deren wichtigste Methoden und Attribute beinhalten. 2. Das Programm muss mehrere Zustände haben, aus denen hervorgeht, welcher Spieler am Zug ist, ob die Maus gedrückt wurde, ob das Spiel zu Ende ist, etc. Modellieren Sie diese Programmzustände als Ablaufdiagramm.