Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst 2010 Kennwort: 66115 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Theoret. Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 6 Bitte wenden! Herbst 2010 Einzelprüfungsnummer: 66115 - Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! 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 uneinge‘schrä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: Wir fixieren das Alphabet & = {a,b} und definieren L C %* durch L= {w | in w kommt genau einmal das Teilwort aaba vor} Z.B. ist baababb € L, aber baabaabab ¢ L. a) Zeigen Sie, dass L regular ist. b) Konstruieren Sie den Minimalautomaten für L. c) Geben Sie die Aquivalenzklassen der Myhill-Nerode Aquivalenz von L durch Reprasentanten an. (Diese Aquivalenz ist definiert durch en; y = > Vu.cue L & yue L.) Tipp: Die Vereinigung aller Klassen muss {a,b}* ergeben und ihre Anzahl entspricht der Zustandszahl des Minimalautomaten. Aufgabe 2: Wir fixieren wieder das Alphabet © = {a,b} und betrachten die Sprache L = {(ab)"a(ba)" |n > 1}. a) Obwohl es auf den ersten Blick nicht so aussieht, ist diese Sprache regulär. Begründen Sie das. b) Professor Pump versucht fälschlicherweise mithilfe des Pumpinglemmas nachzuweisen, dass L nicht regulär ist. Er schreibt: Nehmen wir an, L sei regulär. Dann gibt es eine Pumpingzahl n. Wir betrachten w = (ab)"a(ba)”. Sei jetzt w = xyz eine Zerlegung derart, dass |vy| < n und |y| > 1. Laut Pumpinglemma wäre nun aber zz auch in L. Das ist ein Widerspruch, da xy nach Annahme vollständig im (ab)"-Block von w liegt und somit xz nicht in L sein kann. Begründen Sie detailliert, an welcher Stelle Professor Pump irrt und geben Sie eine Pumpingzahl n für L an. Legen Sie konkret dar, wie jedes Wort w € L mit |w| > n so zerlegt werden kann, wie es vom Pumpinglemma garantiert wird. c) Weisen Sie nun durch korrekte Anwendung des Pumpinglemmas nach, dass 2’ = {(ab)"b(ba)” | n > 1} wirklich nicht regulär ist. Fortsetzung nächste Seite! Herbst 2010 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: Das Multiprozessor-Scheduling-Problem ist wie folgt formuliert: - GEGEBEN: Eine Zahl n von Prozessen und deren Laufzeiten tı,...,t„; eine Zahl m von Prozessoren; eine Deadline D. - GESUCHT: Eine Aufteilung der n Prozesse auf die m Prozessoren; so dass die Summe der Laufzeiten der Prozesse, die einem Prozessor zugeordnet sind, jeweils unterhalb von D bleibt. . e Die Zahlen n,m,tı,...,tm, D sind natürliche Zahlen und in Binärdarstellung gegeben. Weisen Sie nach, dass das Multiprozessor-Scheduling-Problem NP-vollständig ist, indem Sie ein geeignetes NP-vollständiges Problem auf das Multiprozessor-Scheduling-Problem reduzieren. Tipp: Es bietet sich folgender Spezialfall einer vereinfachten Variante des Rucksackproblems an. Gegeben: n natürliche Zahlen ay, ..., am; gesucht: eine Auswahl J C {1,...,n} so, dass }7,., a; = 6 mit b= $77, ai. Aufgabe 4: Gegeben ist eine Menge V von “Arten” und für je zwei Arten v,,v2 € V eine “genetische Distanz” d(v1,v2) die ein Maß dafür ist, wie sehr sich die Gene von v, von denen von v, unterscheiden. Je größer d(vı, v2), umso unterschiedlicher sind v; und v3 aus genetischer Sicht. Es gilt natürlich d(v,v) = 0 für alle v € V und d(v1, v2) = d(v2, v1) > 0 für alle vy, v2 € V. Gesucht ist ein nicht notwendigerweise binärer Baum (“Stammbaum”), dessen Knoten die “Arten” sind und der die Eigenschaft hat, dass die Summe der “genetischen Distanzen” zwischen Eltern und Kindern im Baum möglichst klein ist. a) Welche bekannte graphentheoretische Problemstellung liegt dieser Aufgabe zugrunde? b) Nennen Sie einen Standardalgorithmus, mit dem diese Aufgabe gelöst werden kann. c) Skizzieren Sie den Ablauf des Algorithmus am folgenden Beispiel mit den Arten {A, B,C, D, E, F,G}. Die redundanten Einträge sind weggelassen. d|A BCD EF G A 7 19 5 16 18 16 B 8 9 7 16 15 C 165 18 17 D 15 6 19 - 8 9 F 11 Herbst 2010 Einzelprüfungsnummer 66115 Seite 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Datentypen Betrachten Sie das Verhalten von Kellern (stack), Warteschlangen (queue) und Prioritätswarteschlangen (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. 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 alle Datentypen leer. In welcher Reihenfolge werden die Zahlen bei der nachfolgenden Sequenz ausgegeben? in(10), in(2), in(6), in(5), in(3), in(1), out(), out(), in(15), out(), out(), 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 Zeigen Sie dass f(n) e O(g(n)) gilt für f(n) = 4 n- log(n) + 20 g(n) = n? Aufgabe 3: Hashing Gegegen sei ein Array der Größe 10, z.B. int [ ] hashfeld = new int [10]. Die Hashfunktion sei der Wert modulo 10, h(x)= x% 10. Kollisionen werden mit linearer Verschiebung um 1 (modulo 10) gelöst. in(x) bedeutet, dass die Zahl x eingefügt wird, search(x), dass nach x gesucht wird mit den Antworten „ja“ bzw. „nein“ und out(x), dass x gelöscht wird, sofern x gespeichert ist. Es wird folgende Sequenz von Operationen auf ein anfangs leeres Array ausgeführt: in(19), in(29), in(39), in (10), out(29), out(39), search(29), in(11), in(17), out(10), in(2), in(22) Geben Sie den Inhalt von hashfeld an nach search(29) nach out(10) und nach in(22). Fortsetzung nächste Seite! Herbst 2010 Einzelprüfungsnummer 66115 Seite 5 Aufgabe 4: AVL Bäume a) Fügen Sie nacheinander dieZahlen 10 15 2 6 7 20 1 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 gelöscht werden. Was muss man tun? Aufgabe 5: kürzeste Wege Ein gerichteter Graph G sei durch folgende Entfernungsmatrix gegeben: Die 2 beim Eintrag (a,b) bedeutet, dass es eine Kante der Länge 2 von a nach b gibt. Gesucht ist ein (der) kürzester Weg von a nach h. a) Beschreiben Sie, wie der Dijkstra-Algorithmus auf G arbeitet. Geben Sie dazu an, in welcher Reihenfolge die Knoten bearbeitet werden, und welche Werte dort gespeichert werden. b) Wie lang ist der kürzeste Weg von a nach h? c) Der Dijkstra-Algorithmus soll nur auf Graphen mit Kanten mit nichtnegativer Länge angewendet werden. Erläutern Sie, warum das so ist. Aufgabe 6: reguläre Mengen Gegeben sei die Menge aller Wörter w e {a,b}*, der Länge mindestens 2, bei denen das zweite und das zweitletzte Zeichen gleich sind. Zeigen Sie, dass diese Sprache regulär ist. Tipp: Beachten Sie auch die Wörter der Längen 2 und 3. Fortsetzung nächste Seite! Herbst 2010 Einzelprüfungsnummer 66115 Seite 6 Aufgabe 7: kontextfreie Sprachen Gegeben sei die Grammatik G=({S}, {a,b}, S, P) mit den Produktionen S -> SS, S --> aSb, S--> bSa und S->E a) Welche Eigenschaft haben die Wörter w e L(G) bezüglich der Anzahl der Zeichen a und b? b) Geben Sie eine Ableitung (Ableitungsbaum) an für das Wort aaabbbbbaa. c) Geben Sie alle Wörter der Länge vier von L(G) an. d) Ist L(G) regulär? Begründen Sie Ihre Antwort. Als Begründung müssen Sie entweder eine reguläre Beschreibung (Automat, Ausdruck) angeben oder den Widerspruch begründen. Dabei darf das Pumping Lemma als bekannt vorausgesetzt werden. Man muss das passende Pumping Lemma geeignet anwenden. Aufgabe 8: Turingmaschinen Konstruieren Sie eine Turingmaschine M mit L(M) =L, wobeip,q >21. Beschreiben Sie zusätzlich, wie M arbeitet (Stil: M liest das Zeichen a und speichert ....) L={w| we {a,b}*, w bestehtaus p Zeichena undaus q Zeichenb }. Aufgabe _9: NP und Graph Färbbarkeit Zeigen Sie durch Angabe eines nicht-deterministischen Verfahrens, dass 3-Färbbarkeit in NP liegt. Instanz: Ein Graph G = (V,E) Problem: Gibt es eine 3-Färbung der Knoten, so dass benachbarte Knoten verschiedene Farben haben. Hinweis: 3-Färbbarkeit ist sogar NP-schwer. Das muss nicht gezeigt werden.