Algoritmi e strutture dati Analisi di algoritmi Introduzione

Introduzione
Introduzione
Introduzione
Algoritmi e strutture dati
Obiettivo: stimare la complessità in tempo degli algoritmi
Definizioni
Modelli di calcolo
Analisi di algoritmi
Esempi di valutazioni
Notazione
Introduzione
Perché?
Alberto Montresor
Per stimare il tempo impiegato per un dato input
Per stimare il più grande input gestibile in tempi ragionevoli
Università di Trento
Per confrontare l’efficienza di algoritmi diversi
16 ottobre 2014
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Introduzione
Per ottimizzare le parti più importanti
16 ottobre 2014
1 / 52
Alberto Montresor (UniTN)
Definizioni
Capitolo 2 - Analisi di algoritmi
Introduzione
Complessità
Dimensione dell’input
Definizione: Complessità: “Dimensione” → “Tempo”
Criterio di costo logaritmico
16 ottobre 2014
2 / 52
Definizioni
Come definire la dimensione del input?
La taglia dell’input è il numero di bit necessari per rappresentarlo
Come misurare il tempo?
Esempio: moltiplicazione di numeri binari lunghi n bit
Criterio di costo uniforme
La taglia dell’input è il numero di elementi che lo costituiscono
Esempio: ricerca minimo in un vettore di n elementi
In molti casi...
Possiamo assumere che gli “elementi” siano rappresentati da un
numero costante di bit
Le due misure coincidono a meno di una costante moltiplicativa
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
3 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
4 / 52
Introduzione
Definizioni
Introduzione
Definizioni
Definizione di tempo
Definizione
di tempo
Category:Models
of computation
Tempo ≡ wall-clock time
Tempo
n. operazioni
elementari
The category of≡
Computational
Models lists abstract
models for investigating computing machines. Standard computational models
From Wikipedia, the free encyclopedia
The main article for this category is Model of computation.
assume discrete time paradigm.
Il tempo effettivamente impiegato per eseguire un algoritmo
Un’operazione si considera elementare se può essere eseguita in tempo
Wikimedia Commons has media
“costante” dal processore.
related to Computational models.
Dipende da troppi parametri:
Subcategories
Esempio (Operazioni elementari)
bravura del programmatore
This category has the following 14 subcategories, out of 14 total.
linguaggio di programmazione utilizzato
a *= 2 ?
codice generato dal compilatore
A
processore, memoria (cache, primaria, secondaria)
sistema operativo, processi attualmente in esecuzione
Math.cos(d) ?
D
min(A, n) ?
▶► Denotational semantics (1 C, 7
▶► Actor model (14 P)
P)
(5 P)
E
▶► Automata (computation) (1 C, 1
Introduzione
5 / 52
Alberto Montresor (UniTN)
S
▶► Lambda calculus (3 C, 46 P)
T
▶► Stack machines (1 C, 8 P)
Capitolo 2 - Analisi di algoritmi
P Introduzione
Modelli di calcolo – Definizione
16 ottobre 2014
▶► Turing machine (26 P)
6 / 52
Modelli di calcolo – Definizione
▶► Persistence (2 C, 18 P)
Modelli di calcolo
Modelli di calcolo – Wikipedia
▶► Petri nets (15 P)
Pages in category "Models of computation"
Modello di calcolo
The following 108 pages are in this category, out of 108 total. This list may not reflect recent changes (learn more).
Rappresentazione astratta di un calcolatore
Astrazione: deve permettere di nascondere i dettagli
E cont.
Realismo: deve riflettere la situazione reale
Model of computation
Potenza matematica: deve permettere di trarre conclusioni
“formali” sul costo
A
Extended finite-state machine
Abstract Job Object
7 / 52
Finite state transducer
Algorithm characterizations
Finite-state machine
Alternating Turing machine
FRACTRAN
Alberto Montresor (UniTN)
Pushdown automaton
Quantum capacity
Finite state machine with datapath
Agent-based model
Applicative computing systems
16 ottobre 2014
Probabilistic Turing machine
Q
F
Abstract state machines
B
Capitolo 2 - Analisi di algoritmi
P cont.
Event-driven finite-state machine
Evolution in Variable Environment
Abstract machine
Alberto Montresor (UniTN)
(1 C, 12 P)
L
▶► Combinatory logic (1 C, 8 P)
16 ottobre 2014
▶► Register machines (1 C, 6 P)
▶► Educational abstract machines
P)
C
Capitolo 2 - Analisi di algoritmi
▶► Process calculi (18 P)
R
▶► Applicative computing systems
Dobbiamo considerare una rappresentazione più astratta
Alberto Montresor (UniTN)
P cont.
▶► Abstract machines (1 P)
Funnelsort
H
Capitolo 2 - Analisi di algoritmi
Quantum circuit
Quantum computer
R
Realization (systems)
Register machine
16 ottobre 2014
8 / 52
Introduzione
Modelli di calcolo – Definizione
Introduzione
Modelli di calcolo
Modelli di calcolo
Macchina di Turing
Random Access Machine (RAM)
Una macchina ideale che manipola i dati contenuti su un nastro di
Macchina
di Turingsecondo un insieme prefissato di regole.
lunghezza
infinita,
Quantità infinita di celle di dimensione finita
Accesso in tempo costante (indipendente dalla posizione)
Processore (singolo)
legge il simbolo sotto la testina
Testina
⊥
Memoria:
Ad ogni passo, la Macchina di Turing:
Meccanismo di controllo
Set di istruzioni elementari simile a quelli reali:
Lamodifica
macchina: il proprio stato interno
! legge il simbolo sotto la testina
nuovo
nella cella
! scrive
modifica un
il proprio
statosimbolo
(finito) interno
! scrive un nuovo simbolo nella cella
muove la testina a destra o a sinistra
! muove la testina a destra o a sinistra
a1 a2 a3 a4
Nastro
Cella
Marcatore della prima cella
Modelli di calcolo – Definizione
somme, addizioni, moltiplicazioni, operazioni logiche, etc.
istruzioni di controllo (salti, salti condizionati)
Costo delle istruzioni elementari
Uniforme, ininfluente ai fini della valutazione (come vedremo)
Fondamentale nello
studio
della calcolabilità
Fondamentale
nello
studio
della calcolabilità
✦
Non adatto
per i nostri
Livello
troppo
bassoscopi
per i nostri scopi
✦
✦
Livello troppo basso
Alberto Montresor
(UniTN)
Capitolo 2 - Analisi di algoritmi
✦ Non sufficientemente
realistico
Introduzione
16 ottobre 2014
9 / 52
Alberto Montresor (UniTN)
Esempi di analisi
Capitolo 2 - Analisi di algoritmi
Introduzione
16 ottobre 2014
10 / 52
Esempi di analisi
7
© Alberto Montresor
Tempo di calcolo min()
Tempo di calcolo binarySearch()
Ogni istruzione richiede un tempo costante per essere eseguita
Costante potenzialmente diversa da istruzione a istruzione
Ogni istruzione viene eseguita un certo # di volte, dipendente da n
Item min(Item[ ] A, integer n)
Costo
#
Item min ← A[1]
for integer i ← 2 to n do
if A[i] < min then
min ← A[i]
c1
c2
c3
c4
1
n
n−1
n−1
return min
c5
1
T (n) = c1 + c2 n + c3 (n − 1) + c4 (n − 1) + c5
Il vettore viene suddiviso in due parti:
Parte SX: b(n − 1)/2c
Parte DX: bn/2c
integer binarySearch(Item[ ] A, Item v, integer i, integer j)
Costo
# (i > j) # (i ≤ j)
if i > j then
c1
1
1
return 0
c2
1
0
else
integer m ← b(i + j)/2c
c3
0
1
if A[m] = v then
c4
0
1
return m
c5
0
0
else if A[m] < v then
c6
0
1
return binarySearch(A, v, m + 1, j) c7 + T (bn/2c)c)
0
0/1
else
return binarySearch(A, v, i, m − 1) c7 + T (b(n − 1)/2
0
1/0
= (c2 + c3 + c4 )n + (c1 + c5 − c3 − c4 ) = an + b
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
11 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
12 / 52
Introduzione
Esempi di analisi
Introduzione
Tempo di calcolo binarySearch()
Soluzione della relazione di ricorrenza tramite sostituzione
Assunzioni:
Per semplicità, assumiamo n potenza di 2: n = 2k
L’elemento cercato non è presente
Ad ogni passo, scegliamo sempre la parte DX di dimensione n/2
T (n) = T (n/2) + d
= T (n/4) + 2d
= T (n/8) + 3d
Due casi:
i>j
Esempi di analisi
Tempo di calcolo binarySearch()
(n = 0)
...
T (n) = c1 + c2 = c
n = 2k ⇒ k = log n
= T (1) + kd
i ≤ j (n > 0)
T (n) = T (n/2) + c1 + c3 + c4 + c6 + c7
= T (n/2) + d
Relazione di ricorrenza:
(
c
se n = 0
T (n) =
T (n/2) + d se n ≥ 1
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Introduzione
16 ottobre 2014
13 / 52
= T (0) + (k + 1)d
= kd + (c + d)
= d log n + e.
Alberto Montresor (UniTN)
Notazione
Capitolo 2 - Analisi di algoritmi
Introduzione
16 ottobre 2014
Ordini di complessità
Ordini di complessità
Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo
ottenuto due funzioni di complessità:
Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo
ottenuto due funzioni di complessità:
Ricerca: T (n) = d log n + e
Ricerca: T (n) = d log n + e
logaritmica
Minimo: T (n) = an + b
Minimo: T (n) = an + b
lineare
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
15 / 52
Alberto Montresor (UniTN)
14 / 52
Notazione
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
15 / 52
Introduzione
Notazione
Introduzione
Notazione
Ordini di complessità
Ordini di complessità
Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo
ottenuto due funzioni di complessità:
Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo
ottenuto due funzioni di complessità:
Ricerca: T (n) = d log n + e
logaritmica
Ricerca: T (n) = d log n + e
logaritmica
Minimo: T (n) = an + b
lineare
Minimo: T (n) = an + b
lineare
Una terza funzione deriva dall’algoritmo naïf per il minimo:
Minimo: T (n) = f n2 + gn + h
Una terza funzione deriva dall’algoritmo naïf per il minimo:
Minimo: T (n) = f n2 + gn + h
quadratica
quadratica
Notazione O(f (n)) – Limite superiore
Un algoritmo ha complessità O(f (n)) se il suo tempo di esecuzione è
limitato superiormente da una funzione di complessità f (n).
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Introduzione
16 ottobre 2014
15 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Notazione
Introduzione
Ordini di complessità
15 / 52
Classi di complessità
Per ora, abbiamo analizzato precisamente due algoritmi e abbiamo
ottenuto due funzioni di complessità:
Ricerca: T (n) = d log n + e
logaritmica
O(log n)
Minimo: T (n) = an + b
lineare
O(n)
f (n)
log n
√
n
n
n log n
n2
n3
2n
Una terza funzione deriva dall’algoritmo naïf per il minimo:
Minimo: T (n) = f n2 + gn + h
16 ottobre 2014
Notazione
quadratica
O(n2 )
n = 101
3
3
10
30
102
103
1024
n = 102
6
10
100
664
104
106
1030
n = 103
9
31
1000
9965
106
109
10300
n = 104
13
100
10000
132877
108
1012
103000
Tipo
logaritmico
sublineare
lineare
loglineare
quadratico
cubico
esponenziale
Notazione O(f (n)) – Limite superiore
Un algoritmo ha complessità O(f (n)) se il suo tempo di esecuzione è
limitato superiormente da una funzione di complessità f (n).
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
15 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
16 / 52
Complessità problemi vs algoritmi
Complessità problemi vs algoritmi
Introduzione
Algoritmi e strutture dati
Obiettivo: riflettere sulla complessità dei problemi e degli algoritmi
In alcuni casi, si può migliorare quanto si ritiene “normale”
In altri casi, è impossibile fare di meglio
Analisi di algoritmi
Complessità algoritmi vs Complessità problemi
Qual è il rapporto fra un problema computazionale e l’algoritmo?
Back to basics!
Alberto Montresor
Somme
Moltiplicazioni
Università di Trento
16 ottobre 2014
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
17 / 52
Complessità problemi vs algoritmi
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
18 / 52
Complessità problemi vs algoritmi
Moltiplicare numeri complessi
Moltiplicare numeri complessi
Questioni aperte...
Moltiplicazione numeri complessi
Si può fare di meglio?
Oppure, è possibile dimostrare che non si può fare di meglio?
(a + bi)(c + di) = [ac − bd] + [ad + bc]i
Input: a, b, c, d
Alcune riflessioni
Output: ac − bd, ad + bc
Domande
Considerate un modello di calcolo dove la moltiplicazione costa 1, le
addizioni/sottrazioni costano 0.01.
In questo modello, effettuare 3 moltiplicazioni invece di 4 risparmia
il 25% del costo
Esistono contesti in cui effettuare 3 moltiplicazioni invece di 4 può
produrre un risparmio maggiore
Quanto costa l’algoritmo dettato dalla definizione?
Potete fare di meglio?
Qual è il ruolo del modello di calcolo?
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
19 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
20 / 52
Complessità problemi vs algoritmi
Complessità problemi vs algoritmi
Sommare numeri binari
Limite inferiore alla complessità di un problema
Algoritmo
elementare della somma – sum()
Sommare numeri binari
Notazione Ω(f (n)) – Limite inferiore
richiede di esaminare tutti gli n bit
Algoritmo
elementare
della somma
- sum() tre bit e generare riporto)
costo
totale cn
(c ≡ costo
per sommare
✦
✦
Domanda
✦
costo totale cn (c ≡ costo per sommare tre bit e generare riporto)
Limite inferiore della somma di numeri binari
Esiste ✦unDomanda
metodo più efficiente?
✦
Un problema ha complessità Ω(f (n)) se tutti i possibili algoritmi che lo
risolvono hanno complessità f (n) o superiore.
richiede di esaminare tutti gli n bit
Il problema della somma di numeri binari ha complessità Ω(n).
Esiste un metodo più efficiente?
11101111111111
1 0 1 1 0 0 1 1 0 1 1 0 1 1 1+
111101101101011
1101010100100010
Alberto Montresor (UniTN)
© Alberto Montresor
Complessità
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
21 / 52
18
problemi vs algoritmi
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Moltiplicare numeri binari
Algoritmi aritmetici
Algoritmo elementare della somma – prod()
Confronto della complessità computazionale
moltiplicazione di ogni bit con ogni altro bit
Somma : Tsum (n) = O(n)
costo totale cn
Prodotto : Tprod (n) = O(n2 )
Moltiplicare numeri
binari
2
✦
16 ottobre 2014
22 / 52
Complessità problemi vs algoritmi
Algoritmo “elementare” del prodotto - prod()
n2
Alberto Montresor (UniTN)
*******
*******
*******
*******
*******
*******
*******
*******
*******
Capitolo 2 - Analisi di algoritmi
Si potrebbe erroneamente concludere che...
x
16 ottobre 2014
Il problema della moltiplicazione è inerentemente più costoso del
problema dell’addizione
“Conferma” la nostra esperienza
23 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
24 / 52
Complessità problemi vs algoritmi
Complessità problemi vs algoritmi
Algoritmi aritmetici
Moltiplicare
numeribinari
binari
Moltiplicare numeri
Confronto fra problemi
Per provare che il problema del prodotto è più costoso del problema
della somma, dobbiamo provare che non esiste una soluzione in tempo
lineare per il prodotto
✦ Un metodo algoritmico: divide-et-impera
Divide-et-impera
✦
Divide:
dividi
il problema
in in
sottoproblemi
di di
dimensioni
inferiori
Divide:
dividi
il problema
sottoproblemi
dimensioni
inferiori
Impera: risolvi i sottoproblemi in maniera ricorsiva
✦
Impera: risolvi i sottoproblemi in maniera ricorsiva
Combina: unisci le soluzioni dei sottoproblemi in modo da ottenere
unisci
le soluzioni
dei sottoproblemi in modo da ottenere
la Combina:
risposta del
problema
principale
✦
Abbiamo confrontato gli algoritmi, non i problemi!
Sappiamo solo che l’algoritmo di somma studiato alle elementari è
più efficiente dell’algoritmo del prodotto studiato alle elementari
risposta del problema principale
Moltiplicazione
divide-et-impera
✦ Moltiplicazione ricorsiva
n/2 +
XX==aa· 2n/2
+bb
✦
Nel 1960, Kolmogorov enunciò in una conferenza che la
moltiplicazione ha limite inferiore Ω(n2 )
✦
XY = ac 2 + (ad+bc) 2
✦
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Y Y==cc· 2
2n/2
+dd
n/2 +
n/2
XY
= ac · 2n n+ (ad + bc) · 2n/2
+ bd
✦
Una settimana dopo, fu provato il contrario!
16 ottobre 2014
25 / 52
Complessità problemi vs algoritmi
+ bd
X
a
b
Y
c
d
Nota:
✦ Moltiplicare per 2t ≡ shift di t posizioni, in tempo lineare
16 ottobre 2014
26 / 52
Sommare due vettori di bit anch’esso in tempo lineare
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
✦
Complessità problemi vs algoritmi
Svolgere
la ricorsione
Analisi
della
ricorsione
Moltiplicare numeri binari tramite Divide-et-impera
© Alberto Montresor
0
if n = 1 then
return X[1] · Y [1]
else
spezza X in a; b e Y in c; d
return
pdi(a, c, n/2) · 2n + (pdi(a, d, n/2) + pdi(b, c, n/2)) · 2n/2 + pdi(b, d, n/2)
T (n) =
Nota: Moltiplicare per
n/2
n/2
n/4
n/4
i
log2 n
n/4
n/4
n/4
n/4
n/2
n/4
n/4
+ n/2
n/4
n/2
n/4
n/4
c2 · 4 · n/2
n/2
n/4
n/4
n/4
n/4
c2 · 42 · n/22
c2 · 4i · n/2i
............................................................................
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
16 ottobre 2014
T (1) · 4log n
= c1 · nlog 4
≡ shift di t posizioni, in tempo lineare
Capitolo 2 - Analisi di algoritmi
n/4
n/2 n/2 +
Livello i: 4i istanze
n/24ii copies of n/2i
Leveldii dimensione
is the sum of
T (n) =
Alberto Montresor (UniTN)
+
..........................
c1
n=1
4T (n/2) + c2 · n n > 1
2t
1
2
c2 · 1 · n
nn
boolean [ ] pdi(boolean[ ] X, boolean[ ] Y , integer n)
27 / 52
⇢
c1
4T (n/2) + c2 · n
Alberto Montresor (UniTN)
n=1
n>1
Capitolo 2 - Analisi di algoritmi
= c1 · n2
16 ottobre 2014
28 / 52
Complessità problemi vs algoritmi
Complessità problemi vs algoritmi
Moltiplicare numeri binari
Moltiplicazione di Karatsuba (1962)
A1 = ac
Confronto della complessità computazionale
A3 = bd
Prodotto : Tprod (n) = O(n2 )
m = (a + b)(c + d) = ac + ad + bc + bd
Prodotto : Tpdi (n) = O(n2 )
A2 = m − A1 − A3 = ad + bc
Tutto questo lavoro per nulla?
boolean [ ] karatsuba(boolean[ ] X, boolean[ ] Y , integer n)
if n = 1 then
return X[1] · Y [1]
else
spezza X in a; b e Y in c; d
boolean[ ] A1 ← karatsuba(a, c, n/2)
boolean[ ] A3 ← karatsuba(b, d, n/2)
boolean[ ] m ← karatsuba(a + b, c + d, n/2)
boolean[ ] A2 ← m − A1 − A3
return A1 · 2n + A2 · 2n/2 + A3
Domanda: E’ possibile fare meglio
diecosì?
Algoritmi
Strutture di Dati
Notate che la versione ricorsiva chiama se stessa 4 volte.
n)) , 9c > 0, m > 0 : g(n)  cf (n), 8n
m
n)) , 9c > 0, m > 0 : cf (n)  g(n), 8n
m
n)) , 9c > 0, d > 0, m > 0 : cf (n)  g(n)  df (n), 8n
m
boolean[ ] X, boolean[ ] Y , integer n)
Alberto Montresor (UniTN)
[1] · Y [1]
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
29 / 52
Complessità problemi vs algoritmi
Analisi della ricorsione
0
1
[1] · Y [1]
2
n/4
c2 · 1 · n
nn
n/4
+
n/2
+
n/2
n/2
n/4
n/4
n/4
+
n/2
n/4
n/4
n/4
c2 · 32 · n/22
n/4
T (n) =
n=1
n>1
c1
3T (n/2) + c2 · n
n=1
n>1
Alberto Montresor
⇢ (UniTN)
Capitolo 2 - Analisi di algoritmi
Es. Tkara (106 ) = 3 · 109
L’algoritmo “naif” non è sempre il migliore ...
... a meno che non sia possibile dimostrare il contrario!
............................................................................
⇢
c1
4T (n/2) + c2 · n
Es. Tprod (106 ) = 1012
Prodotto : Tkara (n) = O(n1.58... )
... può esistere spazio di miglioramento ...
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
⇢
Prodotto : Tprod (n) = O(n2 )
Conclusioni
c2 · 3i · n/2i
..........................
T (n) =
30 / 52
Confronto della complessità computazionale
c2 · 3 · n/2
n/2
in a; b e Y in c; d
A1
KARATSUBA (a, c, n/2)
A3 i KARATSUBA(b,
d, n/2)
Livello
i: 3i istanze
n/24ii copies of n/2i
Leveldii dimensione
is the sum of
m
KARATSUBA (a + b, c + d, n/2)
A2
m A1 A3
1 · 2n + A2 · 2n/2 + A3
log2 n
16 ottobre 2014
Moltiplicare numeri binari
X, boolean[ ] Y , integer n)
n/2n/2
Capitolo 2 - Analisi di algoritmi
Complessità problemi vs algoritmi
in a; b e Y in c; d
Svolgere la ricorsione
I (a, c, n/2) · 2n + ( PDI (a, d, n/2) + PDI (b, c, n/2)) · 2n/2 + PDI (b, d, n/2)
RATSUBA (boolean[ ]
Alberto Montresor (UniTN)
log n
T (1) · 3
= c1 · nlog 3
= n1.58...
16 ottobre 2014
31 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
32 / 52
Complessità problemi vs algoritmi
Complessità problemi vs algoritmi
Non finisce qui . . .
GNU Multiple Precision Arithmetic Library
GMP
Utilizzata da Mathematica, Maple, etc.
MUL_FFT_THRESHOLD
«Arithmetic without limitations»
Toom-Cook (1963)
Utilizza Schönhage–Strassen quando l’input è più lungo di k parole
di 64 bit, con k dipendente dall’architettura
Noto come algoritmo Toom3, ha complessità
O(nlog 5/ log 3 ) ≈ O(n1.465 )
Karatsuba = Toom2
Moltiplicazione normale = Toom1
Schönhage–Strassen (1971)
Complessità O(n · log n · log log n)
Basato su Fast Fourier Transforms
Martin Fürer (2007)
Complessità O(n · log n · 2O(log
∗
n)
)
Limite inferiore: Ω(n log n) (congettura)
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
33 / 52
Algoritmi di ordinamento
meas
conf
host type
abi
host name
thres
thres
z10-ibm-linux-gnu
64
lgentoo4.s390.gentoo.wh0rd.org-stat
1728
1728
atom-unknown-linux-gnu
64
gege.gmplib.org-stat
2240
2240
z10esa-ibm-linux-gnu
32
lgentoo3.s390.gentoo.wh0rd.org-stat
2240
2240
power7-unknown-linux-gnu
mode32
gcc1-power7.osuosl.org-stat
2688
2688
bulldozer-unknown-freebsd8.3
64
oshell.gmplib.org-stat
3520
3712
piledriver-unknown-netbsd6.1.3
64
pilenbsd64v61.gmplib.org-stat
3712
3712
powerpc7447-unknown-linux-gnu
32
spigg.gmplib.org-stat
3712
3712
coreihwl-unknown-netbsd6.1.2
64
hannahnbsd64v61.gmplib.org-stat
4224
4224
coreinhm-unknown-netbsd6.1.3
64
bikonbsd64v61.gmplib.org-stat
4224
4032
power7-ibm-aix7.1.0.0
mode64
power-aix.fsffrance.org-stat
4288
4288
atom-unknown-linux-gnu
32
gege.gmplib.org-stat
4544
4544
core2-unknown-netbsd6.1.4
64
repentiumnbsd64v61.gmplib.org-stat
4736
4736
coreisbr-apple-darwin12.5.0
64
poire.loria.fr-stat
4736
4736
coreiwsm-unknown-linux-gnu
64
gcc20.fsffrance.org-stat
4736
4032
power7-unknown-linux-gnu
mode64
gcc1-power7.osuosl.org-stat
4736
4288
powerpc970-apple-darwin8.11.0
mode32
g5.gmplib.org-stat
4736
2688
power7-ibm-aix7.1.0.0
32
power-aix.fsffrance.org-stat
5312
5312
bobcat-unknown-netbsd6.1.3
64
bobcat.gmplib.org-stat
5504
5504
alphaev6-unknown-linux-gnu
standard
agnesi.math.su.se-stat
5760
5760
armcortexa15neon-unknown-linux- standard
parma.gmplib.org-stat
5760
5760
power7-unknown-linux-gnu
32
gcc1-power7.osuosl.org-stat
5760
5312
Alberto
Montresor (UniTN)32
Capitolo 2 - Analisi di algoritmi
core2-unknown-netbsdelf6.1.4
repentiumnbsd32v61.gmplib.org-stat
6784
6784
coreinhm-unknown-netbsdelf6.1.3 Algoritmi
32
6784
6784
dibikonbsd32v61.gmplib.org-stat
ordinamento
coreiwsm-unknown-linux-gnu
32
gcc20.fsffrance.org-stat
6784
6784
k10-unknown-netbsdelf6.1.2
32
tigernbsd32v61.gmplib.org-stat
6784
6784
powerpc970-apple-darwin8.11.0
32
g5.gmplib.org-stat
6784
6784
coreihwl-unknown-netbsdelf6.1.2
32
hannahnbsd32v61.gmplib.org-stat
7424
7424
athlon-unknown-netbsdelf6.1.4
32
tambo.gmplib.org-stat
7552
7808
bobcat-unknown-netbsd6.1.3
32
bobcat.gmplib.org-stat
7552
7552
k10-unknown-netbsd6.1.2
64
tigernbsd64v61.gmplib.org-stat
7552
7808
pentium4-unknown-netbsdelf6.1.4
32
parks.gmplib.org-stat
7552
7808
piledriver-unknown-netbsdelf6.1
32
pilenbsd32v61.gmplib.org-stat
7552
6784
athlon-pc-linux-gnu
32
shell.math.su.se
7808
7808
k8-unknown-linux-gnu
64
gcc12.fsffrance.org-stat
7808
11520
powerpc970-apple-darwin8.11.0
mode64
g5.gmplib.org-stat
9088
9088
k10-unknown-freebsd9.2
64
shell.gmplib.org-stat
9344
7808
number of hosts: 36
med: 5504 med: 5312
cfg/meas avg: 0.98797
Introduzione
Algoritmi e strutture dati
Obiettivo: valutare gli algoritmi in base alla tipologia dell’input
In alcuni casi, gli algoritmi si comportano diversamente a seconda
delle caratteristiche dell’input
Conoscere in anticipo tali caratteristiche permette di scegliere il
miglior algoritmo in quella situazione
Il problema dell’ordinamento
è una buona palestra dove mostrare
configured thresholds are up in the sky
configured thresholds get a green light
questi concetti
Analisi di algoritmi
Algoritmi di ordinamento
Please send comments about this page to gmp-discuss at gmplib.org
Copyright 2000-2014 Free Software Foundation
Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.
Algoritmi d’ordinamento
Università di Trento
Selection Sort
Insertion Sort
Merge Sort
Counting Sort
16 ottobre 2014
Capitolo 2 - Analisi di algoritmi
Table generated: 2014-08-25 08:57:15 (UTC)
configured thresholds are down in the mud
Alberto Montresor
Alberto Montresor (UniTN)
cfg file
s390_64/z10/gmp-mparam.h
x86_64/atom/gmp-mparam.h
s390_32/esame/gmp-mparam.h
powerpc64/mode32/p4/gmp-mparam.h
x86_64/bd1/gmp-mparam.h
x86_64/bd2/gmp-mparam.h
powerpc32/gmp-mparam.h
x86_64/coreihwl/gmp-mparam.h
x86_64/coreinhm/gmp-mparam.h
powerpc64/mode64/p7/gmp-mparam.h
x86/atom/gmp-mparam.h
x86_64/core2/gmp-mparam.h
x86_64/coreisbr/gmp-mparam.h
x86_64/coreinhm/gmp-mparam.h
powerpc64/mode64/p7/gmp-mparam.h
powerpc64/mode32/p4/gmp-mparam.h
powerpc32/p7/gmp-mparam.h
x86_64/bobcat/gmp-mparam.h
alpha/ev6/gmp-mparam.h
arm/v7a/cora15/gmp-mparam.h
powerpc32/p7/gmp-mparam.h
16 ottobre 2014
34 / 52
x86/core2/gmp-mparam.h
x86/coreinhm/gmp-mparam.h
x86/coreinhm/gmp-mparam.h
x86/k10/gmp-mparam.h
powerpc32/p4/gmp-mparam.h
x86/coreisbr/gmp-mparam.h
x86/k7/gmp-mparam.h
x86/bobcat/gmp-mparam.h
x86_64/k10/gmp-mparam.h
x86/pentium4/sse2/gmp-mparam.h
x86/bd2/gmp-mparam.h
x86/k7/gmp-mparam.h
x86_64/k8/gmp-mparam.h
powerpc64/mode64/p4/gmp-mparam.h
x86_64/k10/gmp-mparam.h
16 ottobre 2014
35 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
36 / 52
Algoritmi di ordinamento
Algoritmi di ordinamento
Tipologia di analisi
Ordinamento
Analisi del caso pessimo
Problema dell’ordinamento
La più importante
Il tempo di esecuzione nel caso peggiore è un limite superiore al
tempo di esecuzione per qualsiasi input
Per alcuni algoritmi, il caso peggiore si verifica molto spesso
Es.: ricerca di dati non presenti in un database
Problema
Input: Una sequenza A = a1 , a2 , . . . , an di n numeri
Output: Una sequenza B = b1 , b2 , . . . , bn che sia una
permutazione di A e tale per cui b1 ≤ b2 ≤ . . . ≤ bn
Approccio “demente”:
Genero tutte le possibili permutazioni fino a quando non ne trovo
una già ordinata
Analisi del caso medio
Difficile in alcuni casi: cosa si intende per “medio”?
Distribuzione uniforme
Analisi del caso ottimo
Può avere senso se si conoscono informazioni particolari sull’input
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
16 ottobre 2014
37 / 52
Alberto Montresor (UniTN)
Problema
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
Ordinamento
Selection Sort
Problema dell’ordinamento
selectionSort(Item[ ] A, integer n)
Input: Una sequenza A = a1 , a2 , . . . , an di n numeri
16 ottobre 2014
38 / 52
Selection Sort
for i ← 1 to n − 1 do
integer min ← min(A, i, n)
A[i] ↔ A[min]
Output: Una sequenza B = b1 , b2 , . . . , bn che sia una
permutazione di A e tale per cui b1 ≤ b2 ≤ . . . ≤ bn
Approccio “demente”:
Genero tutte le possibili permutazioni fino a quando non ne trovo
una già ordinata
Approccio “naif”:
integer min(Item[ ] A, integer i, integer n)
integer min ← i
% Posizione del minimo parziale
for j ← i + 1 to n do
if A[j] < A[min] then min ← j
% Nuovo minimo parziale
return min
Complessità nel caso medio, pessimo, ottimo?
Cerco il minimo e lo metto in posizione corretta, riducendo il
problema agli n − 1 restanti valori.
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
38 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
39 / 52
Algoritmi di ordinamento
Selection Sort
Algoritmi di ordinamento
Selection Sort
001_207_13_DEAGO_Algoritmi_OK
Insertion
Sort
Algoritmo efficiente per ordinare piccoli insiemi di elementi
Si basa sul principio di ordinamento di una “mano“ di carte da
gioco (e.g. scala quaranta)
selectionSort(Item[ ] A, integer n)
for i ← 1 to n − 1 do
integer min ← min(A, i, n)
A[i] ↔ A[min]
for i ← 2 to n do
Item temp ← A[i]
integer j ← i
while j > 1 and A[j − 1] > temp do
A[j] ← A[j − 1]
j ←j−1
A[j] ← temp
Complessità nel caso medio, pessimo, ottimo?
i=1
(n − i) =
i
X
=
i=1
Alberto Montresor (UniTN)
n(n − 1)
= n2 − n/2 = O(n2 )
2
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
Ana
1 2 3 4 5 6 7
insertionSort(Item[ ] A, integer n)
integer min(Item[ ] A, integer i, integer n)
integer min ← i
% Posizione del minimo parziale
for j ← i + 1 to n do
if A[j] < A[min] then min ← j
% Nuovo minimo parziale
return min
n−1
X
Insertion Sort
28/01/14 12:25 Pagina 29
7 4 2 1 8 3 5
4 7 2 1 8 3 5
2 4 7 1 8 3 5
1 2 4 7 8 3 5
1 2 4 7 8 3 5
1 2 3 4 7 8 5
1 2 3 4 5 7 8
16 ottobre 2014
39 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
Fig. 2.2 Esecuzione della procedura insertionSort().
Insertion Sort
Algoritmi di ordinamento
2.6
Complessità
Merge Sort
In questo algoritmo
Divide et impera
40 / 52
Merge Sort
ESEMPIO – [Insertion sort]
La Fig. 2.2 mostra l’ordinamento della sequenza di elementi 7
dura insertionSort().
La complessità della procedura dipende dalla disposizione ini
Merge Sort è basato
sulla tecnica
divide-et-impera
in precedenza
so peggiore
si ha quando
il vettore Avista
è ordinato
alla rovescia;
Divide: Spezza
virtualmente
il vettore
di deve
n elementi
in due trasferito in
zione
del for, l’elemento
temp
essere sempre
sottovettori di
n/2 elementi
richiederà
i spostamenti e la complessità della procedura è O(
nate, però,
la procedura
insertionSortsui
() èdue
H(n),
poiché la cond
Combina: Chiama
Merge
Sort ricorsivamente
sottovettori
sempre falsa.
Impera: Unisci (merge) le due sequenze ordinate
Il costo di esecuzione non dipende solo dalla dimensione...
ma anche dalla distribuzione dei dati in ingresso
Domande
Qual è il costo nel caso il vettore sia già ordinato?
Qual è il costo nel caso il vettore sia ordinato in ordine inverso?
Possiamo fare di meglio, diminuendo la complessità in tutti i ca
mo? La risposta è positiva. L’algoritmo Merge Sort è basato su
Bisogna sfruttare 2.4):
il fatto che i due sottovettori sono già ordinati
Cosa succede “in media”? (informalmente)
Idea
Dividi il vettore in due sequenze di n/2 elementi ciascuno, ord
poi “fondi” le due metà ordinate in un’unica sequenza ordina
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
41 / 52
Capitolo
2 - AnalisiMergeSort
di algoritmi (), da chiamare
16 ottobre 2014
42 / 52
La procedura
ricorsiva
con l’istruzio
Alberto Montresor (UniTN)
Algoritmi di ordinamento
Merge Sort
Algoritmi di ordinamento
Merge Sort
Funzionamento Merge()
Merge
Merge Sort
primo
1
mezzo
ultimo
n
i
j
k
B
1 3 7 8 2 4 6 9
i
j
k
A
B 1
3 7 8 2 4 6 9
j
i
k
A
B 1 2
3 7 8
4 6 9
i
j
k
A
B 1 2 3
7 8
4 6 9
i
j
k
A
B 1 2 3 4
7 8
6 9
j
i
k
A
B 1 2 3 4 6
7 8
9
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
Merge Sort
j
k
i Algoritmi di ordinamento
A
B 1 2 3 4 6 7
8
9
Merge()
i
j
k
A
B 1 2 3 4 6 7 8
9integer ultimo,
Merge
(Item
A[
],
integer
primo,
integer
mezzo)
37
k
integer i, j, k, h
iA
← primo; j ← mezzo + 1; k ← primo
B 1 2 3 4 6 7 8
1 2 3 4 6 7 8 9
while i ≤ mezzo and j ≤ ultimo do
A
Merge(integer[ ]
Input:
Merge
A, integer primo, integer ultimo, integer mezzo)
Sort
A è un vettore di n interi
i
k ≤ mezzo < ultimo ≤ n
primo,
ultimo, jmezzo sono tali che 1 ≤ primo
+1 . . . ultimo ] sono
A I 1sottovettori
B
3 7 8 A[primo
2 4 6 . .9. mezzo ] e A[mezzo
già ordinati
i
j
3 7 8 2 4 6 9
Output:
A
A
k
B
1
I due sottovettori sono fusi in un unico sottovettore ordinato
i . . . ultimoj ] tramite un vettore di appoggio
k B
A[primo
B 1
3 7 8
4 6 9
Capitolo 2 - Analisi di algoritmi
i
j
Algoritmi di ordinamento
Merge Sort
A
B 1
7 8
4 6 9
Funzionamento
Merge()
i
j
A
B 1
7 8
6 9
j
i
tresor
A
B 1
7 8
9
j
i
A
B 1
8
9
i
j
A
B 1
9
2
k
Alberto Montresor (UniTN)
A
1 2 3 4 6 7 8 9
B
16 ottobre 2014
43 / 52
2 3
k
2 3 4
k
2 3 4 6
k
if A[i] ≤ A[j] then
B[k] ← A[i]
2 3 4 6 7
k
2 3 4 6 7 8
k
1 2 3 4 6 7 8
© Alberto Montresor
i←i+1
else
B[k] ← A[j]
j ←j+1
k ←k+1
j ← ultimo
for h ← mezzo downto i do
A[j] ← A[h]
37
j ←j−1
for j ← primo to k − 1 do A[j] ← B[j]
© Alberto Montresor
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
44 / 52
45 / 52
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
46 / 52
Algoritmi di ordinamento
Merge Sort
Algoritmi di ordinamento
Merge Sort
Costo computazionale
Costo computazionale
Domanda
Domanda
Qual è il costo computazionale di Merge()?
Qual è il costo computazionale di Merge()? ⇒ O(n)
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
16 ottobre 2014
47 / 52
Alberto Montresor (UniTN)
Merge Sort
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
16 ottobre 2014
47 / 52
Merge Sort
Merge(): Partizionamento
Merge Sort
Programma completo:
33, 21, 7, 48, 28, 13, 65, 17
Chiama ricorsivamente se stesso e usa Merge() per unire i risultati
Caso base: sequenze di lunghezza ≤ 1 sono già ordinate
33, 21, 7, 48
28, 13, 65, 17
MergeSort(Item A[ ], integer primo, integer ultimo)
33, 21
if primo < ultimo then
integer mezzo ← b(primo + ultimo)/2c
MergeSort(A, primo, mezzo)
MergeSort(A, mezzo + 1, ultimo)
Merge(A, primo, ultimo, mezzo)
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
33
16 ottobre 2014
48 / 52
7, 48
21
Alberto Montresor (UniTN)
7
28, 13
48
28
Capitolo 2 - Analisi di algoritmi
65, 17
13
65
16 ottobre 2014
17
49 / 52
Algoritmi di ordinamento
Merge Sort
Algoritmi di ordinamento
Merge(): ricorsione
Merge Sort
Analisi di MergeSort()
7, 13, 17, 21, 28, 33, 48, 65
Un’assunzione semplificativa:
n = 2k , ovvero l’altezza dell’albero di suddivisioni è esattamente
k = log n;
7, 21, 33, 48
21, 33
13, 17, 28, 65
7, 48
13, 28
Tutti i sottovettori hanno dimensioni che sono potenze esatte di 2
Costo computazionale: O(n log n)
17, 65
T (n) =
33
21
7
Alberto Montresor (UniTN)
48
28
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
13
65
16 ottobre 2014
17
50 / 52
(
c
n=1
2T (n/2) + dn n > 1
Alberto Montresor (UniTN)
Merge Sort
Capitolo 2 - Analisi di algoritmi
Algoritmi di ordinamento
16 ottobre 2014
Costo computazionale di Merge Sort
Costo computazionale di Merge Sort
Domanda
Domanda
Qual è il costo computazionale di MergeSort()?
Qual è il costo computazionale di MergeSort()? ⇒ O(n log n)
Alberto Montresor (UniTN)
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
52 / 52
Alberto Montresor (UniTN)
51 / 52
Merge Sort
Capitolo 2 - Analisi di algoritmi
16 ottobre 2014
52 / 52

Download Report