Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: 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: 7 Bitte wenden! Herbst 2013 Einzelprüfungsnummer 66115 Thema Nr. I TellaufgabeI Essel = {1,2} und L¢ &* die Menge aller Wérter erry... cn, derart, dass S$"; ein Vielfaches von drei ist. So ist, z.B. 12112 € L, denn I4+2 414142 7, aber 1221 € Z, den 1+- 2+2 +1 == 6, Delinitionsgemäß ist- auch das leere Wort «€ L. \ 3, Konstruieren Sie einen deterministischen endlichen Automaten für I. 2. Minimieren Sie Ihren Automaten oder begründen Sie, dass er bereits minimal ist. : 3. Leiten Sle aus diesem Automaten einen regulären Ausdruck für 2 ab. Dokumentieren Sie Ihre Arbeitsschritte eceignet, 4. Geben Sie zwei unterschiedliche Wörter an, die im Sinne der MyhillNerode Aquivalenz ~; äzuivalent sind. Biinnerung un, > Voum € Ee vip € L. Begründen Sie Ihre Antwort, 5. Beweisen oder widerlegen Sie folgende Aussage: Llala+b)*) = L((ab")"ab"), wobei L(a) die durch den regulären Ausdruck a definierte Sprache bezeichnet. Ist die Aussage falsch, so müssen Sie ein konkretes Wort angeben, welches aufeinen der beiden regulären Ausdrücke passt und auf den anderen nicht. Ist sie wahr, so müssen Bie beide Richtungen © und I zeigen. Teilaufgabe II Wie man weiß ist die Sprache L = {a"b*e® |n > 0} über dem Alphabet % = {a,b,c} nicht kontextfrei. Dies dürfen Sie im folgenden ohne Begründung voraussetzen. 1. Finden Sie zwei kontextfreie Sprachen Z, und La, sodass L = und. Geben Sie jeweils Grammatiken für diese Sprachen an. Hinweis: L, sorgt dafür, dass die Zahlen der a’s und b’s übereinstimmen, bo . Warum folgt daraus, dass die Klasse der kontextfreien Sprachen nicht unter Komplement abgeschlossen ist? 3. Bekanntlich ist der Schnitt einer kontextfreien Sprache mit einer regillären Sprache wieder kontextirei. Folgern Sle, dass die Sprache L’ = {w | ul, = ws = wie} nicht kontextfrei ist (hier bezeichnet |w|. die Anzahl der Vorkommen des Buchstaben z in ww). Fortsetzung nächste Seite! Herbst 2013 Einzelprüfungsnummer 66115 Seite 3 Tellaufgabe IT] Wir betrachten das wie folgt definierte Problem DOPP: GEGEBEN: Eine deterministische "Turingmaschine M, eine Eingabe x (für M), ein Zustand q (von M), GEFRAGT: Wird der Zustand g bei der Berechnung von M auf z mindestens zweims] besucht? 1. Zeigen Sie durch Angabe einer Reduktion vom Halteproblem, dass DOPP unentscheidbar ist. 2. Begründen Sie, dass DOPP rekursiv aufzählbar (semi-entscheidbar) ist. Tellaufgabe IV Ein ungerichteter Graph G = (VE) ist zusammenhängend, wenn je zwei Knoten in G durch einen Pfad verbunden sind. 1. Der Graph G = (V,.E) sei durch Adjazenzlisten gegeben. Beschreiben Sie, wie man in Zeit O(E] + |V}) prüfen kann, ob € zusammenhängend ist. 2. Beweisen oder widerlegen Sie: Hat jeder Kuoten mindestens |V'|/2 Nachbarn(ganzzahlige Division), so ist. G zusammenhängend. Herbst 2013 Einzelprüfungsnummer 66115 Seite 4 Thema Nr. 2 1. Aufgabe: Endliche Automaten Zeigen Sie durch Angabe eines regulären Ausdrucks, dass die Sprache L regulär ist. L besteht aus der Menge aller natürlichen Zahlen in Dezimalzahldarstellung ohne führende Nullen, die durch zwei oder durch fünf teilbar sind. Konstruieren Sie einen deterministischen endlichen Automaten A mit L(A)=L, 2. Aufgabe: Reguläre Sprachen Zeigen oder widerlegen Sie, dass die folgende Sprache L regulär ist. | L= {a8 b™ [n,m>1, m=2"}, Hinweis: Um zu zeigen, dass L regulär ist, geben Sie einen endlichen Automaten oder einen regulären Ausdruck an. Soll dies widerlegt werden, verwenden Sie das Pumping Lemma, 3. Aufgabe: Minimierung DFA Minimieren Sie den folgenden deterministischen Automaten mit den Zuständen {0,1,2,3,4,5, 6}, dem Startzustand 0 und den Endzuständen {3,6}. Geben Sie z.B. durch die Bezeichnung an, welche Zustände zusammengefasst wurden. Fortsetzung nächste Seite! Herbst 2013 Einzelprüfungsnummer 66115 Seite 5 4. Aufgabe: Berechenbarkeit und Komplexität Gegeben sei die Sprache L = { at pn ckIn,m,k> I,n=m und nk}. a) Geben Sie eine Turingmachine M an, die L erkennt, Beschreiben Sie in Worten, wie ihre Turingmachine arbeitet: b) Welche Zeitkomplexität in O-Notation hat ihre Turingmaschine? Erläutern Sie dies anhand Ihrer in a) gegebenen Beschreibung. 5, Aufgabe: Komplexität Beim BIN PACKING Problem hat man eine Menge von Elementen {x1,.., Xn}- Jedes Element x hat ein nicht negatives Gewicht w(x). Außerdem gibt es Kisten, die je höchstens mit dem Gewicht G beladen werden dürfen. Das Problem ist, die Elemente so in Kisten zu packen, dass keine Kiste überladen wird. Reichen dafür k Kisten? 1) Geben Sie eine formale Beschreibung dieses Problems an (mit Mengen, Summen, ete.). 2) Warum ist dieses Problem in NP? Fortsetzung nächste Seite! Herbst 2013 Einzelprüfungsnummer 66115 Seite 6 6. Aufgabe: O-Notation Gegeben seien die Funktionen EN > N und g!N -> N, wobei f(n) = 2(n-1)2 +3n—-1 und ein)> 1Onlogn + 20n + 30 Geben Sie an, welche der folgenden Aussagen gelten. Beweisen Sie Ihre Behauptungen. a) f(n) € O(g(n)) b) g@) « Of) 7. Aufgabe: Heap und binärer Suchbaum a) @ Fügen Sie nacheinander die Zahlen 7, 1, 12, 8,10, 3,5 in einen leeren binären Suchbaum ein und zeichnen Sie den Suchbaum nach „8“ und nach „3“. Gi) Löschen Sie die „1“ aus dem in (i) erstellten Suchbaum und zeichnen Sie den Suchbaum. Gi) Fügen Sie 7,1,12,8,10, 3,5 in einen leeren MIN-Heap ein, der bzgl. „<“ angeordnet ist. Geben Sie den Heap nach jedem Element an. b) Was ist die worst-case Laufzeit in O-Notation für das Einfügen eines Elements in einen Heap der Größe n? Begründen Sie ihre Antwort. 8. Aufgabe: AVL-Bäume Gegeben sei der folgende AVL-Baum T. Führen Sie auf T folgende Operationen durch. (a) Fügen Sie den Wert 22 in T ein. Balancieren Sie falls nötig und geben Sie den entstandenen Baum (als Zeichnung) an. (b) Löschen Sie danach die 5. Balancieren Sie T falls nötig und geben Sie den entstandenen Baum (als Zeichnung) an. Fortsetzung nächste Seite! Herbst 2013 Einzelprüfungsnummer 66115 Seite 7 9, Aufgabe: Dijkstra Gegeben sei der unten stehende gerichtete Graph G=(V, E) mit positiven Kantenlingen I(e) für jede Kante eeE. Kanten mit Doppelspitzen können in beide Richtungen durchlaufen werden. In welcher Reihenfolge werden die Knoten von G ab dem Knoten a durch den Dijkstra-Algorithmus bei der Berechnung der kürzesten Wege endgültig bearbeitet? Berechnen Sie die Länge des kürzesten Weges von a zu jedem Knoten. Geben Sie einen kürzesten Weg von a nach e an. My oe 10. Aufgabe: Minimaler Spannbaum a) Betrachten Sie den obigen Graphen ohne die Kantenrichtung. Konstruieren Sie dann einen minimalen Spannbaum für G. b) Zeigen Sie durch ein Beispiel, dass ein minimaler Spannbaum eines ungerichteten Graphen nicht eindeutig ist.