Dati e Algoritmi 1 - crono.dei.unipd.itcrono.dei.unipd.it/~da1/MATERIALE/BasicStud1617.pdf · nita...
Transcript of Dati e Algoritmi 1 - crono.dei.unipd.itcrono.dei.unipd.it/~da1/MATERIALE/BasicStud1617.pdf · nita...
Obiettivi formativi
• Capacita di sviluppo e analisi di un algoritmo/struttura dati
• Conoscenza di building block algoritmici fondamentali
• Capacita di problem solving
• Rigore nel ragionamento e nel linguaggio: efficace, essenziale,non ambiguo, senza salti logici
Aspetti organizzativi
• Iscrizione al corso (su Moodle) entro 4 ottobre 2016
• Strumenti online:• Moodle: iscrizione, forum, risultati esami• Uniweb: liste d’esame e pubblicazione voti• Sito del corso: http://crono.dei.unipd.it/∼da1
materiale e info complete
3
Problema Computazionale
Un problema computazionale Π e una relazione tra un insieme I diistanze (input) ed un insieme S di soluzioni (output), ovvero:
Π ⊆ I × S
con l’ulteriore vincolo che per ogni istanza i ∈ I esista almeno unasoluzione s ∈ S tale che (i , s) ∈ Π.
N.B. Π e un insieme di coppie (istanza,soluzione), sottoinsieme ditutte le possibili coppie. Data la coppia (i , s) ∈ Π, diciamo che s esoluzione di i . 5
Esempi
Somma di Interi
• I=coppie di interi; S= interi
• Π associa ad ogni coppia di interi (istanza) la loro somma(soluzione)
• ((1, 9), 10) ∈ Π; ((23, 6), 29) ∈ Π; ((13, 45), 31) 6∈ Π
Ordinamento di Sequenze di Interi
• I=sequenze di interi; S= sequenze ordinate di interi
• Π associa ad ogni sequenza di interi (istanza) la sequenzaordinata costituita dagli stessi interi, eventualmente ripetuti(soluzione)
• (< 43, 16, 75, 2 >,< 2, 16, 43, 75 >) ∈ Π ?(< 7, 1, 7, 3, 3, 5 >,< 1, 3, 3, 5, 7, 7 >) ∈ Π ?(< 13, 4, 25, 17 >,< 11, 27, 33, 68 >)Π ?
6
Esempi (2)
Ordinamento di Sequenze di Interi (ver.2)
• I=sequenze di interi; S= permutazioni
• Π associa ad ogni sequenza di interi (istanza) la permutazioneche la ordina (soluzione)
• (< 43, 16, 75, 2 >,< 4, 2, 1, 3 >) ∈ Π ?(< 7, 1, 7, 3, 3, 5 >,< 2, 4, 5, 6, 1, 3 >) ∈ Π ?(< 7, 1, 7, 3, 3, 5 >,< 2, 5, 4, 6, 1, 3 >) ∈ Π ?(< 13, 4, 25, 17 >,< 1, 2, 4, 3 >) ∈ Π ?
Osservazioni
• un’istanza puo avere piu soluzioni (ad es., ordinamento ver. 2)
• una soluzione puo essere associata a piu istanze diverse (ades., somma di interi)
7
Algoritmo e Modello di Calcolo
Definizione
Un algoritmo e una procedura computazionale ben definita chetransforma un dato input in un output eseguendo una sequenzafinita di passi elementari. L’algoritmo fa riferimento a un modellodi calcolo (o modello di computazione), ovvero un’astrazione dicomputer che definisce l’insieme di passi elementari.
Il modello di calcolo piu utilizzato e il modello RAM1 (RandomAccess Machine)
• input, output, dati intermedi (e programma): in memoria• passi elementari sono operazioni primitive quali:
assegnamento, operazioni logiche, operazioni aritmetiche,indicizzazione di array, restituzione di un valore da parte di unmetodo, ecc.
1Diverso da Random Access Memory! 8
Un algoritmo A risolve un problema computazionale Π ⊆ I × S see solo se:
1 A riceve come input istanze i ∈ I2 A produce come output soluzioni s ∈ S3 Dato un input i ∈ I, A produce come output s ∈ S tale che
(i , s) ∈ Π
In altre parole: A calcola una funzione che mappa ogni istanza inuna soluzione di tale istanza. (Piu soluzioni? A ne calcola una.)
Per semplicita e facilita di analisi, un algoritmo viene di solitodescritto tramite pseudocodice, ovvero un mix di costrutti dilinguaggi di programmazione ad alto livello e linguaggio naturale.
9
Esempio di Pseudocodice
Algoritmo Transpose(A)
Input: matrice A, n × nOutput: matrice AT (trasposta)i ← 0; j ← 1;while i < n − 1 do
scambia A[i , j ] e A[j , i ];if j = n − 1 then i ← i + 1; j ← i + 1;else j ← j + 1;
return A
10
Per taglia (size) di un’istanza si intende una funzione che mappaogni istanza in uno (o piu) valori, i quali forniscono una misuradella sua grandezza.
La taglia e utilizzata per partizionare l’universo delle istanze insottoinsiemi costituiti da istanze tra loro simili e confrontabili, inmodo che l’analisi di un algoritmo possa essere espressaparametricamente in essa.
Ad esempio, l’affermazione l’algoritmo MergeSort richiede tempoO (n log n) specifica la complessita dell’algoritmo espressa infunzione del numero n di elementi da ordinare, cioe della tagliadell’istanza del problema di ordinamento che MergeSort risolve.
11
Strutture DatiGli algoritmi utilizzano strutture dati per organizzare e accedere inmodo sistematico ai dati di input e a dati intermedi generatidurante l’esecuzione.
Definizione
Una struttura dati e una collezione di oggetti corredata di metodiper accedere e/o modificare la collezione. Nella definizione di unastruttura dati si distinguono due livelli di astrazione:
1 livello logico: specifica l’organizzazione logica degli oggettidella collezione, e la relazione input-output che caratterizzaciascun metodo
2 livello fisico: specifica il layout fisico dei dati el’implementazione dei metodi tramite opportuni algoritmi
La specifica al livello logico di una struttura dati viene riferita comeAbstract Data Type (ADT). In Java, la specifica a livello logico diuna struttura dati e fatta da (una gerachia di) interfacce, mentrela specifica a livello fisico e fatta da (una gerachia di) classi.
12
Esercizio
Specificare come problema computazionale Π la ricerca dell’inizio edella lunghezza del piu lungo segmento di 1 consecutivi in unastringa binaria.
Risoluzione
I = stringhe binarie
S = coppie di interi
13
Esercizio
Specificare come problema computazionale Π la verifica se dueinsieme finiti di oggetti da un universo U sono disgiunti oppure no.
Risoluzione
I = coppie di insiemi finiti da U
S = yes,no
14
Analisi degli Algoritmi
Dato un algoritmo A, vogliamo capire quanto “buono” e⇒ analisi di AVari aspetti di A possono essere considerati.
Complessita
• tempo
• spazio
Correttezza
• terminazione
• soluzione del problema computazionale
Noi ci concentreremo su:
1 complessita: tempo
2 correttezza: soluzione del problema computazionale16
Complessita in Tempo (Time Complexity)[GTG, 4.1]
Stima del tempo di esecuzione (running time) di un algoritmo.
Osservazioni
Il tempo di esecuzione (di un programma) dipende da
• istanza di input: di solito cresce con la taglia, ma a parita ditaglia, input diversi possono avere tempi anche molto diversi(e.g., InsertionSort)
• ambiente HW (e.g., processore, sistema di memoria, ecc.)
• ambiente SW (e.g., linguaggio di programmazione, OS,compilatore, etc.)
Come possiamo studiare la complessita in tempo?
17
Studio Sperimentale
In Java: uso System.currentTimeMillis()
• ritorna il numero (long) di millisecondi trascorsi da un eventodi riferimento (la mezzanotte del 1/1/1970)
• invocazione: prima e dopo esecuzione algoritmo ⇒ differenza
Buona idea? OK ma con dei limiti
• non puo considerare tutti gli input
• richiede l’implementazione di un algoritmo con un programma• molto lavoro!• confronto tra algoritmi: difficile (implementazione ha un ruolo)
• HW/SW dependent
18
Requisiti per l’Analisi della Complessita (in Tempo)
1 deve considerare tutti gli input
2 deve permettere di confrontare algoritmi (senzanecessariamente determinare il tempo di esecuzione esatto)
3 deve essere fattibile a partire da una specifica high leveldell’algoritmo (⇒ pseudocodice)
Approccio
• analisi al caso pessimo (worst-case) in funzione della tagliadell’istanza (req. 1,2)• Altri tipi di analisi sono possibili: caso medio (average case),
analisi probabilistica
• conteggio passi elementari nel modello RAM (req. 2,3)
• analisi asintotica (per semplificare il conteggio)
19
Sia A un algoritmo che risolve Π e si usi n per denotare la tagliadell’istanza
Definizione
La complessita (in tempo) al caso pessimo di A e la funzionetA(n) = massimo numero di operazioni (= passi elementari delmodello RAM) che A esegue per risolvere una istanza di taglia n.
Osservazione
Il massimo e fatto su tutte le istanze di taglia n.Hp: per una data istanza, il numero di operazioni e fissato.
20
Esempio
Algoritmo arrayMax(A,n)
Input: array A di n ≥ 1 interiOutput: max intero in AcurrMax ← A[0];for i ← 1 to n − 1 do
if currMax < A[i ] then currMax ← A[i ];
return currMax
21
Conteggio Operazioni
• currMax ← A[0]: 2 ops (indicizzazione+assegnamento)
• i ← 1: 1 op
• n volte:• calcolo n − 1: 1 op• confronto i < n − 1 1 op
• n − 1 volte (i = 1, . . . , n − 1):• currMax < A[i ]: 2 ops (indicizzazione+confronto)• currMax ← A[i ]: 2 ops (se eseguito)• i ← i + 1: 2 ops (implicito)
• return currMax: 1 op
Caso pessimo (array ordinato crescente):3 + 2n + 6(n − 1) + 1 = 8n − 2 ops ⇒ tarrayMax(n) = 8n − 2
Facile, no ?? :)
22
Difficolta
1 Calcolo esatto di tA(n)
2 Identificazione istanza peggiore
Semplificazioni
1 Si ignorano fattori moltiplicativi costanti (= non dipendentida taglia istanza)
2 Si ignorano termini non dominanti
3 Si stimano limiti superiori/inferiori
⇒ Analisi Asintotica
Esempio: 8n − 2
• ≤ cn con c “costante” (e.g., c = 8)
• ≥ c ′n con c ′ “costante” (e.g., c ′ = 1, n ≥ 1)
23
Ci accontentiamo di:
Limite Superiore
Una qualsiasi istanza (=ogni istanza) ci mette al piu t ⇒ l’istanzapeggiore ci mette al piu t
Limite Inferiore
∃ una istanza che ci mette almeno t ⇒ l’istanza peggiore ci mettealmeno t
⇒ non serve identificare l’istanza peggiore (spesso difficile!)
Analisi arrayMax
• istruzioni fuori dal for ⇒ no. costante di op.
• ciclo for:• n − 1 iterazioni• ogni iterazione: no. costante di op.
⇒ complessita proporzionale a n
24
Ordini di Grandezzaf (n), g(n) funzioni da N ∪ 0 a R.
Definizione
f (n) ∈ O (g(n)) se ∃c > 0 e ∃n0 ≥ 0 tali che
f (n) ≤ cg(n),∀n ≥ n0
• tarrayMax(n) ∈ O (n)(c = 8, n0 = 1)
• 2100 ∈ O (1)(c = 2100, n0 = 1)
• tarrayMax(n) ∈ O(n2)
(c = 1, n0 = 8)
25
Definizione
f (n) ∈ Ω (g(n)) se ∃c > 0 e ∃n0 ≥ 0 tali che
f (n) ≥ cg(n),∀n ≥ n0
Esempio: tarrayMax(n) e Ω (n) (c = 1, n0 = 1)
Definizione
f (n) ∈ Θ (g(n)) se f (n) ∈ O (g(n)) e f (n) ∈ Ω (g(n)), ovvero∃c ′, c ′′ > 0 e n0 ≥ 0:
c ′g(n) ≤ f (n) ≤ c ′′g(n), ∀n ≥ n0
Esempio
• tarrayMax(n) e Θ (n) (c ′ = 1, c ′′ = 8, n0 = 1)
• f (n) = 3n log2 n + 4n + 5 log2 n ∈ Θ (n log2 n)
26
Definizione
f (n) ∈ o (g(n)) se ∀c > 0 : ∃n0 ≥ 0 tale che
f (n) ≤ cg(n),∀n ≥ n0
Esempi
• f (n) = 100n e o(n2)
∀c : n0 = 1c
• f (n) = 3nlog2 n
e o (n) ∀c : n0 > 23c (n0 = d2
3c e)
27
Funzioni Notevoli
Parte bassa (floor): bxc = piu grande intero ≤ xEsempio: b3/2c = 1; b3c = 3
Parte alta (ceiling): dxe = piu piccolo intero ≥ xEsempio: d3/2e = 2; d3e = 3
Logaritmo: logb n, b > 0 (di solito b = 2)
Proprieta
Se a, b > 1 costanti allora logb n = (loga n) (logb a)
⇒ se a, b > 1 costanti allora logb n ∈ Θ (loga n)(n0 = 1, c ′ = c ′′ = logb a)⇒ negli ordini di grandezza si omette la base dei logaritmi, secostante.
28
Funzioni Notevoli
Polinomio:∑k
i=0 aini k ≥ 0
Proprieta
Se ak > 0 e k, ai costanti, allora∑k
i=0 aini ∈ Θ
(nk)
• O(nk): c =
∑ki=0 |ai |, n0 = 1
• Ω(nk): c = ak
2 , n0 = d2kγake, con γ = max|ai |, 0 ≤ i < k
Verifica:
29
Ordini di Grandezza: Esempi Utili
• f (n) = (n + 1)5 ∈ Θ(n5)
[GTG,R-4.22]
(n + 1)5 =∑5
i=0 aini con a5 = 1
⇒ si applica la proprieta di primaoppuresi osserva n5 ≤ (n + 1)5 ≤ (2n)5 per n ≥ 1
• f (n) = nk ∈ o (an) se k > 0, a > 1 costanti:
deriva dal fatto che limn→+∞nk
an = 0
• f (n) = (logb n)k ∈ o(nh)
se b > 1, k , h > 0 costanti:
m = logb n ⇒ n = bm ⇒ nh =(bh)m ⇒ f (n) = mk ∈ o (am)
per a = bh > 1
Osservazione
nalog2 n = n(2log2 a
)log2 n = nnlog2 a = n1+log2 a
30
In Pratica
Dato un algoritmo A e detta tA(n) la sua complessita al casopessimo si cerca un limite superiore e/o inferiore a tA(n).
Limite Superiore (Upper Bound)
tA(n) ∈ O (f (n))
Si prova argomentando che per ogni n “abbastanza grande”, perciascuna istanza di taglia n l’algoritmo esegue ≤ cf (n) operazioni,con c costante (non serve determinarla)
31
In Pratica
Dato un algoritmo A e detta tA(n) la sua complessita al casopessimo si cerca un limite superiore e/o inferiore a tA(n).
Limite Inferiore (Lower Bound)
tA(n) ∈ Ω (f (n))
Si prova argomentando che per ogni n “abbastanza grande”, esisteuna istanza di taglia n per la quale l’algoritmo esegue ≥ cf (n)operazioni, con c costante (non serve determinarla)In alcuni casi e comodo argomentare che per ciascuna istanza ditaglia n l’algoritmo esegue ≥ cf (n) operazioni
32
Osservazione
Se tA(n) ∈ O (f (n)) e tA(n) ∈ Ω (f (n)) ⇒ tA(n) ∈ Θ (f (n))
Note:
• f (n) deve essere il piu vicino possibile alla complessita vera(tight bound)
• f (n) deve essere il piu semplice possibile ⇒ no costanti, notermini additivi di ordine inferiore. Solo termini essenziali!
33
Terminologia per Complessita [GTG,4.2]
• logaritmica: Θ (log n), base 2 o costante > 1
• lineare: Θ (n)
• quadratica: Θ(n2)
• cubica: Θ(n3)
• polinomiale: Θ(nk), k ≥ 1 costante
• esponenziale: Ω (an), a > 1 costante
34
Esempio: Prefix Averages ([GTG ] pag. 175-177)
Input: X [0÷ n − 1] array di n interiVogliamo calcolare A[0÷ n − 1] dove
A[i ] =
i∑j=0
X [j ]
1
i + 1, 0 ≤ i < n
Algoritmo prefixAverages1
for i ← 0 to n − 1 doa← 0;for j ← 0 to i do
a← a + X [j ];
A[i ]← ai+1 ;
return A
Complessita
35
Esempio: Prefix Averages ([GTG] pag. 175-177)
Input: X [0÷ n − 1] array di n interiVogliamo calcolare A[0÷ n − 1] dove
A[i ] =
i∑j=0
X [j ]
1
i + 1, 0 ≤ i < n
Algoritmo prefixAverages2
s ← 0;for i ← 0 to n − 1 do
s ← s + X [i ];A[i ]← s
i+1 ;
return A
Complessita
36
Analisi di arrayMax
Algoritmo arrayMax(A,n)
Input: array A di n ≥ 1interi
Output: max intero in AcurrMax ← A[0];for i ← 1 to n − 1 do
if currMax < A[i ] thencurrMax ← A[i ];
return currMax
• tarrayMax(n) ∈ O (n):
• tarrayMax(n) ∈ Ω (n): istanza?1, 2, . . . , n (in effetti qualsiasiistanza va bene in questo caso)
⇒ tarrayMax(n) ∈ Θ (n)
37
Esercizio
Array X di n interi. Algoritmo C :
• ∀ intero pari in X : c1n operazioni
• ∀ intero dispari in X : c2dlog2 ne operazioni
Analisi di complessita
⇒ Θ(n2)
38
Regola di Buon Senso
Complessita polinomiale (o migliore) ⇒ algoritmo efficienteComplessita esponenziale ⇒ algoritmo inefficiente
Giustificazione ≈[GTG, R-4.28]
Hp: tA(n) complessita worst case di A espressa in nsnτ = max taglia eseguibile in tempo τ ⇒ risolvere tA(nτ ) rispettoa nτEsempio
• log2 nτ = τ ⇒ nτ = 2τ
• nτ = τ
• n2τ = τ ⇒ nτ =√τ
• 2nτ = τ ⇒ nτ = log2 τ
39
Complessita polinomiale (o migliore) ⇒ algoritmo efficienteComplessita esponenziale ⇒ algoritmo inefficiente
Giustificazione ≈[GTG, R-4.28]
Hp: tA(n) complessita worst case di A espressa in nsnτ = max taglia eseguibile in tempo τ ⇒ risolvere tA(nτ ) rispettoa nτ
tA(n) nτ : τ = 109 ns nτ : τ = 60× 109 ns nτ : τ = 3600× 109 ns(1 sec) (1 min) 1 hour
log2 n 2109 =∞ ∞ ∞n 109 6× 1010 3.6× 1012
n2 104.5 ≈ 8× 104.5 ≈ 1.8× 106
2n ≈ 30 ≈ 36 ≈ 42
N.B.: numero di atomi nell’universo = 1078 ÷ 1082 = 2259 ÷ 2272
40
Esempio: Sicurezza in Internet
Crittografia a chiave pubblica
Alice& Bob&
message&m
Bob: chiave privata k1, chiave pubblica k2
• Alice invia a Bob un messaggio m cifrato con k2
• Bob decifra il messaggio ricevuto da Alice con k1
41
Algoritmo RSA (Rivest, Shamir, Adleman, 1977)
N = pq, dove p, q numeri primi grandi: p, q ∈ Θ(√
N)
Chiave pubblica: N, e (e funzione di p, q)
Chiave privata: N, d (d funzione di p, q)
messaggio m:
• cifratura: m→ (me) mod N = m
• decifratura: m→(md)
mod N = m
N.B.: pur conoscendo N ed e, per conoscere d , necessario per ladecifratura, mi serve conoscere p e q
Ottenere p e q da N e difficile!
Taglia dell’istanza = numero di bit di N = blog2Nc+ 1.
= n
42
Algoritmo Banale
for p ← 2 to b√Nc do
if (p|N) then return p,N/p;
Se p, q ∈ Θ(√
N)⇒ la complessita e Θ
(√N)
. Θ(√
N)
= 2n2
Esempio
n = 1024 ⇒ 2n2 = 2512 ≥ 10154
Computer piu potente al mondo (10/2015):≈ 60 Petaflop/sec = 6× 1016 flop/sec⇒ 10154 1
6×1016 > 10137 sec
1 anno ≤ 108 sec ⇒ > 10129 anni di calcolo...
Osservazione
Esistono algoritmi piu efficienti ma sempre con complessitaesponenziale. 2009: risolto problema con n = 768 (2 anni dicalcolo, centinaia di macchine). Non si puo escludere l’esistenza diun algoritmo efficiente.
43
Efficienza Asintotica degli Algoritmi
A,B che risolvono Π
tA(n), tB(n) complessita di A, B (rispettivamente) al caso pessimo
tA(n) ∈ o (tB(n)) ⇒ A e “asintoticamente piu efficiente” di B.
N.B.: n0 potrebbe essere molto grande!!
44
Caveat
Analisi al caso pessimo (la piu usata)
Potrebbe riguardare solo istanze patologiche mentre per tutte leistanze di interesse la complessita potrebbe migliorare (es:Quicksort)
Soluzioni
• restringere con opportune assunzioni il dominio delle istanzeper mantenere quelle di interesse ed escludere quellepatologiche
• analisi del caso medio o cambiare probabilisticamentel’esecuzione
45
Caveat
Analisi asintotica (la piu usata)
Le costanti trascurate potrebbero avere un impatto cruciale inpratica.
Esempio
Soluzioni: dare una stima delle costanti nel caso siano moltoelevate
Esempio
46
Tecniche di Dimostrazione [GTG, 4.4]
Da usare nelle analisi di complessita e correttezza.
Esempio/Controesempio
Esempio: Per dimostrare che la complessita di un algoritmo eΩ (f (n)) basta far vedere che (per ogni n abbastanza grande)esiste un’istanza che richiede ≥ cf (n) operazioni
Controesempio: confutare l’affermazione “2i − 1 e primo ∀i ≥ 1”i = 4 ⇒ 2i − 1 = 15 non primo ⇒ l’affermazione e falsa.
47
Dimostrazione per Assurdo (By Contradiction)
Se dobbiamo dimostrare che “X ⇒ Y ” dimostriamo che lanegazione di Y implica la negazione di X o, piu in generale, unassurdo. Esempio: a, b interi ≥ 1: ab dispari ⇒ a dispari ∧ b
dispari
• X= “ab dispari”
• Y= “a dispari ∧ b dispari”
Per assurdo (by contradiction)
[GTG] (pag. 178, 179) distingue tra
1 provare p ⇒ q: dimostro la contropositiva ∼ q ⇒ ∼ p
2 provare q: assumo ∼ q e arrivo a contraddizione
Esempio sopra puo essere visto come esempio di entrambi.48
Induzione
Per provare che una proprieta Q(n) e vera ∀n ≥ n0 (n0 = 1 in[GTG])Si procede cosı:
• scegli opportunamente k ≥ 0
• base: dimostra Q(n0),Q(n0 + 1), . . . ,Q(n0 + k)
• passo induttivo: si fissa n ≥ n0 + k arbitrarioQ(m) vera ∀m : n0 ≤ m ≤ n ⇒ Q(n + 1) vera• “Q(m) vera ∀m : n0 ≤ m ≤ n”: ipotesi induttiva• N.B.: la dimostrazione deve valere per ogni n ≥ n0 + k• di solito k = 0
49
Esempio (Induzione)
Q(n): “∑n
i=0 i = n(n+1)2 ∈ Θ
(n2)”, ∀n ≥ 0 (⇒ n0 = 0)
Esercizio per casa
Dimostrare la seguente proprieta:Q(n): “
∑ni=0 i
2 = n(n+1)(2n+1)6 ∈ Θ
(n3)”, ∀n ≥ 0
50
Esempio: successione di Fibonacci
Successione di Fibonacci:F (0) = 0 F (1) = 1F (n + 1) = F (n) + F (n − 1),∀n ≥ 1
(In [GTG] Prop. 4.20: definita in modo non standard)
F (n) = numero coppie di conigli all’inizio del mese n (n ≥ 1)
• una coppia produce un’altra coppia ogni mese
• una coppia diventa fertile dopo due mesi divita
• i conigli non muoiono
• all’inizio del primo mese ho una coppianeonata
Claim
F (n) = 1√5
(Φn − Φn
)Φ = 1+
√5
2 Φ = 1−√5
2 (Φ=golden ratio)51
Dimostrazione
n0 = 0, k = 1Base: n = 0, n = 1 (esercizio)Passo induttivo:Hp. induttiva: F (k) = 1√
5
(Φk − Φk
)per 0 ≤ k ≤ n,
con n ≥ 1 = n0 + k .F (n + 1)?
52
Induzione Fallace
Dimostriamo F (n) = 0, ∀n ≥ 0 (n0 = 0)
• k = 0
• base: F (0) = 0 ⇒ OK
• induzione: Fissiamo n ≥ 0Hp. induttiva: F (m) = 0, ∀m : 0 ≤ m ≤ nF (n + 1) = F (n) + F (n − 1) = 0 + 0 = 0
Dov’e l’errore?
F (n + 1) = F (n) + F (n − 1) non vale ∀n ≥ 0 ma vale ∀n ≥ 1
53
Induzione Fallace (2)
Dimostriamo “tutte le pecore di un gregge hanno lo stesso colore”Per induzione sul numero n ≥ 1 di pecore nel gregge:
• k = 0
• base: n = 1 ⇒ OK
• passo induttivo: fissiamo n ≥ 1 Hp. induttiva: vero per ognim : 1 ≤ m ≤ n. Vero per n + 1?• n + 1 pecore = n − 1 pecore + pecora1 + pecora2• colore(n − 1 pecore) = colore(pecora1) (per Hp. induttiva).• colore(n − 1 pecore) = colore(pecora2) (per Hp. induttiva).• quindi colore(pecora1) = colore(n − 1 pecore) =
colore(pecora2)
⇒ OK(?)
Dov’e l’errore?
Quando n = 2, ragionamento non vale.
54
Correttezza
Analisi della correttezza di un algoritmo A
Terminazione
Assicurarsi che i cicli (inclusi GOTO) abbiano termine
Soluzione del Problema Computazionale
• Decomporre A in segmenti
• Definire per ogni segmento una proprieta che deve valere allafine del segmento. In particolare la correttezza di A devediscendere (immediatamente) dalla proprieta che deve valeredopo l’ultimo segmentoFine segmento = check point
• Dimostrare che le varie proprieta definite valgono
Segmenti notevoli: cicli (for, while, repeat-until)
55
Invarianti [GTG, 4.4.3]
Definizione
Un invariante per un ciclo e una proprieta espressa in funzione dellevariabili usate nel ciclo, che deve valere all’inizio del ciclo e alla finedi ciascuna iterazione e che, dopo l’ultima iterazione, garantisce lacorrettezza del ciclo.
Esempio: arrayMax(V)
currMax ← V [0];for i ← 1 to n − 1 do currMax ← max currMax, V [i ] ;return currMax
Proprieta: currMax = maxV [0],V [1], . . . ,V [i ]
56
Esempio: arrayFind(A)
Input: elemento x , array A di n elementi A[0], . . . ,A[n − 1]Output: indice i ∈ [0, n) t. c. A[i ] = x , se esiste, altrimenti −1i ← 0;while i < n do
if x = A[i ] then return i ;else i ← i + 1;
return −1
Proprieta: x 6∈ A[0],A[1], . . . ,A[i − 1]
57
Dato l’invariante si procede cosı:
• si dimostra che e vero all’inizio del ciclo (L0 in [GTG])
• si dimostra che se vale prima dell’inizio di una arbitrariaiterazione (cioe alla fine della precedente) allora esso valeanche alla fine dell’iterazione (Li−1 ⇒ Li in [GTG])
• si dimostra che se vale alla fine dell’ultima iterazione, allora ilciclo e corretto (Lk ⇒ L in [GTG])
58
Esempio: arrayMax(V)
currMax ← V [0];for i ← 1 to n − 1 do currMax ← max currMax, V [i ] ;return currMax
Invariante
Li.
= “currMax = maxV [j ] : 0 ≤ j ≤ i”
• L0: vero per l’inizializzazione di currMax
• Li−1 ⇒ Li : vero (by inspection), 1 ≤ i ≤ n − 1
• Ln−1 ⇒ L: vero banalmente (Ln−1 = L)
59
Esempio ([GTG], pag.181)
Algoritmo arrayFind
Input: elemento x , array A di n elementi A[0], . . . ,A[n − 1]Output: indice i ∈ [0, n) t. c. A[i ] = x , se esiste, altrimenti −1
i ← 0;while i < n do
if x = A[i ] then return i ;else i ← i + 1;
return −1
Complessita:
• O (n)
• Ω (n)
⇒ Θ (n)
Invariante
Li.
= “x 6∈ A[0],A[1], . . . ,A[i − 1]”
Correttezza finale: se x ∈ A si restituisce i t.c. x = A[i ],altrimenti si restituisce −1.Dimostrazione correttezza ciclo: ESERCIZIO x CASA
60
Esercizio
Sia A[1÷ n] una sequenza di n bit. Il seguente algoritmodetermina la lunghezza del piu lungo segmento continuo di 1.
max ← 0; curr ← 0;for i ← 1 to n do
if A[i ] = 1 thencurr ← curr +1;if curr > max then max ← curr;
else curr ← 0;
return max
Trovare un invariante.
61
Esempio
Calcolo dell’n-esimo numero di Fibonacci
F (n) =
n n = 0, 1
F (n − 1) + F (n − 2) n > 1.
F (n) = 1√5
(Φn − Φn
)con Φ ≈ 1.62, Φ ≈ −0.62
Algoritmo IT-FIB(n) (algoritmo iterativo)
Input: intero n ≥ 0Output: F (n)if n ≤ 1 then return n;x ← 0; y ← 1;for i ← 2 to n do
temp ← x ;x ← y ;y ← temp +y ;
return y
63
Complessita: Θ (n)
N.B. Operazioni elementari = op. aritmetiche su numeri Θ (Φn)
Correttezza
Basata sul seguente invariante per ciclo forLi
.= “X = F (i − 1),Y = F (i)”
• inizio ciclo: vale L1• invariante mantenuto in ciascuna iterazione
• fine ciclo: vale Ln ⇒ Y = F (n)
Algoritmo migliore basato su F (n) = 1√5
(Φn − Φn
)con Φ, Φ
costanti?
64
Ricorsione [GTG, 5.1-5.4,12.1]
Basata sulla nozione di induzione
Soluzione una istanza di taglia n ottenuta:
• direttamente: n ≤ n0 (caso base)
• ricorrendo a soluzione di ≥ 1 istanze di taglia < n: n > n0
⇒ un algoritmo ricorsivo invoca se stesso al suo interno
Esempio: LinearSum(A,n)[GTG, pag. 207]
Input: array A, intero n ≥ 1Output:
∑n−1i=0 A[i ]
if n = 1 then return A[0];else return LinearSum(A,n − 1)+A[n − 1];
65
Esempio: ReverseArray(A,i,j)[GTG, pag. 208]
Input: array A, indici i , j ≥ 0Output: array A con gli elementi in A[i ÷ j ] ribaltatiif i < j then
swap(A[i ],A[j ]);ReverseArray(A,i + 1,j − 1)
return A
Osservazioni
• LinearSum e ReverseArray sono esempi di linear recursion(= 1 chiamata ricorsiva)
• ReverseArray e esempio di tail recursion (= chiamataricorsiva e ultima operazione, tranne return)
66
Esempio: MergeSort
Sequenza S di n chiavi da ordinare in maniera crescente
• caso base: n = 1 ⇒ OK (gia‘ ordinata)
• n > 1:• dividi S in S1 = S [0÷ d n2e − 1] e S2 = S [d n2e ÷ n − 1]• due invocazioni ricorsive:
• ordina ricorsivamente S1
• ordina ricorsivamente S2
• S ← Merge(S1,S2)
Osservazione
MergeSort utilizza il design pattern “divide and conquer” (o“divide et impera”) che prevede l’utilizzo di 2 o piu chiamatericorsive
67
Analisi di Algoritmi Ricorsivi
Complessita ⇒ relazioni di ricorrenza
A= algoritmo ricorsivo
tA(n) =
f (n) n ≤ n0
costo chiamate ricorsive+costo altre operazioni n > n0
Esempio: LinearSum
tLinearSum(n) =
c1 n = 1
tLinearSum(n − 1) + c2 n > 1
c1, c2 > 0 costanti
68
Esempio: ReverseArray
n = j − i + 1
tReverseArray(n) =
c1 n ≤ 1
tReverseArray(n − 2) + c2 n > 1
c1, c2 > 0 costanti
Osservazione
• Metodi per “risolvere” relazioni di ricorrenza: faremo dei cennipiu avanti.
• Indovinato un limite superiore/inferiore alla relazione diricorrenza, lo si puo dimostrare per induzione.
69
Esempio
Dimostriamo tLinearSum(n) ≤ cn per n ≥ 1, dove c = maxc1, c2(⇒ tLinearSum(n) ∈ O (n))
• base: n = 1 ⇒ OK
• passo induttivo: n ≥ 1Hp. induttiva: tLinearSum(m) ≤ cm, 1 ≤ m ≤ n
tLinearSum(n + 1) = tLinearSum(n) + c2(hp.in)
≤ cn + c2
≤ cn + c = c(n + 1)
Dimostrare tLinearSum(n) ≥ cn per n ≥ 1, dove c = minc1, c2(⇒ tLinearSum(n) ∈ Ω (n)) ESERCIZIO x CASA
Dimostrare tReverseArray(n) ≤ maxc1, c2dn2e per n ≥ 1ESERCIZIO x CASA
70
Esempio: Calcolo delle Potenze [GTG, pag. 209-210]
Input: x ∈ R, n intero ≥ 0Output: p(x , n) = xn
Osservazione
p(x , n) =
1 n = 0
x · p(x , n−12
)2n > 0 dispari
p(x , n2
)2n > 0 pari
Algoritmo Power(x,n)
if n = 0 then return 1;if n is odd then
y ←Power(x,(n − 1)/2);return x · y · y ;
elsey ←Power(x,n/2);return y · y
Complessita
tP(n) =
c1 n = 0
tP (bn/2c) + c2 n > 0
71
Dimostriamo per induzione che tP(n) ≤ c (log2 n + 2) per n ≥ 1,dove c = maxc1, c2• base n = 1: tP(1) = c2 + c1 ≤ 2c ⇒ OK
• passo induttivo: n ≥ 1Hp. induttiva: tP(m) ≤ c (log2m + 2) , ∀m : 1 ≤ m ≤ n
tP(n + 1) = tP (b(n + 1)/2c) + c2hp.ind≤ c (log2b(n + 1)/2c+ 2) + c2
≤ c (log2(n + 1)/2 + 2) + c2
≤ c (log2(n + 1)− 1 + 2) + c2
= c log2(n + 1) + c + c2
≤ c log2(n + 1) + c + c
≤ c (log2(n + 1) + 2)
⇒ OK
⇒ tP(n) ∈ O (log n)72
Algoritmo ricorsivo per il calcolo di F (n) [GTG, 5.5]
Algoritmo BinaryFib(n)
Input: intero n ≥ 0Output: F (n)if n ≤ 1 then return n;return BinaryFib(n − 1)+BinaryFib(n − 2)
• BinaryFib e un esempio di binary recursion
• la ricorsione ricorda la definizione di F (n)...
Complessita
tBinaryFib(n) =
c1 n ≤ 1
tBinaryFib(n − 1) + tBinaryFib(n − 2) + c2 n > 1
c1, c2 > 0 costanti
73
Dimostriamo tBinaryFib(n) ≤ cF (n + 1)− c2, dove c = c1 + c2(⇒ tBinaryFib(n) ∈ O
(Φn+1
)∈ O (Φn))
Per induzione su n ≥ 0:
75
Complessita: Θ (Φn) ⇒ esponenziale in n!
Osservazione: esponenzialita deriva dal dover risolvere molte voltelo stesso sottoproblema, cosa evitata dall’algoritmo iterativo
Correttezza: dimostrazione per induzione su n ≥ 0ESERCIZIO x CASA
76
Algoritmo Efficiente per il Calcolo di F (n)
Basato su potenze:
F (n) = 1√5
(Φn − Φn
)con Φ = 1+
√5
2 , Φ = 1−√5
2
Algoritmo PowerFib(n)Input: intero n ≥ 0Output: F (n)Φ←
((1 +
√5)/2
);
Φ←((1−
√5)/2
);
return (Power(Φ,n)-Power(Φ,n))/√
5
Complessita: Θ (log n)
Correttezza: banale
77
Riepilogo
• Definizioni di base: problema computazionale, taglia di unaistanza, algoritmo, struttura dati, modello di calcolo
• Pseudocodice
• Analisi di complessita (tempo, spazio)• misura target• analisi asintotica, ordini di grandezza: O (),Ω (),Θ (), o ()
• Tecniche di dimostrazione (esempio, controesempio, perassurdo, induzione)
• Analisi di correttezza• procedimento generale• correttezza di cicli: metodo degli invarianti
• Algoritmi ricorsivi: uso dell’induzione nell’analisi
78
Esempio domande prima parte
• Si definisca il problema di trovare il massimo in una sequenza diinteri come problema computazionale.
• Sia A un algoritmo per un problema computazionale Π. Si suppongache per ogni n esista un’istanza di taglia n che richiede ≥ n2
operazioni. Cos’altro si deve provare per dimostrare che lacomplessita al caso pessimo di A e Θ
(n2)?
• Siano A e B due algoritmi che risolvono lo stesso problemacomputazionale Π, dove la complessita al caso pessimo di A e O (n)e quella di B e Ω
(n2). Per ogni n ≥ 1, sia denoti con in l’istanza
peggiore per B, e siano tA(in) e tB(in) il tempo di esecuzione,rispettivamente di A e di B, sull’istanza in. Si puo affermare che pern abbastanza grande tB(in) ≥ tA(in)?
• Sia tA(n) la complessita al caso pessimo di un algoritmo A espressain funzione della taglia dell’istanza n.
1 Dire come si prova che tA(n) ∈ O (f (n)), per una datafunzione f (n).
2 Dire come si prova che tA(n) ∈ Ω (f (n)), per una datafunzione f (n).
79