[Avl-cvs] avl/docs relazione.dvi,1.2,1.3 relazione.tex,1.10,1.11

[Patrizio B. <het...@us...>]

Update of /cvsroot/avl/avl/docs
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv14199

Modified Files:
	relazione.dvi relazione.tex 
Log Message:
manca solo la cancellazione e le tabelle per le performance nela capitolo conclusioni


Index: relazione.dvi
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
Binary files /tmp/cvs3XQuvf and /tmp/cvsjvPIdz differ

Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** relazione.tex	8 Sep 2004 17:59:54 -0000	1.10
--- relazione.tex	17 Sep 2004 12:29:45 -0000	1.11
***************
*** 35,39 ****
  
  Tuttavia, è noto che l'hardware a sè stante è inutile.
! E' (e sarà) sempre necessario del software per comandare tutte le varie periferiche in questione;
  questa cosa fa capire quanto una macchina di per sè velocissima possa essere inutilizabile se il software che la comanda
  contiene errori o è lento.
--- 35,39 ----
  
  Tuttavia, è noto che l'hardware a sè stante è inutile.
! \`E (e sarà) sempre necessario del software per comandare tutte le varie periferiche in questione;
  questa cosa fa capire quanto una macchina di per sè velocissima possa essere inutilizabile se il software che la comanda
  contiene errori o è lento.
***************
*** 53,57 ****
  esaminata l'implementazione proposta e le conclusioni che si possono trarre dopo aver sfruttato ed eseguito il codice prodotto.
  
! \chapter{Breve Panoramica}
  La premessa di questo capitolo è quella di non essere assolutamente un riferimento esaustivo sugli alberi AVL e BST.
  
--- 53,58 ----
  esaminata l'implementazione proposta e le conclusioni che si possono trarre dopo aver sfruttato ed eseguito il codice prodotto.
  
! \chapter{Alberi Binari di Ricerca}
! \section{Introduzione}
  La premessa di questo capitolo è quella di non essere assolutamente un riferimento esaustivo sugli alberi AVL e BST.
  
***************
*** 62,66 ****
  In generale gli alberi superano alcune limitazioni delle altre soluzioni, ad esempio non soffrono di limiti di spazio fisso.
  Generalmente ogni tipo di implementazione ha una doppia faccia, nel senso che risulta ottima e veloce in una certa operazione o in una certa sequenza di dati, mentre ha performance inferiori in altri contesti.
! In questo lavoro ci si concentrerà sull'operazione di ricerca, restringendo l'area agli alberi binari, ovvero quelli i cui nodi hanno al massimo 2 figli.
  L'implementazione BST è basata su questi alberi binari, con in più le condizioni:
  \begin{itemize}
--- 63,68 ----
  In generale gli alberi superano alcune limitazioni delle altre soluzioni, ad esempio non soffrono di limiti di spazio fisso.
  Generalmente ogni tipo di implementazione ha una doppia faccia, nel senso che risulta ottima e veloce in una certa operazione o in una certa sequenza di dati, mentre ha performance inferiori in altri contesti.
! 
! \section{BST}
  L'implementazione BST è basata su questi alberi binari, con in più le condizioni:
  \begin{itemize}
***************
*** 86,90 ****
  Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), ancora un costo lineare.
  Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione.
! 
  Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fdb).
  L'Fdb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello.
--- 88,92 ----
  Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), ancora un costo lineare.
  Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione.
! \section{AVL}
  Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fdb).
  L'Fdb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello.
***************
*** 101,107 ****
  \end{figure}
  Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fdb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano.
! L'operazione base di ricerca in un albero AVL si svolge nello stesso identico modo di un BST: partendo dalla root si procede "camminando" sul figlio destro o sinistro a seconda che il valore da cercare sia rispettivamente maggiore o minore del valore del nodo in cui ci si trova. In questo modo si effettua una ricerca rapidissima dal costo logaritmico rispetto al numero di elementi che compongono l'albero.
  Se la ricerca è una operazione di lettura (e restituzione del nodo eventualemente) che non modifica l'albero, le operazioni di inserimento e cancellazione possono sbilanciare un AVL e far violare le proprietà esposte precedentemente.
  Tuttavia non è necessario ribilanciare completamente tutto l'albero (operazione costosa che avrebbe compromesso l'efficenza di tutto l'algoritmo), ma è sufficiente ribilanciare il ramo interessato dalla modifica in scrittura. Questa dovrebbe essere una cosa scontata, una modifica può cambiare un solo ramo, di certo non stravolgerà i rami che contengono tutti i nodi con valori inferiori.
  Gli AVL vengono mantenuti bilanciati attraverso le Rotazioni.
  Questa operazione non fa altro che ruotare (d'altronde il nome..) i vari nodi, in modo da poter sempre tenere l'albero bilanciato.
--- 103,113 ----
  \end{figure}
  Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fdb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano.
! \subsection{Ricerca}
! L'operazione base di ricerca in un albero AVL si svolge nello stesso identico modo di un BST: partendo dalla root si procede "camminando" sul figlio destro o sinistro a seconda che il valore da cercare sia rispettivamente maggiore o minore del valore del nodo in cui ci si trova. In questo modo si effettua una ricerca rapidissima dal costo logaritmico rispetto al numero di elementi che compongono l'albero. Il costo sarà sempre logaritmico perchè l'albero AVL viene sempre mantenuto bilanciato e non ha quindi il difetto dei BST semplici.
! 
! \subsection{Inserimento}
  Se la ricerca è una operazione di lettura (e restituzione del nodo eventualemente) che non modifica l'albero, le operazioni di inserimento e cancellazione possono sbilanciare un AVL e far violare le proprietà esposte precedentemente.
  Tuttavia non è necessario ribilanciare completamente tutto l'albero (operazione costosa che avrebbe compromesso l'efficenza di tutto l'algoritmo), ma è sufficiente ribilanciare il ramo interessato dalla modifica in scrittura. Questa dovrebbe essere una cosa scontata, una modifica può cambiare un solo ramo, di certo non stravolgerà i rami che contengono tutti i nodi con valori inferiori.
+ 
  Gli AVL vengono mantenuti bilanciati attraverso le Rotazioni.
  Questa operazione non fa altro che ruotare (d'altronde il nome..) i vari nodi, in modo da poter sempre tenere l'albero bilanciato.
***************
*** 124,128 ****
  \end{figure}
  
! La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. Il nodo di partenza ha Fdb pari a +1. E' evidente che se l'Fdb fosse uguale a 0 non ci sarebbe bisogno di ribilanciare l'albero in quando, ovunque un nodo venisse inserito, il nuovo Fdb sarebbe pari a +/- 1, compatibile con gli AVL. In questo caso viene inserito un nuovo nodo nel ramo sinistro del sottoalbero sinistro, modificando in +2 il valore del Fdb della radice. A questo punto viene effettuata la rotazione LL: A sale di un livello e B scende, diventando figlio di A. Tuttavia A aveva già due sotto alberi, i cui valori erano sicuramente inferiori a B per la nozione di AVL. Il sotto albero destro di A viene quindi appeso come sottoalbero sinistro di B. Ora l'albero è di nuovo bilanciato. Da notate che sia A che B ora hanno Fdb pari a zero, quindi un successivo inserimento sarà privo di problemi di bilanciamento.
  La rotazione RR lavora in modo simmetrico, ovviamente.
  
--- 130,134 ----
  \end{figure}
  
! La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. Il punto a) illustra la situazione iniziale: il nodo di partenza ha Fdb pari a +1. E' evidente che se l'Fdb fosse uguale a 0 non ci sarebbe bisogno di ribilanciare l'albero in quando, ovunque un nodo venisse inserito, il nuovo Fdb sarebbe pari a +/- 1, compatibile con gli AVL. Nel punto b)  viene inserito un nuovo nodo (rappresentato con un pallino vuoto) nel ramo sinistro del sottoalbero sinistro, modificando in +2 il valore del Fdb della radice. A questo punto viene effettuata la rotazione LL: A sale di un livello e B scende, diventando figlio di A. Tuttavia A aveva già due sotto alberi, i cui valori erano sicuramente inferiori a B per la nozione di AVL. Il sotto albero destro di A viene quindi appeso come sottoalbero sinistro di B. Ora l'albero è di nuovo bilanciato. Da notate che sia A che B ora hanno Fdb pari a zero, quindi un successivo inserimento sarà privo di problemi di bilanciamento. Il punto c) mostra come si presenta l'albero dopo l'inserimento e la rotazione descritta.
  La rotazione RR lavora in modo simmetrico, ovviamente.
  
***************
*** 166,169 ****
--- 172,176 ----
  \end{itemize}
  
+ \subsection{Cancellazione}
  La cancellazione di un nodo AVL è identica a quella in un albero BST, tuttavia soffre degli stessi problemi dell'inserimento: a seguito dell'eliminazione di un nodo l'albero potrebbe essersi sbilanciato.
  E' quindi necessario ripetere gli stessi controlli di cui si è parlato in precedenza: partire dal nodo più basso del ramo interessato e risalire, bilanciando tutti i nodi con Fdb pari a +/- 2 con rotazioni singole o doppie.
***************
*** 176,185 ****
  In totale il costo di una cancellazione è O(log(n)) nel caso peggiore.
  
! \chapter{Applicazione}\label{Applicazione}
! La struttura dell'applicazione è stata divisa in quattro parti fondamentali.
! Due sono le parti relative alle strutture dati e agli algoritmi AVL (avlt.cpp e avlt.h) e BST (bst.cpp e bst.h), che forniscono ovviamente le funzioni di accesso, creazione e manipolazione degli alberi stessi.
! Le altre due parti sono un "client" per generare gli alberi, fare dei test di inserimento e cancellazione (test.cpp), e un programma in GTK per la grafica a video degli alberi tramite una gradevole GUI (avl.cpp).
! Il linguaggio utilizzato è il C++, che permette di sfruttare le nozioni di ereditarietà tra i BST e gli AVL.
  
  \begin{figure}[htbp]
          \begin{center}
--- 183,206 ----
  In totale il costo di una cancellazione è O(log(n)) nel caso peggiore.
  
! \chapter{Implementazione}\label{Applicazione}
! \section{Struttura e caratteristiche del codice}
! Nei capitoli precedenti gli AVL sono stati descriti come dei BST a cui vengono applicate operazione di bilanciamento dette rotazioni. \`E quindi evidente che gli AVL sono a tutti gli effetti dei BST: è questa la ragione della implementazione in C++ (e non il semplice C), linguaggio orientato agli oggetti che permette di sfruttare l'ereditarietà tra gli AVL e i BST.
! L'implementazione proposta è costituita da quattro parti fondamentali.
! \begin{itemize}
! \item bst.cpp e bst.h: contengono la classe Bst, che implementa gli alberi BST con tutte le strutture dati utilizzate, i metodi di ricerca, di inserimento, di cancellazione, di restituzione dei nodi, di conteggio del massimo e minimo valore, ed infine diversi metodi di visualizzazione (stampa) degli alberi.
! \item avlt.cpp e avlt.h: implementano la classe Avlt, derivandola dalla classe Bst descritta in precedenza. Di conseguenza contengono gli stessi attributi e metodi dei Bst, con l'aggiunta della gestione del Fdb e i metodi che scelgono e implementano le rotazioni necessarie.
! \item test.cpp e test.h: classe Test. \`E la classe che si occupa dei test su entrambi i tipi di albero: si occupa della inizializzazione e primo popolamento degli alberi, ed effettua cancellazioni ed inserimenti random, restituendo il valore del lasso di tempo impiegato. \`E possibile scegliere un test comparativo tra entrambi gli alberi.
! \item avl.cpp: è il vero e proprio Main, la classe client. Si occupa di fornire un'interfaccia di input/output all'utente, permettendo la scelta dei test da effettuare, del numero di nodi con cui popolare l'albero, del numero delle modifiche di interesse.
! \end{itemize}
  
+ Il client (avl.cpp) e le funzioni di stampa contenute in bst.cpp hanno due modalità grafiche: una è basata sul semplice utilizzo delle funzioni C/C++ (printf, cout, scanf) che implementano un'applicazione a linea di comando.
+ L'altra, molto più interessante, implementa una GUI attraverso l'uso delle librerie GTK (www.gtk.org).
+ La GUI permette una visualizzazione degli alberi molto più completa, gradevole ed intuitiva, inoltre permette di effettuare più test senza riavviare l'applicazione e di manipolare gli alberi a proprio piacimento inserendo e cancellando valori scelti dall'utente (questa particolarità non è presente nel client a linea di comando).
+ La scelta delle due interfacce va effettuata al momento della compilazione, il codice è separato e distinto tramite comandi del preprocessore del compilatore \#ifdef , in modo da mantenere il codice più snello e pulito possibile.
+ Da notare che l'implementazione della classi di Test e del client è del tutto indipendente dall'implementazione degli alberi: si possono infatti includere in qualunque altro progetto C++ per sfruttare gli algoritmi in questione.
+ \`E stata prevista anche la compilazione delle due classi come libreria separata e condivisa: questo significa che il codice compilato non verrà incluso direttamente nell'applicazione, ma verrà caricato al volo durante il runtime.
+ Il vantaggio è evidente: se più applicazioni utilizzano questo stesso codice non si spregherà nè del tempo di compilazione, nè spazio fisico su harddisk, rendendo i file binari più snelli e di conseguenza anche più veloci nel caricamento in memoria RAM.
+ 
+ Nella figura \ref{fig:trees} si è modellato tramite UML la struttura delle classi degli alberi, indicando l'ereditarietà, i metodi (distinguendo tra pubblici e privati), le variabili (sempre distinguendo tra pubbliche e private), quindi le interfacce delle classi.
  \begin{figure}[htbp]
          \begin{center}
***************
*** 190,193 ****
--- 211,216 ----
  \end{figure}
  
+ Nella figura \ref{fig:applicazione} si è modellato il resto dell'implementazione: il main che crea un oggetto di tipo Test che al suo interno include due oggetti, un Avlt e un Bst, che andrà a manipolare e testare.
+ Si è fatto uso degli stereotipi UML, tuttavia la rappresentazione è abbastanza intuitiva anche per i non esperti di questo linguaggio.
  \begin{figure}[htbp]
          \begin{center}
***************
*** 198,214 ****
  \end{figure}
  
  Il codice è distribuito sotto licenza GPL e include commenti esplicativi per tutte le funzioni.
! Attraverso il Makefile (chi è familiare con l'ambiente UNIX conosce le potenzialità di scripting che offre) è stata prevista la scelta della compilazione della GUI e della compilazione in modalità libreria condivisa: quest'ultima permette di sfruttare gli algoritmi implementati in qualunque applicazione C++.
  Opzioni Makefile:
  \begin {itemize}
! \item make -> compila l'applicazione implementando la visualizzazione su shell.
  \item make gui -> compila l'applicazione implementando la visualizzazione tramite interfaccia grafica scritta in 
! GTK. E' necessaria la presenza dei pacchetti devel della libraria GTK.
! \\item make shared -> la compilazione è divisa in due: una parte riguarda il client, l'altra riguarda gli algoritmi, 
! che vengono linkati come "shared". in questo modo è possibile utilizzarli in tutte le altre applicazioni necessarie e 
! il file binario è di dimensioni più contenute.
  \end{itemize}
  
  
  \chapter{Conclusioni}\label{Conclusioni}
  Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile.
--- 221,247 ----
  \end{figure}
  
+ \newpage
+ 
+ \section{Compilazione ed utilizzo}
  Il codice è distribuito sotto licenza GPL e include commenti esplicativi per tutte le funzioni.
! Viene distribuito un file compresso tramite gzip (avl.tar.gz).
! Dopo varlo scompattato (tar xzf avl.tar.gz) si troveranno due directory: "docs" e "src".
! La priam contine questa relazione in formato tex (latex), pdf e dvi.
! Per l'applicazione si entri nella directory "src".
! 
! Attraverso il Makefile (chi è familiare con l'ambiente UNIX conosce le potenzialità di scripting che offre) è stata prevista la scelta della compilazione abilitando diverse modalità.
  Opzioni Makefile:
  \begin {itemize}
! \item make -> compila l'applicazione implementando la visualizzazione su shell, il client a linea di comando.
  \item make gui -> compila l'applicazione implementando la visualizzazione tramite interfaccia grafica scritta in 
! GTK. \`E necessaria la presenza dei pacchetti devel della libreria GTK.
! \item make shared -> la compilazione è divisa in due: una parte riguarda il client, l'altra riguarda gli algoritmi, 
! che vengono linkati come "shared". In questo modo è possibile utilizzarli in tutte le altre applicazioni necessarie e 
! il file binario è di dimensioni più contenute. Si crea un binario "avl" e la libreria condivisa "libavl.a".
! 
  \end{itemize}
  
  
+ 
  \chapter{Conclusioni}\label{Conclusioni}
  Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile.