[Avl-cvs] avl/docs relazione.tex,1.3,1.4

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

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

Modified Files:
	relazione.tex 
Log Message:
giangi, dacci un'occhiata, manca solo la parte in cui spiego gli avl.
non so se la parte applicazione va trattata o no, che ne dici?


Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -C2 -d -r1.3 -r1.4
*** relazione.tex	8 Aug 2004 09:44:09 -0000	1.3
--- relazione.tex	23 Aug 2004 13:46:15 -0000	1.4
***************
*** 50,60 ****
  In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis, 1962) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni.
  
! Nel prossimo capitolo verrà illustrato in generale in funzionamento e l'idea alla base delle tecniche, poi verrà 
! esaminata in generale 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.
  Il contesto in cui si colloca questo lavoro è quello dei Dizionari. In ogni problema, di qualsiasi tipo esso sia, si ha a che fare con una certa tipologia e quantità di dati; generalmente si può modellare un problema utilizzando un tipo di dato generico, non ben specificato.
! Questo è il caso del Dizionario: un tipo di dato astratto (ADT, Abstract Data Type) che rappresenti un insieme di tipi di oggetti al quale vengono applicate operazioni di inserimento, cancellazione, ricerca. Sarebbe inutile infatti conoscere degli oggetti senza avere possibilità di manipolarli o gestirli.
  La gestione di un dizionario può chiaramente essere effettuata in una infinità di soluzioni, come array (e qui si potrebbe parlare della disposizione degli oggetti nel contenitore array stesso), liste (con tutti i vari tipi di concatenazione) oppure alberi.
  Quest'ultima soluzione offre numerose alternative, tra queste ci sono proprio gli alberi BST e AVL.
--- 50,61 ----
  In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis, 1962) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni.
  
! Nel prossimo capitolo verrà illustrato in generale il funzionamento e l'idea alla base delle tecniche, poi verrà 
! 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.
+ 
  Il contesto in cui si colloca questo lavoro è quello dei Dizionari. In ogni problema, di qualsiasi tipo esso sia, si ha a che fare con una certa tipologia e quantità di dati; generalmente si può modellare un problema utilizzando un tipo di dato generico, non ben specificato.
! Questo è il caso del Dizionario: un tipo di dato astratto (ADT, Abstract Data Type) che rappresenti un insieme di tipi di oggetti al quale vengono applicate operazioni di inserimento, cancellazione, ricerca. Sarebbe inutile infatti conoscere degli oggetti senza avere la possibilità di manipolarli o gestirli.
  La gestione di un dizionario può chiaramente essere effettuata in una infinità di soluzioni, come array (e qui si potrebbe parlare della disposizione degli oggetti nel contenitore array stesso), liste (con tutti i vari tipi di concatenazione) oppure alberi.
  Quest'ultima soluzione offre numerose alternative, tra queste ci sono proprio gli alberi BST e AVL.
***************
*** 80,89 ****
  In questo modo, se l'albero è composto da n elementi, la ricerca nel caso peggiore costerà O(n), quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato.
  E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile.
! Chiaramente, come già detto in precedenza, avere un costo minore nella ricerca costringerà a performance infariori in altre
! situazioni.
! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con starti di +/-1), in modo da pagare sempre un costo logaritmico per la ricerca.
! Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare dove inserire e per trovare il nodo da cancellare).
  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 (Fsb).
  L'Fsb è 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.
--- 81,90 ----
  In questo modo, se l'albero è composto da n elementi, la ricerca nel caso peggiore costerà O(n), quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato.
  E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile.
! 
! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con differenze di +/-1), in modo da pagare sempre un costo logaritmico per la ricerca.
! Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare la posizione in cui inserire e per trovare il nodo da cancellare).
  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 (Fsb).
  L'Fsb è 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.
***************
*** 99,106 ****
          \label{fig:avl}
  \end{figure}
! Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporando anche l'informazione relativa al Fsb 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.
  
! \chapter{Applicazione}\label{Applicazione}
  
  \chapter{Conclusioni}\label{Conclusioni}
  \end{document}
--- 100,122 ----
          \label{fig:avl}
  \end{figure}
! Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fsb 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.
  
! INSERIMENTO
! CANCELLAZIONE
! ROTAZIONI
  
+ \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 (avl.cpp e avl.h) e BST (bst.cpp e bst.h).
+ Le altre due parti sono un "client" per generare gli alberi, fare test di inserimento e cancellazione, e un programma in GTK per la grafica a video degli alberi tramite una gradevole GUI.
  \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 praticamente non percettibile.
+ Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile.
+ In realtà il risultato è giustificabile con diversi punti:
+ \begin{itemize}
+ \item il generatore di numeri casuali, in realtà non è puramente casuale. E' un limite di quasi tutti i sistemi operativi e processori attuali
+ \item la misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è detto che il sistema operativo assegni al programma le stesse risorse in ogni momento
+ \item la quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime
+ \item non è sicuro che l'implementazione proposta sia la più performante in entrambi i casi. L'uso di strutture dati differenti, compilatori e ottimizzazione specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test.
+ \end{itemize}
  \end{document}