N

Prüfungsteilnehr Prüfungstermin Einzelprüfungsnumner

Kennzahl:

Herbst 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: 3

Bitte wenden!

/ Herbst 1997 Einzelprüfungsnr.: 46112 Seite: 2

Sämtliche Teilaufgaben sind zu bearbeiten!

Verwenden Sie zur Beschreibung von Algorithmen bzw. Datentypen in den Teilaufgaben 1
und 2 eine übliche Programmiersprache (PASCAL, MODULA 0.4.) oder einen entsprechen- |

den ”Pseudocode” ! . |

Teilaufgabe 1

Gegeben sei die Grammatik I mit der Menge £ = {a,b,c} von Terminalzeichen, den Nichtterminalzeichen Z, D und C, dem Axiom Z und den Produktionsregeln

Z>2c D>Ca Ce
zZ27 D2 D-b c>ccC
. (e bezeichne die leere Zeichenreihe.).-
y
£(T) bezeichne die von T erzeugte Sprache. Für xeX* und se £ bezeichne A,{s) die Anzahl der Vorkommen von s in x. Die Mengen M, und M, von Zeichenreihen über Z seien
gegeben durch .
M, = {xe 2" A,(a)+A,(b) 2 1},
M,= {xe=* A,(a)+A,(b) = A,(c)}.
a) Beweisen oder widerlegen Sie folgende Behauptungen: '
al) cabace ¥(T),
2) ADeM,
a3) M,s #(T).
b) Geben Sie einen deterministischen endlichen Automaten an, der genau die Zeichenreihen von M, akzeptiert !
pn c) Gibt es eine reguläre (d.h. Typ-3-) Grammatik, von der genau die Menge M, als
Y) Sprache erzeugt wird? Begründen Sie Ihre Antwort! |

Für das folgende sei ne N, fest vorgegeben. Betrachtet werden nun Zeichenreihen aus =", |
d.h. Zeichenreihen der Länge n über 2. Nehmen Sie an, daß Ihre Programmiersprache zur
Realisierung solcher Zeichenreihen einen Datentyp für Reihungen über I der Art

array [1..n] sigma

(in PASCAL-artiger Notation) mit der üblichen direkten Zugriffsoperation auf die einzelnen
Komponenten der Reihung bereitstellt! (sigma sei ein Datentyp zur Realisierung von ©.)

d) Geben Sie einen iterativen Algorithmus an, der für eine Zeichenreihe x € £" feststellt,
obxeM, ist!

Fortsetzung nächste Seite!



e) Will man die Aufgabe von Teil d) statt durch einen iterativen durch einen rekursiven

g)

Algorithmus lösen, so ist dies unter den gemachten Voraussetzungen nicht direkt möglich. Als ”"Umweg” kann man einen aligemeineren Algorithmus der Art

function ALLGLÖSG (x:array [1..n] sigma, k:integer): boolean

rekursiv formulieren (”Einbettung”), der einen zusätzlichen Parameter k enthält und
für x = (x,,...x,) und k mit 1<k <n feststellt, ob gilt:

A,la,k) + A,lb,l) 2 1.

Dabei bezeichnen A,(a,k) und A,(b,k) die Anzahlen der Vorkommen von a bzw. b unter
den ersten k Zeichen x,,....x, von x. Ein Aufruf ALLGLÖSG(x,n) ("Spezialisierung
k=n?") liefert dann offensichtlich eine Lösung der ursprünglichen Aufgabe von Teil d).

Geben Sie einen rekursiven Algorithmus für ALLGLÖSG an!

Geben Sie einen iterativen Algorithmus an, der für eine Zeichenreike x ¢ 5" feststellt,
obxeM, ist! .

Geben Sie analog zu Teil e) eine geeignete Einbettung der Aufgabe von Teil f) in eine
allgemeinere Aufgabe an, lösen Sie diese durch einen rekursiven Algorithmus, und
geben Sie die Spezialisierung an, mit der man daraus eine Lösung der ursprünglichen
Aufgabe von Teil f) erhält! (Hinweis: Neben der Verallgemeinerung durch den zusätzlichen Paramater k wie in Teil e) ist eine weitere Verallgemeinerung notwendig.)

Teilaufgabe 2

In einer Wirtschaftsuntersuchung werden n Firmen F,,...,F,, (n22) und ihre gegenseitigen
Geschäftsverbindungen der Art "Firma F, beliefert Firma F, mit Waren” (ij ¢ {1,....n})
betrachtet. Erläutern Sie die Darstellung der Menge aller dieser Beziehungen

a) als Adjazenzmatrix,
b) durch Adjazenzlisten!

Geben Sie jeweils auch die entsprechenden Datentyp-Deklarationen an!

Teilaufgabe 3

Erläutern Sie folgende Adressierungsarten für den Speicher einer Rechenanlage:

a) absolute Adressierung,
b) relative Adressierung,
c) indirekte Adressierung!

Geben Sie jeweils auch eine typische Anwendung an!