I
I

|

, t

'

Elnzelp r{llun g r nutilner

Prtlltrn3rte rmln

Prlllun3rtrllnrhrmr
Konnrehl:

FRUHJAHR
L993

Kennwort:
Arbeltrplatz-Nr.

Errte

:

Steetrprilfung

fitr eln Lohremt an öffentllchen
- Prilfunisaufgeben

(vertleft

etudlert)

Froh:

Inlorrnrtlk

Elnzelprilfung:

Autonretentheorle,Algorlthtn.

Anzehl der 3estellten Themen (Aufgaben):
Anzehl der Druekrelten

dlerer

Vorlege:

bttte

I

I

I
?

'

<

-

Sprachen
t
4

wenden!

66110

Schulen

PR.TERlllNr fr0hjahr

- I N Z E t P R U F I N G S N Rr . 6 6 1 L O / S E I T E 2

1993

Slmtllche Tallaufgabcn alnd zu bearboltenl
l. Formale Spracherr
(la) sei c -- (T, /v, P,s) einechomrky-Grammatik.rvas bcdcuten<tieangegebenen
Komponenl'cn?
iVie rind die Produktionenmcnge
P und dcr Ableil,barkeitsbegrill
.

definiert?
(lb) lVelcheformalenEinsclrrirrkuugen
auf P führcnzu dcn rrronotonen,
kontextsen.
ritivcn und kontextfrcienGramrnatiken?Wie liegendie lilasscnder erzeugten
Wortmengenzucinander?Soweitsie nicht gleichrind, gebenSie(ohneBeweis)je
cin typisctrerBeispielaus der Dillerenzmcngean!
( lc) Für liontextlreieGramltatikengilt das Zcrlcgungslcmrna.
Formulieren
und bewcisenSic diescr Lernrna!
(ld) BcweireuSie, da0 cichdic lVortrnerrge

{o,{ | i,j>o^i*il
von cincr koutexfreienGrammatikeneugenlä0ü!
2. Bercchenbarkeit
(2a) Der Bcrcchenbarkeitrbcgrill
kann nach Klecnedurch rekursiveFunktionende.
finiert werden. Geben Sie die Definition der primitiv-rekursiven
und dcr prehurrivenFunktionenal!
(2b) ZcigenSie,daOdcr beschränkte
p-Operatornicht aus rlcm Bcreichder primitivrekursivenFunktionenhinausfülrrt!
(2c) BcweirenSic. da0 dic ganzzahlige
Quadratwurzelfunktion
[.fnJ primitiv-rekursiv
ist!
(2d) Die p-rekurriven Funktionenlassensich unmiltelbar in ruÄdlaProgramme
überrctzen,die Dur au!
'. Wertz

.;.''l,,..;':;:'..].,,,:li.j']|.'lFi]]..-...,.'.'...'.'.i

.;ii,,i;.j.,,!,,r,1,rrdr:1i{,F^J.,1;',!+,.,}rofr"t'uia...l9;gpi9r$clliop'.-.,
:. : i.j$.', ,
' . - * o , , * b i ü ä r i n t i o a ' ' " : t l : i ' f i : - ; r ' l i ; . 1 ' : ; ' ; " ; ' - - i i f ' 3 r ' : 1 il ;
:

.

.

.i.

,..l'':

'.

"

Prozeduriufrufen.

I

bestehen.ZcigeoSie,da0 eskeinwhile-Programmmit geuaueinerVariablco gibt'
dasdie Fuuktion /(r) = 2e berechnet!

Fortsetzung nächste Sel te !

P R .T E R l , f t N rf r 0 h j a h r

- I N Z E t P R IF t N C S N Rr, 6 6 I l O / S E t r E 3

1993

3. Algorithmische Sprachen
definiert.
und einenSatzOperationen
(Jr) EineObjektart ist durcheineTrägermenge
bei einerVerbundartund welcheOperationenrind
Wie entrtehtdie Trägermenge
Sieals Beispiel:
daraufdefiniert?Verwenden
n o d ed a t u n . ( i n t [ r . . g t J t a g ,
int [1. .12JDouat,
i n t I t 9 0 0 . . 1 9 9 9 ]j a h r )
(3b) DefinierenSie die Objektart,der binärenBäumeals rekursiveVerbundartl Mit
welchemKonzept realisiertman rekursiveVerbundartenin den gängigenPro( P.lsclt,, C)?
grammiersprachen
(3r) Beschreiben
SieeineTechnikzur UmwandlungbeliebigerBäumein binäre! Zeigen
daßdasDurchlaufendesBaumesin PräSiedurch einePlausibilitatsbetrachtung,
Ordnungvon dieserUmwandlungnicht berührt wird!
liegt den Artvariantenzugtunde?Erläutern Sie
(3d) WelcheKonstruktionsvorschrift
BeispieltZeigenSie,daßdie unmittelbareVer'
Ihre Antwort an einemgeeigneten
eine gtatischeT1q
wendung des zugrundeliegenden
mathematischenKonzept€xt
prüfung nicht zuläßt!
4. Programmiermethodik
BetrachtenSie folgendeSpezifikationeinesabstrakten Datentyps:
init:

-->

tyPe
tyPe

add:

tyPe r Bat

r€Dov€:

tyTe

--)

is-eupty:

tyPe

f irst:

t5rpe

--1, boolean
--)
Dat

it-enpty(ilit)

I

tnre

ia-eupty(add(t,n))

r

false

flrst(add(init,u)

I

n

retrov€(add(iuit,n) )

r

init

f irst(add(add(t,n),n))

r

f irst(add(t, n))

renove(add(add(t,u) ,E))

I

add(reuove(add(t,u)) ,u)

)

(a") Erläutern Sie unter VerwendungdiesesBeispiels,was die uresenlliche ldee der
algebraischenSpezifikationist!
(4b) Die angegehneSpeziftkationdefiniert einenin der Informaüikhäufig Enzutreffen'
den Datentyp. lltelcherDatentyPist das? Begründung!
{
I

4

Fortsetzung

i

'tJ
J

-

r

rrste

Sel te t

P R . T E R l , l l N rf r ü h j a h r

1993

r 661 tO/SEtTE 4
ElNZEtpRttFrrNCSNR.

({") Dar angegeb€ne
Gleichungslyttem
induziert

auf der Termatgebraeine Kongruenzretation.Gebensie derenformateDeftnirion
an!

(4d) zeigensie, daßesin jederder durch
(") definiertenKongruenzklasren
genaueinen
Term dbt, der entwederdie Operation remotteüberhaupt,
nicht oder nur in der
Form remove
(inft/ enthält!
5. Übe.setzerbau
(5") was veßteht man untereinem
Compilergenerator?
Erläuternsie Aufgabe,Aufbau und Datenfluß!
(5b) Als Eingabefür einencompilergenerator
reichteinekontgxtfreie
Grammatiknicht
aus' Wie werdendie nichtkontextfreien
Aspekteder Syntax und die Semantik
beim compirergeneratoryaccberücksichtigt?
(5") Betrachtensie forgende
crammatik für schreifen:
r*rlE-ctat
::'
ltHrLEb Lo'p reg-of_rtat END;
teq-of-atat
::r
stat€E€nt I aeq_of_ctat stateuent
rtatenent
3:r
HIIILE_atat I otber-atat;
Verändernund/oder ertänzenSie
die erstedieserproduktionen,rc daß yacc die
sprunganweisuntctr,
diezur Realisierung
einerschleifenötig sind,au der ricbtigen
stelle enzeugt.Belirüadensie lhrc
Anderung!
(5d) Bei Erreicheneinessyntaxfehten
kommt es darauf an, die syntaxanalysero fortzusetzen,daß möglichstwenigeFotgefetrter
auftreten. Beschreibensie das auf
Grahamund Rhodeszurückgehende
Verfahrenzum wiederaufsetzen!Ist das verfahrenim Yacceinsetzbar?(Hinweis:
Bei der Beschreibung
spielendie folgenden
Begriffeeine Rotte: Kondensierung,.
Rückwärts-,Vorwärtsschritte.)