Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: ____ 66115 2018 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik Unterrichtsfach) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 8 Bitte wenden! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Gegeben ist der nichtdeterministische endliche Automat (NEA) ({0,1},Q,6,q0, #), wobei Q = {A, B,C}, 090 = A, F = {C} und a) Führen Sie für diesen NEA die Potenzmengenkonstruktion durch; geben Sie alle acht entstehenden Zustände mit ihren Transitionen an, nicht nur die erreichbaren. b) Es sei L eine beliebige reguläre Sprache über dem Alphabet © = {a,b,c}. Die Sprache L’ über dem Alphabet W’ = {a,b} umfasst alle Wörter, die aus Wörtern in L durch Streichen aller cs entstehen. Ist zum Beispiel L = {acb, acbcc, abbaccc}, so ist L’ = {ab, abba}. Zeigen Sie, dass L’ regular ist. c) Die Sprache L, = {a"b" | n > 1} ist bekanntlich kontextfrei aber nicht regulär. Obwohl die kontextfreien Sprachen nicht unter Komplement abgeschlossen sind, ist Lı kontextfrei. Die Sprache Dz = {a"b"c” | n > 1} ist bekanntlich nicht kontextfrei. Geben Sie eine kontextfreie Grammatik für L}, das Komplement von Ly, an. d) Die Sprache Ly = {a"b"c” | n > 1} kann bekanntlich als Schnitt zweier kontextfreier Sprachen dargestellt werden: Lg = Lic* Na*L\ wobei L\ = {b"c” | n > 1}. Zeigen Sie, dass die Komplemente von L,c* und at L{ kontextfrei sind. e) Leiten Sie daraus einen Beweis her, dass die kontextfreien Sprachen nicht unter Komplement abgeschlossen sind. Aufgabe 2: Beim Problem CLIQUE ist ein ungerichteter Graph G = (V,E) und eine natürliche Zahl k gegeben. Gefragt ist, ob es in G eine Teilmenge von k Knoten gibt, die paarweise miteinander verbunden sind (“k-Clique”). Dieses Problem ist bekanntlich NP-vollständig. a) Das Problem 3CLIQUE ist der Spezialfall k = 3, gegeben ist also nur ein Graph und gefragt ist, ob er drei paarweise miteinander verbundene Knoten enthält. Zeigen Sie, dass 3CLIQUE in P ist. b) Das Problem CLIQUE’ ist die Einschrankung von CLIQUE auf den Spezialfall von CLIQUE, bei dem k < [V|/2 ist. Zeigen Sie, dass CLIQUE’ auch NP-vollständig ist. Fortsetzung nächste Seite! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: In einem ungerichteten Graphen ist eine Kante eine Brückenkante, falls deren Entfernung den Graphen in zwei unzusammenhängende Teilgraphen zerschneidet. eEntwerfen Sie einen Algorithmus, der alle Brückenkanten findet. Schreiben Sie den Algorithmus in Pseudo-Code auf. Hinweis: beim Test, ob eine Kante eine Brückenkante ist, versuchen Sie durch geeignete Maßnahmen zu vermeiden, dass Knoten mehrfach besucht werden. Sie können dabei geeignete Datenstrukturen für Knoten und Kanten voraussetzen. - Analysieren Sie die Komplexität Ihres Algorithmus in Abhängigkeit der Anzahl Kanten und Knoten. Aufgabe 4: Gegeben ist folgender Pseudo-Code einer Prozedur MAGICSORT, welcher als Argumente ein Array A und zwei Zahlen !,r übergeben bekommt: MacicSort(A, l,r) 1 ifl+7>r 2 then 3 INSERTIONSORT(A, I, r) //sortiere A von I bis r mit InsertionSort 4 else 5 m:= |(r —1+1)/4| 6 for 1 :=1 to 2 do 7 MacicSort(A,/,r — 2m) 8 MacicSort(A,/ + 2m,r) 9 MacicpSort(A,l+m,r —m) Informell: Wenn der zu sortierende Bereich weniger als 9 Elemente besitzt, so werden diese mit Insertion-Sort sortiert. Andernfalls wird der Bereich in Viertel unterteilt; danach werden rekursiv zuerst die ersten beiden Viertel sortiert; dann die letzten beiden Viertel und schließlich die mittleren beiden Viertel. Diese drei Sortierungen werden noch einmal insgesamt wiederholt. a) Begründen Sie, warum dieser Algorithmus ein korrekter Sortieralgorithmus ist, also den Teilbereich All..r] (einschließlich der Grenzen) korrekt sortiert und den Restbereich unverändert lässt. Sie sollten per Induktion argumentieren und die Elemente in vier Typen einteilen: Typ-1 sind die Elemente, die bei korrekter Sortierung im ersten Viertel stehen sollen, etc. Überlegen Sie sich, dass die Typ-1 Elemente nach den ersten drei Aufrufen in der richtigen (also der ersten) Hälfte stehen. b) Bestimmen Sie die Laufzeit der Methode MAcGıcSorrT als Funktion der Größe n des zu sortierenden Bereiches in O-Notation. Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Geben Sie für folgende Menge A C N einen kommentierten Entscheidungsalgorithmus an, der nur Integer-Variablen, For-Schleifen (for i=a to b), Zuweisungen (=), Integer-Addition (+), If Anweisungen zum Test auf Gleichheit von Integern (if a=b then ...) und Return-Anweisungen (return True/False) verwendet. A={n|nen} Aufgabe 2: Gegeben sei die Sprache B = ({a,b}*abb{a,b}* +) über dem Alphabet {a,b}. a) Geben Sie einen nichtdeterministischen endlichen Automaten Aı an, der B akzeptiert. b) Konstruieren Sie aus Aı einen (deterministischen oder nichtdeterministischen) endlichen Automaten Aa, der B = {a,b}* \ B akzeptiert. c) Konstruieren Sie aus Ag eine rechtslineare Grammatik für B. Aufgabe 3: Gesucht ist eine reguläre Sprache C' C {a, b}*, deren minimaler deterministischer endlicher Automat (DEA) mindestens 4 Zustände mehr besitzt als der minimale nichtdeterministische endliche Automat (NEA). Gehen Sie wie folgt vor: a) Definieren Sie C C {a,b}* und erklären Sie kurz, warum es bei dieser Sprache NEAs gibt, die deutlich kleiner als der minimale DEA sind. b) Geben Sie den minimalen DEA M für C an. (Zeichnung des DEA genügt; die Minimalität muss nicht begründet werden) c) Geben Sie einen NEA N für C an, der mindestens 4 Zustände weniger als M besitzt. (Zeichnung des NEA genügt) Aufgabe 4: Sei Mo, Mı,... eine Gödelisierung der Registermaschinen (RAMs). Beantworten Sie folgende Fragen und beweisen Sie Ihre Antworten. a) Ist folgende Menge entscheidbar? D,={reN|M, hält bei Eingabe 0} b) Ist folgende Menge entscheidbar? Da={yeN | es existiert ein x € N, sodass M, bei Eingabe y hält} c) Ist folgende Menge aufzählbar? D3 = {x EN | es existiert ein y € N, sodass M, bei Eingabe y hält} Fortsetziume nachste Seite! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 5 Aufgabe 5: Reduzieren Sie das Problem NAE-SAT auf SAT, d.h. geben Sie eine totale, in Polynomialzeit berechenbare Funktion f mit der Eigenschaft Vz: x € NAE-SAT = f(z) € SAT an. NAE-SAT = {p | p ist eine aussagenlogische Formel in konjunktiver Normalform, für die eine Belegung der Variablen existiert, sodass in keiner Klausel alle Literale den gleichen Wahrheitswert haben} Beachten Sie, dass die in der Definition von NAE-SAT genannte Belegung die Formel % erfüllt. 2.B. gilt (eVy)A(2V=y) € NAE-SAT (belege z.B. x mit 1 und y mit 0) und (zVy)A(zV-y) & NAE-SAT (belegt man x und y mit dem gleichen Wahrheitswert, so haben alle Literale in der ersten Klausel den gleichen Wahrheitswert, andernfalls haben alle Literale in der zweiten Klausel den gleichen Wahrheitswert). Eine aussagenlogische Formel in konjunktiver Normalform ist also genau dann in NAE-SAT, wenn es eine Belegung gibt, die ejede Klausel der Formel erfüllt und ezugleich in jeder Klausel ein Literal unerfüllt lässt. Nutzen Sie diese Charakterisierung, um die Reduktion zu formulieren. Aufgabe 6: Der Hauptsatz der Laufzeitfunktionen ist bekanntlich folgendermaßen definiert: Satz (Mastertheorem) - Sei T(n)= de O(1), falls n< k mit ke N, a> lund b>1 a:-T(5)+g(n), sonst - Dann gilt 1. g(n) e O(n'& 2-8) für eine>0 = T(n)e ©{n'°b?) 2. g(n) e ©(n'%& 2) => T(n) € ©(n!%s?.\ogn) = ©(g(n):logn) 3. g(n) € 2(n!8 4**) für ein € > O und a-g(z) T(n) € O(a(n)) a) Betrachten Sie die folgende Methode m in Java, die initial mit m(r, 0, r.length) für das Array r aufgerufen wird. Geben Sie dazu eine Rekursionsgleichung T'(n) an, welche die Anzahl an Rechenschritten von m in Abhängigkeit von der Lange n = r.length berechnet. public static int m(int[] r, int lo, int hi) { if (lo < 8 || hi <= 10 || lo >= r.length || hi > r.length) { throw new IllegalArgumentException(); } if (hi - lo == 1) { return r[lo]; } else if (hi - lo == 2) { return Math.max(r[lo], r[lo + 1]); // 0(1) } else { int s = (hi - lo) / 3; int x = m(r, lo, lo +s); int y = m(r, lo +s, lo + 2 * s); int z= m(r, lo + 2 * s, hi); return Math.max(Math.max(x, y), 2); // 0(1) Fortsetzung nächste Seite! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 6 b) Ordnen Sie die rekursive Funktion T(n) aus (a) einem der drei Fälle des Mastertheorems zu und geben Sie die resultierende Zeitkomplexität an. Zeigen Sie dabei, dass die Voraussetzung des Falles erfüllt ist. Aufgabe 7: Sortieren mit Quicksort a) Gegeben ist das folgende Array von Zahlen: [23, 5, 4, 67,30, 15, 25, 21]. Sortieren Sie das Array mittels Quicksort in-situ aufsteigend von links nach rechts. Geben Sie die (Teil-)Arrays nach jeder Swap-Operation (auch wenn Elemente mit sich selber getauscht werden) und am Anfang jedes Aufrufs der rekursiven Methode an. Verwenden Sie als Pivotelement jeweils das rechteste Element im Teilarray und markieren Sie dieses entsprechend. Teilarrays der Länge < 2 dürfen im rekursiven Aufruf durch direkten Vergleich sortiert werden. Geben Sie am Ende das sortierte Array an. b) Welche Worst-Case-Laufzeit (O-Notation) hat Quicksort für n Elemente? Geben Sie ein Array mit fünf Elementen an, in welchem die Quicksort-Variante aus (a) diese Wort-Case-Laufzeit benötigt (ohne Begründung). Aufgabe 8: Bearbeiten Sie folgende Aufgaben zu AVL-Suchbäumen. Geben Sie jeweils bei jeder einzelnen Operation zum Einfügen, Löschen, sowie jeder elementaren Operation zum Wiederherstellen der AVL-Baumeigenschaften den entstehenden Baum als Baumzeichnung an. Geben Sie zur Darstellung der elementaren Operation auch vorübergehend ungültige AVL-Bäume an und stellen Sie Doppelrotationen in zwei Schritten dar. Dabei sollen die durchgeführten Operationen klar gekennzeichnet sein und die Baumknoten immer mit aktuellen Balancewerten versehen sein. a) Fügen Sie (manuell) nacheinander die Zahlen 5, 14, 28, 10, 3, 12, 13 in einen anfangs leeren AVL-Baum ein. b) Gegeben sei folgender AVL-Baum. Löschen Sie nacheinander die Knoten 1 und 23. Bei Wahlmöglichkeiten nehmen Sie jeweils den kleineren Wert anstatt eines größeren. Fortsetzung nächste Seite! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 7 Aufgabe 9: Gegeben sei folgender Graph G. a) Berechnen Sie mithilfe des Algorithmus von Dijkstra die kürzesten Wege vom Knoten s zu allen anderen Knoten im Graphen G. Erstellen Sie dazu eine Tabelle mit zwei Spalten und stellen Sie jeden einzelnen Schritt des Verfahrens in einer eigenen Zeile dar. Geben Sie in der ersten Spalte den jeweils als nächstes fertigzustellenden Knoten v (wird sog. „schwarz“) . als Tripel (v,p, 5) mit v als Knotenname, p als aktueller Vorgängerknoten und 6 als aktuelle Distanz von s zu v über p an. Führen Sie in der zweiten Spalten alle anderen bisher erreichten Knoten v ebenfalls als Tripel (v, p, d) auf, wobei diese sog. „grauen Randknoten“ in folgenden Durchgängen erneut betrachtet werden müssen. Zeichnen Sie anschließend den entstandenen Wegebaum, d.h. den Graphen G, in dem nur noch diejenigen Kanten vorkommen, die Teil der kürzesten Wege von s zu allen anderen Knoten sind. b) Der Dijkstra-Algorithmus liefert bekanntlich auf Graphen mit negativen Kantengewichten unter Umständen ein falsches Ergebnis. i) Geben Sie einen Graphen mit negativen Kantengewichten an, sodass der DijkstraAlgorithmus ausgehend von einem von Ihnen ausgezeichneten Startknoten ein korrektes Ergebnis liefert. ii) Geben Sie einen Graphen mit negativen Kantengewichten an, sodass der DijkstraAlgorithmus ausgehend von einem von Ihnen ausgezeichneten Startknoten ein falsches Ergebnis liefert. Ein Beweis oder eine Begründung ist jeweils nicht erforderlich. Aufgabe 10: Algorithmus von Prim a) Berechnen Sie mithilfe des Algorithmus von Prim ausgehend vom Knoten a einen minimalen Spannbaum des ungerichteten Graphen G, der durch folgende Adjazenzmatrix gegeben ist: ıabedefgh a-146---5 bi-3-4-7c43-1---- d6-1-9620 e-4-9-55fi---65--- g-7-25--8 h5--0--81 Fortsetzung nächste Seite! Frühjahr 2018 Einzelprüfungsnummer: 66115 Seite: 8 Erstellen Sie dazu eine Tabelle mit zwei Spalten und stellen Sie jeden einzelnen Schritt des Verfahrens in einer eigenen Zeile dar. Geben Sie in der ersten Spalte denjenigen Knoten v, der vom Algorithmus als nächstes in den Ergebnisbaum aufgenommen wird (dieser sog. „schwarze“ Knoten ist damit fertiggestellt), als Tripel (v,p,6) mit v als Knotenname, p als aktueller Vorgängerknoten und 6 als aktuelle Distanz von v zu p an. Führen Sie in der zweiten Spalte alle anderen vom aktuellen Spannbaum direkt erreichbaren Knoten v (sog. „graue Randknoten“) ebenfalls als Tripel (v,p,6) auf. Zeichnen Sie anschließend den entstandenen Spannbaum und geben sein Gewicht an. b) Welche Worst-Case-Laufzeitkomplexität hat der Algorithmus von Prim, wenn die grauen Knoten in einem Heap (= Halde) nach Distanz verwaltet werden? Sei dabei n die Anzahl an Knoten und m die Anzahl an Kanten des Graphen. Eine Begründung ist nicht erforderlich. c) Zeigen Sie durch ein kleines Beispiel, dass ein minimaler Spannbaum eines ungerichteten Graphen nicht immer eindeutig ist. d) Skizzieren Sie eine Methode, mit der ein maximaler Spannbaum mit einem beliebigen Algorithmus für minimale Spannbäume berechnet werden kann. In welcher Laufzeitkomplexität kann ein maximaler Spannbaum berechnet werden? Aufgabe 11: Gegeben sei der folgende gerichtete Graph G: Traversieren Sie G ausgehend vom Knoten s mittels a) Tiefensuche (DFS), b) Breitensuche (BFS) und geben Sie jeweils die erhaltene Nummerierung der Knoten an. Besuchen Sie die Nachbarn eines Knotens bei Wahlmöglichkeiten immer in alphabetisch aufsteigender Reihenfolge.