Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Ir Kennwort: es 66115 2012 Ä Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 9 Bitte wenden! Frühjahr 2012 ‘ Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Sei Mo, Mı,... eine Gödelisierung der Registermaschinen (Random-Access-Maschinen, RAMs). Bestimmen Sie, ob folgende Mengen aufzählbar sind. Bestimmen Sie außerdem, ob die Mengen entscheidbar sind. Beweisen Sie Ihre Aussagen! A, = {ED ENXN]| M,; hält auf Eingabe ö nicht innerhalb von £ Rechenschritten} As {(i,z) € Nx N | M; halt nicht auf Eingabe x} Az; = {i€N | für die von M; berechnete Funktion f: N—N gilt dr EN, f(x) = z} i Aufgabe 2: Gegeben ist der folgende nichtdeterministische, endliche Automat M. Konstruieren Sie einen endlichen Automaten M’ mit L(M’) = {a,b}*\ L(M). 7 po © N Aufgabe 3: Beweisen Sie, dass folgende Sprache kontextfrei, aber nicht regulär ist.’ C= {ab™ |n>m-> 1} Aufgabe 4: Gegeben ist die kontextfreie Grammatik G = (©, N,5,R) mit © = {a,b}, N = {S,A,B} und R={S-— A,S — B,A —- aAb,B — AA,B — bBa,A — a}. Geben Sie eine äquivalente Grammatik in Chomsky-Normalform an. Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer: 66115 Seite: 3 Aufgabe 5: Gegeben sind zwei Varianten des Teilsummenproblems (sum of subset, SOS). Beweisen Sie: Sı ist auf 53 in Polynomialzeit reduzierbar. Sy = {(@1,...;Qm;C) | M,@1,--.,;Am,¢ € N und 3dj,..., dm € {0,1, 2} mit S > bya; = c} Sy = {(@1,...,@m,C) | ™M,Q1,...,@m,c EN und FI C {1,...,m} mit Sa; = c} iel Aufgabe 6: Binäre Suchbäume a) Gegeben sei eine Folge von n Zahlen, über deren Verteilung nichts bekannt ist. Es soll ein binärer Suchbaum konstruiert werden, der die Zahlen in dieser Folge speichert. Argumentieren Sie, warum es dafür keinen Algorithmus mit linearer Worst-Case-Laufzeit geben kann. (Um für zwei Zahlen a und 5b zu entscheiden, ob a < b, gehen wir davon aus, dass eine Methode compare(a, b) verwendet werden muss. Diese liefert in O(1) Zeit true, falls a < b und sonst false.) Angenommen die Zahlenfolge sei aufsteigend sortiert. Geben Sie nun einen Linearzeitalgorithmus an, der die Zahlen in dieser Folge in einem binären Suchbaum speichert. Erweitern oder modifizieren Sie Ihren Algorithmus so, dass er in Linearzeit einen balancierten Binärbaum, also etwa einen Rot-Schwarz-Baum oder einen AVL-Baum ausgibt, der die Zahlen in der gegebenen Folge enthält. Zeigen Sie, dass der von Ihrem Algorithmus konstruierte Baum tatsächlich die Eigenschaften eines Rot-Schwarz- oder AVL-Baums besitzt. Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer: 66115 Seite: 4 Aufgabe 7: Kürzeste Kreise Mit der Länge eines Pfads oder eines Kreises bezeichnen wir die Anzahl der Kanten, aus denen der Pfad bzw. der Kreis besteht. Bekanntlich kann man Breitensuche verwenden, um für zwei gegebene Knoten s und ? die Länge eines kürzesten s-t-Wegs zu berechnen. Im folgenden geht es um die Berechnung kürzester Kreise. a) Für einen Graphen G und einen Knoten v von G berechnet KK(G,v) (siehe Abbildung 1) die Länge des kürzesten Kreises in G, der durch v geht. Analysieren Sie die Laufzeit von KK in Abhängigkeit von der Anzahl n der Knoten von G, von der Anzahl m der Kanten von G und vom Grad deg(v) des übergebenen Knotens v. b) Wenn man den Algorithmus KK für jeden Knoten eines Graphen G aufruft, kann man die Länge eines kürzesten Kreises in G berechnen. Welche Laufzeit hat der resultierende Algorithmus in in Abhängigkeit von n und m? c) Geben Sie einen Algorithmus KKschnell(G, v) an, der in O(n +m) Zeit die Länge des kürzesten Kreises in G berechnet, der durch v geht. Argumentieren Sie, warum ihr Algorithmus korrekt ist. Abbildung 1 vum pam aba ee aan mn a sr lee KK(ungerichteter UNBEWICHLELEN rapı ıL= 2 Adi): ={weV | {v,w} € E} 8 foreach w € Adjlvj do 4 | Sei G’ der Graph G ohne die Kante {v, w}. 5 Sei £ die Länge eines kürzesten v-w-Wegs in G’. 6 if 2< L then 7 | Lex s return L Frühjahr 2012 Einzelprüfungsnummer: 66115 _ Seite: 5 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: Für natürliche Zahlen a,b mit b > 0 bezeichne div(a,b) den Quotienten und mod(a,b) den Rest der ganzzahligen Division von a durch b, d.h. es gilt a=b-div(a,b)+mod(a,b) mit 0 = fa,b,c,d,e, fh, %ı = {—}, Le = {4, x, /} ergeben das Alphabet © = Xp UX U Xo. Die Elemente von ©; stellen i-stellige Funktionssymbole dar (i € {0,1,2}). Die nullstelligen Funktionssymbole a,b,c,d,e, f sind symbolische Konstanten. Die Menge der Terme Te ist folgendermaßen definiert: - jedes x € %o gehört zu Te; - für jedes y € ©, und jeden Term t € Te gehört yt zu Te; - für jedes z € Le und je zwei Terme s,t € Te gehört zst zu Te. a) Geben Sie eine kontextfreie Grammatik G an, von der die Menge der Terme generiert wird: L(G) = Te. b) Geben Sie einen Term xsol € Te an, der die z-Komponente der Lésung eines linearen Gleichungssystems az +by =e ce + dy = f darstellt. Zeichen aus &,; U %, haben ihre übliche Bedeutung. Zur Erinnerung: für eine Lösung (x, y) gilt in üblicher Notation ea aS ~ ad — bc af —eb y= ad — bc Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer: 66115 Seite: 8 c) Zeigen Sie GF* xsol durch Angabe einer Ableitung. d) Eine Funktion h: %* — Z wird eindeutig definiert durch: - h(e) =0 - Yu,ve h(u v) = h(w) + h(v) Beispiele: s=+a-aeL t=+a+b€L u=/axa-beL v=+a-—axb€éL h(s) = —1 h(t) =0 h(u) = —1 h(v) = —1 Beweisen Sie die Richtung = in der folgenden Aquivalenz: h(w) = —1 und £[) VYVwer*:weTes (£) Ww „w © Sree ges ny 2 e) Verwenden Sie das Kriterium (£), um einen Kellerautomaten zu konstruieren, der die Sprache Te akzeptiert. Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer: 66115 Seite: 9 Aufgabe 5: Folgendes Codefragment stellt einen Sortieralgorithmus dar: 1 static void sortiere (int p, int q, int{]}] a) { 2 int m,x,y,t,i; 3 if (p>=q) {System.out.print ("Fehler!") ;} 4 m=a[(p+q)/2]; 5 x=p; y=q; 6 do { 7 while (a[{x]m) {y--;} 9 if(xp) {sortiere(p,y,a);} 18 if (x