Dati e Algoritmi 1

Andrea Pietracaprina

Canale 2 INF [5-9]

1

Introduzione al corso

• Cos’e un algoritmo?

• Che scopo ha un algoritmo?

• Che differenza c’e tra un algoritmo e un programma?

• Cos’e una struttura dati e perche le strutture dati sonoimportanti per gli algoritmi?

• Quali caratteristiche deve avere un “buon” algoritmo?

• Cosa rende difficile il progetto di algoritmi “buoni”?

• Perche e importante studiare algoritmi e strutture dati?

2

Introduzione al corso (continua)

3

Introduzione al corso (continua)

Definire problemi computazionali e progettare algoritmi e strutturedati efficienti e fondamentale per moltissime applicazioni attuali:

• Big data: estrarre informazioni da grandi quantita di dati

• Genomica

• Analisi di reti• telecomunicazioni: wireless, sensor networks, internet of things• biologia: PPI networks• web e reti sociali (facebook, twitter, ecc.)• reti elettriche (power grids)

4

Obiettivi formativi

• Capacita di progetto e analisi di algoritmi/strutture 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 15 ottobre 2017pass: INF59

• Strumenti online:• Moodle: iscrizione, forum, risultati esami• Uniweb: liste d’esame e pubblicazione voti• Sito del corso: http://www.dei.unipd.it/capri/DA1/

materiale e info complete

5

Argomenti

• Nozioni di base (12h)

• Text processing (6h)

• Ripasso di Java (4h)

• Alberi (10h)

• Priority queue (10h)

• Mappe e dizionari (10h)

• Grafi (10h)

• Ordinamento (10)

Materiale

• Lucidi: resi disponibili in anticipo e a blocchi

• Dispense (di esercizi): rese disponibili sul sito del corso

• Appunti: da prendere a lezione

• Testo: [GTG14] M.T. Goodrich, R. Tamassia, M.H.Goldwasser. Data Structures and Algorithms in Java, 6/eJohn Wiley and Sons, 2014.

6

Nozioni di base

7

Argomenti Trattati

• Nozioni di: problema computazionale, modello di calcolo,algoritmo, pseudocodice, struttura dati

• Analisi di complessita: analisi al caso pessimo, analisiasintotica, ordini di grandezza

• Analisi di correttezza: tecniche di dimostrazione, induzione,invarianti

• Algoritmi ricorsivi e loro analisi

8

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 . 9

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 interi ordinate ↑• Π associa ad ogni sequenza di interi (istanza) la sequenza

ordinata costituita dagli stessi interi, eventualmente ripetuti(soluzione)

• (< 43, 16, 75, 2 >,< 2, 16, 43, 75 >) ∈ Π SI(< 7, 1, 7, 3, 3, 5 >,< 1, 3, 3, 5, 7, 7 >) ∈ Π SI(< 13, 4, 25, 17 >,< 11, 27, 33, 68 >) ∈ Π NO

10

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 in senso crescente (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)

11

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 RAM 1 (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 un metodo, ecc.

1Diverso da Random Access Memory!12

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 solitospecificato tramite pseudocodice, ovvero un mix di costrutti dilinguaggi di programmazione ad alto livello e linguaggio naturale.

13

Esempio di Pseudocodice

Algoritmo Transpose(A)

Input: matrice A n × nOutput: matrice trasposta AT

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

Osservazioni

L’uso dello pseudocodice

• Assume un implicito accordo sulle operazioni che possonoessere considerate come “passi elementari”

• Deve garantire che la sequenza di passi elementari eseguiti perogni input sia facilmente ricavabile

14

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 in sottoinsiemi costituiti da istanze tra lorosimili e confrontabili, in modo che l’analisi di un algoritmo possaessere espressa parametricamente in essa.

Ad esempio, l’affermazione l’algoritmo MergeSort richiede tempoO (n log n) specifica la complessita dell’algoritmo in funzione delnumero n di elementi da ordinare, cioe della taglia dell’istanza delproblema di ordinamento che MergeSort risolve.

15

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.

16

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

Π = insieme di coppie (X , (j , k)), con X ∈ I e (j , k) ∈ S, tali che:

• Se X contiene almeno un 1, allora il segmento piu lungo di 1consecutivi in X e X [j ÷ j + k − 1]

• Se X non contiene 1 (vuota o tutti 0), allora j = −1 e k = 0.

17

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

Π = insieme di coppie ((X ,Y ), s), con (X ,Y ) ∈ I e s ∈ S, taliche:

• Se X ∩ Y = ∅ allora s = yes

• Se X ∩ Y =6 ∅ allora s = no.

18

Caso di studio 1: Google News

PROBLEMA: Trovare un insieme di articoli molto diversi tra quellipresenti su siti di giornali, tv, radio, ecc.

FORMALIZZAZIONE (diversity problem) :

• articolo = punto in spazio multidimensionale R (ad es.,vettore di conteggi per le parole di un dato vocabolario)

• metrica di distanza d(·, ·)• diversita di un sottoinsieme di R = minima distanza tra due

punti di R.

I = coppie (X , k), con X ⊂ R, k > 1 intero

S = sottoinsiemi Y ⊂ X di cardinaliuta k

Π = insieme di coppie ((X , k),Y ), tali che Y e sottoinsieme di X ,|Y | = k , e Y ha massima diversita.

19

Esercizi

Esercizio

Sia T una stringa arbitraria di lunghezza n ≥ 1 su un alfabeto Σ.E sempre possibile scrivere T come concatenazione di n/m copie diuna stringa P (ovvero T = PP · · ·P n/m volte) dove P halunghezza m ≤ n ed n/m e intero. La periodicita di T e il minimovalore m per cui tale scrittura di T e possibile. Ad esempio, T =abcd ha periodicita 4 mentre T = abababab ha periodicita 2.Definire come problema computazionale il problema di trovare laperiodicita di una stringa T specificando l’insieme delle istanze I,l’insieme delle soluzioni S e il sottoinsieme di Π ⊆ I × S cherappresenta il problema.

20

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 computazionale21

Complessita in Tempo [GTG14, Par. 4.1]

La complessita in tempo (o time complexity) di un algoritmo e unastima del suo tempo di esecuzione (running time).

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?

22

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

23

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 eseguibile 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)

24

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.

• Assumiamo che per ogni data istanza, la sequenza operazionieseguite, e quindi il loro numero, sia fissata. Si parla in questocaso di algoritmo deterministico. Piu avanti vedremo cheesistono algoritmi (algoritmi probabilistici) per i quali taleassunzione non vale.

25

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

26

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 ?? :)

27

Difficolta

1 Identificazione istanza peggiore

2 Calcolo esatto di tA(n)

ANALISI ASINTOTICA

1 Si stimano limiti superiori/inferiori

2 Si ignorano fattori moltiplicativi costanti (= non dipendentidalla taglia dell’istanza)

3 Si ignorano termini additivi non dominanti

28

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

Esempio (arrayMax)

• limite superiore: 8n − 2 (ogni istanza)

• limite inferiore: 6n (istanza con massimo in A[0])

⇒ Dato che le costanti e i termini non dominanti li ignoriamo,possiamo concludere che tarrayMax e proporzionale a n.

29

Osservazione

Si noti che non serve identificare esplicitamente l’istanza peggiore(cosa spesso molto difficile!), e non serve quantificare le costanti.Nel caso di arrayMax e sufficiente osservare che:

• il ciclo consiste di n − 1 iterazioni ciascuna delle quali esegueun numero costante di passi elementari.

• al di fuori del ciclo si esegue un numero costante di passielementari.

30

Ordini di Grandezzaf (n), g(n) funzioni da N ∪ 0 a R.

Definizione

f (n) ∈ O (g(n)) se ∃c > 0 e ∃n0 ≥ 0, costanti non dipendenti dan, 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)

31

Definizione

f (n) ∈ Ω (g(n)) se ∃c > 0 e ∃n0 ≥ 0, costanti non dipendenti dan, 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, costanti non dipendenti da n, tali che:

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)

(c ′ = 3, c ′′ = 12 = 3 + 4 + 5, n0 = 2)32

Definizione

f (n) ∈ o (g(n)) se ∀c > 0 ∃n0 ≥ 0, con c e n0 costanti nondipendenti da n, tale che

f (n) ≤ cg(n),∀n ≥ n0

N.B. n0 e in genere una funzione di c .

Esempi

• f (n) = 100n e o(n2)

∀c : n0 = 100c

• f (n) = 3nlog2 n

e o (n) ∀c : n0 > 23c (n0 = d2

3c e)

∀n ≥ n0 : f (n) = 3nlog2 n

≤ 3n

log2 23c

= cn

33

Funzioni Notevoli

Parte bassa (floor): bxc = piu grande intero ≤ xEsempi: b3/2c = 1; b3c = 3

Parte alta (ceiling): dxe = piu piccolo intero ≥ xEsempi: 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.

34

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:∑k

i=0 aini = akn

k +∑k−1

i=0 aini ≥ akn

k − kγnk−1

per n ≥ n0: aknk − kγnk−1 = ak

2 nk(

2− 2kγakn

)≥ ak

2 nk

(si usa il fatto che n ≥ n0 ≥ 2kγak )

35

Ordini di Grandezza: Esempi Utili

• f (n) = (n + 1)5 ∈ Θ(n5)

[GTG14,R-4.21]

(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

36

Analisi di Complessita in Pratica

Dato un algoritmo A e detta tA(n) la sua complessita al casopessimo si cercano limiti asintotici superiori e/o inferiori 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)

37

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

38

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!

39

Terminologia per Complessita [GTG14, Par. 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

40

Esempio: Prefix Averages ([GTG14 ] p. 164)

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

O

(n−1∑i=0

(i + 1)

)∈ O

(n2)

⇒ quadratica

41

Esempio: Prefix Averages ([GTG14] p. 165)

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

O (n)

⇒ lineare

42

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):• inizializzazione: ≤ c1 ops• ciclo for:≤ c2n ops• return:1 op

con c1, c2 costanti > 0

• tarrayMax(n) ∈ Ω (n): istanza?1, 2, . . . , n (in effetti qualsiasiistanza va bene in questo caso)• inizializzazione: ≥ d1 ops• ciclo for:≥ d2n ops• return:1 op

con d1, d2 costanti > 0⇒ tarrayMax(n) ∈ Θ (n)

43

Esercizio

Array X di n interi. Algoritmo C :

• ∀ intero pari in X : c1n operazioni

• ∀ intero dispari in X : c2dlog2 ne operazioni

Analisi di complessita

• O(n2)

: ∀ intero in X ≤ c1n operazioni (N.B.: per nabbastanza grande, c1n ≥ c2dlog2 ne)

• Ω (n log n) : ∀ intero in X ≥ c2dlog2 ne operazioni [questoargomento vale per ogni istanza]

• Ω(n2): X contiene tutti interi pari ⇒ ∀ intero in X , c1n

operazioni [istanza specifica]

⇒ Θ(n2)

44

Regola di Buon Senso

Complessita polinomiale (o migliore) ⇒ algoritmo efficienteComplessita esponenziale ⇒ algoritmo inefficiente

Giustificazione ≈[GTG14,4.3.2]

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 τ

45

Complessita polinomiale (o migliore) ⇒ algoritmo efficienteComplessita esponenziale ⇒ algoritmo inefficiente

Giustificazione ≈[GTG14,4.3.2]

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

46

EserciziEsercizio

Il seguente pseudocodice descrive l’algoritmo di ordinamento chiamatoInsertionSort

Algoritmo InsertionSort(S)

input Sequenza S[0 ÷ n-1] di n chiavi

output Sequenza S ordinata in senso crescente

for i ←− 1 to n-1 do curr ←− S[i]

j ←− i-1

while ((j ≥ 0) AND (S[j]> curr)) do S[j+1] ←− S[j]

j ←− j-1

S[j+1] ←− curr

47

Esercizio (continua)

1 Trovare delle opportune funzioni f1(n), f2(n) e f3(n) tali che leseguenti affermazioni siano vere, per una qualche costante c > 0 eper n abbastanza grande.

• Per ciascuna istanza di taglia n l’algoritmo esegue ≤ cf1(n)operazioni.

• Per ciascuna istanza di taglia n l’algoritmo esegue ≥ cf2(n)operazioni.

• Esiste una istanza di taglia n per la quale l’algoritmo esegue≥ cf3(n) operazioni.

La funzione f1(n) deve essere la piu piccola possibile, mentre lefunzioni f2(n) e f3(n) devono essere le piu grandi possibili.

2 Sia tIS(n) la complessita al caso pessimo dell’algoritmo. Sfruttandole affermazioni del punto precedente trovare un upper bound O (·) eun lower bound Ω (·) per tIS(n).

48

un algoritmo (o meglio la sua

assenza) ha rivoluzionato la

nostra società

un algoritmo potrebbe

distruggerla

49

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

50

Algoritmo RSA (Rivest, Shamir, Adleman, 1977)

N = p · q, dove p, q numeri primi grandi: p, q ∈ Θ(√

N)

Chiave pubblica: N, e (e < N funzione di p, q)

Chiave privata: N, d (d < N funzione di p, q)

messaggio m:

• cifratura: m→ (me) mod N = m

• decifratura: m→(md)

mod N = m

dove ”mod” denota il resto della divisione intera (% in Java)

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

51

Algoritmo Banale

for p ← 2 to b√Nc do

if (N mod p = 0) then return p,N/p;

Se p, q ∈ Θ(√

N)⇒ la complessita e Θ

(√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.

52

Dalla motivazione del A.M. Turing Award 2002assegnato a Rivest, Shamir e Adleman

RSA is used in almost all internet-based commercial transactions.Without it, commercial online activities would not be as

widespread as they are today. It allows users to communicatesensitive information like credit card numbers over an unsecure

internet without having to agree on a shared secret key ahead oftime. Most people ordering items over the internet dont know thatthe system is in use unless they notice the small padlock symbol in

the corner of the screen. RSA is a prime example of an abstractelegant theory that has had great practical application.

53

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!!

54

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

55

Caveat

Analisi asintotica (la piu usata)

Le costanti trascurate potrebbero avere un impatto cruciale inpratica.

Esempio

• tA(n) = 10100n = Θ (n) (10100=“costante”) tB(n) = n2

⇒ tA(n) = o (tB(n)) ⇒ A e piu efficiente di B

• in realta: tA(n) < tB(n) solo se n > 10100

10100 >> numero di atomi dell’universo...

Esempio

• tA(n) = 400 log2 n tB(n) = log22 ntA(n) < tB(n) ⇒ log2 n > 400 ⇒ n > 2400 ≥ 10100. . .

Soluzioni: dare una stima delle costanti nel caso siano moltoelevate 56

Tecniche di Dimostrazione [GTG14, Par. 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.

57

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)!Y

.= “a pari ∨b pari”

• a pari: a = 2i ⇒ ab = 2ib pari.

=∼ X

• b pari: analogo.

[GTG14] (p. 166-167) distingue tra

1 provare X ⇒ Y : dimostro la contropositiva ∼ Y ⇒ ∼ X

2 provare X : assumo ∼ X e arrivo a contraddizione

Esempio sopra puo essere visto come esempio di entrambi.58

Induzione

Per provare che una proprieta Q(n) e vera ∀n ≥ n0 (n0 = 1 in[GTG14]) Si procede cosı:

• scegli opportunamente k ≥ 0

• base: dimostra Q(n0),Q(n0 + 1), . . . ,Q(n0 + k)

• passo induttivo: si fissa n ≥ n0 + k arbitrario e si dimostra che

Q(m) vera ∀m : n0 ≤ m ≤ n ⇒ Q(n + 1) vera.

Osservazioni:

• “Q(m) vera ∀m : n0 ≤ m ≤ n” e chiamata ipotesi induttiva

• la dimostrazione deve valere per ogni n ≥ n0 + k

• di solito (ma non sempre) k = 0

59

Esempio (Induzione)

Q(n): “∑n

i=0 i = n(n+1)2 ∈ Θ

(n2)”, ∀n ≥ 0 (⇒ n0 = 0)

• k = 0

• base: Q(0) =∑0

i=0 i = 0 = 0·12 ⇒ OK

• passo induttivo: fissa n ≥ 0Ipotesi induttiva: Q(m) vera ∀m : 0 ≤ m ≤ nQ(n + 1):∑n+1

i=0 i =∑n

i=0 i + (n + 1) = (n + 1) + n(n+1)2 = (n+1)(n+2)

2• penultimo “=”: per ipotesi induttiva

Esercizio [GTG14, C-4.35]

Dimostrare la seguente proprieta:Q(n): “

∑ni=0 i

2 = n(n+1)(2n+1)6 ∈ Θ

(n3)”, ∀n ≥ 0

60

Esempio: successione di Fibonacci

Successione di Fibonacci:F (0) = 0 F (1) = 1F (n + 1) = F (n) + F (n − 1),∀n ≥ 1

(In [GTG14] 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 di vita

• i conigli non muoiono

• all’inizio del primo mese esiste una coppia neonata

Claim

F (n) = 1√5

(Φn − Φn

)Φ = 1+

√5

2 Φ = 1−√5

2 (Φ=golden ratio)

61

Dimostrazione

n0 = 0, k = 1Base: n = 0, n = 1 (esercizio)Passo induttivo:Hp. induttiva: F (m) = 1√

5

(Φm − Φm

)per 0 ≤ m ≤ n,

con n ≥ 1 = n0 + k .F (n + 1)?

F (n + 1)(def)= F (n) + F (n − 1)

(hp. ind)=

1√5

(Φn + Φn−1 −

(Φn + Φn−1

))Φn + Φn−1 = Φn−1 (Φ + 1) = Φn−1

(1+√5

2 + 1)

= Φn−1 3+√5

2

3+√5

2 =(1+√5

2

)2⇒ Φn + Φn−1 = Φn−1 · Φ2 = Φn+1

Analogamente: Φn + Φn−1 = Φn+1

⇒ F (n + 1) = 1√5

(Φn+1 − Φn+1

)62

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

63

Induzione Fallace (2)

Dimostriamo “tutte le pecore di un gregge hanno lo stesso colore”[GTG14 C-4.43] Per induzione sul numero n ≥ 1 di pecore nelgregge:

• 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?

Per n + 1 = 2 l’argomento non vale perche n − 1 = 0.

64

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)

65

Invarianti [GTG14, Par. 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 espressa tramite un’opportuna proprieta.

Esempio: arrayMax(V)

Input: Array V di n interi V [0], . . . ,V [n − 1]Output: massimo intero in AcurrMax ← V [0];for i ← 1 to n − 1 do currMax ← max currMax, V [i ] ;return currMax

Proprieta: currMax = maxV [0],V [1], . . . ,V [i ]

66

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]

67

Dato l’invariante si procede cosı:

• si dimostra che e vero all’inizio del ciclo

• si dimostra che se vale prima dell’inizio di una arbitrariaiterazione (cioe alla fine della precedente) allora esso valeanche alla fine dell’iterazione

• si dimostra che se vale alla fine dell’ultima iterazione, allora ilciclo e corretto

68

Esempio: arrayMax(V)

Input: Array V di n interi V [0], . . . ,V [n − 1]Output: massimo intero in AcurrMax ← V [0];for i ← 1 to n − 1 do currMax ← max currMax, V [i ] ;return currMax

Invariante per il ciclo for

currMax = maxV [j ] : 0 ≤ j ≤ i

• All’inizio del ciclo (i = 0) e vero per l’inizializzazione dicurrMax

• Se e vero alla fine della iterazione i − 1 allora a currMax verraassegnato il valore massimo tra V [i ] e il massimo inV [0],V [1], . . . ,V [i − 1], e quindi l’invariante rimane vero.

• Se e vero alla fine del ciclo (i = n − 1) allora currMax e ilmassimo valore nell’array, che e la proprieta finale dicorrettezza del ciclo.

69

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

Invariante per il ciclo for

x 6∈ A[0],A[1], . . . ,A[i − 1]

La proprieta finale di correttezza da provare e: Se x 6∈ A allora ilciclo finisce naturalmente (i = n), altrimenti x = A[i ]

70

Dimostrazione della correttezza tramite l’invariante

• All’inizio (i = 0) l’invariante e vero per vacuita (l’insiemeA[0],A[1], . . . ,A[i − 1] e vuoto)

• Supponiamo che l’invariante valga alla fine di una iterazione econsideriamo la successiva iterazione (con valore i dellavariabile di ciclo). Se in tale iterazione si scopre che x = A[i ]allora l’iterazione e l’ultima eseguita e si restituiscecorrettamente il valore i . Se invece x 6= A[i ] allora i vieneincrementato di 1. In ogni caso l’invariante continua a valere.

• Sia k ultimo valore assunto dalla variabile i : Se k < nsignifica che si e usciti dal while trovando x = A[k], altrimentik = n e l’invariante garantisce che x 6∈ A. In entrambi i casi, ilvalore restituito in output e corretto.

71

Esercizio

Sia S [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 S [i ] = 1 thencurr ← curr +1;if curr > max then max ← curr;

else curr ← 0;

return max

Dimostrare la correttezza del ciclo (ovvero dell’algoritmo) tramiteun opportuno invariante.

72

Svolgimento

Alla fine del ciclo vogliamo che la variabile max contenga lalunghezza del piu lungo segmento continuo di 1 in S [1 . . . n]

Invariante:

• max contiene la lunghezza del piu lungo segmento continuo di1 in S [1 . . . i ]

• curr contiene la lunghezza del piu lungo suffisso continuo di 1in S [1 . . . i ].

Dimostrazione:

• All’inizio l’invariante e vero per vacuita

• Supponiamo che l’invariante sia vero alla fine della iterazione i − 1 econsideriamo l’iterazione i . Verificare per esercizio che le operazionifatte sia nel caso S [i ] = 1 che nel caso S [i ] = 0 assicurano chel’invariante rimanga vero alla fine del ciclo.

• Se l’invariante e vero alla fine del ciclo, la prima proprietadell’invariante implica la proprieta finale desiderata.

73

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

74

Complessita: Θ (n)

N.B. Operazioni elementari = op. aritmetiche su numeri Θ (Φn)

Correttezza

Basata sul seguente invariante per ciclo for:X = F (i − 1),Y = F (i)

• all’inizio ciclo (i = 1) l’invariante vale (esercizio)

• l’invariante e mantenuto in ciascuna iterazione (esercizio)

• se l’invariante vale alla fine ciclo (i = n) ⇒ Y = F (n)

Algoritmo migliore basato su F (n) = 1√5

(Φn − Φn

)con Φ, Φ

costanti?

75

Esercizi

Esercizio

Sia A una matrice n × n di interi, con n ≥ 2, dove righe e colonnesono numerate a partire da 0.

1 Sviluppare un algoritmo iterativo che restituisce l’indice j ≥ 0di una colonna di A con tutti 0, se tale colonna esiste,altrimenti restituisce −1. L’algoritmo deve contenere un solociclo.

2 Trovare un upper bound e un lower bound alla complessitadell’algoritmo sviluppato.

3 Provare la correttezza dell’algoritmo sviluppato, scrivendo unopportuno invariante per il ciclo su cui esso si basa.

76

Esercizio

Sia A una matrice binaria n × n per la quale vale la proprieta chein ciascuna riga gli 1 vengono prima degli 0. Si supponga ancheche il numero di 1 nella riga i sia maggiore o uguale al numero di 1nella riga i + 1, per i = 0, 1, . . . , n − 2. Descrivere un algoritmoche in tempo O (n) conti il numero di 1 in A, e provarne lacorrettezza. L’algoritmo deve contenere un solo ciclo.

77

Ricorsione [GTG14, Par. 5.1-5.4 and 13.1]

Basata sulla nozione di induzione

Soluzione di 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) [GTG14, p. 193]

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];

78

Esempio: ReverseArray(A,i,j)[GTG14, p. 194]

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)

79

Esempio: MergeSort(S)

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:

• MergeSort(S1)• MergeSort(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

80

Analisi di Algoritmi Ricorsivi

Complessita ⇒ relazioni di ricorrenza

Correttezza ⇒ induzione

81

Analisi di Algoritmi Ricorsivi: 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

82

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.

83

Esempio: LinearSum (continua)

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

≤ cn + c2 (per hp. ind.)

≤ cn + c = c(n + 1)

84

Esempio: LinearSum (continua)

Dimostriamo la correttezza di LinearSum(A, n), per induzione perogni n ≥ 1.

• base (n = 1): OK

• passo induttivo: n ≥ 1Hp. induttiva: LinearSum(A,m) e corretto per ogni1 ≤ m ≤ nConsideriamo l’esecuzione di LinearSum(A, n + 1). Grazie allaHp. induttiva LinearSum(A, n) calcola correttamente lasomma dei primi n valori e aggiungendo poi A[n + 1] si ottieneil valore corretto

85

Esercizi

Esercizio

Dimostrare per induzione le seguenti proprieta:

• tLinearSum(n) ≥ cn per n ≥ 1, dove c = minc1, c2(⇒ tLinearSum(n) ∈ Ω (n)).

• tReverseArray(n) ≤ maxc1, c2dn2e+ c1 per n ≥ 0.

• L’algoritmo ReverseArray e corretto.

Esercizio

Si consideri la seguente relazione di ricorrenza:

T (n) =

n per n = 0, 12T (bn/4c) + 3n per n > 1

Dimostrare che T (n) ≤ 6n per ogni n ≥ 0.

86

Esempio: Calcolo di Potenze [GTG14, pp. 195-196]

Input: x ∈ R, n intero ≥ 0

Output: p(x , n) = xn

Osservazione

p(x , n) =

1 n = 0

x · p(x , n−1

2

)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

87

Dimostriamo per induzione che tP(n) ≤ c (log2 n + 2) per n ≥ 1,dove c = maxc1, c2 (il caso n = 0 va gestito a parte)

• 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)88

Calcolo di F (n) ricorsivo [GTG14, Par. 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

89

Dimostriamo tBinaryFib(n) ≥ c1F (n) (⇒ tBinaryFib(n) ∈ Ω (Φn))Per induzione su n ≥ 0:

• base: n0 = 0, k = 1:• tBinaryFib(0) = c1 ≥ c1F (0) = 0• tBinaryFib(1) = c1 ≥ c1F (1) = c1

⇒ OK

• passo induttivo: n ≥ 1 arbitrario (⇒ n + 1 > 1)Hp. induttiva: tBinaryFib(m) ≥ c1F (m), ∀m : 1 ≤ m ≤ n

tBinaryFib(n + 1)(def)= tBinaryFib(n) + tBinaryFib(n − 1) + c2

≥ tBinaryFib(n) + tBinaryFib(n − 1)

(hp. ind)

≥ c1F (n) + c1F (n − 1)

= c1F (n + 1)

⇒ OK

90

Dimostriamo tBinaryFib(n) ≤ cF (n + 1)− c2, dove c = c1 + c2(⇒ tBinaryFib(n) ∈ O

(Φn+1

)∈ O (Φn))

Per induzione su n ≥ 0:

• base: n0 = 0, k = 1:• tBinaryFib(0) = c1 ≤ c1F (1) + c2F (1)− c2 ≤ cF (1)− c2• tBinaryFib(1) = c1 ≤ c1F (2) + c2F (2)− c2 ≤ cF (2)− c2

⇒ OK

• passo induttivo: n ≥ 1 arbitrario (⇒ n + 1 > 1)Hp. induttiva:tBinaryFib(m) ≤ cF (m + 1)− c2,∀m : 1 ≤ m ≤ n

tBinaryFib(n + 1)(def)= tBinaryFib(n) + tBinaryFib(n − 1) + c2

(hp. ind)

≤ cF (n)− c2 + cF (n + 1)− c2 + c2 (Hp.Ind.)

= cF (n + 2)− c2

⇒ OK

91

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 ≥ 0

• base: n0 = 0, k = 1. E immediato vedere che l’algoritmocalcola correttamente F (0) e F (1).

• passo induttivo: n ≥ 1 arbitrario.Hp. induttiva: l’algoritmo calcola correttamente F (m),∀0 ≤ m ≤ n.Dato che n ≥ 1 si ha che n + 1 ≥ 2 e l’algoritmo restituisceF (n) + F (n − 1). Applicando l’hp. induttiva e la definizionedella serie di Fibonacci, si conclude che l’algoritmo calcolacorrettamente F (n + 1).

92

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

93

Esercizi

Esercizio C-5.10 del testo [GTG14]

Il problema della element uniqueness, definito a pagina 162 deltesto [GTG14], chiede che dato un array A di n elementi sidetermini se tali elementi sono tutti distinti.

1 Progettare un algoritmo ricorsivo efficiente per risolverequesto problema, senza fare ricorso all’ordinamento.

2 Esprimere la complessita tEU(n) dell’algoritmo progettato alpunto precedente tramite una relazione di ricorrenza.

3 Provare a indovinare un limite superiore alla complessita edimostrarlo per induzione utilizzando la relazione di ricorrenzadel punto precedente.

94

Esercizio C-5.20 del testo [GTG14]

Si consideri il seguente algoritmo RicSum che somma n interimemorizzati in un array A, dove n e una potenza di 2. Se n = 1allora l’algoritmo restituisce A[0], altrimenti crea un array B di n/2interi con B[i ] = A[2i ] + A[2i + 1], per 0 ≤ i < n/2, e restituisce lasomma degli interi in B calcolata ricorsivamente.

1 Descrivere RicSum tramite pseudocodice.

2 Esprimere la complessita tRicSum(n) dell’algoritmo tramite unarelazione di ricorrenza.

3 Provare a indovinare un limite superiore alla complessita edimistrarlo per induzione utilizzando la relazione di ricorrenzadel punto precedente.

95

Competenze acquisite

• Specificare un task come problema computazionale

• Descrivere un algoritmo tramite pseudocodice

• Analizzare la complessita al caso pessimo di un algoritmoprovandone limiti asintotici (O (),Ω (),Θ ())

• Provare per induzione una proprieta o la correttezza di unalgoritmo ricorsivo

• Trovare l’invariante di un ciclo e utilizzarlo per provarne lacorrettezza. In generale, saper provare la correttezza di unalgoritmo.

• Descrivere un algoritmo ricorsivo spcificandone la complessitatramite una relazione di ricorrenza.

• Dato un limite superiore/inferiore al valore di una quantitadefinita da una relazione di ricorrenza, provare tale limite perinduzione.

96

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).

97

Riferimenti dal testo [GTG14]

• Par. 1.8.2

• Par. 2.1.2

• Par. 13.1

• Cap.4

• Cap.5

98

ErrataCambiamenti rispetto alla prima versione dei lucidi:

• Lucido 29: chiarito meglio l’esempio di arrayMax

• Lucidi 31-33: aggiunta la specifica che le quantita c, c ′, c ′′ e n0 checompaiono negli ordini di grandezza sono costanti non dipendenti da n.

• Lucido 33: n0 = 1/c diventa n0 = 100/c

• Lucido 51: aggiunta la definizione dell’opertore ”mod”

• Lucido 52: sostituito p|N con Nmodp = 0 e Θ(√

N)

= 2n2 con

Θ(√

N)

= Θ(

2n2

).

• Lucido 58: Corretto le pagine di riferimento del libro e sostituito p con Xe q con Y .

• Lucidi 66-73: ristrutturazioni varie

• Lucido 85: aggiunto questo lucido con correttezza di LinearSum

• Lucido 86: modificato l’upper bound da provare nel secondo punto delprimo esercizio

• Lucido 87: (n + 1)/2 diventa ((n + 1)/2) quando e argomento dellogaritmo

99