Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 1
Algoritmi e complessitàAlgoritmi e complessità
La complessitàLa complessitàComplessità in tempo e spazioComplessità in tempo e spazioComplessità asintoticaComplessità asintotica
Algoritmi e complessitàAlgoritmi e complessitàRicerca e ordinamentoRicerca e ordinamento
La macchina di Turing e le classi La macchina di Turing e le classi di complessitàdi complessità
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 2
La complessitàLa complessità
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 3
La complessitàLa complessità
L’analisi di complessità definisce le risorse teoricamente consumate da un algoritmo
complessità temporalecomplessità temporale: tempo necessario all’esecuzione dell’algoritmocomplessità spazialecomplessità spaziale: memoria necessaria all’esecuzione dell’algoritmo
Poiché ad ogni algoritmo corrispondono più implementazioni (più programmi), lo studio della complessità non definisce esattamente il tempo e la memoria usata: si concentra sulle proprietà che sono indipendenti dell’implementazione fornendo un’idea di quanto sia efficiente un algoritmo
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 4
Complessità temporaleComplessità temporaleSi contano le istruzioni eseguite dall’algoritmoPoiché le istruzioni potrebbero essere di natura diversa, si individuano quelle che incidono principalmente sul tempo di esecuzione
Le operazioni in virgola mobileLe operazioni in virgola mobile: le più lente da eseguire per una CPU; sono predominanti se il loro numero è paragonabile al numero delle altre istruzioni Le istruzioni di controlloLe istruzioni di controllo (gli ifif) e le istruzioni più frequenti (sono predominanti se sono in numero molto superiore alle altre istruzioni)Le istruzioni di accesso alla memoria secondaria e alle Le istruzioni di accesso alla memoria secondaria e alle perifericheperiferiche: sono decine di migliaia di volte più lente delle sono decine di migliaia di volte più lente delle istruzioni svolte nella memoria principaleistruzioni svolte nella memoria principale; se un’applicazione ne richiede molte, queste potrebbero essere predominanti (ad es., nei database, l’analisi di complessità è concentrata sugli accessi al disco)
Che cosa si misura? Che cosa si misura? 1 1
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 5
Complessità spazialeComplessità spazialeSi misurano le “posizioni” di memoria occupate dai dati necessari allo svolgimento dell’algoritmoLa complessità spaziale sarà misurata relativamente alla memoria principale se i dati dell’algoritmo possono essere allocati in memoria principale, in base all’occupazione di memoria secondaria quando le strutture dati dell’algoritmo sono troppo grandi per poter risiedere nella memoria centrale
Che cosa si misura? Che cosa si misura? 2 2
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 6
Lo studio della complessità si concentra su i casi in cui il problema è grande:
non importa se un programma di contabilità impiega 1 o 100 millisecondi a calcolare il bilanciocambia molto se il programma della segreteria impiega 1 o 10 secondi a trovare i dati di uno studente nell’archivio
Complessità asintoticaComplessità asintotica Definisce le risorse usate da un algoritmo al crescere della dimensione del problema affrontatoAd esempio: come cambia il tempo di accesso ai dati quando cresce il numero degli studenti nell’archivio della segreteria
Complessità asintoticaComplessità asintotica
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 7
Formalmente, si usa il concetto matematico di ordine ordine di grandezzadi grandezza
sia n la dimensionedimensione del problema, cioè la dimensione dell’input dell’algoritmosia T(n) il tempotempo impiegato per l’esecuzione dell’algoritmo quando l’ingresso ha dimensione nsia f(n) una qualsiasi funzione di n, ad esempio 3, n, n2, n5, 2n Si dice che la complessità asintotica dell’algoritmo è è dell’ordine di dell’ordine di ff((nn)) e si scrive OO ((ff((nn)))) se esiste una costante tale che T(n) f(n)
Osservazione importanteOsservazione importante: in base alla definizione data, algoritmi che differiscono solo per una costante moltiplicativa hanno lo stesso ordine di complessitàEsempioEsempio: due algoritmi che richiedono 4n e 7n operazioni sono entrambi O (n)
Complessità temporale Complessità temporale asintotica asintotica 1 1
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 8
Informalmente…L’ordine O (f(n)) fornisce una misura della complessità temporale di ogni programma che implementa l’algoritmo
EsempioEsempio: Calcolare la somma degli elementi di un array n: numero di elementi dell’array
complessità: O (n)
Complessità temporale Complessità temporale asintotica asintotica 2 2
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 9
Un algoritmo può richiedere un numero di operazioni diverse per ingressi di dimensione uguale:
complessità mediacomplessità media: complessità valutata su tutti i possibili ingressicomplessità nel caso peggiorecomplessità nel caso peggiore: complessità dell’algoritmo per l’ingresso che richiede più operazioni
Di solito, quando si parla di complessità, ci si riferisce alla complessità nel caso peggiore
Complessità media e relativa al caso Complessità media e relativa al caso peggiorepeggiore
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 10
Arrayn: numero degli elementi dell’arrayRicerca/inserimento/cancellazione di un elemento
Complessità O (n)
Liste semplicin: numero delle posizioni nella listaRicerca/cancellazione di un elemento
Complessità O (n)Inserimento di un elemento all’inizio della lista (in testa)
Complessità O (1)
Complessità asintotica: array e Complessità asintotica: array e listeliste
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 11
Alberi binari di ricercan: numero dei nodi dell’alberoInserire, eliminare o ricercare un elemento in un albero binario bilanciato
Complessità: O (log2n)
Complessità asintotica: alberi Complessità asintotica: alberi binaribinari
6
3
1
8
4 7 9
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 12
Complessità asintotica: tabelle Complessità asintotica: tabelle hashhash
ProblemaProblemaMemorizzare in maniera opportuna un insieme di dati tipicamente sotto forma di record in modo da poter reperire un qualsiasi elemento dell’insieme con un numero “piccolo” di tentativi
Cosa significa “piccolo” ?Indipendente (o quasi) dalla dimensione della tabella su cui si effettua la ricerca, quindi con una complessità in tempo pari ad O (1)
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 13
Funzioni hash Funzioni hash 1 1
h: K → {0, 1, 2, …, m–1}
K: insieme dei valori distinti che possono essere
assunti dalle chiavi dei record m: dimensione del vettore in cui si intende memorizzare la tabella
IpotesiIpotesi: K sottoinsieme dei numeri naturaliPossibile funzione di accesso:
h(k) k MOD m, kKValore della funzione sempre compreso fra 0 e m–1
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 14
Funzioni hash Funzioni hash 2 2
Se K non è un sottoinsieme dei numeri naturaliEsempioEsempio: insieme di stringhe alfanumericheLa funzione hash si applica a numeri
Per utilizzarla in corrispondenza di una chiave non numerica occorre associare alla chiave un valore numerico
Necessità di definire funzioni hash generaliAssociazione di un valore numerico ad una chiave di qualunque tipoApplicazione della funzione hash a tale valore
EsempioEsempio: si utilizza la somma dei codici ASCII dei caratteri che costituiscono la stringa
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 15
Collisioni Collisioni 1 1
Associazione, da parte di una trasformazione, della stessa posizione a chiavi distinteSinonimiSinonimiEsempioEsempio: [10,12,20,23,27,30,31,39,42,44,45,49,53,57,60]
h(chiave) (chiave MOD 15)Posizione 0 ← 30, 45, 60Posizione 8 ← 23, 53Posizione 12 ← 12, 27, 42, 57
Ciascuna posizione dell’array può contenere al più un elemento; occorre…
Ridurre al massimo le collisioniGestirle quando si verificano
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 16
Collisioni Collisioni 2 2
Funzioni di hashing perfettohashing perfetto (che evitano i duplicati) sono rare, anche per tabelle grandi
EsempioEsempio: paradosso del compleannoparadosso del compleanno Dato un gruppo di 23 persone, ci sono più del 50% di probabilità che due di esse siano nate nello stesso giorno dell’anno In altre parole, se scegliamo una funzione aleatoria (a
valori casuali) che trasforma 23 chiavi in un indirizzo di una tabella di 365 elementi, la probabilità che due chiavi NON collidano è solo 0.4927 (meno della metà)
Individuare una funzione di accesso che porti ad un numero ridotto di collisioni è un problema complesso
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 17
Collisioni Collisioni 3 3
Tuttavia… numero di collisioni ridotto drasticamente se accettiamo uno spreco del 25% di memoria extraEsempioEsempio: array di 19 elementi (indicizzati da 0 a 18)
Posizione 0 ← 57 Posizione 8 ← 27Posizione 1 ← 20, 39 Posizione 10 ← 10Posizione 3 ← 60 Posizione 11 ← 30, 49Posizione 4 ← 23, 42 Posizione 12 ← 12, 31Posizione 6 ← 44 Posizione 15 ← 53Posizione 7 ← 45
Collisioni non eliminate del tutto 18
17
16
5315
14
13
12, 3112
30, 4911
1010
9
278
457
446
5
23, 424
603
2
20, 391
570
18
17
16
5315
14
13
12, 3112
30, 4911
1010
9
278
457
446
5
23, 424
603
2
20, 391
570
h(chiave) (chiave MOD 19)
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 18
Gestione delle collisioni Gestione delle collisioni 1 1
Uso di liste concatenate destinate alla memorizzazione degli elementi che, in inserimento, hanno portato ad una collisioneRicerca di un elemento di chiave k
Si calcola h(k)Se si verifica una collisione allora si accede alla lista associata alla posizione h(k) e la si scandisce
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 19
Gestione delle collisioni Gestione delle collisioni 2 2
Il costo dell’operazione di ricerca realizzata in modo lineare relativamente alle liste di elementi in collisione si mantiene pressoché indipendente da n (numero degli elementi contenuti nella tabella)
Inserimento/cancellazione costano O (1)
Metodo non adatto a reperire sottoinsiemi di dati con chiave che soddisfi una data relazione
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 20
Sia dato un programma che prende in ingresso i partecipanti ad una competizione e genera (ad esempio per stamparle) tutte le possibili classifiche finali
n: numero di partecipantiComplessità: O (n!)
Si osservi che n! è un numero molto grande anche per n relativamente piccoli
20! 2.432.902.008.176.640.0002.41018
Complessità asintotica Complessità asintotica fattorialefattoriale
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 21
Sia dato un programma che ha come ingresso due array a, b e cerca tutte le coppie (i,j) tali che a[i]b[j]
n: dimensione di am: dimensione di b
Complessità: O (nm)
Complessità asintotica Complessità asintotica polinomialepolinomiale
void search(int a[], int b[], int alength, int blength)
{ … for(i0;ialength;i){ for(j0;jblength;j){ if(a[i]b[j])
printf(“Trovata corrispondenza: a[%d]b[%d]%d”, i, j, a[i]); } }}
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 22
In base alla loro complessità temporale asintotica, gli algoritmi sono tipicamente divisi in classi
Algoritmi a complessità costantecomplessità costante O O (1)(1) o linearelineare O O ((nn))Molto veloci, “scalabili”
Algoritmi a complessità polinomiale complessità polinomiale OO ((nnaa)) per un qualche valore a
Usabili se l’esponente a è piccolo
Algoritmi a complessità esponenziale complessità esponenziale OO ((aann)) per un qualche valore a (1)
Usabili solo per n molto piccoli
Algoritmi facili e difficiliAlgoritmi facili e difficili
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 23
FondamentaleFondamentale: perché gli algoritmi a complessità esponenziale sono considerati quasi inusabili?
Perché richiedono talmente tante operazioni che probabilmente anche i calcolatori futuri non saranno in grado di eseguire in tempi ragionevoli le loro possibili implementazioni (programmi) per dati in ingresso ad alta dimensionalità
Algoritmi a complessità Algoritmi a complessità esponenzialeesponenziale
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 24
EsempioEsempio
Si consideri il programma che genera tutte le classifiche finali di una competizione con n partecipanti, complessità O (n!) (è esponenziale, perché )
Con 20 concorrenti le classifiche sono 20! 2.41018
Un computer che generi 1 miliardo di classifiche al secondo, circa 31016 l’anno, impiegherebbe circa 79 anni per generare tutte le classifiche richiesteTendenzialmente, i computer diverranno sempre più veloci e fra dieci anni forse saranno abbastanza veloci da realizzare in un mese quello per cui adesso occorrono 79 anni ma……comunque, fra dieci anni per risolvere il problema con 21 partecipanti occorreranno ancora 21 mesi e per 25 partecipanti circa 531300 anni!!
nnn !
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 25
Algoritmi e complessitàAlgoritmi e complessità
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 26
Per “cercare” un elemento in un vettore ordinatoordinato esiste un metodo detto ricerca binariaricerca binaria o dicotomicadicotomica
Si confronta il valore valval da ricercare con l’elemento centrale del vettore A[length/2]A[length/2]Se valval è minore dell’elemento mediano, si ripete la ricerca sulla metà sinistra del vettore, altrimenti si ricerca nella metà destra
La ricerca dicotomica La ricerca dicotomica 1 1
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 27
La ricerca dicotomica La ricerca dicotomica 2 2
EsempioEsempio: ricerca del numero 23
0 27
30
34
35
23
20
16
13
98542
Si confronta 23 con 13
Ci si concentra sulla metà destra (da ind. 8 a ind. 14): si confronta 23 con 27
0 27
30
34
35
23
20
16
13
98542
0 27
30
34
35
23
20
16
13
98542
0 27
30
34
35
23
20
16
13
98542
Ci si concentra sulla metà sinistra (da ind. 8 a ind. 10): si confronta 23 con 20
Ci si concentra sulla metà destra (da ind. 9 a ind. 9): trovato!!
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 28
Implementazione della ricerca Implementazione della ricerca dicotomicadicotomica
int search(int val, int A[], int from, int to){ int center(fromto)/2;
if (from to) return 1; if (fromto) {
if (A[from]val) {return from;} return 1;} // si esegue solo se A[from]!val
//si esegue solo se (fromto) if (valA[center]){ return search(val,A,from,center1);} if (valA[center]){ return search(val,A,center1,to);} return center;
}
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 29
Complessità della ricerca Complessità della ricerca dicotomicadicotomica
La ricerca dicotomica divide il vettore in due ad ogni passo:
dopo p passi la dimensione del vettore è
nel caso peggiore, la ricerca si ferma quando è 1, cioè quando plog2n
Quindi la ricerca dicotomica è O (log2n)
p
n
2
p
n
2
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 30
Mergesort Mergesort 1 1
Il MergesortMergesort è un algoritmo basato sul paradigma del divide et imperadivide et impera
Una strategia divide et imperadivide et impera consiste nel suddividere un problema in sottoproblemi, nel risolvere i sottoproblemi, e nel ricomporli per ottenere la soluzione del problema originale
Il Mergesort è composto da due fasi:una fase di divisione del vettore da ordinare in sottovettoriuna fase di ricomposizione dei risultati (merge)
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 31
Mergesort Mergesort 2 2
IdeaIdeaDato un vettore da ordinare, lo si divide in due sottovettori di ugual dimensione, si ordinano i sottovettori e poi si “fondono” insieme
6 5743821
6 821 5743
1 862 3 754
1 8765432
Fusione
Ordinamento Ordinamento
Divisione
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 32
Mergesort: la divisione ricorsivaMergesort: la divisione ricorsiva
Come si ordinano i due sottovettori ?Applicando ricorsivamentericorsivamente la divisione fino a quando il vettore contiene un solo elemento: in tal caso l’ordinamento è banale
6 5743821
Divisione6 821 5743
6 1 2 8 3 4 7 5
3 4 7 56 1 2 8
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 33
Mergesort: la fusione ricorsiva Mergesort: la fusione ricorsiva 11
I sottovettori ordinati verranno poi ricorsivamente fusi
1 8765432
Fusione1 862 7543
1 6 2 8 3 4 5 7
3 4 7 56 1 2 8
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 34
Mergesort: la fusione ricorsiva Mergesort: la fusione ricorsiva 22
La fusione viene realizzata utilizzando due indici che scorrono i due sottovettori da fondere:
1. Ad ogni passo si confrontano i due elementi indicati dagli indici i e j, A[i], A[j]
2. Si copia l’elemento minore in un vettore d’appoggio e si incrementa l’indice corrispondente
3. Si torna al passo 1. fino a quando i due vettori non sono stati completamente visitati
1 2 6 8
3 4 5 7i
j
1 32 4 5 6 7 8
k
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 35
Complessità del MergesortComplessità del Mergesort
Il Mergesort ha complessità O (nlog2n) sia nel caso medio che nel caso pessimoMergesort è un algoritmo ottimoottimo!
La sua complessità asintotica è la migliore possibile
Comunque……esistono algoritmi che per alcuni ingressi fanno meglio di nlog2n (ad es., Bubblesort su vettori ordinati)
…esistono altri algoritmi con complessità nlog2n nel caso pessimo HeapsortHeapsort
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 36
Quicksort Quicksort 1 1
QuicksortQuicksort, come Mergesort, è un algoritmo divide et imperadivide et impera
IdeaIdeaSi divide il vettore A in due sottovettori, che contengono rispettivamente tutti gli elementi maggiori e minori di (per esempio) A[0], cioè il primo elemento del vettore detto pernopernoSi ripete ricorsivamente la divisione…
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 37
3 12 5786
3 5786412
1 32
Si ripartisce il vettore rispetto ad A[1] 4
Si divide rispetto a 3
1 2
8765
Si divide rispetto a 6
5 87
Quicksort Quicksort 2 24 5783612
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 38
Quicksort: l’operazione pernoQuicksort: l’operazione perno 1 1
Come si divide il vettore?Si usano due indici i, j che scorrono il vettore da sinistra e da destra, rispettivamente
L’indice i scorre fino a quando A[i]A[1]
L’indice j scorre fino a quando A[j]A[1]
Si effettua lo scambio fra A[i] e A[j] e quindi si procede come sopra
4 5713682
i j
Si scorrono i, j confrontando con 4
4 5713682
i j
Si scambiano gli elementi
4 5783612
i j
Si scorrono i, j confrontando con 4
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 39
Quicksort: l’operazione perno Quicksort: l’operazione perno 2 2
Alla fine si scambia il perno con l’elemento in posizione j
4 5783612
i j
Si scambiano gli elementi
4 5786312
Si scambia A[j] con il perno
j
3 5786412
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 40
ImplementazioneImplementazione
void perno(int A[], int from, int to)
{
int ifrom1, jto; while(ij){ while(A[i]A[from]) i; while(A[j]A[from]) j; if(ij) scambia(A,i,j);
}
scambia(A,from,j);}
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 41
Complessità del QuicksortComplessità del Quicksort
Il Quicksort ha complessità media O (nlog n)
Il caso pessimo si verifica quando il perno finisce in fondo o in testa al vettore
In tal caso, Quicksort ha complessità pari ad O (n2)
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 42
Mergesort vs QuicksortMergesort vs Quicksort
Mergesort ha il vantaggio di avere complessità sempre O (nlog n)
Quicksort ha il vantaggio di non richiedere un vettore di appoggio: ordina il vettore “in loco” (minore complessità spaziale)
In media, Quicksort si comporta “bene” e, per questo motivo, in pratica spesso è preferito a Mergesort
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 43
Heap Heap 1 1
Ospita gli elementi dell’insieme A di cardinalità n, su cui è definita una relazione d’ordine totale “” Lo heapheap (mucchio) è un albero binario
Proprietà 1Proprietà 1L’albero è quasi perfettamente bilanciato
È completo fino al livello k1, cioè contiene il numero massimo di nodi, 2k1, mentre al livello k contiene un numero di nodi (foglie) compreso tra 1 e 2k
I nodi a livello massimo sono tutti addossati a sinistra Proprietà 2Proprietà 2
Ogni nodo contiene un elemento dell’elemento contenuto nel padre
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 44
Heap Heap 2 2
Noto il valore di n, la forma dell’albero è fissata dalla Proprietà 1L’allocazione degli elementi nei nodi può variare, nel rispetto della Proprietà 2L’elemento massimo dell’insieme è allocato nella radiceNello heap, i sottoalberi di ciascun nodo sono ancora heapLo heap può essere allocato in un array
2338
18
2217
510
2812
63
1 2 3 4 5 6 7 8 9 10
63 3823
12
28
17
22
10 5 18
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 45
Heap Heap 3 3
Con l’allocazione lineare…A[1] è l’elemento contenuto nella radice dello heap
Per ogni A[i], gli elementi corrispondenti ai figli sinistro e destro, se esistono, sono memorizzati in A[2i] e A[2i1]
Se 2in e/o 2i1n il figlio sinistro e/o destro di A[i] non esiste nell’albero
A[2i]A[i] e A[2i1]A[i], quando tali elementi sono definiti
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 46
Heapsort Heapsort 1 1
Lo heap trova la sua applicazione più elegante nel metodo di ordinamento noto come HeapsortHeapsort
Si estrae l’elemento massimo dallo heap (quello nella radice, o in prima posizione nella rappresentazione lineare)Si ricostruisce lo heap…fino a quando non ci sono più elementi nello heap (ovvero gli elementi del vettore sono ordinati)
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 47
Heapsort Heapsort 2 2
Come si ricostruisce lo heap, dopo l’estrazione della radice?
1 2 3 4 5 6 7 8 9 10
63 3823
12
28
17
22
10 5 18
1 2 3 4 5 6 7 8 9 10
18 3823
12
28
17
22
10 5 63
2338
18
2217
510
2812
63
2338
2217
510
2812
18
ContinuaContinua……
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 48
Heapsort Heapsort 3 3
Si considera il massimo fra i due figli della radice e, se max{A[2],A[3]}A[1], si effettua lo scambio
1 2 3 4 5 6 7 8 9 10
18 3823
12
28
17
22
10 5 63
1 2 3 4 5 6 7 8 9 10
3818
23
12
28
17
22
10 5 63
2338
2217
510
2812
18
2318
2217
510
2812
38
Si scambia A[1] con A[2]Si scambia A[1] con A[2]
ContinuaContinua……
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 49
Heapsort Heapsort 4 4
Si considera il massimo fra i due figli di A[2] e, se max{A[4],A[5]}A[2], si effettua lo scambio
1 2 3 4 5 6 7 8 9 10
38 18 23 12 28 17 22 10 5 63
1 2 3 4 5 6 7 8 9 10
38 28 23 1218
17 22 10 5 63
2318
2217
510
2812
38
2328
2217
510
1812
38
Si scambia A[2] con A[5]Si scambia A[2] con A[5]
ContinuaContinua……
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 50
Heapsort Heapsort 5 5
Si estrae A[1] che è l’elemento più grande… e si ricomincia il procedimento di ricostruzione
1 2 3 4 5 6 7 8 9 10
38 2823
12
18 17 2210
5 63
1 2 3 4 5 6 7 8 9 10
5 28 23 12 18 17 22 1038
63
2328
2217
510
1812
38
2328
2217
10
1812
5
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 51
Poiché ogni estrazione e ricostituzione dello heap richiede tempo O (log2n'), se n′ è il numero di elementi attualmente contenuti nello heap…
Heapsort ha complessità O (nlog2n)
L’algoritmo di ordinamento può essere realizzato facilmente sulla “rappresentazione sequenziale” dello heap
Heapsort Heapsort 6 6
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 52
void heapsort(int a[], int left, int right) {
int k, temp, sizerightleft1, *paleft1;
/* si costruisce lo heap */for (ksize2; k1; k)
heap(p, k, size); /* si scambia l’elemento più grande con quello
finale * e si ricostruisce lo heap */
while (size1) {
temp p[1]; p[1] p[size]; p[size] temp; heap(p, 1, size);
}exit(0);
}
Heapsort Heapsort 7 7
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 53
/* Costruzione topdown di uno heap */#define LESS(A,B)((A)(B))
void heap(int a[], int k, int size) {
int j, temp; while (2ksize) { j 2k; if (jsize && LESS(a[j],a[j1]))
j; if (!LESS(a[k],a[j]))
break; temp a[k]; a[k] a[j]; a[j] temp; k j;}
}
Heapsort Heapsort 8 8
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 54
Ancora sulla complessitàAncora sulla complessità
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 55
Problemi e algoritmiProblemi e algoritmi
Anche per i problemi si parla di complessitàTipicamente non si riesce a definire univocamente la complessità di un problema, perché...
...lo stesso problema può essere risolto con algoritmi diversi che hanno diversa complessità…anche se si riesce a stabilire qual è il miglior algoritmo per la risoluzione di un dato problema, tale stima ha comunque un valore non assoluto, ma limitato nel tempo, in quanto non è dato prevedere se in futuro potrà esistere un metodo risolutivo migliore
Per questi motivi, si parla solo di limite inferiore e limite inferiore e superioresuperiore alla complessità di un problema
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 56
Complessità di un problemaComplessità di un problema
In alcuni casi è possibile dimostrare che nessun algoritmo che risolve un dato problema può/potrà impiegare meno risorse di un certo limite inferioreEsempi banaliEsempi banali
Nessun algoritmo che genera tutte le classifiche possibili per n concorrenti può farlo in meno di n! operazioni (il limite inferiore alla complessità è O (n!))Nessun algoritmo può effettuare la somma fra vettori ndimensionali in meno di n operazioni (il limite inferiore alla complessità è O (n))
Esempio non banaleEsempio non banaleNessun algoritmo può ordinare un vettore di n elementi in meno di nlog2n operazioni, nel caso peggiore
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 57
Algoritmi ottimiAlgoritmi ottimi
Un algoritmo si dice ottimoottimo, quando ha complessità pari al limite inferioreEsempiEsempi
Mergesort e Heapsort sono ottimiSi consideri il problema di sommare gli elementi di un vettore: un algoritmo che scorre tutti gli elementi e li somma uno ad uno richiede O (n) operazioni: tale algoritmo è ottimo perché la sua complessità corrisponde con quella minimaSi consideri il problema di inserire un elemento in un albero binario bilanciato che contiene n elementi:
Abbiamo visto una soluzione algoritmica che impone O (log2n) operazioni log2n è un limite superiore per tale problemaSi può dimostrare che tale complessità corrisponde con il limite inferiore e che l’algoritmo proposto è ottimo
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 58
Algoritmi e computerAlgoritmi e computer
Dubbi: La complessità è indipendente dal computer su cui “gira” il programma?Ad esempio, se si inventasse un calcolatore in grado di generare contemporaneamente tutte le classifiche di n concorrenti, allora quel problema non avrebbe più complessità n! Oppure… potrebbe esistere in futuro un computer in grado di ordinare un vettore di qualsiasi lunghezza per mezzo di una sola istruzione
Nessuno conosce la risposta ma, fino ad ora, nessuno è riuscito a progettare un computer con queste capacitàTutti i calcolatori conosciuti sono equivalenti, in termini di capacità di calcolo, ad un computer semplicissimo: la macchina di Turingmacchina di Turing
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 59
La macchina di TuringLa macchina di Turing
Alan Turing (19121954) è considerato uno dei padri dell’informatica
Nel 1936 propose l’idea di una macchina immaginaria che fosse capace di eseguire ogni tipo di calcolo su numeri e simboli
Esistono varie versioni della macchina di Turing, quella più simile ai nostri calcolatori è quella cosiddetta a registria registri
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 60
La macchina di Turing a registriLa macchina di Turing a registri
È costituita da un insieme di registri di lavoro R1, R2, R3,… e di registri di ingresso I1, I2, I3,…
Ogni registro è una cella di memoria che contiene un intero non negativo
I programmi sono costituiti da tre semplici tipi di istruzioni:
incremento: Ri Il registro i viene incrementato di 1
decremento: Ri Il registro i viene decrementato di 1; se il registro ha già valore 0, l’istruzione non ha effetto
salto condizionato: IF Ri GOTO L1
Se il registro i contiene un valore maggiore di 0, si va all’istruzione L1
IF I1 GOTO ciclociclo: I2
I1
IF I1 GOTO ciclofine:Programma che somma Programma che somma
i contenuti di Ii contenuti di I11 e I e I2 2 in Iin I22
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 61
La tesi di ChurchLa tesi di ChurchTuringTuring
La tesi di Churchtesi di ChurchTuringTuring afferma che:Ogni problema intuitivamente calcolabile (risolubile) da un qualsiasi elaboratore è calcolabile da una macchina di Turing, purché dotata di memoria (e tempo di elaborazione) sufficiente
Nessuno è mai riuscito a confutare la tesi di ChurchTuring
La maggior parte dei ricercatori ritiene che sia vera
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 62
Il problema della terminazioneIl problema della terminazione
Supponiamo che esista un programma halthalt in grado di risolvere i problema della terminazione
halt(P,I) restituisce:true se P con ingresso I terminafalse se P con ingresso I non termina
Consideriamo il programma QCosa succede se si applica Q a Q ?
Q(Q) termina o no ?Se Q(Q) termina allora halt(Q,Q) dovrebbe essere vero… ma allora Q(Q) non dovrebbe terminareSe Q(Q) non termina allora halt(Q,Q) dovrebbe essere falso … ma allora Q(Q) dovrebbe terminareQuindi il programma halt non esiste!!Quindi il programma halt non esiste!!
void Q(Program P){while (halt(P,P))
{}}
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 63
Problemi impossibiliProblemi impossibili
Esistono problemi molto difficili… problemi non calcolabili con una macchina di Turing e se la tesi di ChurchTuring è vera con nessun calcolatore!!EsempiEsempi
Problema della terminazioneProblema della terminazioneDato un programma e un suo ingresso, dire se il programma terminerà (o entrerà in un ciclo
indefinito)Problema di PostProblema di Post
Dato un programma e due stati (uno stato è definito da un certo valore delle variabili), dire se a partire dal primo stato si potrà raggiungere il secondo
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 64
La macchina non deterministica La macchina non deterministica 1 1
Nella macchina non deterministica, i programmi includono anche altre istruzioni
scelta casuale: FORK prende in ingresso un insieme di istruzioni e ne esegue una a casoistruzione di accettazione: ACCEPTquando viene eseguita, il programma termina correttamente
Un problema è risolubile se esiste un programma e una scelta casuale per cui il programma termina con ACCEPT e fornisce la risposta desiderata
R4
FORK{ R1,
R1 }
FORK{ R2,
R2 }
IF R1 GOTO cont
IF R4 GOTO no
cont: IF R2 GOTO ok
IF R4 GOTO no
ok: ACCEPTno:Programma che assegna a Programma che assegna a caso valori in {0, 1} a Rcaso valori in {0, 1} a R11 e e RR22 e termina solo se e termina solo se RR11RR2211
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 65
La macchina non deterministica La macchina non deterministica 2 2
La macchina non deterministica “non calcola più di quella deterministica”
Si può dimostrare che tutto ciò che è calcolabile sulla macchina di Turing non deterministica è calcolabile anche sulla macchina deterministica
Si pensa però che la macchina non deterministica sia più efficiente di quella deterministicaIl non determinismo può essere pensato come una forma di parallelismo:
FORK è un istruzione che genera più programmi paralleli
Il parallelismo permette di risolvere i problemi velocemente: ad esempio, si può cercare un elemento in un vettore guardando contemporaneamente a tutte le posizioni del vettore
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 66
Problemi P e NPProblemi P e NP
I problemi decisionaliproblemi decisionali richiedono solo una risposta binaria (sì/no), correlata in genere all’esistenza di una soluzione (es., problema della terminazione) Nella teoria della complessità, i problemi decisionali si dividono in due classi
P P problemi risolubili in tempo polinomiale sulla problemi risolubili in tempo polinomiale sulla macchina di Turing deterministicamacchina di Turing deterministica
NP NP problemi risolubili in tempo polinomiale sulla problemi risolubili in tempo polinomiale sulla macchina di Turing non deterministicamacchina di Turing non deterministica
Includono sia i problemi “facili”, sia anche la quasi totalità dei problemi che si incontrano nelle situazioni pratiche
Ovviamente vale POvviamente vale PNP, ma non è noto se P≠NPNP, ma non è noto se P≠NP
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 67
Problemi NPProblemi NPcompleti completi 1 1
Problema decisionale della soddisfattibilità:Problema decisionale della soddisfattibilità: Data una forma normale congiuntiva F(x1,x2,…,xn) stabilire se esiste un assegnamento di valori delle variabili booleane x1, x2,…, xn che soddisfi F
Qualunque problema della classe NP si riduce, in tempo polinomiale, al problema della soddisfattibilità PS
PS è il “più difficile” fra i problemi di NP
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 68
Problemi NPProblemi NPcompleti completi 2 2
Un problema P è detto NPNPcompletocompleto se PNP e PS si riduce a P
I problemi NPcompleti sono tutti equivalenti fra loro:
Sarebbe sufficiente trovare un algoritmo polinomiale per uno solo di essi ed avremmo trovato un algoritmo polinomiale per risolvere tutti i problemiInoltre, tutti i problemi in NP sarebbero risolubili in tempo polinomiale sulla macchina di Turing deterministica, cioè avremmo dimostrato che NPP!
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 69
Problemi NPProblemi NPcompleti: esempicompleti: esempi
Problema decisionale del commesso viaggiatoreProblema decisionale del commesso viaggiatoreDato un insieme di n città con le relative distanze, trovare, se esiste, un cammino di lunghezza k che, partendo da una città, le visiti tutte tornando in quella di partenzaUn problema NPNParduoarduo (non decisionale)
Programmazione lineare interaProgrammazione lineare interaData una matrice A e due vettori b, c, calcolare un vettore di interi x che soddisfi Axb e minimizzi f(x)cx
Problemi di programmazione linearedefinire l’orario dei treni e degli autobusdefinire l’orario delle lezioni…
Fondamenti di Informatica I Fondamenti di Informatica I a.a. 2008-09 a.a. 2008-09 70
Conclusioni: PConclusioni: PNP e tesi di NP e tesi di ChurchChurch
Attualmente si pensa che NPP …ma nessuno è ancora riuscito a dimostrarlo
Si pensa anche che la tesi di Church sia vera: ovviamente questo non si può dimostrare ma è, eventualmente, solo confutabile
Talvolta, problemi con complessità proibitiva sono utili:
Ad esempio, gli algoritmi crittografici sono basati sul fatto che “decrittare” una chiave è molto complesso e richiederebbe un tempo troppo lungoSe la tesi di Church non fosse vera o se PNP, tali metodi non sarebbero più efficaci