[ALGO 2 Homepage] Algorithmen und Datenstrukturen 2 WS 1999/2000

9. Übung - abzugeben (voraussichtlich) am 11. 1. 2000 in Ihrer Übungsgruppe


9.a Kruskal (schriftliche Ausarbeitung)

Gegeben sei der ungerichtete Graph V={0,1,2,3,4,5,6,7,8} mit den Kanten E={[0,1]16, [0,2]4, [1,6]13, [2,3]11, [2,5]4, [2,6]9, [3,4]5, [3,5]6, [4,7]4, [4,8]3, [5,6]12, [5,7]15, [6,7]6} samt tiefgestellten Kantenbewertungen.
Erstellen Sie nach dem Algorithmus von Kruskal den minimal spannenden Baum. Gefordert ist nicht ein Programm, sondern eine schriftliche "Simulation" des in der LVA besprochenen Algorithmus.


9.b Theorie (schriftliche Ausarbeitung)

Geben Sie von folgenden Prozeduren an, welche asymptotische Zeitkomplexität sie besitzen. Begründen Sie jeweils Ihre Meinung (Keine mathematische Ableitung notwendig!).
(*1*)
PROCEDURE matmpy*(N:INTEGER);
  VAR i,j,k:INTEGER;
BEGIN
  FOR i:=0 TO N-1 DO
    FOR j:=0 TO N-1 DO
      FOR k:=0 TO N-1 DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END matmpy;

(*2*)
PROCEDURE mystery*(N:INTEGER);
  VAR i,j,k:INTEGER;
BEGIN
  FOR i:=1 TO N-1 DO
    FOR j:=i+1 TO N DO
      FOR k:=1 to j DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END mystery;

(*3*)
PROCEDURE strange*(N:INTEGER);
  VAR i,j,k:INTEGER;
BEGIN
  FOR i:=2 TO N-1 DO
    FOR j:=i-1 TO N DO
      FOR k:=i-1 to i+1 DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END strange.


(*4*)
PROCEDURE recurs*(N:INTEGER):INTEGER;
BEGIN
  IF N<=1 THEN
    RETURN 1;
  ELSE
    RETURN recurs(N-1)+recurs(N-1);
  END;
END recurs;

(*5*)
PROCEDURE veryodd*(N:INTEGER);
  VAR i,j:INTEGER;
BEGIN
  FOR i:=1 TO N DO
    IF ODD(i) THEN
      FOR j:=i TO N DO
        (*Einfache Anweisung*)
      END;
      FOR j:=1 TO i DO
        (*Einfache Anweisung*)
      END;
    END;
  END;
END veryodd;

(*6*)
PROCEDURE fibr*(N:INTEGER):INTEGER;
BEGIN
  IF N<=1 THEN
    RETURN 1
  ELSE 
    RETURN fibr(N-2)+fibr(N-1);
  END;
END fibr;

(*7*)
PROCEDURE fibi*(N:INTEGER):INTEGER;
  VAR i,prev,act,next:INTEGER;
BEGIN
  prev:=1;act:=1;next:=1;
  FOR i:=2 TO N DO
    next:=prev+act;
    prev:=act;
    act:=next;
  END;
  RETURN next;
END fibi;
Geben Sie mit Begründung an, welche Zeitkomplexität folgende Problemstellungen haben:
  1. Suchen eines Elementes x in sortierter/unsortierter verketteter/konsekutiver Liste mit jeweils N Elementen
  2. Suchen von Minimum und Maximum in


Last modified: Hörmanseder 98-11-23