Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Frü hj ahr 46115 Arbeitsplatz-Nr.: 2 0 1 2 Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — En Fach: Informatik (Unterrichtsfach) Einzelprüfung: Th. Informatik, Algorith./Datenstr. Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 7 Bitte wenden! Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 2 Thema Nr. 1 Aufgabe 1: Turingmaschinen Die Turingmaschine ,,Reverse“ spiegelt das gegebene Eingabewort. Aus dem Wort FUNKTION wird so zum Beispiel das Wort NOITKNUF. a) Beschreiben Sie die Arbeitsweise der Turingmaschine „Reverse“! b) Geben Sie die Turingtafel von „Reverse“ an! Verwenden Sie nach Möglichkeit nicht mehr als fünf Zustände! c) Geben Sie den Zeitaufwand einer Berechnung von „Reverse“ in Abhängigkeit von der Eingabelänge an! Aufgabe 2: Chomsky-Hierarchie Sei L = {a"b" 20} ! a) Beweisen Sie mittels Pumping-Lemma, dass L nicht kontextfrei ist! b) Zeigen Sie, dass das Komplement von L kontextfrei ist! c) Zeigen Sie, dass das Komplement von L nicht regulär ist! Aufgabe 3: Entscheidbarkeit Das Wortproblem lautet: Kann für eine Sprache immer entschieden werden, ob ein Wort ein Element der Sprache ist oder nicht? Begründen Sie, für welche der folgenden Sprachklassen der ChomskyHierarchie das Wortproblem entscheidbar ist! a) Reguläre Sprachen (Typ 3) b) Kontextfreie Sprachen (Typ 2) c) Kontextsensitive Sprachen (Typ 1) d) Rekursiv aufzählbare Sprachen (Typ 0) Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 3 Aufgabe 4: Komplexitätsklassen Ordnen Sie das Wortproblem (siehe Aufgabe 3) in Komplexitätsklassen ein, sofern es für den betreffenden Sprachtyp entscheidbar ist. Skizzieren Sie zur Begründung das jeweilige Entscheidungsverfahren. a) Reguläre Sprachen (Typ 3) b) Kontextfreie Sprachen (Typ 2) c) Kontextsensitive Sprachen (Typ 1) d) Rekursiv aufzählbare Sprachen (Typ 0) Aufgabe 5 Mit Hilfe des Java-Programms DezHex werden dezimale Ganzzahlen in hexadezimaler Schreibweise (auch hexadekadisch bzw. sedezimal genannt) dargestellt. Die Eingabewerte werden dabei fortgesetzt ganzzahlig durch 16 dividiert, der jeweilige Rest (>=0) ist der Wert einer Ziffer der gesuchten : Hexadezimalzahl. Ergänzen Sie die Klasse Hex durch eine rekursive Methode revout (int z), welche die gesuchte Hexadezimalzahl ausgibt. Die Hexadezimalzeichen sind dabei in der korrekten Reihenfolge auszugeben. Quelltext DezHex 1 class Hex { 2 char[] ziffern = {'0','1','2','3','4','5',"6','7', 3 Ter, TO’ TAM IBY fol I Dt 'RI, ' Ry; 4 int h = 16; 5 6 // Methode revout () 7 u 8 } 9. 10 class Converter { 11 public static void main(String[] args) throws IOException { 12 . int zahl; 13 BufferedReader stdin = 14 new BufferedReader (new InputStreamReader (System.in)); 15 String inData; 16 17 System.out.printin("Dezimalzahl eingeben:"); 18 inData = stdin.readLine (); 19 zahl = Integer.parselnt (inData); 20 21 Hex hex = new Hex(); 22 hex.revout (zahl); 23 } 24 } Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 4 Aufgabe 6 Gegeben sei der folgende gerichtete Graph G = (V, E, d) mit den angegebenen Kantengewichten. a) Geben Sie eine formale Beschreibung des abgebildeten Graphen G durch Auflistung von V, E und dan. b) Erstellen Sie die Adjazenzmatrix A zum Graphen G. c) Berechnen Sie unter Verwendung des Algorithmus nach Dijkstra —- vom Knoten A beginnend — den kürzesten Weg, um alle Knoten zu besuchen. Die Restknoten werden in einer Halde (engl. Heap) gespeichert. Geben Sie zu jedem Arbeitsschritt den Inhalt dieser Halde an. Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 5 Thema Nr. 2 Aufgabe 1: Datentypen Betrachten Sie das Verhalten von Kellern (stack), Warteschlangen (queue) und Prioritätswarteschlagen (priorityqueue oder heap), in die Zahlen eingefügt und wieder gelöscht werden! Für die Prioritäten gilt „x vor y“ genau dann, wenn x > y ist. in(x) bedeutet, dass die Zahl x eingefügt wird (in der Java API add(E 0) oder push(E 0)) out() gibt eine Zahl aus und löscht das ausgegebene Element (in der Java API pop() . oder poll( )). Am Anfang sind die Objekte der Datentypen leer. In welcher Reihenfolge werden die Zahlen bei der nachfolgenden Sequenz in(10), in(2), in(6), in(5), in(3), in(1), out(), out(), in(15), out(), outO), in(12), in(7), out(), out(), out(), in(4), out(), out(), out() a) bei einem Keller, b) bei einer Warteschlange, c) bei einer Prioritätswarteschlange (mit x>y) ausgegeben? Aufgabe 2: O-Notation Gegeben sind die Funktionen £ NN, fin)=2nlognund g: NON, g(n)=n3. Zeigen Sie, dass f € 0 (g(n)). Aufgabe 3: binäre Suchbäume Fügen Sie nacheinander die Zahlen 10 15 22 8 6 20 7 in einen anfangs leeren binären Suchbaum ein und zeichnen Sie den Suchbaum! Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 6 Aufgabe 4: AVL-Bäume a) Fügen Sie nacheinander die Zahlen 10 15 22 8 6 20 7 in einen anfangs leeren AVL-Baum ein! Repräsentieren (zeichnen) Sie alle AVL-Bäume jeweils vor einer notwendigen Rotation und beschreiben Sie die Rotationen (z. B. LL-Rotation für die Nummern ...)! b) Die Zahl 15 soll anschließend wieder gelöscht werden. Was muss man tun? Beschreiben Sie dies informell! Aufgabe 5: reguläre Mengen Gegeben sei die Menge L aller Worte w e {a,b}*, bei denen das erste und das zweite Zeichen gleich sind oder w das leere Wort (A oder €) ist. ' a) Geben Sie einen regulären Ausdruck für L an! b) Geben Sie einen deterministischen endlichen Automaten für L an. Aufgabe 6: Abschlusseigenschaften Zeigen Sie durch die Konstruktion entsprechender Automaten, Grammatiken oder Ausdrücke, dass die regulären Mengen abgeschlossen sind i) unter Vereinigung. (ii) unter Komplementbildung. Aufgabe 7: kontextfreie Sprachen Zeigen Sie durch die Konstruktion einer kontextfreien Grammatik oder eines Kellerautomaten, dass die Sprache L kontextfrei ist. L= {w=aPbilc | p,gr>1, p=q oder g=r} Fortsetzung nächste Seite! En Frühjahr 2012 Einzelprüfungsnummer 46115 Seite 7 Aufgabe 8: Turingmaschinen Konstruieren Sie eine deterministische Turingmaschine M für die Sprache L = {w=aPbdkc" | p,gr>1, p=q oder g=r}. Beschreiben Sie informell, wie Ihre Turingmaschine arbeitet. (M liest die Zeichen a und schreibt ...) Aufgabe 9: P& NP Das Hamilton-Kreis-Problem ist die Frage, ob es in einem ungerichteten Graph G = (V, E) einen einfachen Kreis K gibt, der jeden Knoten genau einmal durchläuft (wobei der Start- und der Endknoten gleich sind). Erläutern Sie, warum dieses Problem in NP ist. (Es ist nicht gefordert zu zeigen, dass dieses Problem NP-schwer ist).