N

Prüfungsteilnehmer Prüfungstermin Einzelp.tifungsnummer

Kennzahl:

Frühjahr 46112
1997

Kennwort:

Arbeitsplatz-Nr.:

Erste Staatsprüfung für'ein Lehramt an öffentlichen Schulen

- Prüfungsaufgaben - ;
Fach: Informatik (nicht vertieft studiert)
Einzelprüfung: Grundlagen der Informatik

Anzahl der gestellten Themen (Aufgaben): 1

Anzahl der Druckseiten dieser Vorlage: 2

Sämtliche Teilaufgaben sind zu bearbeiten!

Teilaufgabe 1

Gegeben sei die Grammatik T mit {a,b,c} als Menge der Terminalzeichen, den Nichtterminalzeichen Z, A und B, dem Axiom Z und den Produktionsregeln

zoaA A->aA B-— 6B
Z->bA A>bB B>c
Arc

£(T) bezeichne den Sprachschatz von T.

a) Sei M die Menge aller Zeichenreihen über {a,b,c}, die mit dem Zeichen c enden.
Beweisen oder widerlegen Sie folgende Behauptungen:

al) #0) ¢ M.
a2) Mes «N.

b) Geben Sie einen deterministischen endlichen Automaten an, der genau die Zeichenreihen von 2(T) akzeptiert.

c) Beschreiben Sie Z(T) durch einen regulären Ausdruck.

Fortsetzung nächste Seite!
Frühjahr 1997 “ Einzelprüfungsnr.: 46112 Seite: 2

Teilaufgabe 2

a) Von einem Algorithmus A der Art
PROCEDURE A( VAR x: ARRAY [1..n10F REAL)

“ sei bekannt, daß er diE Zeitkomplexität O(n?) hat. Erläutern Sie ausführlich, was diese
Aussage bedeutet. In welchem Sinne ist ein Algorithmus mit Zeitkomplexität On)
"besser" als A?

b) Beschreiben Sie verbal die Wirkungsweise des Algorithmus QUICKSORT zum Sortieren einer Folge von Zahlen.

c) Welche Zeitkomplexität hat QUICKSORT ? Begründen Sie Ihre Antwort.
d) Nennen Sie noch wenigstens zwei andere Sortierverfahren mit einer Zeitkomplexität

von gleicher Größenordnung wie die Zeitkomplexität von QUICKSORT.

Teilaufgabe 3

Durch die Funktionsvereinbarung
function f({n:nat)nat:
if n=0 then3
D n=1 then 0d
0 n=2 then 2
else f(n-2) + f(n-3) endif

ist eine Funktion f: N,-+IN, definiert. Die Funktion g: N,xNyxNyxN, +N, sei gegeben
durch u

a(n,x,y,2) = ef(n+2) + yf(n+l) + zF(n).
a) Bestimmen Sie (für beliebige x,y,ze N,) den Wert von g(3,x,y,2).
b) Beweisen Sie, daß für n,x,y,ze N,, n21, gilt: gln,x,y,2) = gin-1y,x+zux).

c) Geben Sie unter Verwendung von b) einen rekursiven Algorithmus an, der g(n,x,y,z)
für beliebige n,x,y,ze N, berechnet.

d) Geben Sie einen iterativen Algorithmus an, der f(n) für beliebiges ne N, berechnet.

Teilaufgabe 4

Gegeben sei die dreistellige Schaltfunktion / mit
fla,b,c) = (and) v(naanb) vlaanc) v(aaac)v(bac) v{mbance).
a) : Geben Sie ein Schaltnetz für fan.
b) Beweisen Sie, daß für alle Schaltvariablen a,b,c gilt:
fla,b,c) = (avabve) a(navbv-ac).
c) Beweisen oder widerlegen sie folgende Behauptungen:

ei) fla,b,c) = f(b,a,c) für alle Schaltvariablen a,b,c.
c2) f(a,b,c) = f(-b,-a,c) für alle Schaltvariablen a,b,c.