Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Frü hj ahr Arbeitsplatz-Nr.: | 2 0 1 4 46115 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: 6 Bitte wenden! Frühjahr 2014 Einzelprüfungsnummer 46115 Seite 2 Thema Nr. 1 Annahmen: i Sie dürfen als bekannt und bewiesen voraussetzen: Die Sprache {a"b°|n>1} ist nicht regulär Die Sprache {aRbU ca|n>1} ist nicht kontext-frei. Um zu zeigen, dass eine Sprache L regulär (kontexfrei) ist, reicht die Angabe einer entsprechenden Beschreibung (Automat, Grammatik, Ausdruck). Sie müssen nicht mehr zeigen, dass Ihre Beschreibung korrekt ist und genau die vorgegebene Sprache beschreibt. Aufgabe 1: Reguläre Mengen Sei L die Menge aller Wörter über dem Alphabet {a,b}, bei denen das erste, zweite und letzte Zeichen übereinstimmen. a) Geben Sie alle Worte bis zur (einschließlich) Länge drei an! b) Beschreiben Sie L i) durch einen regulären Ausdruck ii) durch einen deterministischen endlichen Automaten A! . Aufgabe 2: Regulär oder nicht Sei L dieSpace L={anpm| m=n,n> 1} Ist L regulär oder nicht? Begründen Sie Ihre Antwort durch die Angabe einer passenden Beschreibung für L oder den Nachweis, dass L nicht regulär sein kann! Aufgabe 3: NFA und DFA an Sie zum angegebenen nicht-deterministischen Automaten A = ((0,1,2}, {a,b}, 5, 0, {0,3}) | einen äquivalenten deterministischen endlichen Automaten! A hat die Zustände 0,1,2,3; 0 ist der Startzustand und 0,3 sind Endzustinde. . ry a Fortsetzung nächste Seite! Frühjahr 2014 Einzelprüfungsnummer 46115 Seite 3 Aufgabe 4: Kontextfrei Zeigen Sie, dass die Sprache L kontext-frei ist! L={aunpk ckpmcman| K,m,n>1} Aufgabe 5: Berechenbarkeit und Komplexität Gegeben sei die Sprache L = {a b™ ck] j,m,k21,j#m und j #k} a) Geben Sie eine Turingmaschine M an, die L erkennt! Beschreiben Sie in Worten, wie Ihre Turingmaschine arbeitet! b) Welche Zeitkomplexität in O-Notation hat Ihre Turingmaschine? Erläutern Sie dies anhand Ihrer in a) gegebenen Beschreibung! Aufgabe 6: O-Notation Gegeben sind die Funktionen fund g (über den natürlichen Zahlen): g(n) =100(@J/n +1)? und f(n)=n?-2n+3 Zeigen Sie dass ge O(f) gilt! (Es reicht nicht zu sagen, dass eine Funktion stärker steigt). Aufgabe I Heap und binärer Suchbaum und AVL Baum a) Fügen Sie nacheinander die Zahlen 11, 1,2, 13,9, 10, 7,5 (i) in einen leeren binären Suchbaum und zeichnen Sie den Suchbaum jeweils nach dem Einfügen von „9“ und „5“ (ii) _ineinen leeren Min-Heap ein, der bzgl. „<“ angeordnet ist und geben Sie den Heap nach „9“ und nach „5“ an (ii) | in einen leeren AVL- Baum ein! Geben Sie den AVL Baum nach „2“ und „5“ anund. beschreiben Sie die ggf. notwendigen Rotationen beim Einfügen dieser beiden Elemente! | Fortsetzung nächste Seite! . Frühjahr 2014 Einzelprüfungsnummer 46115 Seite 4 Aufgabe 8: Minimaler Spannbaum — Bestimmen Sie einen minimalen Spannbaum für einen ungerichteten Graphen, der durch die nachfolgende Entfernungsmatrix gegeben ist! Die Matrix ist symmetrisch und „©“ bedeutet, dass es keine Kante gibt. Geben Sie die Spannbaumkanten ein! Wie groß (Wert) ist der minimale Spannbaum? A B C D E F G H A 0 8 —1 © 8 © 7 © B 8 0 © 2 © © © 9 C —1 co 0 5 | 8 1 7 eo D © 2 5 0 6 6 © oo - 8 00 8 6 | 0 6 3 co F © © 1 6 6 0 11 | 4 G 7 oo 7 00 3 11 0 5 H © 9 oo co co 4 5 0 Frühjahr 2014 Einzelprüfungsnummer 46115 Seite 5 Thema Nr. 2 Aufgabe 1: Sei & = {0,1,$} und sei INo = {0, 1, 2,...}. a) Sei . | Lı = {0" $12" | ne INo} U {0?"$1" | ne INo} . ~ Beispiele: 00$1111 € Ly, $ € Ly, 0081 € Ly. 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 L, erzeugt. b) Formulieren Sie das Pumping-Lemma für reguläre Sprachen: „wei L eine reguläre Sprache über dem Alphabet %. Dann gibt es...“ c) Zeigen Sie mittels Pumping-Lemma, für reguläre Sprachen, dass die Sprache Ly nicht regulär ist. Aufgabe 2: a) Geben Sie einen deterministischen endlichen Automaten an (Zeich_ nung), der die Sprache Lg = {a' |i € IN, i ist durch 2, aber nicht durch 3 teilbar} akzeptiert. (IN = {1,2,...}) b) Beweisen oder widerlegen Sie die folgende Behauptung: „Ist die Sprache L nicht regulär, dann ist auch jede echte Teilmenge von L nicht regulär.“ c) Für n > 2 sei zu einem Wort w = a1Q2...Q,: kopflos(w) = {a2...an} - Außerdem sei kopflos(a) = {e} und kopflos(e) = Beweisen oder widerlegen Sie die folgende Behauptung: „Zst die Sprache L regulär, dann ist auch kopflos(L) = U kopf los(w) wel Fortsetzung nächste Seite! regulär.“ Frühjahr 2014 | Einzelprüfungsnummer 46115 | Seite 6 Aufgabe 3: a) Fügen Sie die Zahlen 17, 7, 21, 3, 10, 13, 1, 5 nacheinander in der vorgegebenen Reihenfolge in einen binären Suchbaum ein und zeichnen Sie das Ergebnis! b) Implementieren Sie in einer objektorientierten Programmiersprache oder in entsprechendem Pseudocode eine rekursiv festgelegte Datenstruktur, deren Gestaltung sich an folgender Definition eines binären Baumes orientiert! Ein binärer Baum ist entweder ein leerer Baum oder besteht aus einem Wurzelelement, das einen binären Baum als linken und einen als rechten Teilbaum besitzt. Bei dieser Teilaufgabe können Sie auf die Implementierung von Methoden (außer ggf. notwendigen Konstruktoren) verzichten! c) Beschreiben Sie durch Implementierung in einer gängigen objektorientierten Programmiersprache oder in entsprechendem Pseudocode, wie bei Verwendung der obigen Datenstruktur die Methode loescheKnoten(w) gestaltet sein muss, mit der der Knoten mit dem Eintrag w aus dem Baum entfernt werden kann, ohne die Suchbaumeigenschaft zu verletzen! Aufgabe 4: fn _ Fir Binomialkoeffizienten ") gelten neben den grundlegenden Beziehungen (6) = 1und ("| = 1 oleae) aa} a) Implementieren Sie unter Verwendung von Beziehung A) eine rekursive Methode binRek(n,k) zur Berechnung des Binomialkoeffizienten in einer objektorientierten Programmiersprache oder entsprechendem Pseudocode! auch folgende Formeln: b) Implementieren Sie unter Verwendung von Beziehung B) eine iterative Methode binIT(n,k) zur Berechnung des Binomialkoeffizienten in einer objektorientierten Programmiersprache oder entsprechendem Pseudocode! c) Geben Sie die Laufzeitkomplexität der Methoden binRek(n,k) und binIT(n,k) aus den vorhergehenden beiden Teilaufgaben in O-Notation an!