Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl:. Herbst 66115 Kennwort: 2017 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: 14 Bitte wenden! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Myhill Nerode Für zwei Wörter x,y eT.* und eine Sprache L QT.* gilt x =Ly genau dann, wenn für jedes Wort 2 e E* gilt: (xz e L yz E L). Die Relation =/, ist eine Aquivalenzrelation. Der Satz von Myhill und Nerode sagt, dass eine Sprache genau dann regulär ist, wenn =l endlich viele Aquivalenzklassen hat. a) Wir bezeichnen mit #a(w)die Anzahl Vorkommen des Alphabetsymbols a in der Zeichenkette w. Zeigen Sie mit Hilfe des Satzes von Myhill und Nerode, dass die Sprache Li = {w\ #a(w)= über dem Alphabet {a,6} nicht regulär ist. b) Geben Sie alle Äquivalenzklassen der Äquivalenzrelation an. Hier ist L2 = T((a + b)*a) (über dem Alphabet {a,b}). Begründen Sie auch, warum es keine anderen Äquivalenzklassen gibt. c) Ändert sich die Anzahl der Äquivalenzklassen der Sprache L2, wenn Sie stattdessen Wörter über dem Alphabet {a, b, c} betrachten? Begründen Sie Ihre Antwort. Aufgabe 2: Kontextfreie Sprachen Betrachten Sie die Sprache Li = {a"öc"|n e N} U {a6"^c™|m E N}. a) Geben Sie für Li eine kontextfreie Grammatik an. b) Ist Ihre Grammatik aus a) eindeutig? Begründen Sie Ihre Antwort. Betrachten Sie die Sprache L2 — |n e N}. c) Zeigen Sie, dass L2 nicht kontextfrei ist. Fortsetzimg nächste Seite! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 3: Komplexität Betrachten Sie die folgenden Probleme: 3SAT Gegeben: Eine aussagenlogische Formel (p in konjunktiver Normalform (drei Literale pro Klausel). Frage: Ist p erfüllbar? NAE-3SAT Gegeben: Eine aussagenlogische Formel p in konjunktiver Normalform (drei Literale pro Klausel). Frage: Gibt es eine Belegung, die in jeder Klausel mindestens ein Literal wahr und mindestens ein Literal falsch macht? Wir erlauben, dass NAE-3SAT-Formeln Literale der Form false haben, die immer falsch sind. So ist (xi V false V false) A (->a:i V V xi) in NAE-3SAT (setze Xi wahr). a) Zeigen Sie, dass sich 3SAT in polynomieller Zeit auf NAE-3SAT reduzieren lässt. b) Was können Sie aus a) folgern, wenn Sie wissen, dass 3SAT NF-vollständig ist? c) Was können Sie aus a) folgern, wenn Sie wissen, dass NAE-3SAT NF-vollständig ist? Aufgabe 4: Berechenbarkeit Betrachten Sie die folgenden Sprachen: •H = {rcSa:| hält bei Eingabe x} über Alphabet {0,1,$} - Hg — {w \ Myj hält bei Eingabe e} über Alphabet {0,1} Dabei sei x G {0,1}* und bezeichnet My, die von w G {0,1}* kodierte Turingmaschine. a) Zeigen Sie, dass es eine Reduktion von Hg auf H gibt. b) Zeigen Sie, dass es eine Reduktion von H auf gibt. Diese Reduktionen dürfen mehr als polynomielle Zeit benötigen. Fortsetzung nächste Seite! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 4 Aufgabe 5: Die Begründung zählt Bewerten Sie die folgenden Aussagen und geben Sie eine kurze Begründung (ca. ein bis drei Sätze) Ihrer Bewertung an. Nur Ihre Begründung wird bewertet. a) Eine universelle Turingmaschine muss ein unendliches Eingabealphabet haben, um beliebige Turingmaschinen simulieren zu können. b) Für beliebige reguläre Ausdrücke a,ß gilt: L{a • {a + ß))= L{a) U L{a + ß). c) Sei Li eine Sprache und L2 eine reguläre Sprache. Dann ist Li fl immer entscheidbar. d) Es gibt LOOP-Programme, die auch WHILEkProgramme sind. e) Mit dem Satz von RICE kann man nachweisen, dass es unentscheidbar ist, ob eine gegebene Turingmaschine mehr als 10 Zustände hat. f) Es ist NP-schwer zu entscheiden, ob die Sprache eines endlichen Automaten leer ist. Aufgabe 6: Sortieren und das Gegenteil davon 1. Sei S = (42,4711,98,103,1001,-13,8,98,5,13,45,64,42,98,0,17). Zeichnen Sie den Rekur sionsbaum der Sortierung von S mittels MergeSort. Geben Sie für jeden Knoten sowohl die Ein- als auch die Ausgabe des entsprechenden Aufrufs an. 2. MergeSort benötigt zum Sortieren von n Elementen O(nlogn) Schritte im Worst-Case. Wel che Eigenschaft muss eine Eingabe haben, sodass diese Laufzeit tatsächlich erreicht wird? 3. Geben Sie einen Algorithmus in Pseudocode an, der eine Folge von n Elementen aus der Menge {/ = {0,1} in 0(n) Zeit sortiert. Wir sagen eine Methode M{S) permutiert eine Folge S — {xi, ,Xn) von n paarweise verschiede nen Elementen, wenn sie die Reihenfolge der Elemente von S potentiell verändert (die ursprüng liche Reihenfolge darf auch beibehalten werden). Eine gute Permutationsmethode erzeugt jede mögliche Permutation von S mit gleicher Wahrscheinlichkeit. Betrachten Sie die folgende Permutationsmethode: 1 Algorithmus : CleverShuffle(S') Eingabe : Eine Folge S — {xi,...,Xn) Ergebnis : S wurde permutiert. 2 begin for z 1 to n do k <— Random(z, n); vertausche S[i] <-)■ -SfA:]; Die Methode Random(z, j) wählt dabei zufällig eine ganze Zahl aus dem Intervall [i, j], jede mit Wahrscheinlichkeit Man kann zeigen, dass CleverShuffle jede mögliche Permutation von S erzeugen kann, und jede mögliche Permutation mit gleicher Wahrscheinlichkeit erzeugt. 4. Was ist die asymptotische Laufzeit von CleverShuffle, wenn Random eine Laufzeit von 0(1) hat? Fortsetzung nächste Seite! Einzelprüfungsnummer: 66115 Herbst 2017 Seite: 5 Aufgabe 7: Zählen von binären Suchbäumen Für n > 0 betrachten wir die Folge Xn = (l,...,n) der ersten n natürlichen Zahlen (Xq ist also die leere Folge). Wir wollen einen effizienten Algorithmus entwerfen, der berechnet, wie viele verschiedene binäre Suchbäume für (die Elemente von) X„ existieren. Wir bezeichnen diese Zahl mit b{n). Für n = 2 gibt es zwei verschiedene binäre Suchbäume (d.h. 6(2) = 2): 1. Begründen Sie, dass 5(0) = 1 und 5(1) = 1. 2. Warum ist die Anzahl der verschiedenen binären Suchbäume für die Folge (4,5) genau 5(2)? 3. Begründen Sie, dass 5(3) = 5. 4. Welchen (arithmetischen) Zusammenhang erkennen Sie zwischen der Anzahl der verschiede nen binären Suchbäume für X5 die in der Wurzel den Schlüssel 3 speichern, und der Anzahl der verschiedenen binären Suchbäume für die Folgen (1,2) bzw. (4,5)? Begründen Sie diesen. 5. Begründen Sie, dass = Eo 1 und 5(n) = 1 für n < 1. 6. Wie sieht eine Reihenfolge aus, in der die 5(n) bottom-up berechnet werden können, die mit der Rekursionsgleichung für 5(n) verträglich ist? Begründen Sie Ihre Antwort. 7. Geben Sie ein dynamisches Programm in Pseudocode an, das den Wert 5(n) iterativ statt rekursiv berechnet. 8. Warum ist Ihr Algorithmus korrekt? Begründen Sie Ihre Antwort. 9. Was ist die asymptotische Laufzeit Ihres Algorithmus? Was ist der asymptotische Speicher bedarf Ihres Algorithmus? Begründen Sie Ihre Antworten. Hinweis: Wenn Sie die obige Aufgabe nicht gelöst haben, verwenden Sie folgenden Algorith mus zur Beantwortung dieser Frage (Achtung: Das ist nicht die Lösung obiger Aufgabe!): 1 Algorithmus : ExAlg(n) 2 begin 5 Initialize Array a[0,..,n]; a[0] i— 1; a[l] -h- 2; 6 for l 3 4 2 to n do 7 s — I5 8 for r 9 10 11 1 to / do I s •(— s • (a[r — 1] + a[n — r]); o[Z] — s] return a[n]; Fortsetzung nächste Seite! Einzelprüfungsnummer; 66115 Herbst 2017 Seite: 6 Aufgabe 8: Greedy-Färben von Intervallen Sei X = {Ji,/2,..., eine Menge von n (geschlossenen) Intervallen über den reellen Zahlen R. Das Intervall Ij sei dabei gegeben dnrch seine linke Intervallgrenze Ij E R sowie seine rechte Intervallgrenze rj E R mit rj > Ij, d.h. Ij = [lj,rj]. Wir nehmen in dieser Aufgabe der Einfachheit halber an, dass die Zahlen In, ■ ,rn alle paarweise verschieden sind. Zwei Intervalle Ij, 1^ überlappen sich gdw. sie mindestens einen Punkt gemeinsam haben, d.h. gdw. falls für (o.B.d.A.) Ij < 4, auch 1^ < Vj gilt. Eine gültige Färbung von X mit c e N Farben ist eine Funktion F : X ^ {1,2,...,c} mit der Eigenschaft, dass für jedes Paar Ij,Ik von überlappenden Intervallen F{Ij) ^ F{Ik) gilt. I 2 I Abbildung 1: Eine gültige Färbung von X Eine minimale gültige Färbung von X ist eine gültige Färbung mit einer minimalen Anzahl an Far ben. Die Anzahl von Farben in einer minimalen gültigen Färbung von X bezeichnen wir mit x(X). Wir gehen im Folgenden davon aus, dass für X eine minimale gültige Färbung F* gefunden wurde. 1. Nehmen wir an, dass aus X alle Intervalle einer bestimmten Farbe von F* gelöscht werden. Ist die so aus F* entstandene Färbung der übrigen Intervalle in jedem Fall immer noch eine minimale gültige Färbung? Begründen Sie Ihre Antwort. 2. Nehmen wir an, dciss aus X ein beliebiges Intervall gelöscht wird. Ist die so aus F* entstehende Färbung der übrigen Intervalle in jedem Fall immer noch eine minimale gültige Färbung? Begründen Sie Ihre Antwort. 3. Mit uj{X) bezeichnen wir die maximale Anzahl von Intervallen in X, die sich paarweise überlappen. Zeigen Sie, dass x(A) > uj{X) ist. Wir betrachten nun folgenden Algorithmus, der die Menge X = {F,F ■ ..,In} von n Intervallen einfärbt: - Zunächst sortieren wir die Intervalle von X aufsteigend nach ihren linken Intervallgrenzen. Die Intervalle werden jetzt in dieser Reihenfolge nacheinander eingefärbt; ist ein Intervall dabei erst einmal eingefärbt, ändert sich seine Farbe nie wieder. Angenommen die sortierte Reihenfolge der Intervalle sei Ia(i), ■ ■ ■ , F{n)- - Das erste Intervall F{i) erhält die Farbe 1. Für 1 < i < n verfahren wir im Aten Schritt zum Färben des Aten Intervalls wie folgt: Bestimme die Menge Cj aller Farben der bisher schon eingefärbten Intervalle die /„(p überlappen. Färbe /„-(j) dann mit der Farbe c, = min({l,2,..., n}\ Cj). Fortsetzung nächste Seite! Einzelprüfungsnummer: 66115 Herbst 2017 Seite: 7 4. Begründen Sie, warum der Algorithmus immer eine gültige Färbung von X findet (Hinweis: Induktion). 5. Zeigen Sie, dass die Anzahl an Farben, die der Algorithmus für das Einfärben benötigt, mindestens cü{X) ist. 6. Zeigen Sie, dass die Anzahl an Farben, die der Algorithmus für das Einfärben benötigt, höchstens uj{X) ist. 7. Begründen Sie mit Hilfe der o.g. Eigenschaften, warum der Algorithmus korrekt ist, d.h. immer eine minimale gültige Färbung von X findet. 8. Wir betrachten folgenden Implementierung des Algorithmus in Pseudocode: 1 Algorithmus : ColoringNumber(A'L[l,...,n], Aß[l,...,n]) Eingabe : Felder Xr und Xr mit den rechten und linken Intervallgrenzen. Ergebnis : Minimale gültige Färbung der Intervalle. 2 begin sortiere Xr (und passe Xr an); /* color[i] ist die Feirbe des Intervals i */ initialisiere Array coZor[l,.., n]; // mit Nullen /* lastintervalofcolor[c] ist der Index des letzten Intervals das mit c gefärbt wurde 5 6 7 8 9 10 */ initialisiere Array lastintervalofcolor[l,..,n]; color[l\ ^ freecolor] lastintervalofcolor[freecolor] •<— 1; for i -k— 2 to n do 11 freecolorfound ■(— falsc] 12 for c ■<— 1 to maxcolor do 13 14 // mit Nullen maxcolor <— 1; freecolor <— maxcolor] ic <— lastintervalofcolor[c]] if XL\i] > XR[ic] then /* i schneidet kein Interval der Farbe c 15 16 17 18 19 20 21 22 23 freecolor found freecolor c; */ truc] break; /* i schneidet ein Interval der Farbe c */ Ifreecolorfound then maxcolor <— maxcolor + 1; freecolor <— maxcolor] color[i] ■ N mit Wg = Kq. Dabei bezeichnet Wg den Wertebereich von g, d.h. Wg — {g{x) \ x E N}. Gehen Sie wie folgt vor: a) Definieren Sie eine Funktion ^ : N —>■ N. b) Beweisen Sie, dass g total und berechenbar ist. c) Beweisen Sie Wg C Kq. d) Beweisen Sie Wg D Kq. Aufgabe 3: Sei A die durch den regulären Ausdruck (a + b + c)* ■ c-b* -a - (a + b)* -c-b* beschriebene Sprache. a) Geben Sie einen nichtdeterministischen, endlichen Automaten N an, der A akzeptiert. b) Wandeln Sie N in einen äquivalenten deterministischen, endlichen Automaten um. Fortsetzung nächste Seite! Einzelprüfungsnurnmer; 66115 Herbst 2017 Seite: 9 Aufgabe 4: Sei L die durch den regulären Ausdruck (10U 11)*((11 U£)*l)* beschriebene Sprache. [Alternative Schreibweise: (10 + 11)*((11 + e)*l)*] a) Sei SAT das Erfüllbarkeitsproblem (siehe Aufgabe 1 a) zur Definition). Zeigen Sie: L kann in polynomieller Zeit auf SAT reduziert werden (als Relation: L

AB \BG B ^ GC\b AB I a BA I a Sei w = baaab. Eolgende Tabelle entsteht durch Anwendung des GYK-Algorithmus. Z. B. bedeutet B G V(3,5), dass aus der Variablen B das Teilwort = aab hergeleitet werden kann. Drei Einträge wurden weggelassen. b mi,i) a E(2.2) {A,C} \V{\2) V(2,3) a V(3.3) a V(4A) V'(5,5) HO {A,C} E(3A) b {B} E(4,5) {5,C} Kl,3) V(2,4) V(3,5) (SAC) VA.4) {S,A,C} V{2,5) {s,ci Wl,5) i) Bestimmen Sie die Mengen V(l,2), V(l,3) und V(l,5). ii) Wie entnehmen Sie dieser Tabelle, dass w G L{G) ist? Fortsetzung nächste Seite! Einzelprüfungsnummer: 66115 Herbst 2017 Seite; 10 Aufgabe 6: Wissen Ordnen Sie die unten stehenden Aussagen entsprechend ihres Wahrheitsgehalts in einer Tabelle der folgenden Form ein: Kategorie WAHR FALSCH X XI, X3 X2 Y Y2 Y1 A - Datenstrukturen AI A2 Eine Streutabelle, die Kollisionen mit Hilfe einer verketteten Liste auflöst, kann beliebig viele Elemente speichern. Wird der Datentyp Set (zur Darstellung von Mengen) mit einer doppelt verketteten Liste ohne Sortierung implementiert, dann haben das Einfügen eines Wertes in eine be stehende Menge mit n Werten und das anschließende Löschen eines anderen Wertes aus dieser Menge zusammen eine Laufzeitkomplexität von 0{log2{n)). A3 Eine doppelt verkettete Liste der Länge n ohne wahlfreien Zugriff erlaubt das Löschen des Listenkopfes ebenso wie des Listenendes in 0{1) (konstanter Aufwand, unabhängig von n). A4 Eine doppelt verkettete Liste ohne wahlfreien Zugriff kann zur Umsetzung von Warte schlangen nach dem FIFO-Prinzip verwendet werden. B - Laufzeitkomplexität: Gegeben seien zwei Methoden f(int n) und gCint n) mit den jeweiligen Laufzeiten öf{log{n)) bzw. Og(n). Bei welchen der folgenden Schleifen stimmt die Laufzeitangabe im Kommentar? B1 for (int i = 0; i < n; i++) { f(n); B2 for (int i = 0; i < n; i++) { B3 for (int i = 0; i < n; i *= B4 for (int i = n; i > 0; i /= } // Oin) g(i); } // (9(n2) 2) { f(i); g(i); } // ö{n^) 2) { f(n); } // ö{log''{n)) Fortsetzung nächste Seite! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 11 C - Graphen: Ein minimaler Spannbaum eines zusammenhängenden Graphen mit n Knoten ... Cl ...ist stets eindeutig (zu einem Graphen kann es also keine verschiedenen Spannbäume geben). G2 ... muss nicht immer zusammenhängend sein. C3 ...enthält höchstens n — 2 Kanten. C4 ...enthält genau n — 1 Kanten. D - Bäume: Dl Das Einfügen eines Elements in eine Halde (Heap) mit n Einträgen hat konstante Laufzeit. D2 Das Einfügen von n Werten in einen binären Suchbaum hat eine Laufzeit von 0{n). D3 Sowohl das Einfügen und das Löschen, als auch das Suchen haben in einem AVL-Baum einen Laufzeitaufwand von maximal ö{log2{n)). D4 In einem AVL-Baum entspricht der Balancefaktor eines Knotens der Summe der Höhe des linken Unterbaums und der Höhe des rechten Unterbaums. Aufgabe 7: Rekursion Die Potenzmenge V{n) sei die Menge aller Teilmengen der Zahlen von 1 bis n (jeweils einschließ lich), wobei die leere Menge 0 auch zu den Teilmengen gehört, z. B.P(3)= {0,{1},{2},{3},{1,2}, {1,3}, {2,3}, {1,2,3}}. Ergänzen Sie die Methode potenzmenge, die rekursiv V{n) bestimmen soll: Hinweise zur API der Klasse ArrayList: ► public ArrayList(Collection c): Constructs a list containing the elements of the specified collection, in the order they are retumed by the collection's iterator. ► public boolean add(E e): Appends the specified element to the end of this list. static List (); Fortsetzung nächste Seite! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 12 Aufgabe 8: Bäume a) Fügen Sie die Zahlen 13, 12, 42, 3, 11 in der gegebenen Reihenfolge in einen zunächst leeren binären Suchbaum mit aufsteigender Sortierung ein. Stellen Sie nur das Endergebnis dar. b) Löschen Sie den Wurzelknoten mit Wert 42 aus dem folgenden binären Suchbaum mit aufstei gender Sortierung und ersetzen Sie ihn dabei durch einen geeigneten Wert aus dem rechten Teilbaum. Lassen Sie möglichst viele Teilbäume unverändert und erhalten Sie die Suchbaum eigenschaft. 42 13 28 66 50 99 61 55 c) Fügen Sie einen neuen Knoten mit dem Wert 13 in die folgende Min-Halde ein und stellen Sie anschließend die Halden-Eigenschaft vom neuen Blatt aus beginnend wieder her, wobei möglichst viele Knoten der Halde unverändert bleiben und die Halde zu jedem Zeitpunkt links-vollständig sein soll. Geben Sie nur das Endergebnis an. 28 24 11 12 d) Geben Sie für die ursprüngliche Min-Halde aus Teilaufgabe c)(d.h. ohne den neu eingefügten Knoten mit dem Wert 13) die Feld-Einbettung (Array-Darstellung) an. Fortsetzung nächste Seite! Herbst 2017 Einzelprüfungsnuramer: 66115 Seite; 13 e) Löschen Sie den Wurzelknoten mit Wert 42 aus der folgenden Max-Halde und stellen Sie anschließend die Halden-Eigenschaft ausgehend von einer neuen Wurzel wieder her, wobei möglichst viele Knoten der Halde unverändert bleiben und die Halde zu jedem Zeitpunkt links-vollständig sein soll. Geben Sie nur das Endergebnis an. 21 19 3 7 f) Fügen Sie in jeden der folgenden AVL-Bäume mit aufsteigender Sortierung jeweils einen neu en Knoten mit dem Wert 13 ein und führen Sie anschließend hei Bedarf die erforderliche(n) Rotation(en) durch. Zeichnen Sie den Baum vor und nach den Rotationen. i) AVL-Baum A: 28 ii) AVL-Baum B: 28 12 21 Fortsetzung nächste Seite! Herbst 2017 Einzelprüfungsnummer: 66115 Seite: 14 Aufgabe 9: Graphen a) Wenden Sie den Algorithmus von Kruskal auf den Graphen J- an und geben Sie die Kanten in der Reihenfolge an, in welcher das Verfahren sie in den Spannbaum aufnimmt: Graph T: i 4/ V;: " / \ '■■••••5 / 6\ / E ■■•••.3 \ \5 \ \ 2 ..•••■ / \ D Was Sie in den Graphen zeichnen wird nicht bewertet! b) Für einen beliebigen Graphen Q = {V, E) mit Kantenanzahl e := \E\ und Knotenanzahl V := |V1, welche Laufzeitkomplexitäten (in Landau-C-Notation) haben effiziente Implemen tierungen der Algorithmen von Prim und Kruskal im allgemeinen Fall? c) Ergänzen Sie den Algorithmus von Floyd für Graphen G, dargestellt durch die Adjazenzmatrix g. Der Eintrag ^[j] [k] der Adjazenzmatrix g enthält das (positive) Gewicht der Kante (j, k) bzw. 0, falls es keine solche Kante gibt oder falls j = k. Die Implementierung arbeitet hier in-situ und ergänzt auch indirekte Kanten direkt in g. II betrachte alle Kanten—Tripel vj => vi => vk, II vergleiche diese Weglaenge mit vj => vk (sofern vorhanden) II und aktualisiere ggf. die Weglaenge vj => vk public void floydify (double [] [] g) { int n = g . length ; // durchlaufe alle Knoten vi und vj : for (int i = 0; i < n; i++) {