Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: H Kennwort: _______————_ erbst 46 1 1 5 2016 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (Unterrichtsfach) Einzelprüfung: Th. Informatik, Algorith./Datenstr. Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 12 Bitte wenden! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Reguläre Sprachen a) Konstruieren Sie aus dem NEA A mit der Potenzmengenkonstruktion einen (deterministischen) EA, der dieselbe Sprache akzeptiert. A: b) Beschreiben Sie möglichst einfach, welche Sprachen von den folgenden regulären Ausdrücken beschrieben werden: 1. (a | b)*a 2. (a |b)*a(a | b)*a(a | b)* 3. (a | b)*a(bb)*a(a | b)* Aufgabe 2: Kontextfreie Grammatiken Betrachten Sie die folgende kontextfreie Grammatik G = ({5, A, B,C},{a,b,c}, S,P) mit den Produktionen: S->AB|C A-ale B-BC Cc a) Beschreiben Sie in Worten möglichst genau die von G erzeugte Sprache L(G). b) Geben Sie ohne Begründung an, welche Variablen in der Grammatik - nützlich, - erzeugend oder - erreichbar sind! c) Ist die Grammatik in Chomsky-Normalform? Begründen Sie Ihre Antwort. Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 3 Aufgabe 3: Klassifizierung von Sprachen Welche der folgenden Sprachen über dem Alphabet {a,b} sind a) regulär? b) kontextfrei, aber nicht regulär? c) nicht kontextfrei? 1. Li = {we {a}* | die Länge von w ist 2” für eine natürliche Zahl n} 2. Ly = {akb’|k < fu {a*b’ | k > Of 3. Lz = {arb’ | k < fu {akd! | k > Geben Sie zu Ihrer Antwort jeweils einen Beweis an. Ein Beweis durch Angabe eines Automaten oder eines regulären Ausdruckes ist erlaubt. Wird der Beweis durch die Angabe einer Grammatik geführt, so ist die Bedeutung der Variablen zu erläutern. Aufgabe 4: Probleme und Komplexität Betrachten Sie die beiden folgenden Probleme: VERTEXCOVER Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k e {1,2,3,...}. Frage: Gibt es eine Menge C C V mit |C| < k, so dass für jede Kante (w,v) aus E mindestens einer der Knoten u und v in C ist? VERTEXCOVER3 Gegeben: Ein ungerichteter Graph G = (V, E) und eine Zahl k € {3,4,5,...}. Frage: Gibt es eine Menge C C V mit |C| < k, so dass für jede Kante (u,v) aus E mindestens einer der Knoten u und v in C ist? Geben Sie eine polynomielle Reduktion von VERTEXCOVER auf VERTEXCOVER3 an und begründen Sie anschließend, dass Ihre Reduktion korrekt ist. Aufgabe 5: Hashing 1. Separate Chaining und Linear Probing am Beispiel a) Fügen Sie folgende Werte in der angegebenen Reihenfolge in eine anfangs leere Hashtabelle A der Größe 11 ein: (35, —2, 107, —18, 46, 53, 20, 96, 81). Verwenden Sie die Hashfunktionen hi(k) = |k| mod 11 sowie ho(k) = |3-k? -2-k-—5| mod 11 Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 4 b) und verwenden Sie separate chaining (Hashing mit Verkettungen) und linear probing (lineares Sondieren) zur Kollisionsbehandlung (es sind also insgesamt vier Hashtabellen zu erzeugen). Löschen Sie anschließend den Wert 53 aus den beiden Hashtabellen, welche mittels linear probing erzeugt wurden. 2. Analyse von Hashing 2) b) Seien m,n € N beliebig. T sei eine Hashtabelle der Größe m, die eine Menge S mit |S| =n speichert und zur Kollisionsauflösung Hashing mittels separate chaining verwendet. Wir betrachten für alle 0 < i < m die Urbildmengen S; := {s € S | h(s) = 7} und ihre Größen n, := |S;]. Warum ist die asymptotische worst-case Laufzeit einer Suchoperation in 7’ von der Ordnung O(1 + max;n;)? (Sie dürfen annehmen, dass die Hashfunktion in konstanter Zeit ausgewertet werden kann.) Seien m € N die Größe einer Hashtabelle und n € N beliebig. Zeigen Sie, dass für jede endliche Menge U mit |4| > (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. Aufgabe 6: Suchbäume: AVL-Bäume 1.Fügen Sie nacheinander folgende Werte in einen zu Beginn leeren AVL-Baum ein: 32, 10, 8, 19, 25, 13, 37, 3. Zeichnen Sie den resultierenden AVL-Baum nach jeder Einfügeoperation und geben Sie an, welche Operationen Sie verwendet haben. 2.Löschen Sie den Wert 37 aus dem sich ergebenden Baum aus Aufgabe 1. Zeichnen Sie den resultierenden AVL-Baum nach der Löschoperation und geben Sie an, welche Operationen Sie verwendet haben. Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 5 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: „Bäume“ Ein Suchbaum ist ein binärer Baum, dessen Knoten (einschließlich Blätter) beliebige Werte so speichern, dass alle Werte im linken Teilbaum eines Knotens N kleiner sind als der Wert in N, während die Werte im rechten Teilbaum allesamt größer sind. a) Fügen Sie in einen leeren binären Suchbaum der Reihe nach die folgenden Schlüssel ein und geben Sie den fertigen Baum an: 27, 42, 23, 32, 7, 64, 81 b) Geben Sie jeweils eine Einfügereihenfolge (nicht den Baum) für die obigen Schlüssel an, bei der die Höhe des entstehenden Baums maximal bzw. minimal wird. c) Wie teuer (Komplexitätsmaß in O-Notation) ist der Zugriff auf ein beliebiges Element in einem entarteten (Höhe maximal) bzw. perfekt balancierten (Höhe minimal) binären Suchbaum mit n Einträgen? d) Betrachten Sie den folgenden Baum wahlweise entweder als AVL-Baum oder als Rot-Schwarz-Baum. Fügen Sie in den teilweise gefüllten Baum zusätzlich die Zahl 99 ein. Zeichnen Sie zunächst den Baum direkt nach dem Einfügen des Elements und geben Sie a. im Falle des AVL-Baums die durch das Einfügen veränderten Tupel [H/B] aus Höhe H und Balancefaktor B der betroffenen Knoten an bzw. b. im Falle des Rot-Schwarz-Baums die Farben der einzelnen Knoten an. e) Betrachten Sie Ihr Ergebnis aus Teilaufgabe d).-An welchen Knoten ist eine Rotation erforderlich? Beschreiben Sie jeweils die Art der Rotation. f) Zeichnen Sie den Baum (ihr Ergebnis aus Teilaufgabe d)) nach der Reorganisation (diesmal ohne Höhen/Balance bzw. Farben). Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 6 Aufgabe 2: „Algorithmenkomplexität“ Geben Sie jeweils die kleinste, gerade noch passende Laufzeitkomplexität folgender Java-Methoden im O-Kalkül (Landau-Notation) in Abhängigkeit von n und ggf. der Länge der Arrays an: int matrixSumme(int n, int[}[] feld) { int sum = 9; for (int i=8; icen ir) { for (int j = 8; j 6) { if (n% 2 == 1) { count++; } n >>= 1; // bit-shift right } return count; int find(int key, int[][] keys) { int a = ®, 0 = keys.length; while (o - a>1) { intm= (a+o) / 2; if (keys[m][@] > key) o=m; else a=m } return a; public void simuliere(long n, long[] baelle) { for (int i = 8; i < baelle.length; i++) { baelle[i] = 8; while (--n >= 6) { int anzBaelle = baelle.length - 1; int delta = simLinRek(anzBaelle); // simLinRek in O(anzBaelle) if (baelle.length % 2 == @) { delta--; } int pos = delta / 2 + baelle.length / 2; baelle[pos]++; public static void T(int n) { if (n <= 8) return; for (int i = @; i < 192; ++i) { T(n / 4); } for (int j = 0; j SI NIO w a) Fügen Sie die Schlüsselwerte in der Reihenfolge 1, 6, 9, 2, 3, 12, 4, 5 in eine Streutabelle mit acht Feldern (von 0 bis 7) ein. Verwenden Sie zur Kollisionsauflösung verkettete Listen wie im folgenden Beispiel: Fach Inhalt 0 42 — 666 —> L b) Fügen Sie nun die Schlüsselwerte in der Reihenfolge 4, 5, 6, 12, 9, 3, 2, 1 in eine Streutabelle mit acht Feldern (von 0 bis 7) ein. Verwenden Sie diesmal zur Kollisionsauflösung jedoch lineares Sondieren mit konstanter Schrittweite +3 wie im folgenden Beispiel (die Streutabelle rechts genügt): Fach Inhalt 0 Schlüssel | Sondierte Fächer — 1 42 3 2 666 3(P), 6 3 42 4 5 6 666 7 c) Begründen Sie kurz, warum bei der vorangehenden Streutabelle ein lineares Sondieren mit Schrittweite 3 besser ist als lineares Sondieren mit Schrittweite 4. Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 8 Aufgabe 4: „Rekursion und Dynamische Programmierung“ Mittels Dynamischer Programmierung (auch Memoization genannt) kann man insbesondere rekursive Lösungen auf Kosten des Speicherbedarfs beschleunigen, indem man Zwischenergebnisse „abspeichert“ und bei (wiederkehrendem) Bedarf „abruft“, ohne sie erneut berechnen zu müssen. Gegeben sei folgende geschachtelt-rekursive Funktion für n, m 2 0: n+ FI fallsm=0 a(n,m) = a(1,m— 1) fallsn=0Am#0 a(n + |Jan- 1,m)|;m- 1) sonst a) Implementieren Sie die obige Funktion a(n,m) zunächst ohne weitere Optimierungen als Prozedur/Methode in einer Programmiersprache Ihrer Wahl. b) Geben Sie nun eine DP-Implementierung der Funktion a(n,m) an, die a(n, m) für 0 100000 oder m > 25 aufgerufen werden können soll. Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 9 Aufgabe 5: „Rekursion“ Die nebenstehende Skizze stellt die Wasserleitungen in einem Gebäude exemplarisch wie folgt dar: Q ist der Frischwasseranschluss der Stadtwerke, der beliebig viel Wasser liefern kann, S ist der Abwassergulli, der beliebig viel abführen kann. Neben den Verteilern Q und S hat das Netz im Beispiel zwei weitere Verteiler 1 und 2. Die Rohre zwischen , . den Verteilern sind unterschiedlich dick: z.B. gibt es 9 6 12 5 zwischen Q und 1 eine Hauptleitung mit einer Kapazität von 7 I/s, aber das Abflussrohr von 1 zu S kann nur 3 Vs abführen. Den maximalen Durchfluss von Q nach S erhält man, indem man alle möglichen „Schnitte“ (gestrichelt) durchs Gebäude zieht, zu jedem Schnitt die Rohr-Durchfluss-Summe bestimmt, und von allen Schnitten den minimalen Durchfluss wählt - dieser Schnitt stellt den „begrenzenden Flaschenhals“ zwischen Q und S dar und erlaubt im Beispiel maximal 6 I/s. Implementieren Sie die geforderten Methoden in einer geeigneten Programmiersprache Ihrer Wahl oder Pseudocode. Folgender Java-Code und der Auszug aus der Java-API für List seien zu Ihrer Unterstützung vorgegeben: class Verteiler { final List rohre = new Arraylist<>(); // "Adjazenzliste mit Kanten” } class Rohr { final double df; final Verteiler e, a; Rohr(Verteiler ende, double durchfluss, Verteiler anderesEnde) { this.e = ende; this.df = durchfluss; this.a = anderesEnde; assert df > @ && e != null && a != null; ende.rohre.add(this) ; anderesEnde.rohre.add(this) ; } boolean add(E e): Appends the specified element to the end of this list. boolean contains (Object o): Returns true if this list contains the specified element. boolean remove (Object o): Removes the first occurrence of the specified element from this list, if it is present. a) Finden Sie ausgehend von der Quelle Q zunächst alle über Rohre erreichbaren Verteiler. Implementieren Sie dafür folgende Methode rekursiv: class MaxFlowMinCut { // Fuegt und alle von aus erreichbaren Verteiler zu hinzu. void erreichbareVerteiler(Verteiler v, List ev) { b) Ein „Schnitt“ durch das Rohrsystem wird mit zwei Listen dargestellt: Eine enthält alle Verteiler auf der Seite des Schnitts, die die Quelle Q (inklusive) enthält, und die andere die Verteiler auf der Seite der Senke S (inklusive). Ergänzen Sie folgende Methode, die den Durchfluss an einem „Schnitt“ bestimmt: // Bestimmt den Durchfluss am Schnitt zwischen und . double schnittDurchfluss(List quelleSeite, List senkeSeite) { Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 10 c) Die Berechnung des maximalen Durchflusses beginnt mit folgender Methode: // Bestimmt den maximal moeglichen Durchfluss von zu . public double maximalerDurchfluss(Verteiler quelle, Verteiler senke) { List quelleSeite = new ArrayList<>(); quelleSeite.add(quelle) ; List senkeSeite = new ArrayList<>(); erreichbareVerteiler(quelle, senkeSeite); senkeSeite.remove(quelle); return durchfluss(quelleSeite, senkeSeite, senke); Implementieren Sie die rekursive Hilfsmethode durchfluss. Sie muss nicht optimal sein, d.h. sie darf bereits betrachtete Konfigurationen auch mehrfach untersuchen. // Bestimmt den maximal moeglichen Durchfluss von zu . double durchfluss( List quelleSeite, List senkeSeite, Verteiler senke) { Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); double df = schnittDurchfluss(quelleSeite, senkeSeite) ; Hinweis zum möglichen Ablauf der Rekursion: > 2 an = = = = [ssc | 7 = = = = = = > > 2, N * = = = 3 = Bekursion = un = er - = a” Resurdan 3 “ Es ~ i, IN = F [weisesesee | 6 = = % 7, oe se aoe Se = = = % = = = 3 = = = ’ = “ Rekursior, “ = . = I BS “ = cael 9 aaa) 3 ; % = % s "hp ws fe, en = = = = = = [ass | x = \ = \ % SS ts Gy, welleseite seneSeate > as Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 11 Aufgabe 6 Sei © = {0,1}, sei No = {0,1,2,...}. (a) Sei Ly = {0"1"0"1" | n,m E No} . Beispiele: 001011 € L,, 1100 € L,, 0101 e L.. (al) Zeigen Sie, dass L, kontextfrei ist, indem Sie eine kontextfreie Grammatik G angeben mit L(G) = Lı, und (a2) begründen Sie, warum Ihre Grammatik genau die Sprache Ly erzeugt. (b) Formulieren Sie das Pumping-Lemma für reguläre Sprachen: „Sei L eine reguläre Sprache über dem, Alphabet D. Dann gibt es...“ (c) Sei Ly = {0"170* | n,m, k € No,n > 1,m > 1,k > 1}. Zeigen Sie, dass Lz die Eigenschaft des Pumping-Lemmas für reguläre Sprachen (vgl. (b)) besitzt. (d) Zeigen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die Sprache L, aus (a) nicht regulär ist. Aufgabe 7 Im Nachfolgenden bezeichne M immer eine deterministische Turingmaschine, die als Eingabe eine natürliche Zahl bekommt, und (M) sei Gödelnummer von M. a) Zeigen Sie, dass die Menge Lı ={(M) | es gibt mindestens eine Zahl n, so dass M gestartet mit n hält} rekursiv aufzählbar (= partiell-entscheidbar) ist. Geben Sie dazu einen Algorithmus A an, der als Eingabe eine Gödelnummer (M) bekommt und damit gestartet genau dann hält, wenn (M) e Ly ist. b) Sei Co-Ho = {(M) | M gestartet mit 0 hält nicht}. Es ist bekannt, dass Co-Hg nicht rekursiv aufzählbar (= partiell-entscheidbar) ist. Zeigen Sie durch Reduktion von Co-Ho, dass die Menge Le = {(M) | es gibt genau eine Zahl n, so dass M gestartet mit n halt} nicht rekursiv aufzählbar (= partiell-entscheidbar) ist. Zeigen Sie also konkret: Co-Ho < La. Fortsetzung nächste Seite! Herbst 2016 Einzelprüfungsnummer: 46115 Seite: 12 Aufgabe 8 (a) (b) Gegeben sei der folgende nichtdeterministische endliche Automat N: Konstruieren Sie zu N mit der Potenzmengen-Konstruktion einen äquivalenten deterministischen endlichen Automaten A. Zeichnen Sie nur die vom Startzustand aus erreichbaren Zustände ein, die aber alle. Die Zustandsnamen von A müssen erkennen lassen, wie sie zustande gekommen sind. Führen Sie keine „Vereinfachungen“ durch! Hinweis: In einem deterministischen endlichen Automaten muss es an jedem Zustand für jedes Zeichen einen Übergang geben. Geben Sie einen regulären Ausdruck «{N) für die Sprache an, die der nichtdeterministische endliche Automat N aus (a) akzeptiert.