Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Herbst 2005 66112 Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie, Komplexität, Algorithmen Anzahl der gestellten Themen (Aufgaben); 2 Anzahl der Druckseiten dieser Vorlage: 5 Bitte wenden! Herbst 2005 Einzelprüfungsnummer: 66112 Seite: 2 Thema Nr. 1 Sämtliche Teilaufgaben sind zu bearbeiten! 1. Teilaufgabe (Formale Sprachen) Es sei & = {a,b}. Fir Worter w in D* bezeichne |w| die Lange von w und lwlz die Anzahl der Vorkommen des Symbols z € © in w. Die Sprache L C * enthält alle Wörter w mit der folgenden Eigenschaft: lwl, = wh, und für alle Präfixe (Anfangsstücke) uvon w gilt | ltl. — lls |< 1 Beim Lesen von w von links nach rechts unterscheiden sich die Anzahlen der a’s und b’s also um nie mehr als Eins und am Ende sind es genauso viele a’s wie b’s. a) Geben Sie ein Wort w € L mit |w| = 10 an! b) Geben Sie einen endlichen deterministischen Automaten für Z an! c) Geben Sie einen regulären Ausdruck für Z an! Begründen Sie dabei die Korrektheit des Ausdrucks! d) Die Sprache L' ist definiert durch L'= {w : jwlg = wi, und für alle Präfixe uvon w gilt Jula — ul < 1} Zeigen Sie mit Hilfe des Pumpinglemmas, dass L' nicht regulär ist! e) Geben Sie eine kontextfreie Grammatik für L' an! Erklären Sie die Funktionsweise Ihrer Grammatik! Ein Beweis der Korrektheit ist nicht verlangt. 2. Teilaufgabe (Algorithmen und Datenstrukturen) Sie möchten von München nach Tallinn mit dem Auto fahren und dabei die Anzahl der Tankstopps so klein wie möglich halten. Ihnen liegt eine Liste aller Tankstellen auf dem Weg vor mit der jeweiligen Entfernung von München. Bekannt sind außerdem das Fassungsvermögen des Tanks und der (als konstant angenommene) Verbrauch ihres Autos. Mit folgendem Algorithmus können Sie die Zahl der Tankstopps minimieren. An jeder Tankstelle entscheiden Sie, ob das noch im Tank vorhandene Benzin zur Fahrt bis zur nächsten Tankstelle reicht. Falls ja, so übergehen Sie die Tankstelle, falls nein, so tanken Sie dort voll. a) Zu welcher Klasse von Verfahren gehört diese Methode? b) Implementieren Sie den Algorithmus in einer höheren Programmiersprache (funktional oder objektorientiert, auch Pseudocode) Ihrer Wahl! Sie dürfen voraussetzen, dass die Tankstellen als geeignete Datenstruktur bereits vorliegen, müssen sich also nicht um Ein-/Ausgabe kümmern. Allerdings müssen Sie die verwendeten Datenstrukturen genau dokumentieren! c) Beweisen Sie, dass der Algorithmus korrekt ist, also tatsächlich die Zahl der Tankstopps minimiert! Dazu können Sie zum Beispiel nachweisen, dass zu jedem Zeitpunkt die bereits getroffenen Entscheidungen noch zu einer optimalen Lösung erweitert werden können. Fortsetzung nächste Seite! ‘Herbst 2005 Einzelprüfungsnummer: 66112 Seite: 3 3. Teilaufgabe (Ablaufmodellierung) In einem Automatikfahrzeug müssen Sie beim Starten den Schalthebel in Position N bringen. Ist das Fahrzeug gestartet, so ertönt ein Gong, falls nicht vorher der Sicherheitsgurt angelegt wurde. Sie können dann losfahren, indem Sie den Schalthebel in die Position D bringen, allerdings muss hierbei die Bremse gedrückt werden. Nach dem Ausschalten des Motors kann der Zündschlüssel nur entfernt werden, wenn vorher der Schalthebel in Position P gebracht wurde. a) Modellieren Sie diesen Sachverhalt durch einen Zustandsautomaten! Ihre Modellierung darf und sollte sinnvolle Übergänge enthalten, die im obigen Text nicht ausdrücklich erwähnt, aber auch nicht ausdrücklich verboten sind. b) Zueiner gefährlichen Situation kann es kommen, wenn der Motor läuft und der Schalthebel von N nach D umgelegt wird, ohne dass die Bremse gedrückt wird. Kann diese Situation in Ihrer Modellierung auftreten? Falls ja, so ändern Sie Ihre Modellierung entsprechend ab! c) Gibt es in Ihrem Modell einen zyklischen Ablauf, der einen Zustand enthält, in dem das Auto fährt und einen Zustand, in dem der Motor ausgeschaltet ist? Falls nein, so ändern Sie Ihre Modellierung entsprechend ab! Herbst 2005 Einzelprüfungsnummer: 66112 Seite: 4 Thema Nr. 2 Sämtliche Teilaufgaben sind zu bearbeiten! Teilaufgabe 1: Sei L, die Sprache aller Wörter über {a,b}, für die gilt I, (w) +2 I, (w) = 3n (n eN o> wobei 1, (w) die Anzahl der Vorkommen des Symbols x im Wort w ist. a) Geben Sie einen deterministischen erkennenden Automaten zu Z, an! b) Zeigen Sie, dass Z, regulär ist für jedes neN. Teilaufgabe 2: Geben Sie ein WHILE-Programm an, das die Funktion < x — 2” > berechnet! Teilaufgabe 3: Sei gn: {a,d,c}* — N definiert durch * gn(leeres Wort) = 0, gn(a) =1, gn(b) = 2, gn(c) = 3, * gn(ws) =3 gn(w) + gn(s), (w € {a, b,c}*,s € {a, b, c}) a) Berechnen Sie gn(abc). b) Zeigen Sie, dass gn bijektiv ist! c) Berechnen Sie gn'(123). * Sei numconc die Funktion mit numconc(x, y) = z genau dann, wenn es Wörter u, ve {a,b,c}* gibt mit x = gn(u), y= gn(v)undz=gn(uv). * Sei numlength die Funktion mit numlength(x) = Länge von gn’(x). d) Berechnen Sie numconc(13, 123). e) Geben Sie einen Term t(x, y) für numconc(x, y) an, der numlength enthalten darf! D) Zeigen Sie, dass numconc assoziativ ist! Fortsetzung nächste Seite! Herbst 2005 Einzelprüfungsnummer: 66112 Seite: 5 Teilauf; 4: (Objektorientierter Entwurf) Seit Jahren bemühen sich die Finanzbehörden, insbesondere private Steuerzahler zur elektronischen Abgabe der Steuererklärung (ELSTER) zu bewegen. Erst in den letzten Jahren ist aufgefallen, dass die Unterstützung eines einzigen Betriebssystems zu einschränkend ist. Es sind die Grundlagen eines plattformunabhängigen ELSTER-Programms zur Unterstützung der folgenden Anforderungen zu modellieren: * Das Programm unterstützt die üblichen Formulare einer Steuererklärung, z.B. den Mantelbogen, Anlage N (Nichtselbständige), Kap (Kapitaleinkünfte), .... * Jedes Formular besteht aus Zeilen, die wiederum vorgegebenen Text oder Eingabefelder enthalten können. Einige Felder werden aus den Werten anderer Felder anhand vorgegebener Formeln wie in einer Tabellenkalkulation berechnet. + Zujedem Formular gibt es spezifische Regeln um die Eingaben zu verifizieren. * Eine kontextsensitive und formularspezifische Hilfe zum Ausfüllen der einzelnen Formulare ist anzubieten. « Parallel zur Eingabe der Daten in ein Formular sollen Zusatzinformationen als Freitext erfasst werden, der dann als Anlage z.B. für Begründungen und Absetzungen zu den Formularen beigelegt werden kann. Stellen Sie die relevanten Klassen durch ein verfeinertes UML-Analyseklassendiagramm dar! Spezifizieren Sie Beziehungen zwischen den Klassen! Teilaufgabe 5: (Algorithmen) Gegeben sei ein Hashverfahren mit Kollisionsauflösung innerhalb der Tabelle (offene Adressierung) mit beliebiger Sondierungsfunktion! Modifizieren Sie den Algorithmus zum Einfügen eines Schlüssels so, dass alle entstehenden Sondierungsfolgen sortiert sind (Ordered Hashing)! Geben Sie einen Algorithmus zum Suchen von Schlüsseln an, der diese Eigenschaften ausnutzt! Ändert sich der Aufwand für die Operation wesentlich? Teilaufgabe 6: (Datenstrukturen) a) Erzeugen Sie aus der gegebenen Folge einen 2-3-4 Baum (B-Baum mit Ordnung m=2): 22, 10; 19; 1; 13; 12; 7; 8; 5; 42; 33; 21 Fügen Sie dazu die einzelnen Elemente in gegebener Reihenfolge in einen anfangs leeren 2-3-4 Baum ein. Stellen Sie für jeden Wert die entsprechenden Zwischenergebnisse und die angewendeten Operationen als Bäume dar! b) In dem Ergebnisbaum suchen wir nun den Wert 17. Stellen sie den Ablauf des Suchalgorithmus an einer eigenen Zeichnung grafisch dar! c) Essei n die Zahl derjenigen Schlüssel, die in einem inneren Knoten gespeichert sind. Zeigen Sie: Die Zahl der Blätter, also Knoten ohne Kinder, betragt n +1.