[Avl-cvs] avl/docs relazione.dvi,1.6,1.7 relazione.tex,1.14,1.15

[Gianlorenzo D\\'A. <ja...@us...>]

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

Modified Files:
	relazione.dvi relazione.tex 
Log Message:


Index: relazione.dvi
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v
retrieving revision 1.6
retrieving revision 1.7
diff -C2 -d -r1.6 -r1.7
Binary files /tmp/cvs4cAmvO and /tmp/cvsywobUx differ

Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -d -r1.14 -r1.15
*** relazione.tex	18 Sep 2004 20:06:39 -0000	1.14
--- relazione.tex	19 Sep 2004 10:07:27 -0000	1.15
***************
*** 303,307 ****
  
  
- 
  \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.
--- 303,306 ----
***************
*** 339,343 ****
  \section{Inserimento di una sequenza di valori casuali}\label{ins_cas}
  
! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile.
  
  Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo.
--- 338,342 ----
  \section{Inserimento di una sequenza di valori casuali}\label{ins_cas}
  
! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $n$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{n!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile.
  
  Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo.
***************
*** 345,349 ****
  \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzione, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST.
  
! Questo risultato \`e giustificato dal fatto che un albero di ricerca costruito utilizzando l'implementazione BST inserendo una sequenza casuale di valori ha un'altezza media $h$ pari ad $h=O\left(lg\left(n\right)\right)$ (.........................) uguale cio\`e all'altezza di un albero costruito utilizzando l'implementazione AVL (con la differenza che questo presenta tale valore di altezza per tutte le sequenze di input). L'albero BST ha inoltre il vantaggio di non dover eseguire le operazioni di rotazione e aggiornamento del fattore di bilanciamento.
  \begin{center}
    \includegraphics[width=400pt]{ins_casuale}
--- 344,348 ----
  \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzione, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST.
  
! Questo risultato \`e giustificato dal fatto che un albero di ricerca costruito utilizzando l'implementazione BST inserendo una sequenza casuale di valori ha un'altezza media $h$ pari ad $h=O\left(lg\left(n\right)\right)$ (cfr. \cite{cormen}) uguale cio\`e all'altezza di un albero costruito utilizzando l'implementazione AVL (con la differenza che questo presenta tale valore di altezza per tutte le sequenze di input). L'albero BST ha inoltre il vantaggio di non dover eseguire le operazioni di rotazione e aggiornamento del fattore di bilanciamento.
  \begin{center}
    \includegraphics[width=400pt]{ins_casuale}
***************
*** 417,423 ****
  
  
! \section{Inserimento di una sequenza di valori crescenti}
  
! L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inseriemnto di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$
  
  Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate.
--- 416,422 ----
  
  
! \section{Inserimento di una sequenza di valori crescenti}\label{ins_crescente}
  
! L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inserimento di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$.
  
  Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate.
***************
*** 495,498 ****
--- 494,509 ----
  \end{center}
  \section{Cancellazione di una sequenza di valori decrescenti}
+ 
+ Il test in questione consiste nella cancellazione di una sequenza di $n$ valori in un albero construito nel modo indicato nel paragrafo \ref{ins_crescente}. La sequenza di valori da cancellare \`e decrescente parte cio\`e dal valore pi\`u grande presente nell'albero e finisce con quello pi\`u piccolo. In questo modo l'implemetazione BST \`e costretta a lavorare nelle condizioni peggiori \footnote{un caso ulteriormente peggiore \`e quello in cui si cancella una sequenza di elementi tutti maggiori del massimo elemento presente nell'albero. In tal caso infattti la ricerca dell'elemento non avrebbe mai esito positivo ed ogni cancellazione avremme costo $cn$. \`E facile verificare come in questo caso la cancellazione di una tale sequenza di $m$ elementi costi $O\left(mn\right)$} infatti per come \`e costruito l'albero il valore pi\`u grande \`e l'unica foglia dell'albero e per cercarlo occorre quindi visitare tutti i nodi ottenendo un costo di $O\left(n\right)$.
+ 
+ Per come \`e costruita la sequenza ogni cancellazione \`e in realt\`a la cancellazione dell'elemento massimo dell'albero il quale ad ogni passo diventa pi\`u piccolo di 1 nodo. In questo modo se la prima cancellazione impiega un tempo pari a $cn$ (dove con $c$ si \`e indicata una costante moltiplicativa) allora la seconda cancellazione impiegher\`a un costo pari a $c\left(n-1\right)$ ed in generale la $i$ esima cancellazione (per $1\leq i \leq n$) impiegher\`a $c\left(n-i\right)$. Il costo totale della cancellazione sar\`a pari alla somma dei costi parziali:
+ \[
+ \sum_{i=0}^n c\left(n-i\right)
+ \]
+ sensibilmente superiore ad un costo lineare.
+ 
+ Per le stesse considerazione fatte nel paragrafo \ref{ins_crescente} l'iplementazione AVL offre prestazioni paragonabili a quelle che si ottengono nel caso medio.
+ 
+ Il grafico mostra appunto come mentre la curva degli AVL rimane vicina ad un andamento lineare, quella relativa ai BST cresce con un pendenza sempre maggiore.
  \begin{center}
    \includegraphics[width=420pt]{canc_crescente}
***************
*** 526,528 ****
--- 537,550 ----
  \end{center}
  
+  \begin{thebibliography}{99}
+   \bibitem{AVL} G.M. Adelson-Velskii G.M. , Y.M. Landis,
+   An algorithm for the organization of information
+      {\it Dokl. Akad. Nauk},
+    SSr, 146, 263-266, 1962
+   \bibitem{cormen} T.H. Cormen, C.E. Leiserson, R.L.Rivest,
+   Introduction to Algorithms, 2nd ed.
+      {\it MIT Press},
+    1999
+   \end{thebibliography}
+ 
  \end{document}