Informatik-Treff: Abiturklausur (1997 LK 1. Klausur) 

Aufgabe 1: Rekursives/iteratives Suchen, Konturdiagramme

a) Das beiliegende Programm enthält zwei rekursive Funktionsprozeduren, die die Stelle suchen, an der ein bestimmter Schlüssel x: key in einem sortierten Feld array [1..n] of key vorkommt. Beschreibe umgangssprachlich die Idee, nach der die Suchalgorithmen arbeiten.

b) Welcher der Algorithmen arbeitet auch auf unsortierten Feldern richtig? Welcher der Suchalgorithmen ist auf sortierten Feldern effizienter? Nimm dazu an, im Feld seien ca. n = 1000 Zeichenketten abgespeichert. Überschlage, wie viele rekursive Aufrufe bei jedem der Algorithmen im Mittel erforderlich sind, wenn das gesuchte Element zufällig aus dem Feld ausgewählt wird.

c) Das Feld sei belegt durch / ali / dora / fritz / ulla / (n = 4). Entwirf ein Konturdiagramm, das den Ablauf der Rekursion bei Aufruf von suche1 veranschaulicht, wobei fritz gesucht werden soll. Erläutere, wie die Funktionsergebnisse zurückübergeben werden. Achte auf die Rücksprungadressen.

d) Man möchte l und r jetzt als Referenzparameter vereinbaren. Nimm die nötigen Veränderungen im Hauptprogramm vor und erläutere den Unterschied zwischen Referenz- und Werteparametern. Wie macht sich der Unterschied im Konturdiagramm bemerkbar?

e) Übersetze die beigelegte rekursive Prozedur suche1 in eine iterative Prozedur. Der Prozedurkopf soll nicht verändert werden.

 1 program suchalgorithmenvergleich;
 2 const n = 4;
 3 type key = string[40];
 4 var  feld: array[1..n] of key;
 5      x: key; e: integer;

 6 function suche1 (s: key; l,r: integer): integer;
 7 var k,j: integer;
 8 begin
 9   if l=r then
10     if s=feld[lj then j := l else j := O
11   else begin
12     k := (1+r) div 2;
13     if s>feld[k] then begin
14       k := k+l;
15       j := suche1(s,k,r) end
16     else j := suche1(s,1,k)
17   end
18   suche1 := j
19 end;

20 function suche2 (s: key; l: integer): integer;
21 begin
22   if l>n then suche2 := 0 
23   else
24     if s=feld(l] then suche2 := l
25     else suche2 := suche2(s,1+1)
26 end;

27 begin
28   feld[1] := 'ali'; feld[2] := 'dora'; feld[3] := 'fritz'; feld[4] := 'ulla';
29   x := 'fritz';
30   e := suchel(x,1,n);
31   writeln ('die gesuchte Zeichenkette steht auf Stelle ',e);
32   e := suche2(x,1);
33   writeln ('die gesuchte Zeichenkette steht auf Stelle ',e)
34 end.

Aufgabe 2: Abstrakte Datentypen, Kellerautomaten, cf-Sprachen

a) Erläutere den Unterschied zwischen den abstrakten Datentypen Keller, Schlange, Liste. Gib je mindestens ein typisches Anwendungsbeispiel an, in dem die genannten Datentypen sinnvollerweise zur Anwendung kommen.

b) Die angegebenen Prozeduren realisieren den abstrakten Datentyp Keller (über dem Typ T = char) mit Hilfe von Pointervariablen. Ersetze die nichtssagenden Namen P1 , ... durch treffendere. Eine Prozedur für den Keller fehlt. Welche? Schreibe diese Prozedur.

c) Wir betrachten Zeichenketten, die nur aus den Buchstaben a und b bestehen. Natürlich kann man durch Nachzählen feststellen, ob a und b gleich häufig vorkommen. Die Entscheidung darüber läßt sich aber auch ausschließlich mit Hilfe eines Kellers (über dem Datentyp t = char) durchführen. Erläutere kurz und präzise, wie man vorgehen könnte. Du kannst Deine Überlegungen am Beispiel der Zeichenkette aababbbbabaa darlegen. Schreibe ein Pascal-Prozedur.

Die Tatsache, daß die in c genannte formale Sprache (die aus allen Worten mit gleich vielen a's und b's besteht), durch einen Kellerautomaten akzeptiert werden kann, bedeutet, daß die Sprache kontexttrei ist.

d) Warum kann diese Sprache nicht regulär (also nicht durch einen endlichen Automaten akzeptierbar) sein?

e) Gib eine kontextfreie Grammatik für die genannte Sprache an.

f) Zeichne in Deiner Grammatik den Ableitungsbaum für das Wort aababb.

type t = char;
     keller = ^kelem;
     kelem = record
               inhalt: t;
               next : keller;
             end;

var k: keller; a: string [40]; i: integer;

procedure p1 (var k: keller);
begin
  k := nil
end;

function p2 (k: keller): boolean;
begin
  p2 := (k=nil)
end;

procedure p3 (var k: keller);
begin 
  k := k^.next
end;

function p4 (k: keller): t;
begin
  p4 := k^.inhalt
end; 

Aufgabe 3: Technische Informatik, Schaltnetze, Automaten

Eine 7-Segment Ziffer (0..9, A, b, C, d, E, F) wird durch maximal 7 Leuchtdioden dargestellt. Es geht um Schaltnetze mit 4 Eingängen a = (a3, a2, a1, a0), die die Dualcodierung der anzuzeigenden Ziffer enthalten und einem Ausgang zur Ansteuerung der Leuchtdioden C (oben rechts) bzw. E (unten links).
 

a) Erläutere, was die folgende Funktion mit Ansteuerung der Leuchtdiode C zu tun hat:

function led_C (a: integer): boolean;
begin
  led_C := (a=O) or (a=1) or (a=2) or (a=3) or (a=4) or (a=7) or
           (a=8) or (a=9) or (a=10) or (a=13) 
end;

b) Betrachte die Dualdarstellung der integer-Variablen a und stelle die disjunktive Normalform der Booleschen Funktion auf, die die LED C ansteuert.

c) Gib einen möglichst einfachen Schaltterm zur Booleschen Funktion aus b) an und programmiere eine function led_C (a3, a2, a1, aO: bit): boolean .

d) Die unten stehende Tabelle gehört zur LED E. Konstruiere mit Hilfe eines Karnaugh-Diagramms einen möglichst einfachen Schaltterm zu E.

e) Zeichne das Schaltnetz zu Deiner Lösung d).

f) Beweise durch Anwenden von Gesetzen der Booleschen Algebra, daß die in c) erhaltene Lösung für E äquivalent ist zur disjunktiven Normalform aus der unten stehenden Tabelle.
 

0 = 0000 
1 = 0001 
2 = 0010 
3 = 0011 
4 = 0100 
5 = 0101 
6 = 0110 
7 = 0111 
8 = 1000 
9 = 1001 
A = 1010 
b = 1011 
C = 1100 
d = 1101 
E = 1110 
F = 1111

1 
0 
1 
0 
0 
0 
1 
0 
1 
0 
1 
1 
1 
1 
1 
1

g) Erläutere in eigenen Worten, welche Rolle Schaltnetze bei der technischen Realisierung endlicher Automaten spielen.