Algoritmi e Strutture Dati I
Prima Verifica - 16 Aprile 1999
  1. Scrivere una procedura Pascal LIS(L : DLISTA) per realizzare l'algoritmo di Insertion Sort su una lista bidirezionale di interi L, definita come segue:

    type DLISTA = ^DNodo;
         DNodo = record
                 prev : DLISTA;   { predecessore: nil se primo nodo }
                 elem : Integer;  { chiave memorizzata }
                 next : DLISTA    { successore:  nil se ultimo nodo }
         end;
    var  L : DLISTA;
    
    Per esempio, la lista L = { 1, 5, 3 } è così rappresentata:





  2. Determinare l'ordine di complessità T(n) della seguente funzione Pascal nel caso pessimo, ricavando e risolvendo l'equazione di ricorrenza per T(n):

    function SOMME(A: array [1 .. n] of real; n: integer) : real;
    var k : integer;
        s : real;
    begin
    if (n < 12)
       then SOMME := 0
       else begin
            s := A[1];
            for k := 2 to n do s := s + A[k];
            if (n mod 2) = 0 then SOMME := s + SOMME(A, n div 4)
                             else SOMME := s - SOMME(A, n div 6)
            end
    end 
    


  3. Scrivere una procedura che, dato un vettore di interi A[1 .. N] in ingresso, verifichi efficientemente che tale vettore soddisfi la proprietà di heap.



Soluzioni
  1. procedure LIS(L : DLISTA);
    var key : Integer;
        P   : DLISTA;
    begin
    while (L <> NIL) do
       begin
       key := L^.elem;
       P := L;
       while (P^.prev <> NIL) and (P^.prev^.elem > key) do
          begin
          P^.elem := P^.prev^.elem;
          P := P^.prev
          end;
       P^.elem := key;
       L := L^.next
       end
    end
    

  2. Per ottenere l'equazione di ricorrenza corrispondente, si osservi che bisogna prendere il massimo tra i costi dei rami then-else: Si noti che chiaramente T(n) = Omega(n) essendoci il termine additivo Teta(n). Per trovare un limite superiore T'(n) >= T(n), si maggiori T(n) con la soluzione della seguente equazione:
         T'(n) = T'(n/4) + Teta(n).
    A questo punto è possibile usare il teorema master con f(n) = Teta(n), a = 1 e b = 4. Poiché f(n) è Omega(nlogb a + epsilon) = Omega(nepsilon), per una costante positiva epsilon < 1, la soluzione è data da T'(n) = Teta(f(n)) = Teta(n). Questo implica che T(n) = O(n) e quindi T(n) = Teta(n) per il limite inferiore immediato di cui sopra.


  3. Soluzione iterativa in tempo lineare:
    function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
    var flag : boolean;
        i    : integer;
    begin
    flag := true;
    i := 1;
    while flag and (i <= (N div 2)) do
       begin
       if ((2*i+1) > N) then flag := (A[i] >= A[2*i])
          else flag := (A[i] >= A[2*i]) and (A[i] >= A[2*i+1]);
       i := i + 1
       end;
    HEAP-VERIFY := flag
    end
    
    Altra soluzione iterativa in tempo lineare:
    function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
    var i : integer;
    begin
    i := 2;
    while (i <= N) and (A[i div 2] >= A[i]) do i := i + 1;
    HEAP-VERIFY := (i > N)
    end
    
    Soluzione ricorsiva in tempo lineare:
    function HEAP-VERIFY(A : array [1 .. N] of Integer) : boolean;
       function REC-VERIFY(A : array [1 .. N] of Integer; i : integer) : boolean;
       begin
          if (i > (N div 2)) then REC-VERIFY := true
          else if ((2*i+1) > N) 
              then REC-VERIFY := (A[i] >= A[2*i]) and REC-VERIFY(A, 2*i) 
                                 and REC-VERIFY(A, 2*i+1)
              else REC-VERIFY := (A[i] >= A[2*i]) and (A[i] >= A[2*i+1]) 
                                 and REC-VERIFY(A, 2*i) and REC-VERIFY(A, 2*i+1)
       end;
    begin { HEAP-VERIFY }
    HEAP-VERIFY := REC-VERIFY(A, 1)
    end { HEAP-VERIFY }