Capitolo 1Un’introduzione informale
agli algoritmi
Algoritmi e Strutture Dati
Luigi Laura
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20042
Insieme di istruzioni, definite passo per passo, inmodo da poter essere eseguite meccanicamente e
tali da produrre un determinato risultato
Definizione informale di algoritmo
• Esempio: algoritmo preparaCaffè
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20043
• Gli algoritmi sono alla base dei programmi:i.e., forniscono una descrizione astratta di unmetodo (procedimento) per giungere allasoluzione di un dato problema
Perché studiare algoritmi?
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20044
Pseudocodice
Per mantenere il massimo grado di generalitàdescriveremo algoritmi in pseudocodice:– ricorda linguaggi di programmazione reali come C,
C++ o Java– può contenere alcune frasi in italiano
Traduzione in un particolare linguaggio diprogrammazione può essere fatta in modoimmediato e quasi meccanico
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20045
Progetto ed analisi di algoritmi
Vedremo come progettare ed analizzarealgoritmi che:– producono correttamente risultato desiderato– siano efficienti in termini di tempo di
esecuzione ed occupazione di memoriaScopo progettazione chiaro:
abbiamo bisogno di algoritmi per scrivereun programma!
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20046
Perché analizzare algoritmi?
• Analisi teorica più affidabile di quellasperimentale: vale su tutte le possibiliistanze di dati su cui l’algoritmo opera
• Ci aiuta a scegliere tra diverse soluzionidello stesso problema
• Permette di predire le prestazioni delsoftware, prima ancora di scrivere le primelinee di codice
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20047
Correttezza ed efficienza
Vogliamo progettare algoritmi che:– Producano correttamente il risultato
desiderato– Siano efficienti in termini di tempo di
esecuzione ed occupazione di memoria
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20048
Visita guidata al progetto e analisi di algoritmi tramite
esempio giocattolo:
Calcolo dei numeri di Fibonacci
(problema semplice macon molte soluzioni)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 20049
Leonardo da Pisa, detto Fibonacci c. 1180-1250)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200410
Leonardo da Pisa, detto Fibonacci c. 1180-1250)
Mercante come il padre, vive a Bugia (nellユodierna Algeria)dove si trovava un importante fondaco pisano. Apprendela matematica araba, comprendendo i vantaggi delcalcolo secondo il sistema posizionale.
Opere: Liber abaci, Liber quadratorum, Flos, Praticageometriae
Nel Liber abaci presenta algoritmi per problemi aritmetici eper l’estrazione di radici e il trattamento delle frazioni.Presenta anche problemi tipicamente commerciali comecambio di monete: “Se 1 soldo imperiale che vale 12danari imperiali viene venduto per 31 danari pisani,quanti danari pisani si ottengono per 11 danari imperiali?”
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200411
Problema (Liber abaci, Cap. 12): Quot Paria Coniculorum InUno Anno Ex Uno Pario Germinentur: “Un uomo possiedeuna coppia di conigli in un luogo chiuso e si vuole saperquanti ne vengono creati da questa coppia in un annopoiché è nella loro natura che in un solo mese partoriscanoun’altra coppia e nel secondo mese anche i nuovi natipartoriscono”
Soluzione: “Poichè nel secondo mese la coppia partorisce neavremo 2 in un mese. Una di queste (la prima) partorisceanche nel secondo mese ed avremo quindi 3 coppie. Diqueste, in un mese, due saranno gravide e quindi nel terzomese avremo 5 coppie. ... L’ultimo mese avremo 377coppie. Puoi vedere a margine come abbiamo operato:abbiamo sommato il primo numero al secondo e il secondoal terzo e il terzo al quarto ... e così potrai calcolare per uninfinito numero di mesi”
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200412
Riformulando il problema…
Quanto velocemente si espanderebbe una popolazionedi conigli sotto appropriate condizioni?
In particolare, partendo da una coppia di conigliin un’isola deserta, quante coppie si avrebberonell’anno n?
L’isola dei conigli:
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200413
Come modellare il problema?
Come succede spesso in matematica:(analisi di algoritmi connessa con matematica)
rendere il problema più astrattoper avere un’idea generale del problemasenza perderci nei dettagli di basso livello
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200414
• Una coppia di conigli genera due conigliettiogni anno
• I conigli cominciano a riprodursi soltanto alsecondo anno dopo la loro nascita
• I conigli sono immortali
Modello e ipotesi sui conigli
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200415
Tasso di riproduzione dei conigli
Fn : numero di coppie di conigli presenti nell’anno n
F1 = 1 (una sola coppia)F2 = 1 (troppo giovani per procreare)F3 = 2 (prima coppia di coniglietti)F4 = 3 (seconda coppia di coniglietti)F5 = 5 (prima coppia di nipotini)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200416
L’albero dei conigliLa riproduzione dei conigli può essere descritta in unalbero come segue:
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200417I conigli di Fibonacci
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200418
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200419
• Nell’anno n, ci sono tutte le coppie dell’annoprecedente, e una nuova coppia di conigli perogni coppia presente due anni prima
La regola di espansione
• Indicando con Fn il numero di coppie dell’anno n,abbiamo la seguente relazione di ricorrenza:
Fn-1 + Fn-2 se n≥31 se n=1,2
Fn =
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200420
Il problema
Come calcoliamo Fn ?
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200421
• Possiamo usare una funzione matematica checalcoli direttamente i numeri di Fibonacci.
• Si può dimostrare che:
Un approccio numerico
dove:
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200422
Algoritmo fibonacci1
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200423
• Qual è l’accuratezza su Φ e Φ per ottenere unrisultato corretto?
• Ad esempio, con 3 cifre decimali:
Correttezza?ˆ
258425832583.118987987986.69816221.999923Fnarrotondamentofibonacci1(n)n
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200424
Algoritmo fibonacci2
algoritmo fibonacci2(intero n) → intero if (n ≤ 2) then return 1 else return fibonacci2(n-1) + fibonacci2(n-2)
Opera solo con numeri interi
Poiché fibonacci1 non è corretto, unapproccio alternativo consiste nell’utilizzaredirettamente la definizione ricorsiva:
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200425
Domande tipiche di questo corso
• Quanto tempo richiede fibonacci2?• Come misuriamo il tempo?
– in secondi? (dipende da piattaforma)– in istruzioni macchina? (dipende da
compilatore…)• Prima approssimazione:
– numero linee di codice mandate in esecuzione(indipendente da piattaforma e compilatore)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200426
• Calcoliamo il numero di linee di codicemandate in esecuzione– misura indipendente dalla piattaforma utilizzata
• Se n≤2: una sola linea di codice• Se n=3: quattro linee di codice, due per la
chiamata fibonacci2(3), una per la chiamatafibonacci2(2) e una per la chiamatafibonacci2(1)
Tempo di esecuzione
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200427
Relazione di ricorrenza
In ogni chiamata si eseguono due linee di codice,oltre a quelle eseguite nelle chiamate ricorsive
T(n) = 2 + T(n-1) + T(n-2)
In generale, il tempo richiesto da un algoritmoricorsivo è pari al tempo speso all’interno dellachiamata più il tempo speso nelle chiamate ricorsive
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200428
Albero della ricorsione• Utile per risolvere la relazione di ricorrenza• Nodi corrispondenti alle chiamate ricorsive• Figli di un nodo corrispondenti alle sottochiamate
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200429
• Etichettando i nodi dell’albero con il numero dilinee di codice eseguite nella chiamatacorrispondente:– I nodi interni hanno etichetta 2– Le foglie hanno etichietta 1
Calcolare T(n)
• Per calcolare T(n):– Contiamo il numero di foglie– Contiamo il numero di nodi interni
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200430
• Il numero di foglie dell’albero della ricorsione difibonacci2(n) è pari a F(n)
• Il numero di nodi interni di un albero in cui ogninodo ha due figli è pari al numero di foglie -1
Calcolare T(n)
• In totale le linee di codice eseguite sono F(n) + 2 (F(n)-1) = 3F(n)-2
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200431
fibonacci2 è un algoritmo lento:
T(n) ≈ F(n) ≈ Φn
Possiamo fare di meglio?
Osservazioni
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200432
• Perché l’algoritmo fibonacci2 è lento? Perchécontinua a ricalcolare ripetutamente la soluzione dellostesso sottoproblema. Perché non memorizzare allorain un array le soluzioni dei sottoproblemi?
Algoritmo fibonacci3
algoritmo fibonacci3(intero n) → intero sia Fib un array di n interi Fib[1] ← Fib[2] ← 1 for i = 3 to n do Fib[i] ← Fib[i-1] + Fib[i-2] return Fib[n]
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200433
Una animazione…
L’animazione che segue è stata realizzata conil sistema LeoWeb…
torneremo su questo argomento in seguito…
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200434
Algoritmo fibonacci3
0 1 2 3 4 5 6 7 111098
1 12 3 5 8 13 21 34 55 89 144
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200435
• L’algoritmo fibonacci3 impiega tempoproporzionale a n invece di esponenziale in ncome fibonacci2
• Tempo effettivo richiesto da implementazioni inC dei due algoritmi su piattaforme diverse:
Calcolo del tempo di esecuzione
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200436
• Il tempo di esecuzione non è la sola risorsa dicalcolo che ci interessa. Anche la quantità dimemoria necessaria può essere cruciale.
• Se abbiamo un algoritmo lento, dovremo soloattendere più a lungo per ottenere il risultato
• Ma se un algoritmo richiede più spazio di quello adisposizione, non otterremo mai la soluzione,indipendentemente da quanto attendiamo
Occupazione di memoria
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200437
• fibonacci3 usa un array di dimensione n• In realtà non ci serve mantenere tutti i valori di Fn
precedenti, ma solo gli ultimi due, riducendo lospazio a poche variabili in tutto:
Algoritmo fibonacci4
algoritmo fibonacci4(intero n) → intero a ← b ← 1 for i = 3 to n do c ← a+b a ← b b ← c return b
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200438
• Misurare T(n) come il numero di linee dicodice mandate in esecuzione è una misuramolto approssimativa del tempo diesecuzione
• Se andiamo a capo più spesso, aumenterannole linee di codice sorgente, ma certo non iltempo richiesto dall’esecuzione delprogramma!
Notazione asintotica (1 di 4)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200439
• Per lo stesso programma impaginatodiversamente potremmo concludere adesempio che T(n)=3n oppure T(n)=5n
• Vorremmo un modo per descrivere l’ordinedi grandezza di T(n) ignorando dettagliinessenziali come le costanti moltiplicative…
• Useremo a questo scopo la notazioneasintotica O
Notazione asintotica (2 di 4)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200440
• Diremo che f(n) = O( g(n) ) se f(n) < c g(n)per qualche costante c, ed n abbastanza grande
Notazione asintotica (3 di 4)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200441
• Ad esempio, possiamo rimpiazzare:– T(n)=3Fn con T(n)=O(Fn)– T(n)=2n e T(n)=4n con T(n)=O(n)– T(n)= Fn con O(2n)
Notazione asintotica (4 di 4)
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200442
Possiamo sperare di calcolare Fn in tempoinferiore a O(n)?
Un nuovo algoritmo
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200443
• fibonacci4 non è il miglior algoritmopossibile
• E’ possibile dimostrare per induzione la seguenteproprietà di matrici:
Potenze ricorsive
1 11 0
n= Fn+1 Fn
Fn Fn-1
• Useremo questa proprietà per progettare unalgoritmo più efficiente
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200444
Algoritmo fibonacci5
• Il tempo di esecuzione è ancora O(n)• Cosa abbiamo guadagnato?
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200445
• Possiampo calcolare la n-esima potenza elevandoal quadrato la (n/2)-esima potenza
• Se n è dispari eseguiamo una ulterioremoltiplicazione
• Esempio: 32=9 34 =(9)2 =81 38=(81)2 =6561
Calcolo di potenze
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200446
Algoritmo fibonacci6
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200447
• Tutto il tempo è speso nella procedurapotenzaDiMatrice– All’interno della procedura si spende tempo costante– Si esegue una chiamata ricorsiva con input n/2
• L’equazione di ricorrenza è pertanto:
Tempo di esecuzione
T(n) = O(1) + T(n/2)
• Come risolverla?
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200448
Metodo dell’iterazione
Risulta:
T(n) ≤ kc + T(n/2k)
Per k=log2 n si ottiene
T(n) ≤ c log2 n + T(1) = O(log2 n )
fibonacci6 è quindi esponenzialmente piùveloce di fibonacci3!
Luigi LauraAlgoritmi e strutture dati
da Demetrescu et al. McGraw Hill 200449
Riepilogo
fibonacci6
fibonacci5
fibonacci4
fibonacci3
fibonacci2
O(log n)
O(n)
O(n)
O(n)
O(2n)
O(log n)
O(1)
O(1)
O(1)
O(n)
Tempo diesecuzione
Occupazione dimemoria