PSD PDF - Organizzazione del codice

PSD Organizzazione del codice : l’insieme delle attività relative al concepimento della soluzione Progettazione informatica di un problema. Principi ispiratori Astrazione Procedimento mentale che consente di evidenz...

PSD Organizzazione del codice : l’insieme delle attività relative al concepimento della soluzione Progettazione informatica di un problema. Principi ispiratori Astrazione Procedimento mentale che consente di evidenziare le caratteristiche pregnanti di un problema. Information hiding Nascondere il funzionamento interno deciso in fase di progetto di una parte del programma. Riuso del codice Utilizzo di funzioni o librerie Modularità Suddividere un programma in moduli più piccoli e indipendenti. Semplicità nel correggere gli errori Leggibilità Testabilità Modulo Il modulo è una unità di programma costituita da una interfaccia. Definisce le risorse ed i servizi messi a disposizione dei clienti. Completamente visibile ai clienti Sezione implementativa (body) Implementa le risorse ed i servizi esportati occultata Un modulo può usare altri moduli PSD 1  Un modulo può essere compilato indipendentemente da modulo che lo usa. Moduli in C In c i moduli vengono definiti dai file con estensione.h o anche detti header files. Qui vengono definite le firme dei metodi e delle strutture dati che devono essere poi implementati nel file.c. Per compilare tutti insieme i moduli si usa il makefile. I moduli per essere inclusi usiamo la keyword #include “mylib.h”. Il modulo quindi si presenta come una libreria di funzioni. Dal sorgente all’eseguibile Il processo che trasforma un programma scritto in linguaggio C (il "codice sorgente") in un programma eseguibile che può essere eseguito sul computer coinvolge diverse fasi. Queste fasi sono: precompilazione, compilazione, assemblaggio e collegamento. Di seguito una spiegazione dettagliata di ciascuna fase: 1. Precompilazione (Preprocessing) Il precompilatore ( preprocessor ) esegue delle operazioni preliminari sul codice sorgente prima della compilazione vera e propria. Tra le operazioni principali ci sono: PSD 2  Inclusione dei file di intestazione: I file.h inclusi tramite #include vengono inseriti nel codice sorgente. Sostituzione delle macro: Le macro definite con #define vengono sostituite nel codice. Condizioni di compilazione: Le direttive condizionali come #if , #ifdef , #ifndef , #else , e #endif vengono valutate per includere o escludere porzioni di codice. Il risultato di questa fase è un file sorgente intermedio, ancora in C, con tutte le macro espanse e i file di intestazione inclusi. 2. Compilazione (Compilation) Il compilatore prende il codice sorgente preprocessato e lo traduce in codice assembly specifico per l'architettura della macchina. In questa fase, il compilatore esegue: Analisi sintattica e semantica : Viene controllata la correttezza sintattica e semantica del codice. Ottimizzazione : Il codice può essere ottimizzato per migliorare le prestazioni. Il risultato della compilazione è un file in linguaggio assembly , che rappresenta una versione a basso livello del programma. 3. Assemblaggio (Assembly) Il codice assembly viene poi trasformato da un assemblatore ( assembler ) in codice macchina o codice oggetto ( object code ). Questo è un formato binario che la CPU può comprendere e eseguire. Il risultato è un file con estensione.o o.obj (file oggetto), che contiene codice macchina, ma non è ancora un programma completo eseguibile perché potrebbe mancare di riferimenti a funzioni o variabili definite in altri file oggetto o librerie. 4. Collegamento (Linking) Il linker ( linker ) combina uno o più file oggetto insieme, risolvendo i riferimenti tra di essi (ad esempio, chiamate a funzioni definite in altri file) e aggiungendo eventuali librerie necessarie (come la libreria standard di C). Il linker produce un file eseguibile completo. PSD 3  Il risultato finale è un file eseguibile, con estensione.exe su Windows, o senza estensione su sistemi UNIX-like, che può essere eseguito direttamente dal sistema operativo. Questi passaggi sono spesso automatizzati da strumenti come gcc , che li esegue tutti in sequenza quando si compila un programma C con un singolo comando. Algoritmi di ordinamento Gli algoritrmi di ordinamento ci sono utili quando vogliamo ordinare un insieme di dati 1. Ordinare una breve sequenza di numeri 2. Mettere un elenco di nomi in ordine alfabetico 3. Ordinare i record degli studenti Unisa secondo la data di nascita Proprieta’ : due elementi con la medesima chiave mantengono lo stesso Stabile ordine con cui si presentavano prima dell'ordinamento. In loco: in ogni dato istante al più è allocato un numero costante di variabili, oltre all'array da ordinare Adattivo : il numero di operazioni effettuate dipende dall’input Interno vs esterno : Interno: i dati sono contenuti nella memoria RAM Esterno: i dati sono residenti su disco o su nastro Algoritmi semplici e avanzati Algoritmi semplici: numero di operazioni quadratico rispetto alla taglia dell’input O(n2 ) Selection Sort Insertion Sort Bubble Sort Algoritmi Avanzati. Piu’ efficienti Merge Sort PSD 4  Numero di operazioni rispetto alla taglia dell’input: O(n log n) Quicksort O(n log n)nel caso medio quadratico nel caso peggiore Sviluppo di programmi - Analisi e Progettazione Analisi Specifica cosa fa il programma. Individuazione di: Dati in ingresso e loro vincoli Dati di uscita e loro vincoli Vincoli : condizione definita sui dati di ingresso che deve essere Precondizione soddisfatta affinchè la funzione sia applicabile : condizione definita sui dati di uscita e dati di ingresso e Postcondizione che deve essere soddisfatta al termine dell’esecuzione del programma E’ buona norma usare un dizionario dei dati, una tabella il cui schema è Identificatore, tipo, descrizione La descrizione serve a specificare meglio l’identificatore e a descrivere il contesto in cui il dato viene usato PSD 5  Testing Il testing serve ad esercitare il programma con dati di test per verificare che il suo comportamento sia conforme a quello atteso. Oracolo : è l’output atteso, quello che ci si aspetta il programma produca Malfunzionamento : comportamento del programma diverso da quello atteso Debugging : individuazione e correzione del difetto che ha causato il malfunzionamento. Una volta corretto il malfunzionamento rieseguire tutti i casi di test ADT In informatica un tipo di dato astratto (ADT), e’ un modo per definire e gestire i dati in modo strutturato e organizzato, indipendentemente dalla loro implementazione interna. Vantaggi degli ADT: Astrazione: Gli ADT permettono di concentrarsi sul cosa si fa con i dati, piuttosto che sul come vengono implementati. Questo li rende più facili da usare e da capire, e favorisce la riutilizzabilità del codice. : Gli ADT nascondono l'implementazione interna dei dati, Incapsulamento proteggendoli da modifiche accidentali o intenzionali. Questo aumenta la robustezza e la sicurezza del codice. Modularità: Gli ADT possono essere combinati tra loro per creare strutture dati più complesse, favorendo la modularità e la riutilizzabilità del codice. Come implementare gli ADT in C: In C, gli ADT possono essere implementati utilizzando diversi approcci: : Una struct è un modo semplice per definire un ADT in C. Permette di Struct raggruppare variabili correlate sotto un unico nome e di definire funzioni per manipolarle. Tuttavia, le struct non offrono un controllo completo sull'accesso ai dati, che può esporre a potenziali vulnerabilità. Union : Un'union è simile a una struct, ma permette di memorizzare diversi tipi di dati nella stessa variabile. Le union sono utili quando si ha bisogno di memorizzare un valore che può assumere diverse forme, ma non sono adatte a rappresentare strutture dati complesse. PSD 6  Tipi definiti dall'utente: I tipi definiti dall'utente (typedef) permettono di creare nuovi tipi di dato a partire da tipi di base esistenti. Questo può essere utile per dare un nome più significativo a un tipo di dato complesso o per creare un alias per un tipo di dato di libreria. Polimorfismo : Il polimorfismo è una caratteristica di alcuni linguaggi di programmazione che permette di definire funzioni o operatori che possono lavorare su diversi tipi di dato compatibili. In C, il polimorfismo può essere simulato utilizzando funzioni con argomenti generici o utilizzando tecniche di programmazione orientata agli oggetti. Pseudo Generics Il tipo generico in programmazione e’ uno strumento che permette la definizione di un tipo parametrizzato, che viene esplicitato successivamente in fase di compilazione o ( linking ) secondo le necessita’. Permettono di: Eseguire algoritmi su tipi di dati diversi Applicare ADT su tipi di dati diversi Alcuni linguaggi supportano gli generics a tempo di compilazione (Java). Per risolvere il problema del sorting con diversi dati, bisogna creare un tipo generico che funge da interfaccia, chiamato Item supporti input, output e confronto. Generics in C In C e’ possibile dic hiarare un puntatore ad un topo non specificato (puntatore a void ). E poi assegnarlo al tipo desiderato , a volte e’ necessario usare il casting. void *p_void; int * p_int = p_void; char* p_char = p_void; ADT Lista PSD 7  La lista e’ una sequenza di elementi di un determinato tipo, in cui e’ possibile aggiungere o togliere elementi. E’ possibile specificare la posizione relativa nella quale l’elemento va aggiunto o tolto. Ogni elemento di una lista concatenata e’ un record con un campo puntatore che serve da collegamento per il record successivo. La lista concatenata viene chiamata " autoreferenziante " perché ogni nodo della lista contiene un riferimento a sé stesso attraverso un puntatore al nodo successivo (o precedente, in caso di una lista doppiamente concatenata). typedef struct list *List; struct list{ int size; struct node *head; }; Liste concatenate VS Array Array: dimensione fissa, accesso diretto ad ogni elemento tramite un indice. Lista: dimensione variabile, accesso diretto solo al primo elemento della lista Per accedere ad un generico elemento, occorre scandire sequenzialmente gli elementi della lista. Efficienza computazionale Accesso PSD 8  Lista : per accedere all’iesimo elemento occorre scorrere la lista dal primo all’iesimo elemento Array : ogni elemento di un array e’ accessibile direttamente usando il suo indice (tempo costante) Inserimento e cancellazione : dato un elemento, e’ possibile eliminarlo o aggiungere uno Lista concatenata dopo direttamente (tempo costante) Array : Occorre effetturare dellle operazioni di shift ADT Queue Una coda (queue) è una sequenza di elementi di un determinato tipo, in cui gli elementi si aggiungono da un lato ( tail ) e si tolgono dall’altro lato ( head ). La sequenza è gestita con la modalità FIFO , il primo elemento inserito nella sequenza sarà il primo ad essere eliminato. La coda è una struttura datai lineare a dimensione variabile Si accede solo alla testa Non è possibile accedere ad un elemento diverso dalla testa, se non dopo aver eliminato tutti gli elementi che lo precedono. PSD 9  Può essere implementato con gli array o le liste concatenate. ADT Stack Lo stack è una sequenza di elementi di un determinato tipo, in cui è possibile aggiungere o togliere elementi da un solo lato top dello stack. E’ una struttura dati lineare a dimensione variabile Non è possibile accedere ad un elemento diverso dal primo se non dopo aver eliminato tutti gli elementi che lo precedono LIFO , l’ultimo elemento inserito nella sequenza sarà il primo ad essere eliminato. PSD 10  Lo stack può essere implementato sia con gli array che con le liste. Ricorsione Un sottoprogramma ricorsivo è un sottoprogramma che richiama direttamente o indirettamente se stesso. I linguaggi che gestiscono la ricorsione, lo fanno mediante record di attivazione. Operativamente, risolvere un problema con un approccio ricorsivo comporta Identificare un caso base , con soluzione nota esprimere la soluzione al caso generico n in termini dello stesso problema in uno o più casi più semplici (n-1, n-2, etc.) La struttura dati più importante che abbiamo studiato usa la ricorsione, le liste linkate. Basic recursion In programmazione, risolviamo dei problemi definiti ricorsivamente usando funzioni ricorsive che chiamano se stesse. Tail recursion E’ una forma di ricorsione che alcuni compilatori sono in grado di generare codice ottimizzato. Come funziona la ricorsione in memoria Fondamentalmente un programma C, consiste in 4 aree in cui viene eseguito: area del codice, area dei dati statici, heap e lo stack. l’area del codice contiene le istruzioni macchina che sono eseguite quando il programma e’ in esecuzione. l’area statica contiene dati che persistono oltre la durata del programma, come le variabili globali e le variabili statiche. l’heap contiene la memoria allocata dinamicamente. lo stack contiene informazioni sulle chiamate delle funzioni. Per convenzione, l'heap cresce verso l'alto da un'estremità della memoria di un programma, mentre lo stack cresce verso il basso dall'altra. Stack e record di attivazione PSD 11  Ogni volta che viene invocato un metodo, nella memoria del computer viene creata una struttura chiamata record di attivazione , contenente tutte le sue variabili locali, parametri. I record di attivazione hanno un puntatore al record di attivazione del metodo chiamante, mostrato da una freccia tratteggiata nel diagramma. Quando si verifica ogni chiamata ricorsiva, viene creato un nuovo record di attivazione contenente nuove variabili locali, in modo che ogni chiamata distinta abbia le sue variabili. Parametri in entrata valore di ritorno deposito temporaneo informazioni di stato salvate parametri in uscita Ciclo di vita Il record di attivazione associato a una chiamata di funzione f: E’ creato al momento della invocazione di f Permane per tutto il tempo in cui f è in esecuzione E’ distrutto (deallocato) al termine dell’esecuzione La dimensione del record di attivazione varia da una funzione all’altra per una data funzione, è fissa e calcolabile a priori Esempio dello stack di un programma in C che esegue il fattoriale di 4! PSD 12  Ricorsione Tail Una funzione a ricorsione tail e’ chiamata tail se tutte le chiamate ricorsive sono in coda, quando e’ l’ultima istruzione ad essere eseguita e il suo valore di ritorno in una funzione non fa parte dell’espressione. Quando il compilatore rileva l’uso di una ricorsione tail, sovrascrive il record di attivazione corrente invece di pusharne uno nuovo nello stack. Il compilatore riesce a farlo perche’ la chiamata ricorsiva e’ l’ultima istruzione ad essere eseguita nell’attivazione corrente. Fattoriale ricorsione tail Il calcolo del fattoriale visto in precedenza con la classica ricorsione. In ogni attivazione, ripetendo n=n-1 fino a quando n = 1. Questa definizione non e’ in ricorsione tail perche’ il valore di ritorno di ogni attivazione dipende dal moltiplicare n volte il valore di ritorno della sottoseguente attivazione. Per rendere il calcolo del fattoriale in tail recursion, aggiungiamo un nuovo parametro a, inizialmente settato ad 1, che mantiene il valore del fattoriale calcolato finora nel processo ricorsivo. Questo ci evita di dover moltiplicare il valore restituito da ogni attivazione per n. PSD 13  Come funziona lo stack con la tail recursion. Analisi degli algoritmi Quando stiamo progettando un algoritmo o applicandone uno che e’ accettato apertamente, e’ importante capire come l’algoritmo si esibira’. Ci sono molte ragioni per capire le performance di un algoritmo. Comprendere il carico che un algoritmo impone a un'applicazione ci aiuta anche a pianificare come utilizzare l'algoritmo in modo più efficace. Ad esempio l’algoritmo del garbage collector che raccoglie in modo dinamico spazio di archiviazione per returnare l’heap richiede un tempo considerabile per essere eseguito. Analisi del caso peggiore la metrica con cui viene confrontata la maggior parte degli algoritmi. In altri casi considereremo il caso migliore. In ogni caso l’analisi del caso peggiore ci offre numerosi vantaggi. O-notation PSD 14  La notazione piu’ comune per esprimere le performance di un algoritmo. Viene utilizzato per esprimere l’upper bound di una funzione al’interno di un fattore costante. Complessita’ computazionale Il tasso di crescita e di risorse di un algoritmo richiede rispetto alla dimensione dei dati che tratta. O-Notation La notazione O e’ utilizzata per esprimere le prestazioni di un algoritmo in modo formale. La notazione O esprime il limite superiore di f(n). Normalmente esprimiamo le prestazioni di un algoritmo in funzione della dimensione dei dati che elabora. Cioe’ per alcuni dati di dimensione n , descriviamo le sue prestazioni con una funzione f(n). Regole della notazione O-Notation Quando osserviamo una funzione f(n) in termini di tasso di crescita , possiamo ignorare i termini costanti perche’ man mano che il valore di n diventa sempre più grande, alla fine i termini costanti diventeranno insignificanti. Ex. Ad esempio, se T (n) = n + 50 descrive il tempo di esecuzione di un algoritmo e n, la dimensione dei dati elaborati, è solo 1024, il termine costante in questa espressione costituisce già meno del 5% del tempo di esecuzione. Possiamo ignorare i moltiplicatori costanti dei termini perche’ anch’essi diventeranno insignificanti all’aumentare del valore di n. Ex. Ad esempio, se T1(n) = n2 e T2(n) = 10n descrivono i tempi di esecuzione di due algoritmi per risolvere lo stesso problema, n deve solo essere maggiore di 10 perché T1 diventi maggiore di T2. Infine, dobbiamo considerare solo il termine di ordine piu’ alto perche’, ancora una volta, all’aumentare di n, i termini di ordine superiore superano rapidamente quelli di ordine inferiore. Ex. PSD 15  Ad esempio, se T(n) = n2 + n descrive il tempo di esecuzione di un algoritmo e n è 1024, il termine di ordine inferiore di questa espressione costituisce meno dello 0,1% del tempo di esecuzione. I termini costanti sono espressi come O(1). Quando si analizza il tempo di esecuzione di un algoritmo, applicare questa regola quando si dispone di un attivita’ che si sa verra’ eseguita in un determinato periodo di tempo, indipendentemente dalle dimensioni dei dati elaborati. O c( ) = O( ) Le costanti moltiplicative vengono omesse. Quando si analizza il tempo di esecuzione di un algoritmo, applicare questa regola quando si dispone di un certo numero di attività che vengono eseguite tutte nello stesso periodo di tempo. Ad esempio, se tre attività vengono eseguite ciascuna nel tempo T(n) = n, il risultato è O(3n), che semplifica in O(n). Formalmente affermato, per qualche costante c: O(cT) = cO(T) = O(T).\ L'addizioneviene eseguita prendendo il massimo. Quando si analizza il tempo di esecuzione di un algoritmo, applicare questa regola quando un'attività viene eseguita dopo un'altra. Ad esempio, se T1(n) = n e T2(n) = n2 descrivono due attività eseguite in sequenza, il risultato è O(n) + O(n2), che semplifica in O(n2). Complessita’ Computazionale L’aspetto di interesse di un algoritmo e’ la sua complessita’, ovvero il tasso di crescita delle risorse che richiede rispetto alla dimensione dei dati che elabora. La notazione O descrive la complessita peggiore di un algoritmo semplicemente ispezionando la sua struttura complessiva. O(2!) Complessita’ Esempio Algoritmi Recupero del primo elemento arr elemento trovato al O(1) da un set di dati primo posto Dividere un set di dati a metà, O(log n) quindi dividere le metà a metà, Binary Search ecc. Attraversamento di un set di ricerca lineare in un array o O(n) dati lista Suddivisione ripetuta di un set O(n log n) di dati a metà e attraversamento Merge Sort, Quick Sort di ogni metà PSD 16  Attraversamento di un set di dati una volta per ogni membro Selection Sort, Insertion O(n2 ) di un altro set di uguali Sort, Bubble Sort dimensioni Generazione di tutti i possibili O(2 ) n sottoinsiemi di un insieme di ??? dati Generazione di tutte le possibili O(2!) ??? permutazioni di un set di dati Definizioni Importanti sugli alberi Ecco le definizioni di altezza, nodo e livello in un albero: 1. Nodo: Un nodo è l'elemento fondamentale di un albero. Ogni nodo contiene un valore o un dato, e può avere zero o più nodi figli, che sono a loro volta alberi. In un albero binario, ogni nodo può avere al massimo due figli : uno a sinistra e uno a destra. Il nodo principale dell'albero, da cui partono tutti gli altri nodi, è chiamato radice. 2. Livello: PSD 17  Il livello di un nodo è la distanza dalla radice, misurata in termini di numero di archi (o passaggi) necessari per raggiungere quel nodo a partire dalla radice. La radice dell'albero si trova al livello 0, i suoi figli diretti al livello 1, i figli di questi ultimi al livello 2, e così via. 3. Altezza: L'altezza di un albero è definita come la lunghezza del percorso più lungo dalla radice a un nodo foglia (un nodo senza figli). In altre parole, l'altezza è il numero massimo di archi tra la radice e una foglia. Per convenzione, l'altezza di un albero che consiste di un solo nodo (la radice) è 0. In un sottoalbero, l'altezza di un nodo è pari al massimo tra le altezze dei suoi figli, più uno. ADT BST L'ADT (Abstract Data Type) BST (Binary Search Tree) è una struttura dati molto utilizzata in informatica per organizzare e gestire dati in modo efficiente. Un albero binario di ricerca (BST) è un tipo specifico di albero binario che soddisfa alcune proprietà particolari che lo rendono adatto per operazioni di ricerca, inserimento e cancellazione. Caratteristiche principali di un BST: 1. Struttura ad Albero Binario: Un BST è costituito da nodi, e ogni nodo può avere al massimo due figli: uno a sinistra e uno a destra. 2. Proprietà di Ricerca Binaria: Per ogni nodo, i valori nel sottoalbero sinistro sono minori o uguali al valore del nodo, e i valori nel sottoalbero destro sono maggiori del valore del nodo. Questa proprietà è fondamentale perché permette di effettuare ricerche efficienti. 3. Ricerca, Inserimento e Cancellazione: Ricerca: Per trovare un elemento in un BST, si inizia dalla radice e si confronta l'elemento cercato con il valore del nodo corrente. Se è minore, si continua la ricerca nel sottoalbero sinistro; se è maggiore, nel sottoalbero destro. PSD 18  Inserimento: Inserire un nuovo nodo in un BST implica trovare la posizione corretta seguendo la stessa logica della ricerca, e quindi aggiungere il nodo come foglia. Cancellazione: Cancellare un nodo da un BST può essere più complesso, specialmente se il nodo da cancellare ha due figli. Esistono diverse strategie per gestire la cancellazione, mantenendo comunque la proprietà di ricerca binaria. 4. Complessità: Le operazioni sull’albero binario di ricerca hanno complessità O(h) , dove h è l’altezza dell’albero. Nel caso migliore, un BST bilanciato permette operazioni di ricerca, inserimento e cancellazione in tempo (O(log n)), dove n è il numero di nodi dell'albero. Nel caso peggiore, se l'albero è sbilanciato (per esempio, quando i nodi sono inseriti in ordine crescente o decrescente), la complessità può degenerare in O(n), rendendo il BST simile a una lista collegata. 1. BST Bilanciati: Per evitare i problemi legati agli alberi sbilanciati, esistono varianti di BST come gli alberi AVL o gli alberi Red-Black, che introducono meccanismi di bilanciamento automatico per garantire che l'albero resti il più possibile bilanciato. Alberi Bilanciati e Delta Bilanciati Un albero binario di ricerca si dice DELTA bilanciato se per ogni nodo la differenza (in valore assoluto) tra le due altezze è minore o uguale a DELTA. Per DELTA = 1 si parla di alberi bilanciati. Le operazione sull’albero binario di ricerca hanno complessità logaritmica se l’albero è DELTA bilanciato. Si può dimostrare che l’altezza dell’albero è DELTA + log2 n Alberi AVL L'Albero AVL: Un Albero Binario di Ricerca Bilanciato Cos'è un Albero AVL? PSD 19  L'albero AVL (dal nome dei suoi inventori Adelson-Velsky e Landis) è un tipo di albero binario di ricerca auto-bilanciato. La caratteristica principale di un albero AVL è che per ogni nodo, la differenza di altezza (o bilanciamento) tra i suoi sottoalberi sinistro e destro non può essere superiore a 1. Questo garantisce che l'altezza dell'albero sia sempre logaritmica rispetto al numero di nodi, migliorando l'efficienza delle operazioni di ricerca, inserimento e cancellazione. Proprietà principali: 1. Bilanciamento : Per ogni nodo dell'albero, la differenza di altezza tra il sottoalbero sinistro e quello destro (detta anche fattore di bilanciamento) deve essere -1, 0 o 1. 2. Auto-bilanciamento : Dopo ogni operazione di inserimento o cancellazione, l'albero potrebbe perdere il bilanciamento. In tal caso, vengono eseguite delle rotazioni (singole o doppie) per ristabilire il bilanciamento. Operazioni principali: 1. Ricerca: La ricerca di un elemento avviene come in un normale albero binario di ricerca, seguendo un percorso dal nodo radice verso le foglie. La complessità è O(log n)grazie al bilanciamento dell'albero. 2. Inserimento: Viene inserito un nuovo nodo come in un normale albero binario di ricerca. Dopo l'inserimento, si verifica il bilanciamento dell'albero risalendo verso la radice. Se il bilanciamento viene violato, si eseguono una o più rotazioni per ripristinarlo: Rotazione sinistra (Left Rotation, LR) Rotazione destra (Right Rotation, RR) Rotazione sinistra-destra (Left-Right Rotation, LR) Rotazione destra-sinistra (Right-Left Rotation, RL) 3. Cancellazione: Si rimuove il nodo come in un normale albero binario di ricerca. PSD 20  Dopo la cancellazione, si verifica il bilanciamento dell'albero risalendo verso la radice. Se il bilanciamento viene violato, si eseguono le rotazioni necessarie per ripristinarlo. Esempi di rotazioni: Rotazione destra (RR): Quando un nodo ha un fattore di bilanciamento di +2 e il suo sottoalbero sinistro ha un fattore di bilanciamento di +1, si esegue una rotazione destra per ridurre l'altezza del sottoalbero sinistro. Rotazione sinistra (LL): Quando un nodo ha un fattore di bilanciamento di -2 e il suo sottoalbero destro ha un fattore di bilanciamento di -1, si esegue una rotazione sinistra per ridurre l'altezza del sottoalbero destro. Rotazione sinistra-destra (LR): Se un nodo ha un fattore di bilanciamento di +2, ma il sottoalbero sinistro ha un fattore di bilanciamento di -1, si esegue prima una rotazione sinistra sul sottoalbero sinistro e poi una rotazione destra sul nodo principale. Rotazione destra-sinistra (RL): Se un nodo ha un fattore di bilanciamento di -2, ma il sottoalbero destro ha un fattore di bilanciamento di +1, si esegue prima una rotazione destra sul sottoalbero destro e poi una rotazione sinistra sul nodo principale. Vantaggi dell'albero AVL: Efficienza: Le operazioni di ricerca, inserimento e cancellazione hanno una complessità di O(logn), il che le rende efficienti anche per insiemi di dati molto grandi. Bilanciamento automatico: L'albero si bilancia automaticamente, evitando il degenerarsi in una lista lineare, cosa che può accadere negli alberi binari di ricerca non bilanciati. Svantaggi: Costi di aggiornamento: Il bilanciamento dell'albero richiede un costo aggiuntivo di tempo per l'esecuzione delle rotazioni durante l'inserimento e la cancellazione. Questo può rendere l'albero AVL meno adatto per applicazioni in cui gli inserimenti e le cancellazioni sono molto frequenti. PSD 21  Heap L'heap è una struttura dati molto utilizzata in informatica, specialmente nelle applicazioni che richiedono una gestione efficiente di priorità, come nel caso di code di priorità, algoritmi di ordinamento e gestione della memoria. L'heap è una struttura dati a forma di albero, tipicamente implementata come un heap binario. Proprietà fondamentali di un heap 1. Proprietà di Completezza: Un heap è un albero binario completo. Questo significa che ogni livello dell'albero è completamente riempito, eccetto forse l'ultimo livello, che deve essere riempito da sinistra a destra. 2. Proprietà di Heap: Max-Heap: In un max-heap, per ogni nodo, il valore del nodo è maggiore o uguale ai valori dei suoi figli. Il massimo valore si trova quindi alla radice dell'albero. Min-Heap: In un min-heap, per ogni nodo, il valore del nodo è minore o uguale ai valori dei suoi figli. Il minimo valore si trova quindi alla radice dell'albero. Implementazione dell'Heap Sebbene l'heap sia un albero, viene solitamente implementato utilizzando un array (vettore) per sfruttare la sua proprietà di completezza. Se l'indice di un nodo è \(i\), allora: Nodo genitore: si trova all'indice ⌊ i−1 2 ⌋ ​ Figlio sinistro: si trova all'indice (2i + 1) Figlio destro: si trova all'indice (2i + 2) Operazioni sull'Heap 1. Inserimento: Un nuovo elemento viene aggiunto alla fine dell'heap (cioè in fondo all'array). Si esegue il "risalimento" (o "up-heap" o "heapify up") dell'elemento aggiunto, confrontandolo con il suo genitore e scambiandoli se necessario, finché la proprietà di heap non è ripristinata. PSD 22  2. Estrazione del massimo/minimo (pop): Nel max-heap, il massimo (che si trova alla radice) viene rimosso. L'ultimo elemento dell'heap viene spostato alla radice. Si esegue il "discendimento" (o "down-heap" o "heapify down") di questo elemento, scambiandolo con il maggiore (o minore, nel caso di min-heap) dei suoi figli, finché la proprietà di heap non è ripristinata. 3. Costruzione dell'Heap: Per trasformare un array arbitrario in un heap, si può usare l'algoritmo di heapify, che procede dal primo nodo non foglia (metà dell'array) fino alla radice, eseguendo il "down-heap" per ogni nodo. 4. Heap Sort: Heap sort è un algoritmo di ordinamento che utilizza un heap per ordinare un array. Il processo consiste nel costruire un max-heap dall'array e poi ripetutamente estrarre il massimo (cioè, la radice del heap) e ridurre la dimensione dell'heap, spostando l'elemento massimo alla fine dell'array. Complessità delle operazioni Inserimento: (O(log n)) Estrazione del massimo/minimo: (O(log n)) Costruzione dell'heap: (O(n)) Heap Sort: (O(n log n)) Applicazioni dell'Heap 1. Code di priorità: L'heap è la struttura dati sottostante per implementare una coda di priorità, dove l'elemento con la massima (o minima) priorità viene servito per primo. 2. Heap Sort: Utilizzato per ordinare array in (O(n log n)),è un algoritmo di ordinamento in-place. 3. Gestione della memoria: Gli heap vengono utilizzati per la gestione dinamica della memoria, in particolare nel contesto della garbage collection. PSD 23  4. Algoritmi di grafi: L'heap è spesso usato in algoritmi come Dijkstra per trovare il percorso minimo, dove l'estrazione dell'elemento con il minimo costo è cruciale. Differenza tra Heap e Altre Strutture Un heap differisce da una struttura dati come l'albero binario di ricerca (BST) in quanto non impone un ordinamento tra fratelli (i figli di un nodo non hanno un ordine specifico tra di loro), mentre in un BST, ogni nodo a sinistra è minore e ogni nodo a destra è maggiore del nodo padre. In sintesi, l'heap è una struttura dati versatile e potente che bilancia efficienza e semplicità, risultando fondamentale in molti algoritmi e applicazioni di elaborazione dati. Adt Albero Un ADT (Abstract Data Type) Albero è una struttura dati gerarchica che si compone di nodi collegati tra loro tramite archi (o rami). È utilizzato per rappresentare dati con una relazione gerarchica naturale, come strutture a directory, alberi genealogici, espressioni matematiche e molto altro. Ecco una spiegazione dettagliata delle componenti e delle operazioni associate con un albero: Componenti di un Albero 1. Nodo: Un singolo elemento di un albero che contiene un valore o un dato. Ogni nodo può avere zero o più nodi figli. 2. Radice: Il nodo superiore dell'albero. È l'unico nodo che non ha alcun genitore. 3. Figlio: Un nodo che discende da un altro nodo. Il nodo superiore è chiamato genitore. 4. Foglia: Un nodo che non ha figli. 5. Sottoalbero: Un nodo e tutti i suoi discendenti formano un sottoalbero. 6. Altezza: La lunghezza del cammino più lungo dalla radice a una foglia. 7. Profondità: La lunghezza del cammino dalla radice a un dato nodo. 8. Livello: La distanza di un nodo dalla radice. La radice è al livello 0, i suoi figli al livello 1, e così via. PSD 24  9. Grado: Il numero di figli di un nodo. Il grado di un albero è il massimo grado di qualsiasi nodo nell'albero. Tipi di Alberi 1. Albero Generale: Ogni nodo può avere un numero qualsiasi di figli. 2. Albero Binario: Ogni nodo può avere al massimo due figli, chiamati figlio sinistro e figlio destro. 3. Albero Binario di Ricerca (BST): Un albero binario in cui per ogni nodo, tutti i nodi nel sottoalbero sinistro hanno valori minori o uguali al valore del nodo, e tutti i nodi nel sottoalbero destro hanno valori maggiori o uguali. 4. Albero Bilanciato: Un albero binario in cui la profondità dei due sottoalberi di ogni nodo differisce di al massimo uno. 5. Heap: Un albero binario completo in cui ogni nodo è maggiore o uguale (max-heap) o minore o uguale (min-heap) rispetto ai suoi figli. Operazioni Fondamentali sugli Alberi 1. Inserimento: Aggiungere un nodo in una posizione appropriata nell'albero. 2. Cancellazione: Rimuovere un nodo dall'albero e ristrutturare l'albero per mantenere le proprietà specifiche (ad esempio, nel caso di un albero binario di ricerca). 3. Ricerca: Trovare un nodo con un valore specifico. Può essere ottimizzato utilizzando strutture come BST. 4. Traversamento: Visitare tutti i nodi dell'albero in un ordine specifico. In-order (Visita Simmetrica): Visita il sottoalbero sinistro, il nodo radice, e poi il sottoalbero destro. Pre-order (Visita Predecessore): Visita il nodo radice, poi il sottoalbero sinistro e infine il sottoalbero destro. Post-order (Visita Successore): Visita il sottoalbero sinistro, poi il sottoalbero destro, e infine il nodo radice. Level-order (Visita per Livelli): Visita i nodi livello per livello dall'alto verso il basso. PSD 25