Algoritmi e Strutture Dati I (Prima Verifica

Algoritmi e Strutture Dati I
Prima Verifica - 16 Aprile 1999

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:

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

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

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

Per ottenere l'equazione di ricorrenza corrispondente, si osservi che bisogna prendere il massimo tra i costi dei rami then-else:
- T(n) = O(1) per n < 12;
- T(n) = max { T(n/4), T(n/6) } + Teta(n) per n >= 12.
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(n^{log_b a +
epsilon}) = Omega(n^epsilon), 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.

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 }