Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnunrmer Kennzahl: Herbst Kennwort: 2002 66TT2 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzahlder gestelltenThemen(Aufgaben): 2 dieserVorlase: Anzahlder Druckseiten 7 Bitte wenden! Herbst2002 Seite:2 Einzelprüfungsnummer : 66lLz Thema Nr. I Sämtliche Teilaufgaben sind zu bearbeiten! Aufeabe L Gegebenist ein endlicherAutomat A mit Zustandsmenge S: {S0,S,,S}S}So,Sr},AlphabetI={0,1}, Anfangszustand So,Endzuständen ö: {S.,S5} und der folgendenZustandsübergengsfunktion =s,,ö(s0,1) =s,,ö(s,,0) =s4, =s0, =so. ö(s0,0) ö(q,1)=s5, ö(s,,0) ö(s,,1) =s4 ö (s3,0)=s5,ö (s3,i):s., 6 (s4,0):s3,ö (s,,1):s5,I (s5,0)=s3, ö (s5,1) des Automaten!Ist der Automat deterministisch? a) ZeichnenSie das Zustandsdiagrarnm b) Welche Zuständesind äquivalent(mit Begründung)? c) KonstruierenSie einen zu A äquivalenten,minimalen deterministischenAutomaten! d) GebenSie eine rechtslineareGrammatikan, die die SpracheL(A) (von A) erzeugt! e) GebenSie eilen regulärenAusdruckmit der SpracheL(A) an! Aufeabe 2 unddie SpracheL= {weI*|wenthältgleichviele awieb} ! a) GebenSie eine mebrdeutige,kontextfreieGrammatik G an, die die SpracheL erzeugt! Gegeben seidasAlphabetI={a,t} b) GebenSie hir die Worte baabund ababjeweils einenAbleitungsbauman! c) Zeigen Sie, dassdie Grammatik G nicht ehdeutig (ambig) ist! d) Gesuchtist eine eindeutigeGrarrmatik G', die dieselbeSprachewie G hat! Vervollst?indigenSie dazu den folgendenAnsatz durch Hinzunahmevon filnf weiteren Produkionsregetn: G= ({S,AB}, >, P',S)wobeiP'={s -+ an,s-+ te,S -+ bAS,...} Aufgabe 3 Gegebensei die Funktion p: Na -+ Nr mit p(n) = 2' ""ttts n +I,p(I) =I FortsetzungnächsteSeite! Herbst2002 Einzelprüfungsnummer : 66112 Seite:3 a) GebenSieeinerekursiveFunktionsdefinition mit Kopf frurctionf(n: nat)nat; an, die die Funllion p berechnet!Dabei sollen nur aritlmetische Grundoperationen(wie z.B. Addition, Multiplikation,.. .) verwendetwerden. b) BestimmenSie das zur Funktionsdefinitionin Teil a) gehörendeFunktional @! (GebenSie auch die Funktionalitätvon (D an!) c) ZeigenSie,dassdie Funlrtionp ein FixpunktdesFunktionals@ ist! d) Zeiget Sie, dassdie Funktionsdefinitionvon Teil a) terminierendistl e) GebenSiedie Ordnung der Zeit- und der Speicherplatzkomplexität der in a) definierten Funktion an (mit Begründung)! - f) GebenSie eine iterative (nicht rekursive)Funlcionsdefinitionzur Berechnungvon p an! (Wiederum dürfen nur arithmetischeGrundoperationenverwendetwerden!) g) GebenSie die Ordnung der Zeit- und der Speicherplatzkomplexität der in f) definierten Funktion an (mit Begründung)! Aufeabe 4 In einer Anforderungsanalyse ftt ein Banksystemwird der folgendeSachverhaltbeschrieben: Eine Bank hat einen Namenund sie führt Konten. JedesKonto hat eine Kontonummer.ehen Kontostandund einenBesitzer. Der Besitzerhat einenNamenund eine Kundennummer.Ein Konto ist entwederein Sparkontooder ei:r Girokonto. Ein Sparkontohat einen Ztnssatz,ein Girokonto hat einenKreditrahmenund eineJabressebühr. a) DeklarierenSie geeigneteKlassenin Javaoder in C++ , die die obenbeschriebenenAnforderungenwiderspiegeln!NutzenSiedabeidasVererbungskonzept aus,wo es sinnvollist! Gibt esKlassen, die als abstraktzu verstehensind? b) GebenSie für alle nicht abstraktenKlassenbenutzerdefinierteKonstruktorenan mit Parametern zur Initialisierung der folgendenWerte: der Name einer Bank, die Kontonunmer, der Kontostand,der Besitzerund der Zinssatz(bzw. Kreditrahmenund Jahresgebi.ihr) einesSparkontos (bzw. Girokontos),der Nameund die KundennummereinesKontobesitzers! ErgänzenSie die Klassenum Methodenflir die folgendenAufgaben! Nutzen Sie wenn immer möglich dasVererbungskonzeptausund verwendenSie ggf. abstrakte(bzw. virtuelle) Methoden! c) Auf ein Konto soll ein Betrag ei:rgezahltwerdenkönnenund es soll ein Betragabgehobenwerden können. Soll von einemSparkontoein Betragabgehobenwerden, danndarf der Kontostandnicht negativwerden. Bei einer Abhebungvon einemGirokonto darf der Kreditrahmennicht überzogen werden. FortsetzunenächsteSeite! Herbst2002 Einzelprüfungsnumm er: 66lLZ Seite:4 d) Ein Konto kann eine Jahresabrechaung durchflihren. Bei der Jahresabrechnung einesSparkontos wird der Zrnsertraggut geschrieben,bei der Jahresabrechnung einesGirokontos wird die Jahresgebührabgezogen(auch wenn dadurchder Kreditrahmenüberzogenwird). e) Eine Bank kann einen Jahresabschluss durchführen.Dieser bewirkt, dassftit iedesKonto der Bank eine Jahresabrechnung durchgeführtwird. 0 Ehe Bank kann eil Sparkontoeröffnen. Die Methodesoll die folgendenfünf Parameterhaben: den Namenund die Kundennurnmerdes Kontobesitzers,die Kontonummer,den (anfünglichen) Kontostandund den ZinssatzdesSparkontos.Alle Parametersind als String-Objekteoder als Werte einesGrunddatentypszu übergeben!Das Sparkontomussnach seinerEröffoung in den Kontenbestandder Bank aufgenommenseitr. FortsetzungnächsteSeite! Herbst2002 Seite:5 : 66ILz Einzelprüfungsnummer Thema Nr. 2 Sämtliche Teilaufgaben sind zu bearbeiten! Aufeabe I (Automatenund formale Sprachen) Gegebensei folgendeGramrnatikG überdemAlphabetI={a,b,<,>} S -+ R -+T R+ T-+aU U+BU U+B B-+a B+b Wörter! L(G) beschreibtdie bezüglicheher Klammer korrekr geschachtelten a) GebenSiedie von G erzeugteSpracheL(G) als Teiknengevon I* an! b) GebenSie einen geeigneten,möglichst einfachenAutomatenan, der dieseSpracheL (G) akzeptiert! Sie die zu L (G,) gehöc) G, sei die TeilgrammatikausG mit dem StartsymbolT. Bescbreiben rendenWörter durch einenregulärenAusdruck! - d) Andern Sie die Sprache,so dassWörter die bezüglichzweier verschiedenerKlammern a) und b> korrekt geschachteltsind, akzeptiertwerden! GebenSie eine kontextfreie GrammatikG, an! e) Erweitern Sie den Automatenausb), so dassdie Schachtelungmit allgemeinenKlammern w> endlicherLänge k d.h. lwl o a) GebenSie einenfunktionalen,rekursiven Algorithmus an, der die Formel (F) direlt umseta! b) BestimmenSiedie KomplexitätdiesesAlgorithmusgemessen an derZahl der Additionenzur Berechnungvon f"! c) GebenSie einenfunktionalenAlgorithmus an, der mit n Additionen F berechnet! d) Implementieren SiediesenAlgorithmusin Java! e) ImplementierenSie einen imperativenAlgorithmus in Java, der { mit n - l Additionen berechnet! Aufgabe3 Datenstrukturen a) ErzeugenSie ausder gegebenenFolge einen 2-34 Baurn: 2 2 ;l 0 ; 1 9 ;l ; 1 3 ;1 2 ; 7 ; 8 ;5 ; 4 2 ; 3 3 ; 2 1 FügenSie dazudie einzelnenElementein gegebenerReihenfolgein einen anfaagsleeren 2-3-4 Bavn ein! Stellen Sie für jeden Wert die entsprechenden Zwischenergebnisse und die angewendetenOperationenals Bäumedar! b) In dem Ergebnisbaumsuchenwir nun den Wert 17. StellenSie den Ablauf des Suchalgorithmus an einer eigenenZeichnunggrafisch darl c) LöschenSie nun, unter AnwendungdesAlgorithmus ,,Löschenmit Vorschau" die Elementemit denWerten5,22, lO in der gegebenen Reihenfolge.StellenSie fär jedenWert die entsprechenden Zwischenergebnisse und die angewendeten Operationenals Bäumedar. Aufeabe 4 Algorithmen In einemSackbahnhofmit drei Gleisenbefindensich ia den GleisenSl und 52 zwei Zügejeweils mit Waggons1ü1llgllahnhof A und B. Gleis53 ist leer. StellenSie die Züge zusammen" die nur Waggonsfür einenZielbehnhofenthalten!BetrachtenSieSl, 52 und 53 als Stapelund errwerfen Sie einenAlgorithmus, der die Züge so umordnet,dassanschließendalle Waggonsfür A in Sl und alle Waggonsfür B in 52 stehen! FortsetzungnäcbsteSeite! Herbst2002 Aufeabe5 : 66IL2 Einzelprüfungsnummer Seite:7 ObjektorientierterEntwurf Analysefür eineBibliothekerstellenlIn dem SysSie sollenin dieserAufgabeeineobjektorientierte Ausleiher,der Bibliothekarund Bücher(edes Buch ist genaueinmal,d.h. tem sollenmindestens nicht mehrfachvorhanden)repräsentieftsein. DesweiterenexistierenfolgendeGeschäftsprozesse: 1. Buchausleihen:ein Ausleiher,dessenNameund Anschriftdem Systembekanntsird, leiht ein Buchaus. Ein Ausleihergibt ein geliehenes Buchzurück. Hier wird auchgleichbei 2. Buchzurückgeben: (dieses überzogenerFrist Buches)die Zah\ng für die Mahnungeingeforden. 3. Mahnungenverschicken:Der Bibliothekar überprüft bei allen entliehenenBücherndie Ausleihfrist. Fallsdieseabgelaufenist, verschickter an denAusleihertäglicheineMahnung. Ein Buch soll folgendeAttributebesitzen:1) Autoren,2) Titel, 3) Jahr,4) ISBN, 5) Genreund 6) Möglicbkeitenseinund esexistieren Schlagwörter.Genrekanndabeieinevon fünf verschiedenen mindestens50 verschiedeneSchlagwörter,die allerdings vom Benutzererweitert werdenkönnen. Als ChefentwicklermüssenSie folgendeAufgabenerledigen: für diesesSzenario! a) ZeichnenSie ein Analyse-Klassendiagramm an! Sequenzdiagramme b) FertigenSie für alle Geschäftsprozesse