hüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort:

1999

66112

Arbeitsplatz-Nr.:

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

Informatik (vertieft studiert)

Efuzelprüfung:

Automatentheorie,Komplexität,Algorith.

Anzahl der gestelltenThemen(Aufgaben):

2

Anzahlder DruckseitendieserVorlage:

4

Bitte wenden!

Herbst 1999

Einzelprüfungsnumme
r : 66LL2

Seite:2

Thema Nr. L

SämtlicheTeilaufgabensind zu bearbeiten!

1. Gegebenseiend.iespracheL = 1 a2n63n I n > 0) über r = ia, bi,
die GrammatikenGi (i = 7,2) mit StartvariablenS1und Produktionenmengen
P r = P ou { A - > a a ,B - > b b b } ,
Pz= Po u {sz + LSiR, LA -+ aa,aA + aaa,aB + abbb,bB -+ bbbb,bR + b} ,
wobeiPo= {Sr + ABS1,51-+ AB, BA -+ AB}
a. BeweisenSie:
al) L E L(Gr),
a2)L g L(Gr).
b.

GebenSie ein Wort in L(G1) an, dasnicht Eiementvon L(G/ ist.

c.

Ist L reguiär?(Begnindungl)

d. Ist L kontextfrei?(Begründungl)
e.
2.

Ist L kontextsensitiv?(Begnindung!)

ZeigenSie:
Ist die Funktion f : N2-+ N ( N Menge der nanirüchen Zahleneinschließiich0)
LooP-berechenbar(primitiv rekursiv),so ist auchdie Funktion g: N2-+ N mit
v

sQ,il = fl /{r, i)
j = 0

LO OP-berechenbar ( primitiv-rekursiv).
3. Welche der folgenden Eigenschaftensind für (determinisrische)TuringmaschinenM
entscheidbar?
(Begründung!)
a. M terminierrbei Eingabe1999.
b. M berechneteine LooP-berechenbareFunktion.
c.

Zu det von M berechnetenFunktion 7 : N2-+ N gibt es ein
/ berechnendes
WHILE-Programm mit höchstens zwei (ineinander geschachteiten)WHILESchieifen.

4. Erklären und vergleichen Sie zwei Ihnen bekannteParameter-Übergabe-Mechanismen
bei Prozeduraufrufen.

- 3Herbst L999

Einzelprüfungsnufilmer
: 66tI2

Seite:3

Thema Nr. 2

Sämtliche Teilaufgaben sind zu bearbeiten!
Aufeabe 1:
a) GebenSie einenDatentypfür einfachverketteteListen von ganzenZahlenan.Als programmiersprachekönnenSiedafürPascal,Modula,oderC wtihlen.VerwendenSiezur DefinitiondesDatentypsdasPointerkonzept
dervon IhnengewähltenSprache.
b) SchreibenSie eineProzedurodereineFunktioninsert, dle eineganzeZahl i in eineaufsteigendgeordnete
Liste 1 an die korrekteStelleeinordnel;
z . B .l i e f e ritn s e r t v o n3 i n < I , 2 , 2 , 7 ,8 > d i eL i s t e< I , 2 , 2 , 3 , 7 , g > .
c) SchreibenSie eineProzeduroderFunktion1öschen, die in einerListe 1 eineganzeZahl i an
der Stelle löscht, an deri in J,zuerstvorkormt.

Aufeabe 2:
a) ErklärenSie die Begriffe yonZeit- und Speicherplatz-Komplexität.
b) Ein bekanntesSpielträgt den Namen"Tärme von Hanoi". Das Spielwird mit n ScheibenverscliedenerGrößegespielt,die aufdie stäbeA, B, c gestecktwerdenkönnen.Zu Beginnstecken
alle Scheibenauf StabA und zwar derart,dassis,,rr'.iis
eile kleinereScheibeauf
einergrößerenScheibeiiegt. Die Aufgabebestehtdarin,die Scheibenvon StabA nachStabB
umzustecken,
wobeifolgendezwei Regelnzu beachtensind:
(1) In jedemSchrittdarf nur genaueineScheibebewegtwerden,
(2) einegrößereScheibedarf nie auf einerkleinerenScheibeliegen.
Der Algorithmus,der die Zugfolgebeschreibt,ist wie foigt:
hanoi(int n, var Stabquelle,var Stabziel, var Stabvia);
if n= l then
/*bewegeScheibevon QuellenachZielxl;
elsebegin
hanoi(n-l, quelle,via,ziel);
/*bewegeScheibevon QuellenachZiel*/;
hanoi(n-l, via,ziel,quelle);
end;
endhanoi
BeweisenSie,dassdie Zeitkomplexitätvon hanoi exponentiellist. Siekönnenannehrnen,
dass
das'Bewegen
von Scheibenimmer 1 Zeiteinheitbraucht.
Hinweis:GebenSie eineuntereund eineobereSchrankefür die Zeitkomplexitätvon hanoi an
und verwendenSie vollständigeInduktionzum Beweisder Schranken.

FortsetzungnächsteSeite!

Herbst 1999

Einzelprüfungsnumme
r : 66tLz

Seite:4

Aufeabe 3:
a) Sei {1"},'.nneineFamilievon Sprachen,definiertdurch
ln= {w e {0, 1}* llwl >n > 1 und das n_Ietzte
Zeichenvon w ist l}.
Dabeibezeichnetlwl die LZingedesWortesw.
a1) GebenSie die allgemeineForm einesnichtdeterministischen
endlichenAutomaten
für ln an.
a2) GebenSie einen deterministischenendlichenAutomatenfür
l, an.
a3)
Geben Sie denregulärenAusdruck13für 13an (d.h.L(r) = lr).
b) Gegebensei die Sprache| = {w e ia,b}* | lwl6= 2l\\,lol,d.h. w ist ein Wort von
L, wenn die
Anzahl derb's in w gleichzweimaldie Aazahl der a's in w ist.
bl)
Gebensie einekontextfreieGrammatikf an,die die SpracheL erzeugt,d.h.L = L(l). (Hinweis:DieRegelS -+ e, wobeiS dasStartsymbolbezeiJhnet,
ist zugelassen.)
BegründenSie,
warum Ihre Grammatikdie SpracheL erzeugt.
b2)
WandelnSie dieseGrammatikin eineBackus-Naur-Form
um. (Dabeiist sowohldie BNFwie EBNF- Schreibweise
zu1ässig.)
b3)
GebenSie die AbleitungdesWortesw = babbaban.
.A,ufeabe4:
a) ErläuternSie die auf Flbyd und Hoarezurückgehen<ie
Verifikationsmethode.
(In Ihrer Antwort
müssenSie mindestens
die Begriffe von Zusicherung,schwächste
Vorbedingungund prädikattransformationerklZiren.)
b) BetrachtenSie folgendesProgrammfragment
pmit derVorbedingungV = (x = a&y =b) und
derNachbedingung
N = (z = a.b), wobeia, b ganzeZahlensind.
z;= 0i
whilex<>0do
beginz := z+ y; x := x - 1 end;

bl)
bz)
b3)

Zeigen Sie,dassdie Formel I = (x.y+z = a.b) eine Schieifeninvariante
ist.
Beweisensie die partielle Korrektheit von p bezüglichder VorbedingungV und
der NachbedingungN.
Was fehlt noch frir eine voilständigeVerifikation? TerminierrdiesesProgramm immer?
Begründen Sie Ihre Antwort.