Prüfungsüeilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 2004 66TL2 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichenSchulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzahl der gestelltenThemen (Aufgaben): 2 Aruahl der Druckseitendieser Vorlage: 7 Bitte wenden! Herbst2004 Einzelprüfungsnummer: 66112 Seite:2 Thema Nr. 1 SämflicheTeilaufgabensindzu bearbeiten! Hinweis: VerwendenSie zur Formulierungvon Algorithmenbzw.Datentypeneine gängigehöhere Programmiersprrtche oder einen entsprechenden Pseudocode.Erläutern Sie alle anzugebenden Algorithmen,Automatenund Turing-Maschinen ausgiebigdurchKommentare. TeilaufgabeI JedeKarte in einemKartenspielhaI eineFarbe Kreuz, Pik, Herz oderKaro und einenl(ert. Mögliche Werte sind die Zahlenwerte2 bis 10, die Bildwerte Bube, Dame, König sowie iler Wert As. EineKartenverteilungbestehtaus 12Karten. ' GebenSie einengeeignetenDatent)? zur Darstellungvon Kartenverteilungensowie Algorithmen an, die für einederartigeDarstellungFolgendes leisten: a) Für eineKartenverteilung v undeineKarteI soll festgestellt werden,ob /r in v enthaltenist. b) Für eineKartenverteilung v soll die Anzahlder in u enthaltenen Kartenk mit folgenderEigenschaftbestimmtwerden:ft hat einenBildwert,und v enthältkein As von sleicherFarbe. Teilaufgabe2 Gegeben seidie Funktionsvereinbarun! (in Pseudocode-Notation) function f(x,y: integer/integer : if x < -y then x - y elsef(x + 2, y - 3) endif - a) BestimmenSiedenWert von/(5,8). b) BeweisenSie:/terminiertfür alle integer-Zahlen x, y. c) GebenSie eineniterativenAlgorithmusan,derf(x, y/ für beliebigeinteger-Zahlen.r, y berechnet. Teilaufgabe3 Gegeben seidasAlphabetf : {o,b}unddieGrammatik C - ({S,A,B},)],p,S) mit derMenge P der Regeln FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 661Iz Seite:3 S'- aB B-+bl0A A---aB f(G) sei die von G erze:ugleSprache. a) Geben Sie eine Ableitung von ababab in G an. ' " s-1 * r b) Beweisen Sie:f(G): .{f, t I lnZtl. r.,b)." c) KonstruierenSiedirekt ausG zunächsteinennichtdeterministischen endlichenAutomaten,der die Sprachef(G) akzepiert,unddarauseinendeterministischen endlichenAutomaten,derebenfalls t(G) akzeptiert. d) WievieleZuständemussjederdeterministische endlicheAutomat,derf (G) akzeptiert,mindestenshaben?BegründenSieIhreAntwort. e) ErsetzenSiedie Regel A ---'aB in G durcheinekontextfreieRegelderForm A --+r mit z e {S,A,B,a,ö}+,so dassdiederartveränderte Grammatik die Sprache {( ( o b' \ " - ' e- \z't- - t | , > o-) } erzeugt.BegründenSie Ihre Antwort. f) Die Sprachentr und .L" seiengegeben durch Lt : (ob)"€ f {t*u)" * (bo,)', €f l r,> 1},L2: {{ut,)" * l rr> 1} i) Ist L, regulär? ii) Ist I, kontextfrei? iii) Ist L, regulär? iv) Ist L, kontextfrei? BegründenSie Ihre Antworten. Fortsetzung nächsteSeite! Herbst2004 Einzelprüfungsnurlmer . 66tI2 Seite:4 Teilaufgabe4 a) DefinierenSiein Pseudocode odereinerhöherenProgrammiersprache einegeeignete Datenstruktur zur Repräsentation von AVL-Bäumen. SchreibenSiesodanneineFunktion,die überprüft,ob ein beiiebigesElementdieserDatenstruktur tatsächlichein AVL-Baum ist. Zu Ihrer Information:SolcheineFunktionkannzu Testzwecken sinnvoilsein,spieltaberbei derregulärenVerwendungvon AVL-BäumenkeineRolle. BeachtenSie,dassein AVL-Bauminsbesondere auchein binärerSuchbaumist. b) SchreibenSieeineFunktion,die eineLinksrotationder WurzeleinesAVL Baumesdurchführt. Beschreiben Siedetailliert,welcheFormderBalancierungsstörung durchdieseRotationbehoben werdenkannund in welchenSituationen (Einfügen,Löschen)eszu ihr kommenkann.GebenSie dieLatfzeit ihrerImplementieruns mit Hilfe der O-Notationan. -5 Herbst2004 Einzelprüfungsnummer: 66112 Seite:5 ThemaNr. 2 SämtlicheTeilaufgabensindzu bearbeiten! l. Teilaufgabe(Automatentheorie) Es seiE die Mengealler WörterüberdemAlphabet{0, 1}, die mit 01 enden. a) GebenSieeinenregulärenAusdruckan,derE beschreibt. b) GebenSieeinendeterministischen endlichenAutomatenan,derE akzepliert. c) Beschreiben die natürlichen Sie Zahlen,derenBinärdarstellung in / liegt, auf andereWeise. 2. Teilaufgabe(FormaleSprachen) ' Geben Sieeinekontextlreie Grammalik an.diedieSprache A: rlcftiuuuRw.RuR , u,u.wc {a.bl'} eueug!.Dabeiist (arar.. . u,)n : 0., an... a2atfüt allea' ar,...,a, € {a,b) . 3. Teilaufgabe(Berechenbarkeit) Man gebeeineTuringmaschine mit einemBandan,die die Funktion/ : {0,1}- -- {0,1}definiertdurch: /f (\ w, \ - c. l e^r [1, falls die Anza]rl der Einsen in u clurch 3 teilbar ist l [0 sorrst berechnet. 4. Teilaufgabe (Komplexität) GebenSie einennichtdeterministischen Algorithmus an, der dasPartitionsproblem P A R T I T I O N : 0 " , , . . . , & , n ^) , a 1 , . . . , a€, , N , A : l ( l q { 1 ., . . , m l l I {{", z € r ü t -D , f , . r ) } in Polynomialzeitlöst. AnalysierenSie dreLaufzeitIhresAlgorithmus. FortsetzungnächsteSeite! Herbst2004 Einzelprüfungsnummer : 66112 Seite:6 5. Teilaufgabe(objektorientierter Entwurf) Ein VolkslaufbesitzteinenNamen,die Längeder Strecke,der Ort und dasDatumsindweiterewichtige Eigenschaften. Ein Volkslaufwird von MitgliedemeinerLaufsportgruppe veranstaltet. Läufer, die andemLauf teilnehmenwollen,müssenzur AnmeldungIluen Namen,die Lauflsportgruppe, der sieangehören und ihre Altersklasse mitteilen.Es soll deutlichzwischenderRolle alsLaufizeranstalter und alsMitläuferunterschieden werden. a) ModellierenSiedenSachverhalt durchein l-ML Klassendiagramm. Dabeisoll zum Ausdruck kommen,dassaneinemVolkslaufmindestens 50 Läuferteilnehmenund ein Läuferdurchausan mehrerenVolksläufenteilnehmenkann. b) GebenSieein Objektdiagramm {ür folgendeSituation - Sammynimmt teil an Residenzlauf. Sammynimmt teil anNikolauslauf. Hansveranstaltet Nikolauslauf. Paulnimmt teil an Residenzlauf. Haile nimmt teil anResidenzlauf. c) Implementieren Siedie KlasseLäuferin Java.Dabeisoll ein LäufereinenNamen,eineLaufsportgruppeund seinGeburtsjahr alsAttributebesitzen.EineMethodebestimmtdie Altersklasse. Altersklassen sindnur vom Geburtsjahr abhängig. - unterl8 Jahre: Jugend - 19bis 29 Jahre: Haupt - zwischen i undi + 4Jahren:Mi i:30,35,... d) SehenSienun vor, dassderLäuferauchseineVolkslauf-Teilnahmen einsehenkann.LesenSie eineentsprechende Datenstruktur an. SchreibenSieeineMethode printlaeufe (inc jahr), die die NamenallerLäufe,bei denener im Jahrj ahr mitgelaufenist, ausgibt. 6. Teilaufgabe(Systemmodellierung) Ein Kaffeeautomat wird durch3 Knöpfebedient.Diesekönnennur gedrücktwerden,lalls keineLampeblinkt. NachdemEinschalten mit Knopf 1 wird dasWasseraufgehei zt, Lampe1 blinkt. Ist dieserVorgang beendet,so leuchtetLampeI und durchDruck aufKnopf2 kanndasMahlenund Ausgießen desKaffeeserreichtwerden.WährenddiesesVorgangesblinkt Lampe2. DurchDruck auf Knopf 3 wird Dampfbereitet,Lampe3 blinkt. Ist dieseAufbereitungfertig (Lampe3 leuchtetnun),sokarurdurch Knopf 2 Dampfabgelassen werden.WährenddiesesVorgangesblinkt Lampe2. Durchemeuten DruckaufKnopf3 kannzur Kaffee-Ausgabe zurückgeschaltet werden,wiederblinkt Lampe3. Knopf jedem 1 schaltetin ModusdenAutomataus. ModellierenSiediesenSachverhalt durcheinenZustandsautomaten. Fortsetzung nächsteSeite! Herbst2004 Einzelprüfungsnummer: 66112 Seite:7 7. Teilaufgabe(AlgorithmenundDatenstrukturen) Ein gerichteterDistanzgraph sei durchseineAdjazenzmatrixgegeben. (ln einerZeile stehendie Llingendervon demZeilenkopfausgehenden Wege.) M M A D R N " A P R N 5 1 0 3 9 2 1 l 7 - 4 - - 6 - a) Stellen Sie den Graph in der üblichen Form dar. b) Bestimmen Sie mit dem Algorithmus von Dijkstra ausgehendvon M kürzesteWege zo allen anderenKnolen. c) BeschreibenSie wie ein Heap als Prioritätswarteschlange in diesemAlgorithmus verwendetwerden kann. d) GebenSie die Operation: ,,entfemendes Minimums" für einen Heap an. Dazu gehört selbstverständlichdie RestrukturierungdesHeaps.