Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Herbst
Kennwort:

2003

66LT2

Arbeitsplatz-Nr.:

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

Informatik (vertieft studiert)

Einzelprüfung:

Automatentheorie, Komplexität, Algorith.

Anzahl der gestelltenThemen (Aufgaben):

2

Anzahl der Druckseitendieser Vorlage:

6

Bitte wenden!

Herbst20A3

Einzelprüfungsnummer
: 66LLz

Seite:2

Thema i\r. L

SämtlicheTeilaufgaben
sindzu bearbeiten!

Für dasAlphabet E : {o,t} und n,ru e No sei L(n,m) s I * wie folgt definiert:
L(n,m) =
. Er l* enthält genaun Zeichen0 und m Zeichenl} .
{*
1. GebenSie alle Elementevon L(3,2) anl

2. BeweisenSie:Für alle n,me No mit n>0 und m > 0 gilt:

L(n,m): {O*l* e L(n -1,*)\u {lw lw e L(n,* -t)\ .

3. In dieserTeilaufgabesoll ein Algorithmusentwickeltwerden,der zu gegebenenn,rz e Nodie
MengeL(n,m) bestimmt.VerwendenSiedazueinegängigehöhereProgrammiersprache
odereinen entsprechenden
Pseudocode.NehmenSie dabeian, dassdie gewlihlte Sprachedie Datentypen
char (für Zeichen),nat (für No) sowiefür jedenDatentypd einenDatentypsequd derListen
(Sequenzen)
von Elementenvom Typ d zur Verfügungstellt.Für Listenseiendie Konstanteempty
(leereListe) und folgendeFunktionenverfügbar:
isempty(x)
frrtt(*)
rest(x)
prefix (a, x)

(Test,ob die Liste-r leerist),
(erstesElementder Liste.x),
(Liste x ohneihr erstesElement),
(AnfügendesElementsa alsneueserstesElementan die Listex).

Zeichenketten
seienals Listenvon ZeichenundMengenvon Zeichenketten
als Listenvon Zeichenkettenrepräsentiert.@abei sollendie ElementeeinerMenge in der Liste nicht mehrfach
vorkommen.)
a) GebenSie einenAlgorithmus an, der fi.ir ein Zeichenz und n e N^ die Zeichenkettez*
(d,.i. 22...z mit k Zeichenz) alsErgebnishat!
b) GebenSie einenAlgorithmus an, der für zwei Mengenvon Zeichenkettendie Vereinigung
dieserMengenals Ergebnishat!
c) GebenSie einenAlgorithmus an, der frir eineMengeM von Zeichenkettenund etn Zeichenz
die Menge{zwlwe U\ alsErgebnis
hat!
d) GebenSie (unter Verwendungvon Teilaufgabe2 und der Algorithmen unter a), b) und c)) einenAlgorithmusan,der flir beliebigen, z e No dieMengeL(n, n ) als Ergebnishat!
GebenSie ausftihrlicheErläuterungenzu Ihren kisungen an!
Fortsetzunsneichste
Seite!

Herbst2003

Einzelprüfungsnummer
: 66112

Seite:3

4. Gegebensei die GrammatikG = (V,>, P, S) ^i1 V = \S ,4 n) und derMengeP derProduktionen

s-+o loalrslre
e-+llle
B-+lsllB

L(G) seidie von G erzeugteSprache.
a) BeweisenoderwiderlegenSie: ll0ll

- L(G).

b) BeweisenoderwiderlegenSie: 11010e Z(G/.
c) KonstruierenSie direkt aus G zunächsteinennichldeterministischenendlichenAutomaten,der
die SpracheZ(G/ akzeptiert,und darauseinendeterministischenendlichenAutomaten,der ebenfallsL (G) akzeptiertl
d) Beweisen
Sie:Z(O =u^Z(l,n).

5. BeweisenSie:Fürjedes z e No ist die SpracheL^= U L(n,m) regali.x(vom Typ 3).
T€NU

6. BeweisenSie,dassflir beliebigen,tn,e No mit n < m gilt:
a) Zu jedemw=0w'e L(n,m) gibtes teNo,veZ(fr,#) und v'e X. mit w=0v1v'.
b) Zujedemw=0w'eL(n,n) gibtesft,jeNo,veZ(ft,*)und v'e L(j,j) mit w--0vlv'.
7. Die SpracheL sei definiertals Z - U L@,,n).
'-r

a) Beweisen Sie: Z ist nicht r"r*;;.
b) GebenSie eine kontextfreie (d.h. Tp,-2-)Grammatik an, dieL erzeugt.
8. GebenSie eine deterministischeTuringmaschineT an mit folgendenEigenschaften:
a) f berechnetdie Funktion
,f 'NoxX -+{0,1},

weL(n't)
f (n,w):{l ?i:
fallswEL(n,l)
[0,

in folgendemSinne:
#) hält I nachendlicherZeit
Angesetztauf dasWort 1' #w (mit n e No,w e X- und Trennzeichen
in einerKonfigurationan,in der f (n,w) alsErgebnisauf demArbeitsfeldsteht.
GebenSie ausführlicheErläuterungenzur WirkungsweiseIhrer Lösungl
b) Die Anzahl der Rechenschrittevon 7 für eineEingabeder unter a) genanntenArt ist 0(2').
BegründenSiedieseAussagefür Ihre Lösung!
-4Herbst2003

Einzelprüfungsnummer
: 66112

Seite:4

Thema Nr. 2

SämtlicheTeilaufgabensind zu bearbeiten!
Automatentheorie,formale Sprachen,Berechenbarkeit
1. Seiendieregulären
Ausdrücke
a=(^b' )*abundB:ab(bab)*

gegeben.

a) ZeigenSiedie AquivalenzderbeidenregulärenAusdrücke,also L(a) = L(P) .
b) GebenSie eine L(a) erzeugende
Grammatikan.
c) GebenSie einendeterministischenerkennendenAutomatenan, der L(p) akzeptiert.

2. SeiL die Sprachealler Wörterüber {a,b} die,,aba"alsTeilwort enthalten.KonstruierenSieeinen
deterministischenerkennendenAutomatenfür L!

3. KonstruierenSieeineTuring-Maschine,
die die Präfixrelationpräfix aü 2x p1 > = {0,1}enr
scheidet,d. h. die charakteristischeFunktion charo/d/ri
berechnet(x präfx y : e x ist Anfangsstück
von y).
4. ZeigenSiedie Konektheitder (aussagenlogischen)
Regel
---+
B kannman auf B -A schließen"!
,,AusA+
5. a) ZeigenSiemit Hilfe vollst2indiger
Induktion,dassdasfolgendeProgrammbzgl. derVorbe>
dingung x 0 und der Nachbedingung(drei_hochx) = 3. partiell konekt ist!
(define
( ilrei-hoch
x)
(conal ((= x 0) 1)
(e1se (" 3 (drei-hoch
) )

(- x 1).)))

Funktion(drei_hochx) unterderVorbedingungx e No termib) ZeigenSie,dassdie gegebene
niert, indem Sie eine geeigneteTerminierungsfi:nktionangebenund begründenSie,warum die
von Ihnen angegebene
Funktion dasGewünschteleistetl

FortsetzungnächsteSeite!

Herbst2003

Einzelprüfungsnummer
: 66112

Seite:5

6. Gegebensind die drei folgendenProzedurenzur Multiplikation zweier natürlicher Zahlen.
(mu1t n m)
(define
(cond ( (= n 0) 0)
(else + n (mu1t (- n 1) m) ) )
)
)
(define
(mu1t2 n m)
(cond ( (= n 0) 0)
((even? n) (* 2 (mu1t2 (/ n 2) n)))
(else (+ m (mu1t2 (- n L) m) ) )
) )
( def ine (mu 1 t3 n m )
(m u l t-i te r
( def ine
c o u n te r m sum)
(cond ((= counter 0) sum)
(e1se (mult-iter
(- counter
)
)
(mult-iter
n m 0)
)

1-) m (+ m sum) ) )

GebenSie für jede dieserProzedurenan, welchen Speicherbedarfund welchen Zeitbedarfdie jeweils erzeugtenProzessehaben! Formulieren Sie die Ergebnissein der O(f(n))-Notation!

7 . SchreibenSie in einer funktionalen Programmiersprachefolgende Prozeduren:
a) Die Prozedwmod( x, y ) berecluretclenRestbei clerDivision nattirlicher Zahlen Falls die
Division aufgeht,wird der Divisor ausgegebel.
Die Parametergenügender Vorbedingungx > 0 und y > 0.
mod :

( zah1,

Beispiel:

zahl ) ->

za}:l.

mod(34,7) = 6 wegen34:7 = 4 Rest6
mod(12,4) = 4wegen12 : 4= 3 Rest0

b) Die ProzedurLen berechnetdie Anzahl der Elementein einerListe.
len

:

(liste)

->

zahl

Beispiel: len(I2;1; 1; 1; 4l ) = 5
c) In einerListe werdenKettenbrächeimplementiert.Sie habenfolgendeEigenschaften:
. Sie sind periodisch.Die Periodebeginntstetsbeim zweitenEintrag der Liste und reichtbis
zu derenEnde: [Z;7ffi1=2;] ;5:4;I :5;4;l ;5;4;l ;...
. Falls n < lenfliste)ist die n. StelledesKettenbruchsdasn. Elementin der Liste.
Beispiel:3. Stelle(L2;1,;5; 4l) = 5
. Falls n > len(liste)wird die Zählungder Stellenstetsam Beginn der Periodefortgesetzt.
Beispiel:5. Stelle(12;l; 5; 4J)= 1;
7. Stelle(12:;l;5;41) = 4;
8. Stelle(12;t; 5; 4l) = 1;
usw.
Die Prozedurn*te-stel1e
n*te-Fte11e

Beispiel:

( 1iste,

die n. StelledesKettenbruchs.
berechnet
zahl ) ->

za|r]-

n-te-stelLe(I2;1; 5; 41, 3) = 5

FortsetzungnächsteSeite!

Herbst2A03

Einzelprüfungsnunrmer
: 66I Lz

Seite:6

d) Der Wert einesKettenbruchslässtsich näherungsweise
dwch die Einbeziehungseinerersten
Stellen berechnen.Sein Wert wird urnsogenauer,je mehr Stellen für die Berechnung
verwendetwerden.
Sei s(n) die n. Stelle des Kettenbruchsund k(n) der NäherungswertdesKettenbruchsunter
Einbeziehungder erstenn StellendesKettenbruchs,dann gilt folgenderekursiveDefinition:

A(n)={

0
|
s(n)* A(n-l)+ A(n-2)

falls n = -l
f a l l sn : 0
fallsn )l

B(n): {

I
0
s(n)* B(n-l)+ B(n-2)

falls n = -l
falls n = 0
fallsn )l

k(n) = A(n/B(n)

SchreibenSie eineProzedur,die denNäherungswertk(n) nachobigat Formelnberechnet!
8. a) ImplementierenSie in einerobjektorientiertenSpracheeinenbinliren Suchbaumfir ganzeZahlen! Dazu gehörenMethodenzum Setzenund Ausgebender Attribute zahl, linker teilbaumund
rechter_teilbaum.
b) SchreibenSiedie Methodefuege_ein
c) SchreibenSiedie Methodepost_order
gibt!

1. . . 1, die eineZahl in denBaumeinfügt!
( ) , die die Zahlenin derReihenfolgepostorderausd) ErgänzenSie Ihr Programmum die rekursiv implementierteMethodesumme ( . . . ) , die die
Summeder ZahlendesUnterbaums,dessenWurzel der Knotenx ist, zwückgibt! Falls der Unterbaumleerist, ist derRückgabewert
0!
i n t s u m r n e( K n o t e n x ) { . . . }
e) SchreibenSie ein Folge von Anweisungen,die einenBaum mit NamenBinBaum erzeugtund
nacheinanderdie Zahlen5 und 7 einftigt!
In denbinärenSuchbaumwerdennochdie Zahlen4, 11,6 und 2 eingefrigt.ZeichnenSieden
Baum,denSiedanacherhaltenhaben,und schreibenSiedie eingefügten
Zahlenin derReihenfolge der Traversierungsmöglichkeit
postorderauf)