Esercizi svolti a lezione il 2 Marzo 2001 & Esercizi proposti

(ATTENZIONE: chi trova un errore in questa pagina ricevera' un premio!!!)

Alberi binari

Lo scopo di questa lezione e' introdurre il progetto incrementale di algoritmi su strutture dati dinamiche ricorsive (come liste e alberi).

Introduzione

Gli esercizi presentati faranno riferimento alla UNIT "alberi" presentata nel corso di di Programmazione II.

Esercizi svolti a lezione

Introduciamo una "notazione lineare" per gli alberi binari: Usando questa notazione possiamo specificare delle operazioni ricorsive per "pattern matching" sulla struttura degli alberi (ragionando quindi "ad alto livello" rispetto ai dettagli della realizzazione della struttura dati con la UNIT "alberi").

Nel seguito svolgeremo alcuni esercizi sugli alberi in 5 passi:

  1. Scriveremo l'intestazione (in PASCAL) della procedure o function richiesta dall'esercizio, corredandola di ASSERZIONE INIZIALE e ASSERZIONE FINALE.
  2. Scriveremo un algoritmo con la notazione "ad alto livello" menzionata in precedenza.
  3. Tradurremo l'algoritmo "pseudo-codice" Pascal.
  4. Tradurremo l'algoritmo in Pascal.
  5. Ottimizzeremo l'implementazione dell'algoritmo.
Come vedremo scrivere gli algoritmi con la notazione "ad alto livello" sara' piu' semplice che non il procedere direttamente con la scrittura di "pseudo-codice" Pascal. I passi 3 e 4 di traduzione da notazione "ad alto livello" a Pascal saranno quasi "meccanici". Il passo 5 potra' variare di difficolta' (di solito consistera' nell'eliminazione di una ricorsione di coda).

Modifica di un albero binario nel suo speculare

  1. Intestazione 
    {AI: t e' inizializzato e "contiene" l'albero T}
{AF: t "contiene" l'albero speculare di T}
procedure r (var t:tree);
  2. Algoritmo "ad alto livello" 
    r([]) = []
r([n,L,R]) = [n,r(R),r(L)]
  3. Algoritmo in "pseudo-codice" Pascal 
    procedure r (var t:tree);
  begin
    if t<>nil then
      begin
        --SCAMBIA t^.left E t^.right
        r(t^.left);
        r(t^.right);
      end;
  end;
  4. Algoritmo in Pascal (CON I COMMENTI)

    Si osservi che, data la particolare implementazione della struttura dati albero binario contenuta nella UNIT "alberi", il parametro della procedura puo' essere passato per valore (SI NOTI CHE passare il parametro per valore limita la nostra liberta' nel cambiare l'implementazione della struttura dati in future versioni della procedura che mantengano la stessa intestazione; PERCHE?). 

    {AI: t e' inizializzato e "contiene" l'albero T}
{AF: t "contiene" l'albero speculare di T}
procedure r (t:tree);
{SPECIFICA DELL'ALGORITMO:
 r([]) = []
 r([n,L,R]) = [n,r(R),r(L)]
}
  var temp:tree;
  begin
    if t<>nil then
      begin
        temp:=t^.left; t^.left:=t^.right; t^.right:=temp;
        r(t^.left);
        r(t^.right);
      end;
  end;
  5. Eliminazione della ricorsione di coda

    La procedura e' gia' scritta nella forma adatta per appicare l'elinazione della ricorsione di coda come descritta nei lucidi presentati a lezione dal docente di Programmazione II. 

    {AI: t e' inizializzato e "contiene" l'albero T}
{AF: t "contiene" l'albero speculare di T}
procedure r (t:tree);
{SPECIFICA DELL'ALGORITMO:
 r([]) = []
 r([n,L,R]) = [n,r(R),r(L)]
 NOTA: e' stata eliminata la ricorsione di coda
}
  var temp:tree;
  begin
    while t<>nil do
      begin
        temp:=t^.left; t^.left:=t^.right; t^.right:=temp;
        r(t^.left);
        t:=t^.right;
      end;
  end;

Esecuzione di una operazione v su tutti i nodi di livello l

Supponiamo di avere una procedure di intestazione 
{AI: e e' inizializzato}
{AF: l'operazione "v" e' stata applicata ad e}
procedure v (var e:elemtype);
  1. Intestazione 
    {AI: t e' inizializzato e "contiene" l'albero T,
     l>=0}
{AF: t "contiene" l'albero ottenuto applicando v 
     a tuttil i nodi di T di livello l}
procedure a (t:tree, l:integer);
  2. Algoritmo "ad alto livello" 
    a([],l) = []
a([n,L,R],0) = [v(n),L,R]
a([n,L,R],l) = [n,a(L,l-1),a(R,l-1)], dove l>0
  3. Algoritmo in "pseudo-codice" Pascal

    Passiamo immediatatamente alla fase successiva

  4. Algoritmo in Pascal 
    procedure a (t:tree,l:integer);
  begin
    if t<>nil then 
    if l=0 then v(t^.elem)
    else begin
           a(t^.left,l-1);
           a(t^.right,l-1);
         end;
  end;
  5. Eliminazione della ricorsione di coda

    La procedura e' gia' scritta nella forma adatta per applicare l'eliminazione della ricorsione di coda come descritta nei lucidi presentati a lezione dal docente di Programmazione II. Il programma risultante e' il seguente: 

    procedure a (t:tree,l:integer);
  begin
    while t<>nil do 
      if l=0 then v(t^.elem)
      else begin
             a(t^.left,l-1);
             t:=t^.right; l:=l-1;
           end;
  end;

Esercizi proposti

Esercizi

Realizzare una procedura che soddisfi la seguente specifica:

{AI: t e' inizializzato e "contiene" l'albero T,
     l1,l2>=0}
{AF: t "contiene" l'albero ottenuto applicando v 
     a tuttil i nodi di T di livello l compreso tra l1 e l2 (l2>=l>=l1)}
procedure a (t:tree, l1,l2:integer);