Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 66 1 12 2006 Arbeitsplatz-Nr.: 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: 7 Thema Nr. 1 Automatentheorie Anmerkungen zur Notation: Sei T(A) die von einem endlichen Automaten A = (Z,2,6,5,E) erzeugte Sprache. Dann wird 6: P(Z)x 2’ — P(Z) wie folgt induktiv definiert: ö(Z’,e) = Z' für alle Z’ CZ ah x = 6 §(Z’,ar) = U_8(5(z,a),2) Sei nun der nichtdeterministische endliche Automat (NFA) N = ({s, B,,B,,B,} ,{a,b},7, {5},{5}) mit folgender Überführungsfunktion y gegeben: b Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66112 Seite: 2 a) Bestimmen Sie die Menge 2 = 5({5},baabb). Gilt baabb € T(N)? b) Konstruieren Sie einen deterministischen endlichen Automaten (DFA) M, der die Bedingung T(N)=T(M) erfüllt! €) Geben Sie einen regulären Ausdruck für T(N) an! d) Bilden Sie zu N eine reguläre Grammatik mit L(G)=T (N)! Formale Sprachen Gegeben sei eine Grammatik für bedingte Anweisungen, deren Produktionsmenge unter anderem Folgendes enthält: Anweisung if-Anweisung if-Anweisung | Andere-Anweisung if Bedingung then Anweisung | if Bedingung then Anweisung else Anweisung Terminale sind dabei unterstrichen. Die Nicht-Terminale Andere-Anweisung und Bedingung können mit dem gegebenen Ausschnitt der Grammatik nicht weiter abgeleitet werden. Deuten Sie daher in den Syntaxbäumen die entsprechenden Teilbäume mit einem Dreieck an! a) Zeigen Sie, dass die Grammatik mehrdeutig ist, indem Sie Syntaxbäume angeben! b) Wählen Sie logische Ausdrücke und Anweisungen für die Syntaxbäume aus der vorherigen Teilaufgabe so, dass die Ausführung der zugeordneten Programme zu verschiedenen Ergebnissen führt! c) Wie kann diese Mehrdeutigkeit aufgelöst werden? d) Geben Sie Produktionsregeln an, die Ihre Lésung aus Aufgabenteil (c) realisieren, so dass die Grammatik eindeutig wird! Berechenbarkeit Untersuchen Sie, ob die folgenden Mengen und Sprachen entscheidbar bzw. semi-entscheidbar sind! Begründen Sie jeweils Ihre Antwort! a) fi (A= {n EN|fme Al, wobei AC.N eine entscheidbare Menge und f: N — IN eine totale und berechenbare Funktion ist. b) Li\L2, wobei L; CN eine semi-entscheidbare und L, < Neine entscheidbare Sprache ist. Algorithmen und Datenstrukturen a) Gegeben sei die folgende Folge ganzer Zahlen: 6, 13, 4, 8, 11, 9, 10. > Fügen Sie obige Zahlen der Reihe nach in einen anfangs leeren AVL-Baum ein und stellen Sie den Baum nach jedem Einfügeschritt dar! > Löschen Sie das Wurzelelement des entstandenen AV L-Baums und stellen Sie die AVLEigenschaft wieder her! Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66112 Seite: 3 b) Gegeben sei der folgende gerichtete und gewichtete Graph: > Bestimmen Sie mit Hilfe des Algorithmus von Dijkstra die kürzesten Wege vom Knoten A zu allen anderen Knoten! Geben Sie dabei nach jedem Verarbeitungsschritt den Zustand der Hilfsdatenstruktur an! > Skizzieren Sie einen Algorithmus für den Tiefendurchlauf von gerichteten Graphen, wobei jede Kante nur einmal verwendet werden darf! c) Ein wesentlicher Nachteil der Standardimplementierung des QUICKSORT Algorithmus ist dessen rekursiver Aufruf. > Implementieren Sie den Algorithmus QUICKSORT ohne den rekursiven Prozeduraufruf! Systementwurf a) Erklären Sie den Begriff Vererbung und benennen Sie die damit verbundenen Vorteile! b) Erstellen Sie zu der folgenden Beschreibung eines Systems zur Buchung von Flügen ein Klassendiagramm, das neben Attributen und Assoziationen mit Kardinalitäten auch Methoden zur Tarifberechnung enthält! Setzen Sie dabei das Konzept der Vererbung sinnvoll ein! > Die Fluggesellschaft bietet verschiedene Flugrouten an, die durch den jeweiligen Startflughafen und Zielflughafen charakterisiert werden. > Jeder Flug besitzt eine Flugnummer, eine Abflugzeit, eine geplante Ankunftszeit und ist genau einer Flugroute zugeordnet. Flugrouten sollen auch gespeichert werden, falls noch keine zugehörigen Flüge existieren. > Flugbuchungen beziehen sich auf einzelne Plätze im Flugzeug. Sowohl in der Economy Class als auch in der Business Class gibt es Nichtraucher- und Raucherplätze. Zu jeder Buchung wird das Datum vermerkt. > Zu jedem Passagier müssen die Adressinformationen erfasst werden. > Die Berechnung des Tarifs soll vom System unterstützt werden. Jeder Flug besitzt einen Grundpreis. Für Plätze der Business Class wird ein Aufschlag verrechnet. Auf diesen ermittelten Zwischenpreis sind zwei Arten von Rabatten möglich: - Jugendliche Privatkunden unter 25 Jahren erhalten einen Nachlass auf den Flugpreis. - Geschäftsreisende erhalten Vergünstigungen in Abhängigkeit ihrer gesammelten Flugmeilen. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66112 Seite: 4 c) Erstellen Sie ein exemplarisches Objektdiagramm! Es soll mindestens einen Flug enthalten, in dem sowohl ein privater Kunde als auch ein Geschäftskunde einen Platz gebucht haben! Wählen Sie geeignete Attributwerte! d) Beschreiben Sie den Vorgang „Tarifberechnung‘“ wahlweise als Sequenzdiagramm oder Kommunikationsdiagramm! Thema Nr. 2 Aufgabe 1 Gegeben sei ein Variablenalphabet V = {4,B} und ein Terminalalphabet T = {a,b}. Es sei G; = (V,T,P;,A) die kontextfreie Grammatik mit den Produktionen P = {A aAb|bB,B— bBjaB|A} und G2 = (V, T,P,,A) die kontextfreie Grammatik mit den Produktionen P,={A- aAb|Ba,B— bBlaB|\}, wobei X für das leere Wort steht a) Welches sind die von G, bzw G; generierten Sprachen L(G,) bzw. L(G;)? Geben Sie Beschreibungen von L(G;) bzw. L(G2), die nicht auf die Grammatiken G7 bzw. G> Bezug nehmen! Beweisen Sie Ihre Behauptungen! b) Zeigen Sie, dass die kontextfreien Sprachen L(G,) und L(G) nicht regulär sind! ©) Welches sind die Sprachen L(G,) U L(G,) und L(G,)NL(G,)? Welche dieser Sprachen ist regulär? Aufgabe 2 Es sei I = {0,1}. Das Alphabet }, bestehe aus allen Paaren von Elementen aus Y, geschrieben als Spaltenvektoren der Länge 2 über ¥, also 2,-| | Ein Wort w= ww, ...w, €, mit w, = y 0 0 1 0 0 1 1 1 abla p> ,1 Dies ist eine Beispielpixelgrafik. Die Folie enthalt eine Überschrift. Im Hauptteil befindet sich eine Pixelgrafik mit einer Bildunterschrift. Grafik und Bildunterschrift bilden eine Gruppe. Der Folienmaster enthält ein hellgraues Rechteck als Hintergrund für den Hauptteil (ohne Überschrift) und ein Logo (Pixelgrafik) in der oberen rechten Ecke. Geben Sie zu dieser Folie und dem zugehörigen Folienmaster ein UML-Objektdiagramm an! Hinweis: Gehen Sie von den üblichen Folienmaßen aus: Höhe=21cm, Breite=29,7cm aus. Alle Angaben für Breiten, Höhen und Positionen von Folienelementen dürfen Sie schätzen, keinesfalls müssen diese maßstabsgetreu sein! Das Koordinatensystem habe in der oberen linken Ecke seinen Nullpunkt, Punkte im Inneren des Folienbereichs haben positive x- und y-Koordinaten. c) Die Folie aus Aufgabe b soll präsentiert (dargestellt) werden. Zeichnen Sie für diese Situation ein UML-Sequenzdiagramm! Aufgabe 4 Ein Navigationssystem soll folgenden Service anbieten. Ausgehend von einem aktuellen Standort eines Anfragenden sollen alle Restaurants einer bestimmten Küchenrichtung (z. B. italienisch, chinesisch) ausgegeben werden, die sich innerhalb eines quadratischen Bereichs einer anzugebenden Grö- Be um diesen befinden (s. Abbildung): Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66112 Seite: 7 / i & 3H standort AR chinese Rainer B® cieche Gehen Sie vereinfachend davon aus, dass sowohl der Standort, als auch alle Restaurants jeweils mit ihren (x, y)-Koordinaten vorliegen, wobei 0 < x < xmax und 0 < y < ymax gelten soll. Verwenden Sie zur Formulierung von Algorithmen bzw. Datentypen eine gängige höhere Programmiersprache oder einen entsprechenden Pseudocode! Erläutern Sie Ihre Lösung ausgiebig durch Kommentare! a) b) c) Geben Sie einen geeigneten Datentyp zur Verwaltung der Restaurants an! Zusätzlich zur Lage ((x, y)-Koordinaten) soll der Name, die Adresse, die Telefonnummer und die Küchenrichtung angegeben werden! Geben Sie einen Algorithmus an, der als Eingabe einen Standort in (x,y)-Koordinaten, eine Bereichsgröße und eine bevorzugte Küchenrichtung erhält und der als Ergebnis eine Datenstruktur liefert, die alle Restaurants dieser Richtung innerhalb eines achsenparallelen, quadratischen Bereichs um den Standort enthält! Lösungshinweis: Eine mögliche Strategie besteht darin, zunächst nur die Restaurants mit passender x-Koordinate zu identifizieren und aus diesen diejenigen mit passender y-Koordinate auszuwählen. Geben Sie die Laufzeit Ihres Verfahrens in O(n)-Notation an und begründen Sie Ihr Ergebnis! Aufgabe 5 a) b) c) Geben Sie einen rekursiven Algorithmus vom Typ „Teile und Herrsche“ zum Zeichnen einer Approximation des Geradenabschnitts an, welcher zwei gegebene Punkte (x1,y1) und (x2,y2) verbindet, indem Pixel mit ganzzahligen Koordinaten gezeichnet werden! Dabei soll der erste zu zeichnende Punkt etwa in der Mitte zwischen den beiden gegebenen Punkten liegen. Wann kann die Rekursion abgebrochen werden? Gehen Sie davon aus, dass zum Zeichnen eines Pixels eine Operation zeichne mit geeigneten Parametern zur Verfügung steht. Verwenden Sie (auch im Teil c.) zur Formulierung eine gängige höhere Programmiersprache oder einen entsprechenden Pseudocode. Erläutern Sie Ihre Lösung ausgiebig durch Kommentare! ‘Warum sollte man dieses Problem nicht mit einem Algorithmus vom Typ „Teile und Herrsche“ lösen? Geben Sie eine bessere Lösung für die unter a.) beschriebene Aufgabenstellung an!