Estratto del documento

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

Anteprima
Vedrai una selezione di 15 pagine su 67
Algoritmi e Programmazione - Appunti Pag. 1 Algoritmi e Programmazione - Appunti Pag. 2
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 6
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 11
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 16
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 21
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 26
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 31
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 36
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 41
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 46
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 51
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 56
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 61
Anteprima di 15 pagg. su 67.
Scarica il documento per vederlo tutto.
Algoritmi e Programmazione - Appunti Pag. 66
1 su 67
D/illustrazione/soddisfatti o rimborsati
Acquista con carta o PayPal
Scarica i documenti tutte le volte che vuoi
Dettagli
SSD
Scienze matematiche e informatiche INF/01 Informatica

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher federico.brunero di informazioni apprese con la frequenza delle lezioni di Algoritmi e programmazione avanzato e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Torino o del prof Cabodi Giampiero.
Appunti correlati Invia appunti e guadagna

Domande e risposte

Hai bisogno di aiuto?
Chiedi alla community