Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: — 66115 2019 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: T'heoret. Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 8 Bitte wenden! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1 Antworten Sie auf die folgenden Behauptungen mit Wahr/Falsch und geben Sie eine kurze Begründung an. (a) Wenn Lz regular ist und L, C Le gilt, dann ist L, auch regulär. (b) Q = {a4 | HEN. q = 77} ist bekanntlich nicht regular. Behauptung: Q* ist ebenfalls nicht regulär. (c) Wenn L C D* entscheidbar ist, dann ist auch das Komplement L = D* \ L entscheidbar. (d) Jedes N P-vollständige Problem ist entscheidbar. Aufgabe 2 (a) Gegeben sei der nichtdeterministische endliche Automat A über dem Alphabet % = {a,b} wie folgt: a, b a a, b start — Konstruieren Sie einen deterministischen endlichen Automaten, der das Komplement L(A) = {w € &* | w ¢ L(A)} der von A akzeptierten Sprache L(A) akzeptiert. Fortsetzung nächste Seite! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 3 (b) Gegeben sei zudem der nichtdeterministische Automat B über dem Alphabet D = {a,b}: b ze a start —(«) (a) a Konstruieren Sie einen endlichen Automaten (möglicherweise mit e-Übergängen), der die Sprache (L(A)L(B))* C %* akzeptiert (A aus der vorigen Aufgabe). Erläutern Sie auch Ihre Konstruktionsidee. Aufgabe 3 Gegeben sei die kontextfreie Grammatik G = (V,D, P, S) mit Sprache L(G), wobei V = {$S,T,U} und © = {a,b}. P bestehe aus den folgenden Produktionen: $— TUUT T- aT le U + Ub |a (a) Geben Sie fünf verschiedene Wörter w € D* mit w € L(G) an. (b) Geben Sie eine explizite Beschreibung der Sprache L(G) an. (c) Bringen Sie G in Chomsky-Normalform und erklären Sie Ihre Vorgehensweise. Aufgabe 4 Wir betrachten die Turingmaschine M = (Q,, F,%,T,O],6). Hierbei ist die Zustandsmenge Q = {90, da; %, 9, Qr} mit Startzustand go und akzeptierenden Zuständen F = {q;}. Das Eingabealphabet ist © = {a,b,$}, das Bandalphabet ist T = ZU {U} mit Blank-Zeichen D für leeres Feld. Die Übergangsfunktion 6: Q xT > Q xI x {L, N, R}, wobei der Schreib-Lese-Kopf mit L nach links, mit N nicht und mit R nach rechts bewegt wird, ist durch folgende Tabelle gegeben (bspw. ist ö(go,a) = (9,I,R)): a b $ O do (da, I, R) (q, O, R) (as, $, N) (qf, O, N) da (da, a, R) (da, b, R) (Biss $, R) (az, a, L) db (9b a, R) (4, b, R) (9; $, R) (az, b, L) qL (91,0, L) (gr, b, L) (qr, $, L) (go, O, R) Fortsetzung nächste Seite! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 4 (a) Die Notation (v,g,aw) beschreibt eine Konfiguration der Turingmaschine: der interne Zustand ist q, der Schreib-Lesekopf steht auf einem Feld mit a € T, rechts vom Schreib-Lesekopf steht w € I, links vom Schreib-Lesekopf steht v € I“. Vervollständigen Sie die Folge von Konfigurationen, die die Turingmaschine bei Eingabe ab$ bis zum Erreichen des Zustands g; durchläuft. Sie können auch Ihre eigene Notation zur Darstellung von Konfigurationen verwenden. (e, do, ab$) —_ (€, da, 6S) — (0, qa) $) — (b) Sei w € {a, b}* beliebig. Mit welchem Bandinhalt terminiert die Turingmaschine bei Eingabe von w$? Geben Sie auch eine kurze Begründung an. Aufgabe 5 Wir betrachten das Behälterproblem BEHAELTER. Gegeben ist eine Menge von k € N Behältern, die jeweils ein Fassungsvermögen der Größe b € N haben. Gegeben sind weiterhin n Objekte mit jeweiligen Größen aı,...,@„. Gesucht ist eine Zuordnung der n Objekte auf die k Behälter, sodass keiner der Behälter überläuft. Formal sind Instanzen des Behalterproblems BEHAELTER durch Tupel (k,}, a1,...@n) gegeben, die wie folgt zu interpretieren sind: - k EN steht für eine Anzahl von Behältern. - Jeder Behälter hat ein Fassungsvermögen von bEN. - Die a, stehen für die jeweiligen Größen von n Objekten. Zuordnungen von Objekten zu Behältern geben wir durch eine Funktion v an, wobei v(j) = i wenn das j-te Objekt (mit Größe a,) dem i-ten Behälter zugeordnet wird. (k,b,aı,...Q,) ist eine JA-Instanz von BEHAELTER, wenn es eine Zuordnung v von Objekten auf Behälter (v : [1;n] — [1; k]) gibt, die sicherstellt, dass kein Behälter überläuft: (k,b,a1,...4n) € BEHABLTER <=> (3v: [1;n] > [1;k]. Vik. S> a; <0) i=v(3) Wir betrachten auch das modifizierte Problem GERADEBEHAELTER. Instanzen von GERADEBEHAELTER tragen die zusätzliche Einschränkung, dass alle a; gerade (durch zwei teilbar) sein müssen. Fortsetzung nächste Seite! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 5 (a) Warum ist sowohl BEHAELTER € NP als auch GERADEBEHAELTER € NP? (b) (c) Beweisen Sie, dass das Problem BEHAELTER auf das Problem GERADEBEHAELTER in polynomieller Zeit reduzierbar ist. BEHAELTER ist NP -vollständig. Begründen Sie, was obige Reduktion für die Komplexität von GERADEBEHAELTER bedeutet. Aufgabe 6 (Algorithmen und Datenstrukturen) Aus dem Känguru-Wettbewerb 2017 — Klassenstufen 3 und 4. (a) (c) (d) Luna hat für den Kuchenbasar Muffins mitgebracht: 10 Apfelmuffins, 18 Nussmuffins, 12 Schokomuffins und 9 Blaubeermuffins. Sie nimmt immer 3 verschiedene Muffins und legt sie auf einen Teller. Welches ist die kleinste Zahl von Muffins, die dabei übrig bleiben können? A: 1, B: 3, C: 4, D: 7, E: 8 Geben Sie die richtige Antwort auf die im Känguru-Wettbewerb gestellte Frage und begründen Sie sie. Lunas Freundin empfiehlt den jeweils nächsten Teller immer aus den drei aktuell häufigsten Muffinsorten zusammenzustellen. Leiten Sie aus dieser Idee einen effizienten GreedyAlgorithmus her, der die Fragestellung für beliebige Anzahlen von Muffins löst (nach wie vor soll es nur vier Sorten und je drei pro Teller geben). Skizzieren Sie in geeigneter Form, wie Ihr Algorithmus die Beispielinstanz von oben richtig löst. Beschreiben Sie eine mögliche und sinnvolle Verallgemeinerung Ihrer Lösung auf n Muffinsorten und k Muffins pro Teller fürn >4undk>3. Diskutieren Sie, wie man die Korrektheit des Greedy-Algorithmus zeigen könnte, also dass er tatsächlich immer eine optimale Lösung findet. Ein kompletter, rigoroser Beweis ist nicht verlangt. Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 6 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1 (k-kleinste Elemente) Gegeben sei eine unsortierte Liste von n verschiedenen natürlichen Zahlen. Das k-kleinste Element ist das Element, das größer als genau k — 1 Elemente der Liste ist. (a) Geben Sie einen Algorithmus mit Laufzeit O(nlogn) an, um das k-kleinste Element zu berechnen. (b) Gegeben sei nun ein Algorithmus A, der den Median einer unsortierten Liste von n Zahlen in O(n) Schritten berechnet. Nutzen Sie Algorithmus A um einen Algorithmus B anzugeben, welcher das k-kleinste Element in O(n) Schritten berechnet. Argumentieren Sie auch, dass der Algorithmus die gewünschte Laufzeit besitzt. (c) Geben Sie einen Algorithmus an, der für alle © = 1,...,|n/k] das i - k-kleinste Element berechnet. Die Laufzeit Ihres Algorithmus sollte O(nlog(n/k)) sein. Sie dürfen weiterhin Algorithmus A, wie in Teilaufgabe (b) beschrieben, nutzen. Aufgabe 2 (Spannbäume) (a) Berechnen Sie zu dem angegebenen Graph einen minimalen Spannbaum. Nutzen Sie den Algorithmus von Kruskal. Geben Sie tabellarisch mit jedem Schritt des Algorithmus an, welche Kanten dem Baum bereits hinzugefügt wurden. Fortsetzung nächste Seite! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 7 (b) Der Durchmesser eines Spannbaums ist die Länge des längsten einfachen Pfads im Baum. Geben Sie ein möglichst effizientes Verfahren an, den minimalen Spannbaum mit Durchmesser 2 zu bestimmen, falls ein solcher existiert. Analysieren Sie die asymptotische worst-case Laufzeit Ihres Algorithmus in Abhängigkeit der Kanten- und Knotenanzahl. (c) Geben Sie nun ein effizientes Verfahren an, den minimalen Spannbaum mit Durchmesser 3 zu bestimmen, falls ein solcher existiert. Analysieren Sie die asymptotische worst-case Laufzeit Ihres Algorithmus. Aufgabe 3 (Rotierende Bäume) (a) Ein Binärbaum ist eine rechtslineare Kette, falls kein Knoten im Baum ein linkes Kind besitzt. Zeigen Sie, wie ein beliebiger Binärbaum durch höchstens n (n=Anzahl der Elemente im Baum) Rotationen in eine rechtslineare Kette umgewandelt werden kann. (b) Gegeben sei ein Algorithmus wie in Teil (a) gefordert. Zeigen Sie, dass ein Binärbaum durch O(n) Rotationen in einen beliebigen anderen Binärbaum gleicher Knotenanzahl umgewandelt werden kann. (c) Zeigen Sie, dass es nicht möglich ist, einen binären Heap in O(n) Operationen, die nicht notwendigerweise Rotationen sind, in einen binären Suchbaum umzuwandeln. Hinweis: Ihre Lösung sollte nicht länger als 4 Sätze sein. Aufgabe 4 (O-Notation) Zeigen oder widerlegen Sie die folgenden Aussagen zur O-Notation. (a) 2” € O(3”). (b) 2282" € O(n). Fortsetzung nächste Seite! Frühjahr 2019 Einzelprüfungsnummer: 66115 Seite: 8 Aufgabe 5 (Formale Sprachen und Komplexität) Wie Sie wissen, ist der Schnitt zweier kontextfreier Sprachen nicht notwendigerweise selbst kontextfrei und es ist unentscheidbar, ob der Schnitt zweier durch Grammatiken gegebener kontextfreier Sprachen leer ist. Das Shufflle-Produkt L}x La zweier Sprachen L,, La über dem Alphabet % ist bekanntlich definiert durch Ly * Lo = {yj Ugd2...UnUn | UiU2-.-Un € Ly, viv2...Un € Lg mit wy, ..., Un; V1, ++, Un © D*} Die Sprache Lı * La enthält also alle Wörter, die man durch Verzahnen eines Wortes in Lı mit einem Wort in Le erhalten kann. Beispiel: {aab, abab} x {aa} = {aaaab, aaaba, aabaa, aaabab, aabaab, aababa, abaaab, abaaba, ababaa} Shuffle-Produkte spielen bei der Verifikation nebenläufiger Programme eine wichtige Rolle. (a) Geben Sie einen regulären Ausdruck für das Shuffle-Produkt der (selbst durch reguläre Ausdrücke gegebenen) Sprache a*b* mit der Sprache c*d* an. (b) Zeigen Sie unter Verwendung des o.a. Resultats über Schnitte kontextfreier Sprachen, dass folgendes Problem unentscheidbar ist: Gegeben sind zwei kontextfreie Sprachen Lı, La über dem Alphabet © = {a,b} durch Grammatiken, sowie eine reguläre Sprache L über © durch regulären Ausdruck. Gefragt ist, ob (Li x La) NL leer ist. Es bietet sich an, zu einer Sprache L über % die Sprache L’ aller Wörter über dem von © disjunkten Alphabet D’ = {a’, b’} zu betrachten, die man durch Ersetzen von a durch a’ und b durch b’ erhält. (c) Dieses Resultat legt nahe, dass das Shuffle-Produkt zweier kontextfreier Sprachen nicht selbst kontextfrei sein muss. Hier soll ein rigoroser Beweis erbracht werden: Seien Lı = {a”b"|n > 1} und La = {c"d”|n > 1}. Zeigen Sie mithilfe des Pumpinglemmas für kontextfreie Sprachen, dass Lı x La nicht kontextfrei ist.