Prüfungsteilnehme* Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Frühjahr 46112
1995

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

Bitte wenden!
Frühjahr 1995 ° Einzelprüfungsnr.: 46112 - Seite: 2

1)

2)

3)

4)

5)

6)

Sämtliche Teilaufgaben sind zu bearbeiten!

Welche Eigenschaften charakterisieren einen Algorithmus?

Beschreiben Sie eine universelle Turingmaschine möglichst
exakt. .

a) Wie kann man das Terminieren eines Programms beweisen?

b) Gibt es ein allgemeines Verfahren, das für jedes Programm
und jede Eingabe dazu entscheidet, ob die Berechnung
terminiert?

Schreiben Sie ein Programm, das die Anzahl S(m,n) der
Zerlegungen einer natürlichen Zahl m in Summanden, die alle
natürliche Zahlen und kleiner gleich n sind, berechnet.

(Beispiel: S(4,2) = 3, weil 4 = 2+2 = 2+1+1 = 1+r1+1+1)

Hinweis: Leiten Sie zunächst eine geeignete Rekursionsfornel
her.

Gegeben sei die Grammatik G = (ZL,T,Prod,S) mit dem Zeichenvorrat r={S,X,Y} TT, .dem terminalen Zeichenvorrat T={a,c} dem
Startsymbol S und der Produktionsmenge Prod = [(S->aXc),
(X->XX), (X->AY), (aA->aa), (YA->AY), (Yoe->ec)}

a) Ist die Grammatik kontextfrei?
b) Geben Sie die von G erzeugte Sprache L(G) an und
begründen Sie Ihre Antworten. ,

Welche Datenstrukturen zur Implementierung von Bäumen kennen
Sie? Beschreiben Sie diese und eine Prozedur, die das Einfügen
eines Knotens in einen Baum leistet.

Yan