A1. Introduzione agli Algoritmipages.di.unipi.it/bodei/CORSO_FP_20/FP/Lezioni/... · n 1,618...
Transcript of A1. Introduzione agli Algoritmipages.di.unipi.it/bodei/CORSO_FP_20/FP/Lezioni/... · n 1,618...
Chiara Bodei, Jacopo SoldaniDipartimento di InformaticaUniversità of Pisa
A1. Introduzione agli AlgoritmiFondamenti di Programmazione e Laboratorio
Algoritmi: Definizione Informale
2
Es. algoritmo CuociLaPasta
1. Riempi la pentola d’acqua
2. Metti la pentola sul fornello
3. Accendi il fornello
4. Attendi che l’acqua sia arrivata ad ebollizione
5. Aggiungi il sale
6. Butta la pasta
7. Attendi il tempo di cottura della pasta
8. Scola la pasta
9. Spegni il fornello
Un algoritmo è un insieme di istruzioni, definite passo per passo, che possono essere riprodotte meccanicamente
per determinare il risultato desiderato
Algoritmi: Perché? Come?
3
Gli algoritmi costituiscono una delle basi della programmazione
→ Forniscono il procedimento per giungere alla soluzione di un dato problema di calcolo
Gli algoritmi saranno descritti ad alto livello, utilizzando il cosiddetto pseudocodice
• Lo pseudocodice ricorda linguaggi di programmazione reali (come il C), ma
• può contenere anche frasi in linguaggio naturale.
NB: La traduzione in un particolare linguaggio di programmazione (come C) può essere fatta in modo quasi meccanico.. provateci! :)
Correttezza ed Efficienza degli Algoritmi
4
Un algoritmo deve essere (i) corretto ed (ii-iii) efficiente, ovvero deve
i. produrre correttamente il risultato desiderato,
ii. essere "veloce" (efficiente in termini di tempo di esecuzione), e
iii. essere "economico" (efficiente in termini di occupazione di memoria)
(ii) e (iii) determinano la complessità in tempo e spazio dell’algoritmo
Come Analizzare gli Algoritmi, e Perché Farlo
5
Come analizzare correttezza e complessità degli algoritmi?
• Analisi teorica (tramite dimostrazioni di correttezza e complessità)
• Analisi sperimentale (tramite l’analisi di possibili istanze di dati su cui l’algoritmo opera)
Analisi teorica (vs. analisi sperimentale)
• più affidabile, poiché vale su tutte le possibili istanze di dati su cui l’algoritmo può operare
• semplifica il confronto tra diverse soluzioni algoritmiche per uno stesso problema
• consente la predizione delle prestazioni di un programma software che implementi effettivamente un algoritmo
Fibonacci: Un Problema Noto…..e Sei Diversi Algoritmi per Risolverlo
6
I Conigli di Fibonacci
7
Domanda: Quante coppie di conigli si avrebbero all’anno 𝒏, partendo da una singola coppia di conigli?
Condizioni (aka. assunzioni):
• Ogni coppia di conigli fertili genera due nuovi coniglietti ogni anno
• I conigli risultano fertili solamente dal secondo anno dopo la loro nascita
• I conigli sono immortali
Problema: Quanto velocemente si espanderebbe una popolazione di conigli in un’isola deserta e sotto appropriate condizioni?
I Conigli di Fibonacci: Tasso di Riproduzione
8
Sotto tali condizioni, e partendo da una singola coppia di coniglietti, si ottiene quanto segue
• 𝐹1 = 1 // una sola coppia di conigli
• 𝐹2 = 1 // troppo giovani per riprodursi
• 𝐹3 = 2 // una coppia si riproduce
• 𝐹4 = 3 // una coppia si riproduce, mentre l’altra è troppo giovane
• 𝐹5 = 5 // due coppie si riproducono, una è troppo giovane
• …
dove
𝐹𝑛 : numero di coppie di conigli presenti nell’anno 𝒏
Domanda: Qual è la regola di espansione della popolazione?
La Regola di Espansione dei Conigli di Fibonacci
9
Nell’anno 𝑛 ci sono le seguenti coppie di conigli:
• tutte le coppie dell’anno precedente e
• una nuova coppia di coniglietti per ogni coppia fertile (ovvero già presente due anni prima)
Continuando ad indicare con 𝐹𝑛 il numero di coppie di conigli presenti nell’anno 𝑛, abbiamo quindi la seguente relazione di ricorrenza:
𝐹𝑛 = ቊ𝐹𝑛−1 + 𝐹𝑛−2 𝑛 ≥ 31 𝑛 = 1,2
Problema: Come calcoliamo 𝐹𝑛?
Approccio Numerico: Fib1
10
L’ennesimo numero della sequenza di Fibonacci si può calcolare in funzione della sezione aurea 𝝓, grazie alla formula di Binet
𝐹𝑛 =𝜙𝑛 − −𝜙 −𝑛
5
Problema: 𝜙 è un numero irrazionale, non rappresentabile nella memoria di un calcolatore
Soluzione: Approssimare la sezione aurea 𝜙 con un valore rappresentabile, es 1.618
𝐹𝑛 =1,618𝑛 − −1,618 −𝑛
5
L’algoritmo Fib1
11
int Fib1(int n) {
return1,618𝑛− −1,618 −𝑛
5;
}
Domanda: L’algoritmo Fib1 è corretto?
Correttezza di Fib1
12
L’accuratezza di una soluzione come quella dell’algoritmo Fib1 dipende strettamente da come/quanto sono approssimati i valori non rappresentabili (come 𝜙, ad esempio)
Ad esempio, approssimando 𝜙 con 3 cifre decimali (ovvero usando 1.618 al posto di 𝜙) si ha che
… quindi (un approccio come quello in) Fib1 non può essere considerato corretto.
n 1,618𝑛− −1,618 −𝑛
5Fib1(n) 𝐹𝑛
3 1.99992 2 2
16 986.698 987 987
18 2583.1 2583 2584
Domanda: E se usassimo direttamente la definizione ricorsiva di 𝐹𝑛?
Approccio Ricorsivo: Fib2
13
NB: Operando solamente con numeri interi, non presenta il problema dell’approssimazione.
→ Calcola correttamente l’ennesimo numero della sequenza di Fibonacci!
int Fib2(int n) {
if n<=2 then return 1;
else return Fib2(n-1) + Fib2(n-2);
}
Domanda: Quanto tempo richiede Fib2?
Misurare la Complessità in Tempo
14
Come misurare il tempo impiegato da un algoritmo?
• In secondi?
(mmm…dipende dalla piattaforma di esecuzione…)
• In numero di istruzioni macchina?
(mmm…dipende dal compilatore…)
• Altre idee?
In prima approssimazione, consideriamo
• il numero di linee di pseudocodice mandate in esecuzione
(indipendente da piattaforma/compilatore…)
Tempo di Esecuzione di Fib2
15
Numero di linee di codice mandate in esecuzione da Fib2:
• n=1 → 1 linea di codice
• n=2 → 1 linea di codice
• n=3 → 2 linee per Fib2(3), 1 per Fib2(2), e 1 per Fib2(1)
• n=4 → 2 linee per Fib2(4), 2 per Fib2(3), e 1 per Fib2(2)
• …
Osservazione: Quando n>=3
• si eseguono due linee di codice,
• oltre a quelle eseguite nelle chiamate ricorsive
Relazione di Ricorrenza
16
Per Fib2, quindi, si ha che𝑇(𝑛) = 2 + 𝑇(𝑛 − 1) + 𝑇(𝑛 − 2)
In generale: il tempo richiesto da un algoritmo ricorsivo è pari al tempo speso all’interno della chiamata
più quello speso nelle chiamate ricorsive
Domanda: Come calcolare 𝑇(𝑛)?
Albero di Ricorsione
17
La ricorsione può essere visualizzata mediante il cosiddetto albero di ricorsione
• nodi ≈ attivazioni della funzione
• archi ≈ chiamate ricorsive
Ad esempio
Fib2(6)
Fib2(5) Fib2(4)
Fib2(3) Fib2(2)
Fib2(2) Fib2(1)
Fib2(4)
Fib2(3) Fib2(2)
Fib2(2) Fib2(1)
Fib2(3)
Fib2(2) Fib2(1)
Calcolare 𝑇 𝑛
18
Intuitivamente, il valore di 𝑇(𝑛) può essere calcolato
• assegnando "pesi" i nodi dell’albero con il numero di linee di codice eseguite nella chiamata corrispondente,
- i nodi interni "pesano" 2 istruzioni
- i nodi foglia "pesano" 1 istruzione
• contando i numeri di nodi interni e di foglie, e
• moltiplicandoli per il loro peso
Calcolare 𝑇 𝑛 (2)
19
Osservazione 1: Il numero di foglie dell’albero di ricorsione di Fib2(n) è pari a 𝐹𝑛
Osservazione 2: Il numero di nodiinterni in un albero in cui ogninodo ha 2 figli è pari alnumero di foglie – 1
In totale, le line di codice eseguite sono𝑇 𝑛 = 𝐹𝑛 + 2 ∙ (𝐹𝑛 −1) = 3𝐹𝑛 − 2
Fib2(6)
Fib2(5) Fib2(4)
Fib2(3) Fib2(2)
Fib2(2) Fib2(1)
Fib2(4)
Fib2(3) Fib2(2)
Fib2(2) Fib2(1)
Fib2(3)
Fib2(2) Fib2(1)
Fib2(n) è lento, visto che 𝑇 𝑛 ≈ 𝐹𝑛
Una Soluzione Più Veloce?
20
L’algoritmo Fib2 calcola ripetutamente la soluzione dello stesso sottoproblema
Ad esempio, per Fib2(5)
• calcola Fib2(4), risolvendo ricorsivamente
• Fib2(3) e
• Fib2(2), e poi
• ricalcola Fib2(3), risolvendo ricorsivamente
• Fib2(2) e
• Fib2(1)
Idea: E se ci salvassimo i risultati già calcolati?
Usare la Memoria: Fib3
21
NB: Sfrutta l’array F di n interi per evitare di ricalcolare i valori di 𝐹𝑖−1 e 𝐹𝑖−2 per ogni 𝑖 ∈ [2, 𝑛)
int Fib3(int n) {
int *F = malloc(n*sizeof(int)); // F è un array di n interi
F[0]=F[1]=1;
for (int i=2;i<n;i++)
F[i] = F[i-1] + F[i-2];
return F[n-1];
}
Domanda: Quanto tempo richiede Fib3? Quanta memoria?
Tempo di Esecuzione di Fib3
22
L’algoritmo Fib3 "scorre un array di n interi" per calcolare 𝐹𝑛• Il numero di istruzioni da eseguire cresce proporzionalmente con 𝑛 e
• non esponenzialmente come nel caso di Fib2
Hardware Fib2(58) Fib3(58)
Pentium IV1700 MHz
15820 secondi(circa 4 ore)
0,7 milionesimi di secondo
Pentium III450 MHz
43518 secondi(circa 12 ore)
2,4 milionesimi di secondo
PowerPC G4 500MHz
58321 secondi(circa 16 ore)
2,8 milionesimi di secondo
Occupazione di Memoria
23
Il tempo di esecuzione non è il solo "costo" (o meglio, la sola risorsa di calcolo) da considerare
→ L’occupazione di memoria può essere altrettanto cruciale
algoritmo lento
algoritmo che occupa più memoria di quella disponibile
necessario attendere a lungo per avere la soluzione
desiderata
non calcola mai la soluzione, indipendentemente dal
tempo che ci mette
Risparmiare Memoria: Fib4
24
NB: Fib3 usa un array di n interi, quando basterebbe mantenere solamente gli ultimi due valori di 𝐹𝑛
int Fib4(int n) {
int f1,f2,fcurr;
f1=f2=1;
for (int i=2;i<n;i++) {
fcurr = f1 + f2;
f1 = f2;
f2 = fcurr;
}
return fcurr;
}
NB: Fib4 impiega sempre un numero di istruzioni proporzionale a n, ma richiedendo un numero costante di interi in memoria (invece che una funzione di n)
Come Misurare il Tempo (2)
25
No, è una misura molto approssimativa! Ad esempio, possiamo aumentare le linee di codice• inserendo commenti o• andando a capo più spesso
senza però aumentare anche il tempo di esecuzione del programma
Per lo stesso programma, potremmo concludere che • 𝑇 𝑛 = 15𝑛 + 3 // senza commenti/accapo• 𝑇 𝑛 = 350𝑛 + 5 // con commenti/accapo
Necessaria una notazione che permetta di astrarre da dettagli inessenziali come costanti e costanti moltiplicative..
Domanda: Ha davvero senso misurare 𝑇(𝑛) come il numero di linee di codice mandate in esecuzione?
Notazione Asintotica
26
𝑇 𝑛 = 𝑓 𝑛 = 𝑂(𝑔 𝑛 )
se 𝑓(𝑛) < 𝑐 ∙ 𝑔(𝑛) per
• una qualche costante 𝑐 e
• 𝑛 sufficientemente grande (ovvero più grande di un qualche valore 𝑛0)
Notazione Asintotica
27
Alcuni esempi
• 𝑇(𝑛) = 𝑛 + 2 diventa 𝑇(𝑛) = 𝑂(𝑛)
• 𝑇(𝑛) = 137𝑛 + 25 diventa 𝑇(𝑛) = 𝑂(𝑛)
• 𝑇(𝑛) = 2𝑛 + 14 diventa 𝑇(𝑛) = 𝑂(2𝑛)
• 𝑇(𝑛) = 2𝑛 + 𝑛3 + 3 diventa 𝑇(𝑛) = 𝑂(2𝑛)
Notazione Asintotica: Fib4
28
Fib4 impiega un numero proporzionale ad n di istruzioni per calcolare 𝐹𝑛
𝑇𝐹𝑖𝑏4 𝑛 = 𝑂(𝑛)
Domanda: Possiamo calcolare 𝐹𝑛 in un tempo inferiore a 𝑂(𝑛)?
Metodo delle Potenze: Fib5
29
È possibile dimostrare per induzione la seguente proprietà di matrici
1 11 0
𝑛
=𝐹𝑛+1 𝐹𝑛𝐹𝑛 𝐹𝑛−1
Sfruttando questa proprietà si ottiene un nuovo algoritmo
int Fib5(int n) {
M = 1 11 0
;
for (int i=0;i<n-1;i++)
M = M * 1 11 0
;
return M[0][0];
}
Domanda: Il tempo di esecuzione è sempre 𝑂(𝑛).E quindi? A cosa serve?
Calcolare le Potenze in Modo Furbo
30
Calcoliamo la potenza n-esima di un numero moltiplicando quel numero n volte per se stesso
67 = 6 ∗ 6 ∗ 6 ∗ 6 ∗ 6 ∗ 6 ∗ 6 = 279.936
Possiamo però procedere anche come segue:
67 = 63 ∗ 63 ∗ 6 = 62 ∗ 6 ∗ 62 ∗ 6 ∗ 6 = 279.936
Ovvero scomporre il calcolo di una potenza 𝑥𝑦 in
• calcolo di 𝑥𝑦/2,
• moltiplicazione 𝑥𝑦/2 per se stesso e
• moltiplicazione del risultato per 𝑥 (solo se 𝑦 è dispari)
Fib6
31
int Fib6(int n) {
int M = 1 11 0
;
potenza(M,n-1);
return M[0][0];
}
void potenza(int Matrice[][2],int esponente) {
if (n>1) {
potenza(Matrice,esponente/2);
Matrice = Matrice * Matrice;
}
if (esponente%2 == 1)
Matrice = Matrice * 1 11 0
;
}
Tempo di Esecuzione di Fib6
32
Dipende strettamente dall’esecuzione di potenza
• potenza richiede tempo costante per essere eseguita, più
• la chiamata ricorsiva a potenza con input esponente/2
Fib6 quindi rispetta la seguente relazione di ricorrenza
𝑇 𝑛 = ቐ𝑂 1 + 𝑇
𝑛
2, 𝑛 > 1
𝑂(1), 𝑛 ≤ 1
Domanda: Come risolverla?
Metodo dell’Iterazione
33
Iterando su 𝑛, si ottiene
𝑇 𝑛 ≤ 𝑐 + 𝑇𝑛
2≤ 𝑐 + 𝑐 + 𝑇
𝑛
4≤ 𝑐 + 𝑐 + 𝑐 + 𝑇
𝑛
8= 3𝑐 + 𝑇
𝑛
23
In generale
𝑇 𝑛 ≤ 𝑘𝑐 + 𝑇𝑛
2𝑘
Per 𝑘 = log2 𝑛 si ottiene𝑇 𝑛 ≤ 𝑐 ∙ log2 𝑛 + 𝑇 1 = 𝑂(log2 𝑛)
Fib6 quindi è esponenzialmente più veloce di Fib3
Riepilogo: Complessità e Confronto di Soluzioni Diverse
34
Algoritmo Complessità in Tempo Complessità in Memoria
Fib2 𝑂(2𝑛) 𝑂(𝑛)
Fib3 𝑂(𝑛) 𝑂(𝑛)
Fib4 𝑂(𝑛) 𝑂(1)
Fib5 𝑂(𝑛) 𝑂(1)
Fib6 𝑂(log2 𝑛) 𝑂(log2 𝑛)