Prüfungsüeilnehmer

Prüfungstermin

Einzelprüfungsnummer

Kennzahl:

Frühjahr
Kennwort:

2003

66TL2

Arbeitsplatz-Nr.:

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

Informatik (vertieft studiert)

Einzelprüfung:

Automatentheorie,Komplexität,Algorith.

Anzahlder gestelltenThemen(Aufgaben): 2
Anzahlder DruckseitendieserVorlase:

4

Bitte wenden!

Frühjahr 2003

Einzelprüfungsnummer
: 66112

Seite:2

Thema Nr. L

1. BeweisenSie: L((oB)*u): L(o(Fo,)*)für beliebigereguläreAusdrückea, B!
2. BetrachtenSie folgendekontextfreieGrammatikG:
S + ABlAaBb
A + aaAle
B + bbBle
a) BestimmenSie die durch G erzeugteSprache!
b) Ist L(G) regulär?(Begründung!)
3. Ist die Menge der durch 7 teilbarennatürlichenZahlenfieweils mit Begründung)
a) entscheidbar?
b) semi-entscheidbar?
c) primitiv-rekursiv?
d) regulär?
e) rekursiv aufzählbar?
4. GebenSie ein WHILE- oder LOOP-Programmfür die Fakultätsfunktionan! Makros für
x'.: ! + z undx F !. z könnenSiebenutzen.
(x teilt y e1z: x.z: !) primitiv-rekursivist.
5. ZeigenSie,dassdie Teilbarkeitsrelation
6. Sei F die Formel (A ^ B) v (_-A^ C) -+ B v C.
a) Ist F eine Tautologie?(Begründung!)
b) Ist F erfüllbar?(Begründung!)
7. SeiF dieFormel x Y y P(x,y) -+Vx I y P(y,x)
Ist ^F allgemeingültig?(Begründung!)

-3Frühjahr2003

Seite:3

: 66112
Einzelprüfungsnummer

Thema Nr. 2

Aufeabe l: (Zahlendarstellung
zur Basis p)
FührenSie die Subtraktion342
773 fir zwei Darstellungendurch,nZimlichzur Basis8 und
16! D. h. betrachtenSie die beidenZahleneinmalals Oktalzahlenund einmalals Hexadezimalzahlen,und rechnenSiejeweils das entsprechende
Ergebnisaus! GebenSie nebendem Oktalbzw. Hexadezimalwert
auchdessenDezimalwertan!
desErgebnisses
Aufeabe2: (Mengendarstellungen)
Mengen:
BetrachtenSie folgendeDarstellungen
von lnteger-wertigen
_

i)

eine einfachverketteteListe ohneMehrfachvorkommenvon Elementen,

ii) ein balancierter
binärerSuchbaum.
BearbeitenSienun folgendeTeilaufgaben:
a) ProgrammierenSie für beide Darstellungenin einer funktionalen ProgrammierspracheIhrer Wahl
dieSuchenacheinemElement!Für ii) müssenSie dazueinenDatentypfür einenBinärbaumdefinieren.
b) Ausgehendvon Ihren Lösungenzu a): welche worst-caseKomplexität (in der Elementezahlder
Menge) habenIhre beiden Suchprogramme?
Wennj4
c) KennenSie eine weitereDarstellungsweise
mit einernoch besserenSuchkomplexität?
beschreiben
Siediesekurz!
.-

d) ln welcherder beidenDarstellungeni) und ii) ist dasEinJügeneinesElementsrechnerischaufwändigerund warum?
Aufeabe3: (Verifikation)
BetrachtenSie die folgendeSchleife:WHILE i + 100D0 i::i+1.
a) BeweisenSie die partielleKorrektheitder Schleifebezüglichder Vorbedingungtrue und der
Nachbedingung
i :100!
Vorbedingung,für die totale
b) TotaleKorrektheitist nicht gegeben.Wie lautetdie schwächste
Korrektheit besteht?
c) Die von Ihnenin b) vorgeschlagene
VeränderungderVorbedingungerforderteinenneuenBeweis derpartiellenKorrektheit.FührenSiediesendurch,und gebenSie aucheineAbstiegsfunkder Abstiegstion zur TerminationdesProgrammsan! WeisenSiedie gefordertenEigenschaften
funktion exolizit nach!

FortsetzungnächsteSeite!

Frühjahr2003

Einzelprüfu
ngsnummer
: 66112

Seite:4

Aufeabe4: (FormaleSprachen)
OrdnenSiedie folgendenformalenSprachen
in die Chomsky-Hierarchie
ein!

a)

i|;r{a'ln>o\
i i l { a ' o l' , > o }
iiil{a't'c' l, = o}
il{a'b'c'd'l r r o}

b) BeweisenSie Ihre Aussagefür ii)! DazumüssenSienachweisen,
dassdie Sprachein der von Ihnen angegebenen
Klasseliegt (etwadurch AngabeeinerGrammatik),nicht aberin der nächstkleinerenKlasse.
Aufeabe5: (Abzählbarkeit)
N bezeichnet
die natürlichenZahlen.
a) DefinierenSiepräzisedenBegriff derI bztihlbarkeiteinerMengeund stellenSieihn einerpriDisenDefinitiondesBegriffs derrekursivenAufzählbarkeiteinerMengegegenüber!
b) SkizzierenSiedenBeweisderAbzählbarkeitder Menge N" allerFolgenmit maximaln Elementen (für festesn)!
c) SkizzierenSiedenBeweisderÜberabzählbarkeit
Folgen!
derMenge NN allerunendlichen
Aufeabe6: (Turing-Maschinen)
Ein Turing-Maschinen-Programm
ist eineFolgevon Quintupeln:
(Zustand,gelesenesBandsymbol,
Folgezustand,geschriebenes
Bandsymbol,
Kop fb ewegungsrichtung)
GebenSie ein Programman, daszwei beliebigepositive, ganzeZahlenaddiert! Sie dürfen sich die
Repräsentationder Zahlen und ihre Anordnung auf dem Band aussuchen.Wählen Sie weise; Ihre
Wahl bestimmtdie Komplexität desProgrammserheblich!BeschreibenSie die von Ihnen gewählte
Darstellungund dasProgrammhinreichend!