Informatik I

WS 2000/2001, Prof. Jürg Gutknecht

Konvergenzübungen

Aufgabe 1. Wir nehmen folgende Deklarationen an:

  CONST z = 0; t = 2;
  VAR si: SHORTINT; i: INTEGER; li: LONGINT; ch: CHAR;
      s: SET; r: REAL; lr: LONGREAL; b: BOOLEAN;

Beurteilen Sie die folgenden Zuweisungen. Welche sind illegal und warum?

  si := ORD(CHR(71)); i := ORD("G"); li := ORD(CHR(72));
  i  := 1 + ENTIER(r); si := SHORT(ENTIER(3.14));
  b  := 3 < MAX(REAL) OR li > i + 4; ch := 44X; b := 44X > "a";
  ch := "this is true"; b := ("abc" > "this") & (MAX(REAL) > 1/t);
  b  := (CAP(6DX) = "M") & (li = 1/z); i := 4 + CHR("a")

Aufgabe 2. Gegeben seien ganzzahlige Konstanten X und Y. Was wird durch das folgende Programm berechnet? Welche Anweisung innerhalb der WHILE-Schleife kann weggelassen werden, ohne dass dies einen Einfluss auf das Resultat hätte?

  x := X; y := Y; z := 0; (* x >= 0 *)
  WHILE x > 0 DO
    IF ODD(x) THEN z := z + y; x := x - 1 END;
    y := 2 * y; x := x DIV 2
  END;

Aufgabe 3. Identifizieren Sie den Gültigkeitsbereich aller Deklarationen in folgendem Modul. Finden Sie einen Fehler. Welches sind die Werte der globalen Variablen, nachdem Modul M in den Speicher geladen worden ist (wobei der Fehler korrigiert sei).

  MODULE M;
    VAR i, j: INTEGER;
    PROCEDURE A*;
      VAR i: INTEGER;
      PROCEDURE B*(VAR i, j: INTEGER);
        VAR k: INTEGER;
      BEGIN k := i; i := j; j := k
      END B;
    BEGIN i := 2; B(i, j)
    END A;
    PROCEDURE C;
    BEGIN A; i := 2*j
    END C;
  BEGIN C
  END M.

Aufgabe 4. Welche der folgenden Prozedursignaturen sind legal?

  PROCEDURE f(x: REAL): ARRAY OF CHAR;
  PROCEDURE f(x: REAL): REAL;
  PROCEDURE g(i: INTEGER): VAR x: REAL;
  PROCEDURE P(x: REAL, y: CHAR);
  PROCEDURE P(x: REAL), (y: CHAR);
  PROCEDURE Q(a, b, c: REAL; VAR r1, r2, i1, i2: REAL);

Aufgabe 5. Angenommen

  CONST x1 = 1; x2 = 2; x3 = 3; x4 = 4; x = 3.14159;
  VAR a, b, c, aR, bR, aI, bI: REAL; i: INTEGER;
    xR, yR, xI, yI: LONGREAL;
  PROCEDURE Root(a, b, c: REAL; VAR x1, x2, y1, y2: REAL);
  PROCEDURE Sin(x: REAL): REAL;
  PROCEDURE Min(x, y: INTEGER): INTEGER;

Welche der folgenden Prozeduraufrufe sind korrekt?

  Root(a, b, c, aR, bR, aI, bI); 
  Root(1, 3, 4, x1, x2, x3, x4);
  Sin(3.14159); 
  a := Sin(x1); 
  i := Min(x, x1); 
  i := Min(x1, x2);
  Root(a, b, c, 3, 4, 5, 6); 
  Root(a, 3*b, c+1, xR, yR, xI, yI);

Aufgabe 6. Warum muss im folgenden v ein VAR-Parameter sein?

  PROCEDURE SetZero(VAR v: ARRAY OF REAL);
    VAR i: INTEGER;
  BEGIN
    i := 0; WHILE i # LEN(v) DO v[i] := 0; INC(i) END
  END SetZero;

Aufgabe 7. Geben Sie eine zu folgender Prozedur gleichwertige Oberonanweisung an:

  PROCEDURE Assign(src: ARRAY OF CHAR; VAR dst: ARRAY OF CHAR);
    VAR i: INTEGER;
  BEGIN (* LEN(dst) > Length(src) *)
    i := 0; WHILE src[i] # 0X DO dst[i] := src[i]; INC(i) END;
    dst[i] := 0X
  END Assign;

Aufgabe 8.

(a.) Programmieren Sie eine Oberon Prozedur

  PROCEDURE Length (x: ARRAY OF CHAR): INTEGER;

welche die Länge des in x liegenden Strings berechnet.

(b.) Gegeben sei

  PROCEDURE Test1(a: ARRAY OF CHAR; VAR b: ARRAY OF CHAR);
  BEGIN
    Out.Int(Length(a), 1); Out.Ln;
    Out.Int(LEN(a), 1); Out.Ln;
    Out.Int(Length(b), 1); Out.Ln;
    Out.Int(LEN(b), 1); Out.Ln
  END Test1;

Was tut das folgende Oberonkommando, wenn es aufgerufen wird?

  PROCEDURE Test2*;
    VAR a: ARRAY 32 OF CHAR;
  BEGIN
    a := "Hello"; Test1("world!", a)
  END Test2;

Aufgabe 9. Gegeben sei

  MODULE DeclTest;

    IMPORT Out;

    VAR global : INTEGER;

    PROCEDURE Proc1;
      VAR local: INTEGER;
    BEGIN local := 1
    END Proc1;

    PROCEDURE Proc2*;
      VAR local: INTEGER;
    BEGIN local := 0;
      Proc1;
      Out.Int(local,0); Out.Ln()
    END Proc2;

    PROCEDURE Proc3;
    BEGIN global := 1
    END Proc3;

    PROCEDURE Proc4*;
    BEGIN global := 0;
      Proc3;
      Out.Int(global,0); Out.Ln()
    END Proc4;

    PROCEDURE Proc5*;
      VAR global: INTEGER;
    BEGIN global := 0;
      Proc3;
      Out.Int(global,0); Out.Ln()
    END Proc5;

  END DeclTest.

Fragen:

Was geschieht, wenn Proc2 aufgerufen wird?
Was geschieht, wenn Proc4 aufgerufen wird?
Was geschieht, wenn Proc5 aufgerufen wird?
Warum geben die Aufrufe von Proc4 und Proc5 verschiedene Resultate, obwohl die Zeilen zwischen BEGIN und END identisch sind?

Aufgabe 10. Gegeben sei

  MODULE ParamTest;

    IMPORT Out;

    PROCEDURE Quad1 ( a : INTEGER );
    BEGIN a := a * a;
    END Quad1;

    PROCEDURE Quad2 ( VAR a : INTEGER );
    BEGIN a := a * a;
    END Quad2;

    PROCEDURE Quad3 ( a : INTEGER ): INTEGER;
    BEGIN RETURN a * a;
    END Quad3;

    PROCEDURE TestQuad*;
    VAR x : INTEGER;
    BEGIN
      x := 5; Quad1(x); Out.Int(x,0); Out.Ln();
      x := 5; Quad2(x); Out.Int(x,0); Out.Ln();
      x := 5; x := Quad3(x); Out.Int(x,0); Out.Ln()
    END TestQuad;

  END ParamTest;

Tippen Sie dieses Programm ein und lassen Sie es laufen. Finden Sie heraus warum es das tut was es tut.

Aufgabe 11. Implementieren Sie folgende Basisfunktionen für Zahlenvektoren:

  PROCEDURE Min(a: ARRAY OF REAL): REAL;
  PROCEDURE Max(a: ARRAY OF REAL): REAL;
  PROCEDURE Average(a: ARRAY OF REAL): REAL;

Aufgabe 12. Was ist die Ausgabe des folgenden Programmes beim Aufruf von Test.Print?

  MODULE Test;
    IMPORT Out;
    PROCEDURE Print*;
      PROCEDURE P(n: INTEGER);
      BEGIN
        IF n # 0 THEN Out.Int(n, 2); P(n-1); Out.Int(n, 2) END
      END P;
    BEGIN P(3)
    END Print;
  END Test.

Aufgabe 13. Gegeben seien

  TYPE
    Node = POINTER TO NodeDesc;
    NodeDesc = RECORD next: Node END;
  VAR a, b: Node;

Angenommen, a und b repräsentieren je eine (bereits aufgebaute) Liste. Programmieren Sie dann

(a.) die Konkatenation a & b der Listen a und b

(b.) die intermittierende Liste a0, b0, a1, b1, ... die abwechselnd je ein Element von a und ein Element von b enthät (und nach dem Aufbrauchen der kürzeren Liste das Ende der längeren).

Aufgabe 14. Erstellen Sie eine Prozedur zur Bestimmung der Höhe eines beliebigen binären Baumes bei gegebener Wurzel root:

  TYPE Node = POINTER TO NodeDesc;
    NodeDesc = RECORD left, right: Node END;

  VAR root: Node;

Aufgabe 15. Es seien x, y und z Variablen vom Typ REAL und

PROCEDURE f (x: REAL): REAL;
PROCEDURE g (y: REAL): REAL;

zwei Funktionen. In welchen Fällen ist z := f(x) + g(y) nicht gleichwertig mit z := g(y) + f(x)?

Aufgabe 16. Wir betrachten die folgende Prozedur zur Multiplikation c := A*b einer Matrix A mit einem (passenden Spalten-)Vektor b:

PROCEDURE Multiply (VAR A: ARRAY OF ARRAY OF REAL; VAR b, c: ARRAY OF REAL);
  VAR i, j: INTEGER;
BEGIN
  FOR i := 0 TO ? DO c[i] := 0;
    FOR j := 0 TO ?? DO
      c[i] := c[i] + a[i, j]*b[j]
    END
  END
END Multiply;

(a.) Ersetzen Sie die "?" durch die korrekten Konstrukte

(b.) Was passiert beim Aufruf Multiply(A, b, b)?

(c.) Wie kann (b.) "geheilt" werden?

Aufgabe 17. Ein Stack (Stapel) ist eine LIFO-Liste (Last In, First Out). Das heisst, es kann jeweils nur das Element entfernt werden, das als letztes eingefügt worden ist.

Auf einem Stack sind folgende Operationen definiert:

Create: erzeugt einen neuen leeren Stack
Push: legt ein Element zuoberst auf den Stack
Pop:  loescht das oberste Element (oftmals wird auch noch dessen Inhalt zurueckgegeben)
Top:  gibt den Inhalt des obersten Elementes zurueck
IsEmpty: gibt an, ob ein Stack leer ist

Implementiere im vorgegeben Programmskelet "Stack.Mod" die Prozeduren Push, Pop, Top und IsEmpty. Teste deinen Stack mit dem Modul TestStack aus "TestStack.Mod".

Aufgabe 18. Gegeben sei folgende Datenstruktur einer linearen Liste:

TYPE
	TElem = POINTER TO TElemDesc;
	TElemDesc = RECORD
		val: INTEGER;
		next: TElem;
	END;
	TList = RECORD
		first, last: TElem;
	END;

Implementiere dazu das folgende Interface:

PROCEDURE Init*(VAR list: TList);

Erstellt eine neue leere Liste.

PROCEDURE Insert*(VAR list: TList; val: INTEGER);

Hängt das Element mit dem Wert 'val' vorne an die Liste an.

PROCEDURE Append*(VAR list: TList; val: INTEGER);

Hängt das Element mit dem Wert 'val' hinten an die Liste an.

PROCEDURE Delete*(VAR list: TList; val: INTEGER):INTEGER;

Löscht alle Elemente mit dem Wert 'val' aus der Liste und gibt die Anzahl der gelöschten Elemente zurueck.

Hinweis: Schreibe sowohl hier als auch in den folgenden Aufgaben ein Testprogramm, ähnlich dem Modul TestStack.Mod.

Aufgabe 19. Implementiere ähnlich wie in Aufgabe 18 eine geordnete Liste mit folgender Datenstruktur:

TYPE
	TElem = POINTER TO TElemDesc;
	TElemDesc = RECORD
		key, val: INTEGER;
		next: TElem;
	END;
	TList = RECORD
		first, last: TElem;
	END;

Dazu sei folgendes Interface gegeben:

PROCEDURE Init(VAR list: TList);

Initalisiert eine neue leere Liste.

PROCEDURE Insert(VAR list: TList; key, val: INTEGER);

Fügt ein das Element mit Schluessel 'key' und Inhalt 'val' in die Liste ein. Die Elemente müssen in der Liste nach den Schlüsseln geordnet sein. Es sollen zudem keine Elemente mit gleichen Schlüsseln vorkommen.

PROCEDURE Delete(VAR list: TList; key);

Löscht das Element mit dem dazugehörigen Schlüssel.

PROCEDURE Find(VAR list: TList; key):INTEGER;

Sucht nach dem Element mit dem Schlüssel 'key' und gibt dessen Inhalt 'val' zurück. Überlege dir auch, was du machst, falls eine Suche erfolglos endet.

Aufgabe 20. Gegeben die Definition einer verketteten Liste:

TYPE
    Element = POINTER TO ElementDesc;

    ElementDesc = RECORD
        next : Element;
        val : INTEGER;
    END;

Implementiere:

PROCEDURE Merge (VAR dst : Element; src1, src2 : Element);

Fügt zwei geordnete Listen zu einer neuen geordneten Liste zusammen. src1 und src2 zeigen jeweils an den Anfang der Eingabelisten. Die Eingabelisten werden bei der Verarbeitung zerstört (destructive merge).