M;
ripeti fino a cella vuota, ricordare che, se M = 2*max, α < 1;
• importante: h non deve mai ritornare 0, altrimenti si entra in un ciclo infinito.
• 2
Complessità
Ipotesi: hashing semplice uniforme;
• probing uniforme.
•
Tentativi di “probing” per la ricerca:
search hit: 1/(1 – α));
• search miss: 1/α ln(1/(1 – α)).
•
Confronto tra alberi e tabelle di hash
Tabelle di hash:
più facili da realizzare;
• unica soluzione per chiavi senza relazione d'ordine;
• più veloci per chiavi semplici.
•
Alberi (BST e loro varianti):
meglio garantite le prestazioni (per alberi bilanciati);
• 45
permettono operazioni su insiemi con relazione d'ordine.
• Code a priorità e heap
Definizioni
Albero binario con:
• proprietà strutturale: quasi completo (tutti i livelli completi, tranne eventualmente
◦ l'ultimo, riempito da SX a DX), quasi bilanciato (i cammini radice-foglia sono
lunghi/uguali a meno di una differenza di lunghezza pari a 1);
proprietà funzionale: chiave massima nella radice.
◦
Implementazione: mediante vettore.
•
Heap → Molto utile per imporre un limite superiore allo sbilanciamento dell'albero e alla
memoria usata.
Implementazione
Struttura dati: vettore di Item h->A[0 … maxN – 1];
• h->heapsize(A): numero di elementi in heap h->A;
• radice in h->A[0];
• dato h->A[i]:
• il figlio SX è h->A[LEFT(i)] dove LEFT(i) = 2i + 1;
◦ il figlio DX è h->A[RIGHT(i)] dove RIGHT(i) = 2i + 2;
◦ il padre è h->A[PARENT(i)] dove PARENT(i) = (i – 1)/2.
◦
Funzione HEAPify
Trasforma in heap i, Left(i), Right(i), dove Left(i) e Right(i) sono già heap.
• Assegna ad A[i] il max tra A[i], A[Left(i)] e A[Right(i)].
• Se c'è stato cambio A[i] ↔ A[Left(i)] applica ricorsivamente HEAPify su sottoalbero con
• radice Left(i).
Analogamente per scambio A[i] ↔ A[Right(i)].
• Complessità: T(n) = O(lgn).
•
Funzione HEAPbuild
Trasforma un albero binario memorizzato in vettore A in uno heap:
le foglie sono heap;
• applica HEAPify a partire dal padre dell'ultima foglia o coppia di foglie fino alla radice;
• 46
complessità: T(n) = O(n).
•
Funzione HEAPsort
Trasforma il vettore in uno heap mediante HEAPbuild:
scambia il primo e ultimo elemento;
• riduci la dimensione dello heap di 1;
• ripristina la proprietà di heap;
• ripeti fino a esaurimento dello heap.
•
Caratteristiche:
complessità: T(n) = O(n lgn);
• in loco;
• non stabile.
•
Coda a priorità
Definizione:
struttura dati PQ per mantenere un set di elementi di tipo Item, ciascuno dei quali include un
• campo priorità;
operazioni principali: inserzione, estrazione del massimo, lettura del massimo, cambio di
• priorità.
Implementazione della struttura dati:
vettore/lista non ordinato;
• vettore/lista ordinato;
• heap di dati/indici.
•
ADT coda a priorità: I soluzione
La coda a priorità contiene dati, l'ADT è una struct con:
la coda a priorità: vettore (heap) pq->A di dati di tipo Item;
• heapsize: intero.
•
Funzione PQinsert
Aggiunge una foglia all'albero (cresce per livelli da SX a DX, rispettando la proprietà
• strutturale).
Risale dal nodo corrente (inizialmente la foglia appena creata) fino al più alla radice.
• Confronta la chiave del dato contenuto nel padre con la chiave del dato da inserire,
facendo scendere il dato del padre nel figlio se la chiave da inserire è maggiore,
altrimenti inserisce il dato nel nodo corrente. 47
Complessità: T(n) = O(logn).
Funzione PQextractMax
Modifica l'heap, estraendone il valore massimo, che è contenuto nella radice:
scambia la radice con l'ultima delle foglie (quella più a destra nell'ultimo livello);
• riduce di 1 la dimensione dell'heap;
• ripristina le proprietà dell'heap mediante applicazione di HEAPify.
•
Complessità: T(n) = O(logn).
Funzione PQchange
Modifica la priorità di un elemento in posizione data (si conosce l'indice nell'heap a cui
• si trova l'elemento).
Risale dalla posizione data fino al più alla radice confrontando la chiave del padre con la
• chiave modificata, facendo scendere la chiave del padre nel figlio se la chiave modificata
è maggiore, altrimenti la inserisce nel nodo corrente.
Applica HEAPify a partire dalla posizione data.
•
Complessità: T(n) = O(logn).
Sequenzializzazione della funzione di insert a partire da un indice noto.
ADT coda a priorità: II soluzione
La coda a priorità contiene gli indici dei dati. L'ADT è una struct che contiene:
1. la tabella di simboli pq->tab che contiene i dati di tipo Item;
2. la coda a priorità: vettore (heap) pq->A di indici (interi);
3. il vettore pq->qp per memorizzare a quale indice nello heap della coda a priorità si trova
un certo dato;
4. pq->heapsize: intero.
Il client fornisce e riceve i dati.
• La tabella di simboli memorizza i dati e gestisce la corrispondenza dato/indice e
• indice/dato. Il costo di queste operazioni dipende dall'implementazione della tabella di
simboli.
La coda a proprietà memorizza gli indici dei dati.
• Le decisioni sono prese in base ai confronti sulle proprietà dei dati.
• In un'ottica di modularità si disaccoppiano la coda a priorità e la tabella di simboli dei
• dati. 48
ADT di I cat. coda a priorità di indici
Scelta della tabella di simboli:
la complessità di PQchange dipende da quella della ricerca dell'indice in un tabella di
• simboli che corrisponde a un certo elemento;
tabelle basate su vettori/liste: O(n);
• tabelle di hash: O(1) nel caso medio.
•
Si implementa la tabella di simboli mediante una tabella di hash (open addressing con linear
probing).
Funzione PQinsert
Procede come nel caso di PQ di item:
inserendo l'elemento nella tabella di simboli;
• risalendo dal nodo corrente (inizialmente la foglia appena creata) fino al più alla radice.
• Poiché lo heap contiene indici e non dati, si usa la tabella di simboli per ottenere il dato
contenuto nel padre, la cui chiave è confrontata con la chiave del dato da inserire;
mantenendo aggiornato il vettore pq->qp.
•
Funzione PQextractMax
Modifica lo heap, estraendone il valore massimo, che è contenuto nella radice:
scambia la radice con l'ultima delle foglie (quella più a destra nell'ultimo livello);
• riduce di 1 della dimensione dello heap;
• ripristina le proprietà dello heap mediante applicazione di HEAPify;
• l'accesso al dato avviene attraverso la tabella di simboli;
• HEAPify e SWAP aggiornano anche pq->qp.
•
Funzione PQchange
La tabella di hash ritorna con costo unitario l'indice dell'elemento.
• Il vettore pq->qp, dato l'indice precedente, ritorna con costo unitario la posizione
• dell'elemento nello heap.
Si risale dalla posizione data fino al più alla radice confrontando la chiave del padre con
• la chiave modificata, facendo scendere la chiave del padre nel figlio se la chiave
modificata è maggiore, altrimenti la inserisce nel nodo corrente.
Si applica HEAPify a partire dalla posizione data.
• 49
Il paradigma greedy
Definizioni
Il paradigma greedy è un'alternativa all'esplorazione esaustiva dello spazio delle possibilità per i
problemi di ottimizzazione:
a ogni passo: per trovare una soluzione globalmente ottima si scelgono soluzioni
• localmente ottime;
le scelte fatte ai singoli passi non vengono successivamente riconsiderate (no backtrack);
• scelte localmente ottime sulla base di una funzione di appetibilità (costo).
•
Vantaggi:
algoritmo molto semplice;
• tempo di elaborazione molto ridotto.
•
Svantaggi: soluzione non necessariamente ottima.
Algoritmo
Appetibilità note in partenza e non modificate:
partenza: soluzione vuota;
• ordina le scelte per appetibilità decrescenti;
• esegui le scelte in ordine decrescente, aggiungendo, ove possibile, il risultato alla
• soluzione.
Appetibilità modificabili: come prima con modifica delle appetibilità e coda a priorità.
Selezione di attività
Input: insieme di n attività caratterizzate da tempo di inizio e tempo di fine [s, f).
• Output: insieme con il massimo numero di attività compatibili.
• Compatibilità: [s , f ) e [s , f ) non si sovrappongono, cioè s ≥ f oppure s ≥ f .
• i i j j i j j i
Approccio greedy: ordinamento delle attività per tempo di fine crescente, si poteva anche
• ordinare per tempo di inizio crescente o durata crescente, dipende molto dalla
distribuzione.
Il cambiamonete
Input: monetazione, resto da erogare.
• Output: resto con numero minimo di monete.
• Appetibilità: valore della moneta.
• 50
Approccio greedy: a ogni passo moneta di maggior valore inferiore al resto residuo.
•
Il problema dello zaino
Dato un insieme di N oggetti ciascuno dotato di peso w e di valore v e dato un peso massimo
j j
cap, determinare il sottoinsieme S di oggetti tali da massimizzare il costo di ogni elemento
rispetto la capienza massima.
Approccio greedy:
ordino gli oggetti per valore specifico decrescente e aggiungo l'oggetto con massimo
• valore specifico compatibile con il peso disponibile;
se ogni oggetto può essere preso per una sua frazione, ad ogni passo aggiungo la frazione
• di oggetto a massimo valore specifico compatibile con il peso disponibile.
Codici di Huffman (1950)
Codice: stringa di bit associata ad un simbolo s appartenente a S:
• a lunghezza fissa;
◦ a lunghezza variabile;
◦
Codifica: da simbolo a codice;
• Decodifica: da codice a simbolo.
•
Codici a lunghezza fissa:
numero di bit n = log (card(S));
• 2
vantaggio: facilità di decodifica;
• uso: simboli isofrequenti.
•
Codici a lunghezza variabile:
svantaggio: difficoltà di decodifica;
• vantaggio: risparmio di spazio di memoria;
• uso: simboli con frequenze diverse;
• esempio: alfa
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
-
Algoritmi - Programmazione I
-
Algoritmi - Appunti
-
Algoritmi e strutture dati
-
Programmazione e algoritmi 2