Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 461 15 2018 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (Unterrichtsfach) Einzelprüfung: Theoretische Informatik/ Algorithmen /Datenstrukturen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 13 Bitte wenden! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1 (Reguläre Sprachen) [24 PUNKTE] (a) [4 PUNKTE] Betrachten Sie die formale Sprache L C {a,b}* aller Wörter, die mit aa beginnen oder mit bb enden. (eben Sie einen regulären Ausdruck für die Sprache L an. (b) [10 PUNKTE] Entwerfen Sie einen nichtdeterministischen endlichen Automaten, der die Sprache L aus Teilaufgabe (a) akzeptiert. (c) [10 PUNKTE] Wandeln Sie den folgenden nichtdeterministischen Automaten mit Hilfe der Potenzmengenkonstruktion in einen äquivalenten deterministischen Automaten um. (Berechnen Sie dabei nur erreichbare Zustände.) Aufgabe 2 (Kontextfreie Sprachen) [32 PUNKTE] (a) [4 PunKTE] Betrachten Sie die formale Sprache L über dem Alphabet % = {0,1,2} aller Wörter wv mit w € {0,1}* und ve {1,2}* so dass die Anzahl der Oen in w genau doppelt so hoch ist wie die der 2en in v. Geben Sie zwei Wörter über % an, die in L enthalten sind und zwei Wörter über %, die nicht in L enthalten sind. Die Wörter sollen mindestens Länge 5 haben. (b) [10 PUNKTE] Geben Sie eine kontextfreie Grammatik für die Sprache L an. Erklären Sie den Zweck der einzelnen Nichtterminale (Variablen) und der Grammatikregeln Ihrer Grammatik. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 3 (c) [2 PUNKTE] Geben Sie für eines Ihrer beiden Wörter aus Teilaufgabe (a), dasin L enthalten ist, einen Ableitungsbaum des Wortes mit Ihrer Grammatik aus Teilaufgabe (b) an. (d) [10 PUNKTE] Beweisen Sie, dass die Sprache L aus Teilaufgabe (a) nicht regulär ist. (e) [6 PUNKTE] Ist die folgende Aussage richtig oder falsch? Begründen Sie Ihre Antwort: „Jede Teilmenge einer kontextfreien Sprache liegt in der Klasse P.“ Aufgabe 3 (Entscheidbarkeit) [34 PUNKTE] (a) [6 PUNKTE] Betrachten Sie das folgende Entscheidungsproblem: Eingabe: eine (geeignet codierte) Turingmaschine M, ein Eingabewort w und eine natürliche Zahl n Aufgabe: entscheiden, ob die Turingmaschine M auf das Eingabewort w nach höchstens n Schritten hält Ist dieses Problem entscheidbar? Begründen Sie Ihre Antwort. (b) [20 PUNKTE] Beweisen Sie mit Hilfe eines Reduktionsbeweises, dass das folgende Problem nicht entscheidbar ist: Eingabe: eine (geeignet codierte) Turingmaschine M und sowie ein Eingabewort w Aufgabe: entscheiden, ob M auf Eingabewort w gestartet hält und das Wort w nicht akzeptiert (c) [8 PUNKTE] Beweisen Sie, dass das Problem aus (b) semi-entscheidbar (= rekursiv aufzählbar) ist. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 4 Aufgabe 4 (Hashing) [71 PUNKTE] Ein Wörterbuch, das die Operationen SUCHEN, EINFÜGEN und LÖSCHEN zur Verfügung stellt, kann mit einer Hashtabelle implementiert werden. Im Folgenden seien m,n € N beliebig, TIO,. ..,m — 1] eine Hashtabelle der Größe m und $ C U eine Menge aus dem Universum U mit |S| = n die in T mittels der Hashfunktion h:U — {0,...,m — 1} gespeichert werden soll. Hashing mit Verkettung 4.1 4.2 4.3 4.4 4.5 [2 Punkte] Beschreiben Sie kurz, wie eine Hashtabelle aufgebaut ist, die Verkettung zur Kollisionsbehandlung verwendet. [6 Punkte] Beschreiben Sie kurz, wie die Wörterbuchoperationen SUCHEN, EINFÜGEN und LÖSCHEN in einer Hashtabelle wie in Aufgabe 4.1 beschrieben umgesetzt werden. [6 Punkte] Zeigen Sie, dass für jede endliche Menge U mit |U| > (n — 1)m +1 und jede Hashfunktion h:U — {0,...,m — 1} eine Menge S C U mit |S| = n existiert, so dass alle Elemente von S durch h auf denselben Eintrag der Hashtabelle abgebildet werden. Hinweis: Betrachten Sie die größte der Urbildmengen U; := {s eU | h(s) =i} (für 1 Zahlen Ausgabe : MiNi , Ak ud d= Minn-(-1) Alk] k=n-(i-1) Wir wollen durch Induktion zeigen, dass für alle 1 < 1 < n die Aussage A, : Nach dem /-ten Durchlauf der Schleife ist all] = aı gilt. 5.2 [4 Punkte] Führen Sie den Induktionsanfang | = 1 aus. 5.3 [8 Punkte] Führen Sie den Induktionsschritt | — 1 — / (für 1 <1 1} Geben Sie für die Sprachen jeweils an, ob sie regulär sind oder nicht. Geben Sie einen Beweis für Ihre Antwort. Um Regularität zu zeigen, reicht die Angabe eines Automaten oder eines regulären Ausdrucks, der die Sprache akzeptiert. Aufgabe 2 (Kontextfreie Sprachen) [14 PUNKTE] Für den Beweis von Kontextfreiheit in dieser Frage reicht die Angabe eines Automaten oder einer Grammatik. (Beschreiben Sie dann die Konstruktionsidee des Automaten oder der Grammatik.) Für den Beweis von Nicht-Kontextfreiheit verwenden Sie eine der üblichen Methoden. (a) |3 Punkte] Seien Z, und L, nicht-kontextfrei. Ist es dann immer so, dass auch Lı U La nicht-kontextfrei ist? Beweisen Sie Ihre Antwort. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 9 (b) [3 Punkte] Sei Z3 nicht-kontextfrei und L, regulär. Kann L3 U L, kontextfrei sein? Kann La U La nicht-kontextfrei sein? Beweisen Sie Ihre Antworten. (c) [3+5 Punkte] Wir bezeichnen mit #,(w) die Anzahl der Vorkommen des Zeichens o im Wort w. Zum Beispiel ist #,(baaca) = 3 und #,(baaca) = 1. Betrachten Sie die folgenden Sprachen über dem Alphabet I = {a, b,c, d}: Ls = {w € L(a*b*c*d") | #a(w) = #o(w) und #.(w) = #a(w)} Le = {w € L((a+b+c+d)*) | #.(w) = #,(w) und #.(w) = #a(w)} Sind Ls und Le jeweils kontextfrei oder nicht? Beweisen Sie Ihre Antwort. Aufgabe 3 (Entscheidbarkeit und Komplexität) [10 PUNKTE] SeiG = (V,E) ein ungerichteter Graph. Wir sagen, dass ein Knoten u von einem Knoten v gesehen wird, falls u = v oder (u,v) € E. Wir nennen A C V eine alles sehende Menge (ASM), falls jeder Knoten in V von mindestens einem Knoten in A gesehen wird. Wir nennen A teilbar, falls A partitionierbar in nicht-leere Teilmengen A, und Ag ist, so dass jeder Knoten in V entweder von mindestens einem Knoten in A, oder von mindestens einem Knoten in As gesehen wird (aber nicht von sowohl einem Knoten in A, als auch von einem Knoten in Asa). Wir betrachten die folgenden Probleme: ASM Gegeben: Ungerichteter Graph G = (V, FE) und k EN Gefragt: Hat G eine ASM A mit |A| < k? Teilbare ASM Gegeben: Ungerichteter Graph G = (V, £) und k Ee N Gefragt: Hat G eine teilbare ASM A mit |A| < k? (a) [8 PUNKTE] Beweisen Sie, dass ASM in Polynomialzeit reduzierbar ist auf Teilbare ASM. (b) [2 PUNKTE] Was kénnen Sie aus a) folgern bezüglich der NP-Vollständigkeit der Probleme? Fortsetzung nachste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 10 Aufgabe 4 (Längste Pfade) [45 PUNKTE] Gegeben sei der folgende azyklische, gerichtete Graph. Der kritische Pfad eines solchen Graphen ist definiert als derjenige Pfad von einem beliebigen Knoten mit Eingangsgrad 0 zu einem beliebigen Knoten mit Ausgangsgrad 0 mit der maximalen Pfadlänge. Analog ist der kritische Pfad zu einem beliebigen Knoten der Pfad mit maximaler Pfadlänge von einem Knoten mit Eingangsgrad 0 zu diesem Knoten. Im gegebenen Graphen ist beispielsweise der kritische Pfad zu Knoten E der von A über D und G nach E mit der Pfadlänge 3. Der Pfad von B aus ist kürzer (Pfadlänge 1), weil Knoten E nur direkt von Knoten B aus erreichbar ist. Von Knoten © aus ist Knoten E nicht erreichbar. (a) [5 PunKTE] Bestimmen Sie den kritischen Pfad des gegebenen Graphen. Geben Sie die Knotenfolge des kritischen Pfades und seine Pfadlänge an. (b) [10 PUNKTE] Da der gegebene Graph azyklisch ist, können seine Knoten topologisch sortiert werden. Formal ist die topologische Sortierung eines Graphen G = (V,E) eine injektive Abbildung ord:V — {1,...,|V|} sodass gilt: Viu,w) € E:ord(v) < ord(w) Dabei bezeichnet V die Knotenmenge und E die Kantenmenge des Graphen. Führen Sie eine topologische Sortierung des Graphen durch. Geben Sie eine mögliche topologische Sortierung der Knoten des Graphen an. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 11 (c) [5 PUNKTE] Angenommen, Sie haben im gegebenen Graphen die kritischen Pfade zu allen Vorgängerknoten eines Knotens v bestimmt. Wie berechnet sich dann der kritische Pfad zum Knoten v? (d) [25 PUNKTE] Formulieren Sie anhand der Kenntnisse, die Sie durch die Aufgabenteile b und c gewonnen haben, einen Algorithmus, der die Länge des kritischen Pfades eines gerichteten, azyklischen Graphen berechnet und geben Sie die asymptotische Laufzeit Ihres Algorithmus in der O-Notation an. Hinweis: Sie dürfen in Ihrem Algorithmus eine Funktion topsort(G) verwenden. Diese liefert eine topologische Sortierung der Knoten des Graphen G als Liste in einer asymptotischen Laufzeit in O(|V| + |E|) zurück. Aufgabe 5 (Backtracking) [25 PUNKTE] Das Springerproblem ist ein kombinatorisches Problem, das darin besteht, für einen Springer auf einem leeren Schachbrett eine Route von einem gegebenen Startfeld aus zu finden, auf der dieser jedes Feld des Schachbretts genau einmal besucht. Ein Schachbrett besteht aus 8x8 Feldern. Ein Springer kann bei einem Zug von einem Ausgangsfeld aus eines von maximal 8 Folgefelder betreten, wie dies in der folgenden Abbildung dargestellt ist. Der Springer darf selbstverstndlich nicht über den Rand des Schachbretts hinausspringen. DD oS F&F oD „10 Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 12 Eine Lösung des Springerproblems mit Startfeld h1 sieht wie folgt aus. Die Felder sind in ihrer Besuchsreihenfolge durchnummeriert. Der Springer bewegt sich also von hi nach £2, dann von f2 nach h3 usw. 41 10 29 26 49 12 31 16 28 25 40 11 30 15 50 13 9 42 27 56 61 48 17 32 24 39 58 47 64 53 14 51 43 8 55 62 57 60 33 18 38 23 46 59 54 63 52 3 TY 44 21 36 5 2 19 34 22 37 6 45 20 35 4 1 Formulieren Sie einen rekursiven Algorithmus zur Lösung des Springerproblems von einem vorgegebenen Startfeld aus. Es sollen dabei alle möglichen Lösungen des Springerproblems gefunden werden. Die Lösungen sollen durch Backtracking gefunden werden. Hierbei werden alle möglichen Teilrouten systematisch durchprobiert, und Teilrouten, die nicht zu einer Lösung des Springerproblems führen können, werden nicht weiterverfolgt. Dies ist durch rekursiven Aufruf einer Lésungsfunktion huepf(z, y, z) zu realisieren, wobei - x und y die Koordinaten des als nächstes anzuspringenden Feldes sind, und - z die aktuelle Rekursionstiefe enthält. Wenn die Rekursionstiefe 64 erreicht und das betreffende Feld noch unbesucht ist, ist eine Lösung des Springerproblems gefunden. Der initiale Aufruf Ihres Algorithmus kann beispielsweise über den Aufruf huepf(1,8,1) erfolgen. Wählen Sie geeignete Datenstrukturen zur Verwaltung der unbesuchten Felder und zum Speichern gefundener (Teil)Lösungen. Der Algorithmus soll eine gefundene Lösung in der oben angegebenen Form ausdrucken, also als Matrix mit der Besuchsreihenfolge pro Feld. Fortsetzung nächste Seite! Herbst 2018 Einzelprüfungsnummer: 46115 Seite: 13 Aufgabe 6 (Balancierte Bäume) [20 PUNKTE] Es sei der folgende AVL-Baum mit Schlüsseln aus N gegeben: (a) (b) [10 Punkte] Fügen Sie in den gegebenen Baum den Schlüssel 15 ein! Rebalancieren Sie anschließend den Baum so, dass die AVL-Eigenschaft wieder erreicht wird. Zeichnen Sie den Baum nach jeder Einfach- und Doppelrotation und benennen Sie die Art der Rotation (Links-, Rechts-, Links-Rechts-, oder Rechts-Links-Rotation). Argumentieren Sie jeweils über die Höhenbalancen der Teilbäume. Zeichnen Sie nach jedem Schritt die Höhenbalancen in den Baum ein. [10 Punkte] Löschen Sie den Schlüssel 25 aus dem gegebenen Baum! Rebalancieren Sie anschließend den Baum so, dass die AVL-Eigenschaft wieder erreicht wird. Zeichnen Sie den Baum nach jeder Einfach- und Doppelrotation und benennen Sie die Art der Rotation (Links-, Rechts-, Links-Rechts-, oder Rechts-Links-Rotation). Argumentieren Sie jeweils über die Höhenbalancen der Teilbäume.