Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 66115 2015 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (verieft studiert) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 10 Bitte wenden! Herbst 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 © = {a,b} enthält alle Wörter, in denen das Wort bab, oder das Wort aba, oder beide vorkommen. Also ist z.B. babbba € L, aber bbaabbb ¢ L. a) Begründen Sie, dass L regular ist. b) Geben Sie einen nichtdeterministischen Automaten für L mit 7 Zuständen an. Der Automat soll zu Beginn nichtdeterministisch entscheiden, ob nach bab oder aba gesucht wird. c) Führen Sie auf diesem Automaten die Potenzmengenkonstruktion durch und minimieren Sie anschließend den resultierenden deterministischen Automaten. d) Geben Sie ein Beispiel (mit Begründung!) einer Sprache an, welche nicht durch einen deterministischen endlichen Automaten mit nur einem Endzustand erkannt werden kann. e) Begründen Sie, dass jede Sprache L C {a,b}? (NB: e & L) von einem nichtdeterministischen Automaten mit nur einem Endzustand erkannt werden kann. Hinweis: Sie können die Sprachen U = {w| wa € L} und V = {w | wb € L} verwenden. Aufgabe 2: Gegeben ist ein gerichteter Graph G = (V, E), der eine Web-Site repräsentieren soll. Die Knoten des Graphen sind die einzelnen Seiten; eine Kante (v,v’) € E bedeutet, dass die Seite v’ auf der Seite v verlinkt ist. Weiterhin sind eine Menge P von “Trails”, also typischen Besuchssequenzen gegeben. Jeder solche Trail ist einfach ein Pfad in G, also eine Folge (vı,...,%,) von Knoten mit (vi, Vier) € & für i = 1...n—1. Diese Trails werden durch statistische Analyse des Surfverhaltens der Besucher der Web-Site ermittelt. Nun soll ein Algorithmus gefunden werden, der Werbeanzeigen möglichst effizient platziert; hierzu soll zu gegebener Zahl k, eine Auswahl W von k Seiten (also Knoten von G) ermittelt werden, sodass jeder Trail mindestens eine Seite in W enthält. Zeigen Sie durch Reduktion von einem geeigneten Problem aus dem Informatikduden oder aus der von Ihnen besuchten Vorlesung, dass es NP-vollständig ist zu entscheiden, ob bei vorgelegten G,P und k eine solche Auswahl W existiert. Beachten Sie, dass Sie sowohl die Zugehörigkeit zu NP, als auch die NP-Härte (NP-Schwere) zeigen müssen. Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: Beim Postschen Korrespondenzproblem (PCP) ist bekanntlich eine Liste von Paaren (11, U1),-.-, (Un, Un) mit u,v; € D* für ein Alphabet D gegeben. Zum Beispiel (u, vı) = (b, bab) und (tg, v2) = (ba, aa) und (us, vs) = (abb, bb), wobei hier also n = 3 und D = {a,b} sind. Gefragt ist, ob es eine Indexfolge 74, t2,...,1nN, wobei i, 5 sein. Beispiel: (21,22,23,24) = (6,7,12,14) und (rı,r2,r3,rı) = (5,6,5,1). Hier könnten Sie bei km 7 und km 14 werben, was einen Gewinn von 700TEUR liefert, oder aber bei km 6 und 12, was einen Gewinn 1IMEUR liefert. Dass das Aufstellen der Tafeln auch Kosten verursacht, bleibt hier außer Betracht. 1.Für jedes i < n sei f{f) die größte Zahl unterhalb von i, sodass x; — zyü) > 5. Der Wert f(t) sei undefiniert, wenn keine solche Zahl existiert. Im Beispiel ist f(4) = 2, f(3) = 1 und f(2), f(1) sind undefiniert. Beschreiben Sie, wie die Werte f(n), f(n—1),..., f(1) zusammen in Zeit O(n) bestimmt werden können. 2.Sei W; der maximal erzielbare Gewinn bei ausschließlicher Verwendung der Positionen £1,.-.,%;. Überlegen Sie sich, wie man W; aus den Werten W,; für j < i berechnen kann. 3.Beschreiben Sie, wie W, mit dynamischer Programmierung in Zeit O(n) berechnet werden kann. Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: “Bäume und Rekursion “ Gegeben sei folgende Klasse Node für binäre Bäume: class Node implements Comparable { char c; // irrelevant for inner nodes int f; // frequency (number of occurrences of c) Node zero; // child Node one; // child // creates a leaf public Node(char c, int f) { this.c = c; this.f = f; } // creates an inner node public Node(Node zero, Node one) { this.f = zero.f + one.f; this.zero = zero; this.one = one; } // natural ordering based on the frequency @Override public int compareTo(Node that) { return this.f - that.f; } } Aus der Java-API dürfen Sie auch folgende Methoden verwenden: HashMap: > V put(K key, V value) > V get(Object key) Collections: } static > void sort(List list) LinkedList: » int sizeQ) b> E removeFirst0 > void addFirst(E e) String: > char charAt(int index) > String substring(int beginindex) a) Ergänzen Sie die Methode count, welche die HashMap map von Node-Objekten anlegt. Für jedes Zeichen c des übergebenen Strings s soll map ein Node-Objekt für dieses Zeichen in Node.c enthalten. Am Ende der Schleife gibt Node. £ jeweils an, wie oft das Zeichen c in s vorkommt. Das in der letzten Code-Zeile erzeugte Ergebnis von count ist die Liste der Node-Objekte aus map. Beispiel: Ergebnis für (oy Per? cee’ cr co" er eh count("helloworld”) fa fa fel fel 2 =) fel Linkediist count(String s) { assert s f= null : new IllegalArgumentException(); HashMap map = new HashMap<>(); for (char c : s.toCharArray()) { // TeDe: Code hier ergaenzen } return new LinkedList<>(map.values()); Fortsetzune nächste Seitel Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 5 b) Vervollständigen Sie die Methode merge, die zuerst die Node-Liste mit der APIMethode Collections. sort sortiert, damit die kleinsten Knoten X und Y (bzgl. compareTo) am Anfang der Liste stehen. Dann verschmilzt sie X und Y zu einem neuen inneren Knoten N, wobei X zum zero-Kind und Y zum one-Kind von N wird. Anschließend werden X und Y aus der Liste entfernt und N hinzugefügt. Beispiel: ce ch’ Erster Durchlauf von f3 fel merge(count(s)) far s = "helloworld" Schließlich wiederholt merge den vorangehend beschriebenen Vorgang, bis nur noch ein Knoten (die Wurzel des Baums) in der Liste übrig bleibt. Beispiel: merge(count("helloworld")): cll f=3 te er f=1 f=1 void merge(LinkedList nodes) { // ToDde: Code hier ergaenzen Der Pfad von der Wurzel des resultierenden Baums zu einem Zeichen c stellt dessen Huffman-Codierung dar: h e io wo r tod b < 100 1010 11 11 01 600 01 1017 11 002 Ergänzen Sie nun die rekursive Methode dec, die eine als String aus 0 und 1 gespeicherte Bitfolge b wieder zur ursprünglichen Zeichenkette dekodiert. Dazu traversiert sie den Baum wiederholt entsprechend der Folge b: Sobald ein Blatt erreicht wird, ergänzt sie das Zwischenergebnis mit dem zugehörigen Zeichen und beginnt die Dekodierung der restlichen Folge wieder an der Wurzel des Baums. Falls die Folge vorzeitig (vor Erreichen eines Blatts) endet, dann kann nicht entpackt werden und die Methode muss eine IllegalArgumentException Werfen. String decode(Node root, String b) { assert (root != null && b I= null) : new IllegalArgumentException()}; return dec(root, root, b); } String dec(Node root, Node node, String b) { // Todo: Code hier ergaenzen Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 6 Aufgabe 2: “Haldensortierung “ Gegeben sei folgende Klasse: class W { int t; String f; fh ses Dazu gibt es verschiedene Comparatoren, zum Beispiel: // ascending order for field W.t class ComparatorAscByFieldT implements Comparator { // Returns a negative integer, zero, or a positive integer as the // first argument is less than, equal to, or greater than the second. @0verride public int compare(W ol, W 02) { // ... Außerdem steht Ihnen die vorgegebene Methode swap zur Verfügung: void swap(W[] w, int a, int b) { // ... a) Phase 1: Die Haldensortierung beginnt mit der Herstellung der Max-HeapEigenschaft von rechts nach links. Diese ist für alle Feldelemente im dunklen Bereich bereits erfüllt. Geben Sie die Positionen (IDs) derjenigen Elemente des Feldes an, die das Verfahren im ,Versickerschritt* far das nächste Element mit Hilfe des ComparatorAscByFieldT miteinander vergleicht: IDsangeben> 0 1 2 3 4 5 6 c wiederherstellt, indem sie das Element w[i] „versickert‘. k bezeichnet das Ende des unsortierten Bereichs. Fortsetzune nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 7 // restores the max-heap property in w[i ta k] using ¢ void reheap(W[] w, Comparator c, int i, int k) { int leftId = 2 * i + 1; int rightId = leftId + 1; int kidId; } // ToDo: Code hier ergaenzen d) implementieren Sie nun die eigentliche Haldensortierung. Sie dürfen hier die Methode reheap verwenden. // sorts w in-situ according to the order imposed by c void heapSort(W[] w, Comparator c) { int n = w.length; // Phase 1: Max-Heap-Eigenschaft herstellen ff (siehe Teilaufgabe a) // ToDo: Code hier ergaenzen // Phase 2: jeweils Maximum entnehmen und sortierte Liste am Ende aufbauen ff (siehe Teilaufgabe b) // Tobo: Code hier ergaenzen Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 8 Aufgabe 3: “Laufzeitanalyse mittels Landau-0-Kalkül“ Gegeben seien die folgenden Methoden, in denen bestimmte Stellen mit Kommentaren der Form /** x **/ markiert sind. Geben Sie zunächst für jede solche Stelle einer Methode eine geschlossene Formel an, die exakt berechnet, wie oft die jeweiligen Stellen, in Abhängigkeit von den Eingangsgrößen n und m, durchlaufen werden. Ermitteln Sie anschließend für diese Quellcode-Fragmente jeweils die kleinste obere Schranke für den Laufzeitaufwand im O-Kalkül (Landau-Notation) abhängig von den Parametern. Skizzieren Sie in wenigen Sätzen, wie Sie die Aufwandklasse abgeschatzt haben — eine Beweisführung ist nicht verlangt. a) matrixVectorMul static int[] matrixvectorMul(int[{][] mat, int[] vec) { int hoehe = mat.length; /* -> m */ if (hoehe <= @) return new int[9]; int breite = mat(@].length; /* -> n */ int[] erg = new int[hoehe]; for (int zeile = @; zeile < hoehe; ++zeile) { er 1 “x for (int spalte = 8; spalte < breite /** 2 **/; ++spalte) { erg[zeile] +—mat[zeile][spalte] * vec[spalte]; jr 3 #8] } } return erg; } b) zaehlen static int zaehlen(int n) { int count = 8; while (n > 8) { if (n % 2 == 1) { ++Count; } n /= 2; /** 4 ef } return count; } c) f static int f(int n) { if (n <= 6) { return @; } else { for (int i = 0; i < nj ++i) { /* Operationen mit konstantem Aufwand */ return f(n / 2); } } Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 9 Aufgabe 4: Zeigen oder widerlegen Sie die folgenden Aussagen (die jeweiligen Beweise sind sehr kurz): a) Sei LC D*. Ist Z regulär, so ist jede Teilmenge U von Z auch regulär. b) Sei Z eine Sprache über dem Alphabet D, die rekursiv aufzählbar (= partiell-entscheidbar), aber nicht entscheidbar ist. Sei Z = D* \ L das Komplement von L. Dann ist L rekursiv aufzählbar. c) Seien LZ, und La beliebige kontextfreie Sprachen über dem Alphabet %. Dann ist InN La entscheidbar. d) Alle Probleme in NP sind entscheidbar. Schreiben Sie zuerst zur Aussage „Stimmt“ oder „Stimmt nicht“ und dann Ihre Begründung. Aufgabe 5: a) Sei m € INo = {0,1,2,...}. Definieren Sie formal die Menge H,, der Gödelnummern der Turing-Maschinen, die gestartet mit m halten. b) Gegeben sei das folgende Problem E: - Entscheide, ob es für die deterministische Turing-Maschine M mit der Gödelnummer (M) mindestens zwei Eingaben wı, wa € INo, wı ~ We, gibt, so dass die Maschine M gestartet mit w, halt und dass M gestartet mit wa hält. Zeigen Sie, dass E nicht entscheidbar ist. Benutzen Sie, dass H,, aus (a) für jedes m € INo nicht entscheidbar ist. c) Zeigen Sie, dass das Problem E aus (b) partiell-entscheidbar (= rekursiv aufzählbar) ist. Aufgabe 6: a) Gegeben sei der folgende nichtdeterministische endliche Automat N: b) Geben Sie einen regulären Ausdruck a{N) für die Sprache, die der nichtdeterministische endliche Automat N aus (a) akzeptiert, an. Fortsetzung nächste Seite! Herbst 2015 Einzelprüfungsnummer: 66115 Seite: 10 c) Sei L = {a*b* | k € IN}. Jemand behauptet, einen deterministischen endlichen Automaten mit Zustandsmenge Q = {go, --- ‚9n-ı}, Startzustand go und Endzustandsmenge F konstruiert zu haben mit L = L(A). Geben Sie in Abhängigkeit von A ein Wort z € L an, das folgende Eigenschaft besitzt: Aus einer akzeptierenden Rechnung von A für z können Sie ein Wort 2 konstruieren mit der Eigenschaft: (i) A akzeptiert 2 und (ii) Z ¢ L. Beweisen Sie konkret die Eigenschaften (i) und (ii) für Ihr Wort z. Nachtrag zur Einzelprüfungnr. 66115, Thema 2 Seite 9, Aufgabe 6, Buchstabe a) Bitte fügen Sie nach dem abgebildeten nichtdeterministischen endlichen Automaten folgende Fragestellung ein: „Konstruieren Sie zu N mit der Potenzmengen-Konstruktion einen äquivalenten deterministischen endlichen Automaten A. Zeichnen Sie die nur vom Startzustand erreichbaren Zustände ein, diese aber alle. Die Zustandsnamen von A müssen erkennen lassen, wie sie zustande gekommen sind. Führen Sie keine „Vereinfachungen“ durch!“