Informatik-Treff: Abiturklausur (1996 LK 1. Klausur)
Abituraufgabe für den Leistungskurs Informatik
Aufgabe 1:
Zur Erkennung bestimmter Muster in formalen Sprachen werden üblicherweise Akzeptoren (erkennende Automaten) verwendet.
Es sei folgender Akzeptor A = ( X, Z, S, F, f ) gegeben:
X = {a, b, c},
Z = {Z0, Z1, Z2, Z3},
S = Z0,
F = {Z0, Z2}
und f:
| Z | X | Z' |
| Z0 Z0 Z0 |
a b c |
Z1 Z0 Z0 |
| Z1 Z1 Z1 |
a b c |
Z3 Z2 Z3 |
| Z2 Z2 Z2 |
a b c |
Z1 Z3 Z0 |
| Z3 Z3 Z3 |
a b c |
Z3 Z3 Z3 |
a1) Zeichen Sie den Zustandsgraphen zu A .
a2) Geben Sie drei Wörter w an, die von A akzeptiert werden und auch drei Wörter, die nicht akzeptiert werden.
a3) Geben Sie die von A akzeptierte Sprache L(A) an. (formal oder in eigenen Worten)
a4) Beschreiben Sie kurz, welche Bedeutung den einzelnen Zuständen dieses Akzeptors jeweils zukommt.
b1) Geben Sie eine reguläre Grammatik G = ( N, T, S, R ) an, die L(A) erzeugt, also genau die Sprache, die der Akzeptor A akzeptiert.
b2) Leiten Sie zwei Wörter w mit Hilfe der Regeln ab. Ein Wort muß mindestens die Länge 5 haben.
Jeder endliche Automat läßt sich technisch als Schaltwerk realisieren. Der gegebene Automat A soll jetzt als Schaltwerk mit folgenden Eigenschaften realisiert werden:
Eingänge:
Das Schaltwerk habe drei Eingänge a, b und c. Die Zeichen des zu prüfenden Wortes werden nacheinander eingegeben. Fehleingaben sollen nicht vorkommen und brauchen nicht berücksichtigt zu werden. Die Taktsteuerung der Eingabe erfolgt automatisch und braucht nicht beachtet zu werden. Um die drei Eingabezeichen a, b und c zu verarbeiten, sind jedoch keine drei Eingangsleitungen notwendig; es reichen zwei. Dem eigentlichen Schaltwerk soll daher ein Schaltnetz vorgeschaltet werden, welches die drei Zeichen a, b und c in zwei Eingangsleitungen x1 und x2 des eigentlichen Schaltwerks umwandelt.
Ausgänge:
Das Schaltwerk hat nur eine Ausgabeleitung y1 . Diese Leitung soll genau dann auf 1 gesetzt werden, wenn der zugehörige Akzeptor A das momentan gelesene Eingabewort akzeptieren würde. Die Leitung soll andernfalls auf Null gesetzt werden.
Das gesamte Schaltwerk soll also folgendes Aussehen haben:
|
(*) vorgeschaltetes Schaltnetz
c1) Entwickeln Sie das (vorgeschaltete) Schaltnetz, das die Eingabezeichen a, b und c in der angegebenen Weise in die Eingabezeichen x1 und x2 umwandelt. Das Schaltnetz soll minimiert sein!
Eingabe |
X1 X2 |
a b c |
0 1 1 0 1 1 |
Hinweis:
Fehlbedienung (mehrere Zeichen gleichzeitig, keine Eingabe) kann außer Acht gelassen werden (don't care), so daß nur 3 Fälle auftreten können.
c2) Codieren Sie die Zustände des Akzeptors in geeigneter Weise. Ordnen Sie den codierten Zuständen die Speicheeinheiten zu. Verwenden Sie JK-FF.
c3) Stellen Sie die Zustandstabelle in der folgenden Form auf:
alter Eingabe Zustand X Z Z1 Z0 X1 X2 |
neuer Ausgabe Zustand Y Z' Z1 Z0 Y1 |
Speicher J1 K1 J2 K2 |
c4) Entwickeln Sie die Schaltterme für Y1, J1, K1, J2 und K2 mit Hilfe von KV-Diagrammen.
c5) Zeichnen Sie das vollständige Schaltbild. Die Ansteuerung
durch den Takt braucht nicht mitgezeichnet zu werden.
Aufgabe 2:
Die Schülerbücherei der Gesamtschule Lummerland (Name geändert) befindet sich im Aufbau. Um den wachsenden Bücherbestand systematisch zu erfassen, wird ein Computerprogramm benutzt, das folgende Daten erfassen soll:
Der Datenbestand wird als Datei (file) auf der Festplatte des Verwaltungscomputers gespeichert.
a1) Geben Sie eine geeignete PASCAL-Typendeklaration für die Bücherdatei an. Gestalten Sie dabei das letzte Ausleihdatum als untergeordnetes RECORD mit den Komponenten Tag, Monat und Jahr.
a2) Eine häufig vorkommende Anfrage an das System ist die, ob ein bestimmtes Buch schon vorhanden ist (oder noch angeschafft werden muß). Schreiben Sie dazu eine PASCAL-Funktion mit dem angegebenen Kopf.
FUNCTION vorhanden (buch: buchTyp; VAR f: dateiTyp): boolean;
Diese Funktion erhält den gesamten Datensatz eines Buches übergeben. Die Funktion soll daraufhin überprüfen, ob Autor und Titel des Buches im Bestand von f vorkommen. Es sollen nur diese beiden Angaben überprüft werden! Sie können davon ausgehen, daß die externe Plattendatei bereits vor Aufruf der Datei mit dem Bezeichner f verbunden wurde (assign). Die Datei ist jedoch noch nicht zum Lesen geöffnet.
Der Datenbestand wird immer größer. Das direkte Arbeiten auf der Plattendatei ist häufig zu langwierig. Die Daten sollen zum Arbeiten in den (genügend großen) Arbeitsspeicher geladen werden und dort in einer Baumstruktur abgelegt werden.
Aus Gründen der Übersichtlichkeit wird im folgenden nur noch die Buchnummer anstatt des gesamten Datensatzes angegeben. Die Buchnummer ist außerdem das relevante Ordnungskriterium (Hauptschlüssel). Die Datenübernahme vom Plattenspeicher in den Arbeitsspeicher geschieht wie folgt: Die Daten werden sukzessive von der Platte gelesen und im Arbeitsspeicher in eine Baumstruktur eingepasst. Dabei wird ein binärer Suchbaum, der zu Beginn leer ist, aufgebaut.
b1) Zeichnen Sie den binären Suchbaum, der beim Einlesen der folgenden Buchnummern entsteht.
540, 260, 300, 700, 270, 800, 35, 600, 950, 790, 400, 650, 795, 796, 15, 420, 350, 450, 797
b2) Traversieren Sie den in b1) entstandenen Baum in inorder, preorder und postorder. Geben Sie jeweils durch Ausgabe der Buchnummern an, in welcher Reihenfolge die Knoten besucht werden.
b3) Die Suche nach einer bestimmten Buchnummer kommt eher selten vor (z. B. Archivierungsanfragen). Häufiger wird nachgefragt, ob ein Buch vorhanden ist und/oder ausleihbar ist (Ausleihanfragen). Dazu ist der Hauptschlüssel 'Buchnummer' weniger geeignet. Nennen Sie ein sinnvolles anderes Ordnungskriterium, welches bei Ausleihanfragen ein günstigeres Suchverhalten zeigt, und begründen Sie es. Falls sich kein eindeutiger Primärschlüssel anbietet, verwenden Sie nachrangige Ordnungskriterien (Primärschlüssel, Sekundärschlüssel, ggf. Tertiärschlüssel).
Die Erfahrungen mit dem Schülerbücherei-Verwaltungsprogramm haben gezeigt, dass der Baum, der beim Einlesen der Datei entsteht (vgl. Aufgabenteil b1)) in der Regel recht unausgeglichen ist. Daher soll das Programm so erweitert werden, dass der Baum nach dem Einlesen jedes Datensatzes zunächst "ausbalanciert" wird.
c1) Erläutern Sie die Grundidee der ausgeglichenen bzw. balancierten Suchbäume, speziell der AVL-Bäume mit eigenen Worten.
c2) Erstellen Sie mit den Testdaten aus b1) einen AVL-Baum. Rahmen Sie die zu Rotationen führenden Knoten ein. Geben Sie an, welche Art von Rotation ausgeführt wird, und zeichnen Sie den Baum nach jeder Rebalancierung neu. Markieren Sie die danach angefügten Elemente (z. B. durch gestrichelte Verbindungslinien).
c3) Von welcher Ordnung (O-Kalkül) sind die Operationen Suchen, Löschen und Einfügen in AVL-Bäumen? Wägen Sie Aufwand und Nutzen des Ausbalancierens bei AVL-Bäumen gegeneinander ab. Beziehen Sie auch andere Baumstrukturen in Ihre Argumentation mit ein.
c4) Nennen Sie Einsatzbereiche, bei denen der Einsatz von AVL-Bäumen sinnvoll ist und solche, wo man besser darauf verzichten sollte. Begründen Sie jede Ihrer Antworten.