Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: — Herbst 66115 2014 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an 6ffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 6 Bitte wenden! Herbst 2014 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Wir fixieren das Alphabet © = {0,1} und definieren ZL < &* durch L = {w | in w kommt das Teilwort 0010 höchstens einmal vor} Es ist also 000 € L, 00010 € L, aber 00010000100 ¢ Z und auch 0010010 ¢ L. a) Zeigen Sie, dass L regular ist. b) Vervollständigen Sie durch Hinzufügen eines weiteren Zustandes, sowie von Kanten und der Angabe der Endzustände folgendes Diagramm zu einem deterministischen Automaten für L. Übertragen Sie dazu das Diagramm auf Ihr Arbeitspapier. 0 0 1 0 0 1 0 —> Go > G1 —> G2 > 93 > da — G5 > Ug —> G7 c) Zeigen Sie durch Ausführung des Minimierungsalgorithmus, dass dieser Automat minimal ist. d) Geben Sie die Aquivalenzklassen der Myhill-Nerode Aquivalenz von L durch Reprasentanten an. (Diese Aquivalenz ist definiert durch en, y ==> Vusue LDS yu e L.) Geben Sie zu zwei Klassen Ihrer Wahl neben dem gewählten Repräsentanten noch ein weiteres Element an. Geben Sie für die Klasse, in der sich das leere Wort befindet, einen regulären Ausdruck an. Aufgabe 2: Ordnen Sie die folgenden formalen Sprachen bestmöglich in die Chomsky-Hierarchie ein und geben Sie eine ausreichende Begründung an: a) Ly = { (ab)"a(ab)” | n > 1} b) = { (ab)"(ab)" | n > 1} c) Ly = { (ab)"(ab)"(ab)” | n > 1} d) Lg = { (ab)"(ab)"a(ab)” |n >= 1} e) 1 = { (ab)"a(ab)"a(ab)” | n > 1}. (Bei dieser Teilaufgabe ist keine Begründung notwendig.) f) Le sei die Menge aller syntaktisch korrekten Java-Programme, die ohne Eingabe nicht terminieren. g) Lr sei die Menge aller wohlgeformten Klammerausdrücke, also (),(()),(Q)Q) € Lr, aber )O) (OO € Lr. Fortsetzung nächste Seite! Herbst 2014 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: Bekanntlich sind beim RUCKSACK-Problem natürliche Zahlen aı,...,a, und eine Zielzahl b gegeben und es ist gefragt, ob eine Teilmenge I € {l,...,n} existiert, sodass _,., a = b. Dieses Problem ist: bekanntermaßen NP-vollständig. a) Zeigen Sie, dass die Variante GRUCKSACK, bei der die Zahlen a; und b allesamt gerade sein müssen, ebenfalls NP-vollständig ist. b) Zeigen Sie, dass die Variante BZRUCKSACK, bei der die Zahl b eine Zweierpotenz sein muss, ebenfalls NP-vollständig ist. c) In welche Komplexitätsklasse fällt die Variante ZARUCKSACK, bei der es nur zwei verschiedene Arten von Gewichten gibt, also zwei Zahlen u,v existieren, sodass a; € {u,v} für t=1,...,n? Aufgabe 4: Es seien natürliche Zahlen aı,...,a, in Form eines Arrays gegeben. Die Zahlen a, steigen bis zu einem gewissen Punkt an und fallen anschließend wieder. Formal existiert also m < n, sodass Folgendes gilt: Ist 1 <7 < m, so ist a; < aj41. Ist m ajy4. a) Entwerfen Sie einen Algorithmus, der den größten Eintrag des Arrays, also max; a; in Zeit O(log n) bestimmt. Geniigt die Eingabe nicht der Spezifikation, so darf sich Ihr Algorithmus vollig beliebig verhalten. b) Jetzt erlauben wir auch die Möglichkeit, dass die Arraywerte “liegenbleiben”, also dass m < n existiert, sodass gilt: Ist 1 <7 < m, dann ist a; < aj4,. Ist m rn. Begründen Sie, dass kein Algorithmus mit Laufzeit O(logn) existiert, der entscheidet, ob ein Array von der oben beschriebenen Form ist. Hilfe: Lassen Sie einen hypothetischen Algorithmus auf der Eingabe a; = 0 firi =1,...,n laufen. Herbst 2014 Einzelprüfungsnummer: 66115 Seite: 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: a) Minimieren Sie folgenden deterministischen, endlichen Automaten. b ao b) Bestimmen Sie einen regulären Ausdruck für die von dem folgenden nichtdeterministischen, endlichen Automaten akzeptierte Sprache. Aufgabe 2: Beweisen Sie folgende Aussagen. a) Ly = {we {0,1}* | die Länge von w ist durch 2 oder 3 teilbar} ist regulär. b) Lo = {w € {0,1}* | w = 010" mit i,j,k € N und j =i +k} ist kontextfrei. Fortsetzung nächste Seite! Herbst 2014 Einzelprüfungsnummer: 66115 Seite: 5 Aufgabe 3: | a) Definieren Sie eine berechenbare Funktion f: N — N mit entscheidbarem Definitionsbereich und unentscheidbarem Wertebereich. Begründen Sie Ihre Aussagen. b) Beweisen oder widerlegen Sie folgende Aussagen. i) Jede berechenbare Funktion h: N — N mit endlichem Wertebereich besitzt einen entscheidbaren Definitionsbereich. ii) Jede berechenbare Funktion h: N — N mit endlichem Definitionsbereich besitzt einen entscheidbaren Wertebereich. Aufgabe 4: a) Die Fibonacci-Funktion fib: N— N ist definiert durch a _ SS falls x € {0,1} fib(z) = | f(e@-—1)+ f(x —2) sonst. Beweisen Sie, dass fib nicht in polynomieller Zeit berechenbar ist. b) Sei f: NN eine totale, in polynomieller Zeit berechenbare Funktion mit f(x) > x für alle xz € N. Wy bezeichne den Wertebereich der Funktion f. Beweisen Sie, dass W; € NP. Aufgabe 5: Gegeben sei eine Standarddatenstruktur Stapel (Stack) mit den Operationen evoid Push(Element e), eElement Pop(), eBoolean Empty(). sowie dem Standardkonstruktor Stapel(), der einen leeren Stapel zur Verfügung stellt. a) Geben Sie eine Methode Stapel Merge(Stapel S, Stapel 7’) an, die einen aufsteigend geordneten Stapel zurückgibt, unter der Bedingung, dass die beiden übergebenen Stapel aufsteigend sortiert sind, d.h. S.Pop() liefert das größte Element in $ zurück und T'.Pop() liefert das größte Element in T zurück. Als Hilfsdatenstruktur dürfen Sie nur Stapel verwenden, keine Felder oder Listen. b) Analysieren Sie die Laufzeit Ihrer Methode. Aufgabe 6: Gegeben sei ein einfacher Sortieralgorithmus, der ein gegebenes Feld A dadurch sortiert, dass er das Minimum m von A findet, dann das Minimum von A ohne das Element m usw. a) Geben Sie den Algorithmus in Pseudocode an. Implementieren Sie den Algorithmus in situ, d.h. so, dass er außer dem Eingabefeld nur konstanten Extraspeicher benötigt. b) Analysieren Sie die Laufzeit Ihres Algorithmus. c) Geben Sie eine Datenstruktur an, mit der Sie Ihren Algorithmus beschleunigen können. Fortsetzung nächste Seite! Herbst 2014 Aufgabe 7: Einzelprüfungsnummer: 66115 Gegeben sei folgende Adjazenzmatrix des Graphen G („*“ bedeutet, dass zwischen den beiden Knoten keine direkte Verbindung existiert): TMOO|DM>iO 8) Blan 8 lwi-[O;O gialol 3] slolal> 8/8 [| RIO] 8 om n/8imlolnl8|83|N 8/01 NI ISIN T coloje| 878 )—) 8M @|co/-3)h9; 8) 38) 8 7 a) Bestimmen Sie mit dem Algorithmus von Dijkstra den kürzesten Weg von der Quelle Q bis zu den Senken C und F. Verwenden Sie zur Lösung eine Tabelle nach unten stehendem Muster, markieren Sie in jeder Zeile den jeweils als nächstes zu betrachtenden Knoten und führen Sie die Prioritätsliste der noch zu betrachtenden Knoten in der letzter: Spalte (der nächste Knoten steht links): Seite: 6 A B Cc D E F Queue + 0 oo x 0 x x Q b) Geben Sie den vorangehend ermittelten, kürzesten Weg von Q zu F als Knotenfolge an. c) Bestimmen Sie mit Hilfe des Verfahrens nach Kruskal den kleinsten Spannbaum des Graphen G. Geben Sie die Kanten (Knotenpaare) in der Reihenfolge an, in der Sie sie dem minimalen Spannbaum gemäß Kruskal hinzufügen würden. Wie groß ist die Kantengewichtssumme im Spannbaum insgesamt?