Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort:

2000

66112

Arbeitsplatz-Nr.:

Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen
- PrüfungsaufgabenFach:

Informatik (vertieft studiert)

Eirzelprüfung:

automatentheorierKomplexität,Algorith.

Anzahl der gestelltenThemen(Aufgaben): z
Anzahlder DruckseitendieserVorlage:

5

Bitte wenden!

Herbst2000

Eirzelprüfungsnurlmer
: 66112

Seite:2

Thema Nr. I

Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe L:

(Lexikalischer Vergleich)

Listen von Listen ganzerZahlen kann man lexikalischordnen.Eine Liste [x,, ..., x*] heißt lexikalisch kleiner als eine Liste [y,, ..., yn], falls es ein i mit 0 < i ( min(m, n) so gibt, dassgilt:
Xk : yn für alle k : 1, ..., i und
entwederi: m ( noderx,*, ( yi*,.
Wlihlen Sie für die folgenden Teilaufgabena) - d) eine beliebige(edoch für alle Teilaufgabendieselbe)Programmiersprache.
a) Geben Sie einen Datenfyp für Listen von ganzenZahlen und einen Datentyp für Listen von Listen von ganzenZahlen an.
b) ProgrammierenSie den lexikalischenVergleich lex auf Listen von garTzen
Zahlen als eine
Funlüion oder Prozedur.
c) SchreibenSie eine Prozedur oder eine Funktion lex_insert,
die eine Liste I von ganzen
Zahlenin eine lexikalisch geordneteListe 1l- von Listen von ganzenZahlen an die korrekte
Stelle einsortiert.
Z. B. liefert die Anwendungvon lex_insert
auf die Argumente[1, 3] und IU,2],, fL,,7f,
[a]l die Liste [IL,2], [1, 3], [1,7f, [a]l als Ergebnis
d) SchreibenSie eine Prozeduroder Funktion insert_sort,
die eine Liste von Listen von Zahlen 11 lexikalischsortiert. Die Prozeduroder die Funlrion soll lex insert verwenden.

Aufgabe2:

(Berechenbarkeit)

SeienA, B c Norekursivaufzählbar.BeweisenSiedie folgendenBehauptungen:
a) A u B ist rekursivaufzählbar.
b) A x B ist relrursivaufzählbar.

FortsetzunsnächsteSeite!

Herbst2000

Aufgabe 3:

Eirzelprüfungsnumme
r : 66L12

Seite:3

(Sprachenund Automaten)

a) Zeigen Sie, dassdie Sprache
1 : {a'b": (m ist durch 3 teilbar und n ist ungerade)oder (m ist geradeund n : 0)}
regulär ist. GebenSie den regulärenAusdruck an.
b) Konstruierensie einen endlichennichtdeterministischen
Automateq der L erkennt.
c) KonstruierenSie einenendlichendeterministischenAutornaten,der L erkennt.
d) Sei L, : {a"b": m, n ) 0 und m/n : 213}.IstL, vom Typ Chomsky-2,ist L, zugleichvom Typ
Chomsky-3?BeweisenSie Ihre Behauptung.

Aufgabe 4:
''

(Programmierung)

a) Erläurern Sie die auf Floyd und Hoare zurückgehende
Verifikationsmethode.(In Ihrer Antwort
müssenSie mindestensdie Begriffe von Zusicherung,schwächsteVor- und stärksteNachbedingung erklären.)
b) Betrachtensie folgendesProgrammfragmentmir der vorbedingungv = (s : 0 & i : 0) und der
Nachbedingung
N: (s : (n+ 1)*n/2),wobeii, n und s ganzeZahlensind.
whilei (:ndo
begin
s:=s*i:
i::i+l
ead.
bl) ZeigenSie, dassi < n*1 & s : (i-L)*i/2 eineSchleifeninvadante
ist, und beweiseoSie, dass
dieseerhaltenbleibt.
b2) BeweisenSiedie Nachbedingung.
b3) Terminiert dasPrograrrmimmer?BeweisenSie Ihre Antwort.

-4Herbst2000

Einzelprüfungsnummer
: 66112

Seite:4.

Thema Nr. 2

Sämtliche Teilaufgaben sind zu bearbeiten!

l. GebenSie Zustandsdiagramme
flir deterministischeendlicheAutomatenfür die folgendenSprachenan.
a) Die Mengeder Wörter w e {a, b\*, derenLängelwl entwederdurch2 oder 3 ohneRestteilbar ist.
b) SeiZ die Spracheder Aufgabe1.a);d. h.
t : {w e {a, bl*: lwl entwederteilbardurch2 oder3}
Sei i = {a, b\* - L dasKomplementvon Z. GebenSie einenregulärenAusdruck flir die
SprachenZ und tr an.

2. BeweisenSie, dassdie SprachelahUn : m e N) kontextfrei, abernicht regulär ist.
3. SkizzierenSie in Pseudocodedie Implementierungeiner Operation,die auseiner verkettetenListe die Elementeentfernt, die mehrfachvorkommen.GebenSie die notwendigenDatenstrukh:ren
an, wobei die verketteteListe mit Zeigem (Pointers)implementiertwerdensoll.
4. ln dieserAufgabewerdenin Pseudocode
die Datenstrukturund Implementierungvon bestimmten
Operationenfür binäre Bäumegegeben.
.
a) Definieren Sie in Pseudocodedie Datenstrukturfür die Implementierungvon binärenBäumen
(arree), wobeiBlätterdadurchdargestelltwerden,dassleft und righr denWert nul-r häben.
b) ImplementierenSie eine Methode
voj-d printlnorder

{)

für BTree, die den Baum in Infixdarstellungausgibt.
c) GebenSie den Codean, der die Variable r mit DatentypBrree mit einemBaumbelegt, dessenInfixdarstelluns2+3*4ist.

FortsetzungnächsteSeite!

Herbst2000

Einzelprüfungsnumm
er: 66LL2

Seite:5

5. GebenSie eine kontextfreieGramrntik (oder BNF) an für die Mengeder palindrome gerader
Länge über {a, b, c) wobei die Mitte durch . markiert ist, alsoz. e. ab. ba. SkizzierenSie die
Implernentierungeinesrecursivedescentparsersin pseudocode6. DieseAufgabebeziehtsich auf dasSortierungsverfahren
quicksorr.
a) GebenSie Pseudocode
flir quicksorr an.
b) SimulierenSie die Schrittevon quicksorr auf der Eingabe4, 2, l, 3, g, 5, 0, 6, 7.
c) Was ist dasworst-case-V
erhaltenvon quicksorr?
d) Für welche Eingabenzeigt quicksort dasworst-case-yerhalten?
e) Was ist dasaverage-case-Verhalten
von quicksort?