Nozioni di Base (I parte)

(1)

Dati e Algoritmi 1 : A. Pietracaprina

(2)

Argomenti trattati

• _{Nozioni di: problema computazionale, modello di calcolo,}

algoritmo, pseudocodice, struttura dati

• _{Analisi di complessit`}_{a: analisi al caso pessimo, analisi}

asintotica, ordini di grandezza

• _{Analisi di correttezza: tecniche di dimostrazione, induzione,}

invarianti

• Algoritmi ricorsivi e loro analisi

(3)

Problema computazionale

Un problema computazionaleΠmette in relazione un insieme I di possibili input (chiamati istanze) con un insiemeS di possibili output (chiamati soluzioni). Precisamente,Π`e sottoinsieme del prodotto cartesianoI × S, cio`e un insieme di coppie (i , s)con

i ∈ I es ∈ S. Per concretezza, Si richiede che per ogni istanza

(4)

Esempi

Somma di Interi (Z) • I= {(x, y ) : x, y ∈ Z }; • S= Z; • Π = {((x , y ), s) : (x , y ) ∈ I, s ∈ S, s = x + y }. Ad es: ((1, 9), 10) ∈ Π; ((23, 6), 29) ((13, 45), 31)

Ordinamento di array di interi • I= {A : A = array di interi};

• S= {B : B = array ordinati di interi};

• Π = {(A, B) : A ∈ I, B ∈ S, B contiene gli stessi interi di A}. Ad es.

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

(5)

Esempi

Ordinamento di sequenze di interi (ver.2) • I= {A : A = array di interi}; • S= {P : P = permutazioni};

• Π = {(A, P) : A ∈ I, P ∈ S, P ordina gli interi di A}. Ad es. (< 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

• una soluzione pu`o essere associata a pi`u istanze diverse (ad es., somma di interi)

(6)

Algoritmo e modello di calcolo

Definizione

Algoritmo: procedura computazionale ben definita che transforma un dato input in un output eseguendo una sequenza finita di passi elementari.

L’algoritmo fa riferimento a unmodello di calcolo, ovveroun’astrazione di computer che definisce l’insieme di passi elementari.

Il modello di calcolo pi`u utilizzato `e il modello RAM1_{(Random Access}

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.

1

Diverso da Random Access Memory!

(7)

Un algoritmo Arisolve un problema computazionale Π ⊆ I × S se e solo se:

1 A riceve come input istanze i ∈ I

2 A produce come output soluzionis ∈ S

3 Dato un inputi ∈ I, A produce come outputs ∈ S tale che

(i , s) ∈ Π

In altre parole:

• _{L’algoritmo A calcola una funzione che mappa ogni istanza}

(input) in una soluzione di tale istanza (output);

• _Se _Π_{ammette pi`}_{u soluzioni per un istanza}_i_{, l’algoritmo A ne}

(8)

Pseudocodice

Per semplicit`a e facilit`a di analisi, descriviamo un algoritmo utilizzando unopseudocodicestrutturato come segue: Algoritmonome(parametri)

Input: breve descrizione dell’istanza di input

Output: breve descrizione della soluzione restituita in output descrizione chiara dell’algoritmo tramite un mix di costrutti di linguaggi di programmazione e linguaggio naturale, dalla quale sia facilmente determinabile la sequenza di passi elementari eseguita per ogni dato input.

USARE SEMPRE QUESTA STRUTTURA PER LO PSEUDOCODICE!!

(9)

Esempio: calcolo della trasposta di una matrice

Problema Computazionale

• I =

• S =

(10)

Algoritmo Transpose(A) Input:

Output:

(11)

Definizione

Pertaglia (size) di un’istanzasi intende una funzione che mappa ogni istanza in uno o pi`u valori, i quali forniscono una misura della sua grandezza. La taglia quindi partiziona l’universo delle istanze in sottoinsiemi di istanze tra loro ”confrontabili”.

Le propriet`a di un algoritmo oggetto di analisi sono spesso espresse in funzione della taglia dell’istanza.

Ad esempio: MergeSort ha complessit`a O (n log n)

In questo caso,n, il numero di elementi da ordinare, è la taglia dell’istanza e la complessità è espressa in funzione di essa.

(12)

Strutture dati

Gli algoritmi usano strutture dati per organizzare e accedere in modo sistematico ai dati di input e a dati intermedi generati durante l’esecuzione.

Definizione

Unastruttura dati`e una collezione di oggetti corredata di metodi di accesso e/o modifica.

Duelivelli di astrazione:

1 Livello logico: specifica l’organizzazione logica degli oggetti

della collezione, e la relazione input-output di ciascun metodo (a questo livello si parla di Abstract Data Type o ADT)

2 Livello fisico: specifica il layout fisico dei dati e la

realizzazione dei metodi tramite algoritmi. Ad esempio in Java:

• _{Livello logico:} _{(gerarchia di) interfacce} • _{Livello fisico:} _{(gerarchia di) classi.}

(13)

Esercizio

Specificare come problema computazionaleΠla verifica se due insieme finiti di oggetti da un universoU sono disgiunti oppure no.

(14)

Esercizio

Specificare come problema computazionaleΠla ricerca dell’inizio e della lunghezza del pi`u lungo segmento di1consecutivi in una stringa binaria.

(15)

Esercizio

SianoAeB due array dininteri ciascuno. Scrivere un algoritmo in pseudocodice per calcolare un arrayC dininteri, tale che

(16)

Esercizio

SianoAeB due array dined minteri, rispettivamente. Scrivere un algoritmo in pseudocodice per calcolare il seguente valore:

v = n−1 X i =0 m−1 X j =0 A[i ] · B[j ]. 16

(17)

Esercizio

SiaAun array di ninteri distinti, ordinato in maniera crescente, edx un valore intero. Scrivere un algoritmo in pseudocodice che restituisca l’indice dix inA, sex appare inA, e−1altrimenti (l’algoritmo deve implementare la ricerca binaria).

(18)

(19)

Analisi degli algoritmi

L’analisi di un algoritmo A mira a studiarne l’efficienza e l’efficacia. In particolare, essa pu`o valutare i seguenti aspetti:

Complessit`a

• tempo

• _spazio

Correttezza

• _terminazione

• soluzione del problema computazionale Noi ci concentreremo su:

1 complessit`a: tempo

(20)

Complessit`

a in Tempo [GTG14, Par. 4.1]

Obiettivo: stimare il tempo di esecuzione (running time) di un algoritmo per valutarne l’efficienza e poterlo confrontare con altri algoritmi per lo spesso problema computazionale.

Osservazioni

Il tempo di esecuzione (di un programma) dipende da

• _{istanza di input: di solito cresce con la taglia, ma a parit`}_{a di}

taglia, 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 complessit`a in tempo?

(21)

Studio Sperimentale

In Java: uso System.currentTimeMillis()

• _{ritorna il numero (long) di millisecondi trascorsi da un evento}

di riferimento (la mezzanotte del 1/1/1970)

• _{invocazione: prima e dopo esecuzione algoritmo} ⇒ differenza Buona idea? OK ma con dei limiti

• _{non pu`}_{o considerare tutti gli input}

• _{richiede l’implementazione di un algoritmo con un programma}

• molto lavoro!

• confronto tra algoritmi: difficile (implementazione ha un ruolo)

(22)

Requisiti per l’analisi della complessit`a in tempo

1 deve considerare tutti gli input

2 deve permettere di confrontare algoritmi (senza

necessariamente determinare il tempo di esecuzione esatto)

3 deve essere eseguibile a partire da una specifica high level

dell’algoritmo (⇒ pseudocodice)

Approccio

• _{analisi al caso pessimo (worst-case) in funzione della taglia}

dell’istanza (req. 1,2)

• Altri tipi di analisi sono possibili: analisi al caso medio (average case), analisi probabilistica

• _{conteggio passi elementari nel modello RAM (req. 2,3)} • _{analisi asintotica (per semplificare il conteggio)}

(23)

Sia A un algoritmo che risolveΠ ⊆ I × S. Definizione

Lacomplessit`a (in tempo) al caso pessimodi A `e una funzione

tA(n)definita come il massimo numero di operazioni che A esegue

per risolvere una istanza di taglia n.

Terminologia: operazioni≡passi elementari del modello RAM.

In altre parole:

• _Sia _t_A,i ₌_{numero di operazioni eseguite da A per l’istanza}_i • _Allora _t_A_{(n) = max{t}_A,i _{: istanza i ∈ I di taglia n}}_.

(24)

Esempio: ArrayMax

Algoritmo ArrayMax(A)

Input: arrayA[0 ÷ n − 1] din ≥ 1interi Output: max intero inA

currMax← A[0]; fori ← 1ton − 1do

if (currMax< A[i ]) then currMax← A[i ]; return currMax

Taglia dell’istanza: n(ragionevole) Per ognin fissato si deve:

• Identificare l’istanza peggiore di taglia n.

• Contare il max numero di operazioni richieste per risolvere tale istanza peggiore.

Facile?

(25)

Limiti inferiori e superiori

Per superare la difficolt`a di identificare l’istanza peggiore si ricorre alla stima di limiti superiori/inferiori.

Si cercano funzionif1(n) e f2(n) tali che

• _t_A_{(n) ≤ f}₁_(n) _{(limite superiore)} • _t_A_{(n) ≥ f}₂_(n) _{(limite inferiore)}

(26)

Analisi di ArrayMax

`

E facile vedere che per una qualsiasi istanza di taglian:

• _{al di fuori del ciclo for ArrayMax esegue un numero costante}

(rispetto an) di operazioni.

• in ciascuna delle n − 1 iterazioni del ciclo for si esegue un numero costante di operazioni.

⇒esistono costantic1, c2, c3, c4> 0 tali che per ogni n

tArrayMax(n) ≤ c1n + c2 (limite superiore)

tArrayMax(n) ≥ c3n + c4 (limite inferiore)

(27)

Analisi di ArrayMax

Dobbiamo stimare le costanti c1, c2, c3, c4? No, perch´e:

• _{E difficile contare in modo preciso le operazioni.}`

• La scelta del set di operazioni `e arbitraria e, in pratica, pu`o variare da computer a computer.

• _{Il tempo di esecuzione, che la complessit`}_{a vuole stimare,}

dipende da tanti fattori che `e impossibile quantificare in modo preciso, e quindi una quantificazione della complessit`a precisa sino alle costanti non ha senso

(28)

Analisi asintotica

• Si ignorano fattori moltiplicativi costanti (= non dipendenti dalla taglia dell’istanza)

• _{Si ignorano termini additivi non dominanti}

Nel caso di ArrayMax `e sufficiente stabilire che

• _t_ArrayMax_(n)_`_{e al pi`}_{u proporzionale a}_n _{(limite superiore)} • _t_ArrayMax_(n)_`_{e almeno proporzionale a}_n _{(limite inferiore)}

In questo caso otteniamo una stima stretta (tight) della complessit`a:

tArrayMax(n) `e proporzionale a n

Per esprimere efficacemente affermazioni come quelle fatte sopra si usano gliordini di grandezza

(29)

Ordini di grandezza

f (n), g (n)funzioni daN ∪ {0}aR.

Definizione

f (n) ∈ O (g (n))se∃c > 0e∃n0≥ 1, costanti non dipendenti dan, tali che

(30)

Esempi

• _{f (n) = 3n + 4} _per_{n ≥ 1}⇒ f (n) ∈ O (n)(c = 7, n0= 1) • f (n) = 3n + 4 pern ≥ 1⇒ f (n) ∈ O (n)(c = 4, n0= 4) • _{f (n) = n + 2n}2 _per _{n ≥ 1}_⇒ _{f (n) ∈ O n}2 (c = 3, n0= 1) • _{f (n) = 3n + 4} _per_{n ≥ 1}⇒ f (n) ∈ O n2 (c = n0 = ) • _{f (n) = 2}100 _per_{n ≥ 1}_⇒ _{f (n) ∈ O (1)}₍_{c =} _n 0 = ) Ricordando chetArrayMax(n) ≤ c1n + c2 pern ≥ 1e c1, c2> 0 costanti, possiamo concludere che

tArrayMax(n) ∈ O (n) (c = c1+ c2, n0 = 1)

(31)

Definizione

f (n) ∈ Ω (g (n))se∃c > 0e ∃n₀ ≥ 1, costanti non dipendenti da

n, tali che

(32)

Esempi

• _{f (n) = 3n + 4} _per_{n ≥ 1}⇒ f (n) ∈ Ω (n)(c = 3, n0 = 1) • f (n) = 3n + 4 pern ≥ 1⇒ f (n) ∈ Ω (n)(c = 1, n0 = 1) • _{f (n) = n + 2n}2 _per _{n ≥ 1}_⇒ _{f (n) ∈ Ω n}2 (c = 1, n0 = 1) • _{f (n) = 6n}2_{+ 1}_per_{n ≥ 1}_⇒ _{f (n) ∈ Ω (n)}₍_{c =} _n 0= ) • _{f (n) = 2}100 _per_{n ≥ 1}_⇒ _{f (n) ∈ Ω (1)} ₍_{c =} _n 0 = ) Ricordando chetArrayMax(n) ≥ c3n + c4 pern ≥ 1 ec3, c4 > 0 costanti, possiamo concludere che

tArrayMax(n) ∈ Ω (n) (c = c3, n0 = 1)

(33)

Definizione

f (n) ∈ Θ (g (n))sef (n) ∈ O (g (n))e f (n) ∈ Ω (g (n)), ovvero

∃c0_{, c}00 _{> 0}_e _n

0≥ 1, costanti non dipendenti dan, tali che:

c0g (n) ≤ f (n) ≤ c00g (n), ∀n ≥ n0

Esempi

• f (n) = 3n + 4 ∈ Θ (n) • _{f (n) = n + 2n}2_{∈ Θ n}2 • _{f (n) = 2}100 _{∈ Θ (1)} • _t_ArrayMax_{(n) ∈ Θ (n)}

(34)

Definizione

f (n) ∈ o (g (n))se∀c > 0 ∃n0 ≥ 1, conc en0 costanti non dipendenti dan, tale che

f (n) ≤ cg (n), ∀n ≥ n0, ovverolimn→+∞f (n)/g (n) = 0.

N.B.n0 `e in genere una funzione dic.

Esempi

• _{f (n) = 100n} _per_{n ≥ 1}⇒ f (n) ∈ o n2

(per ogni c > 0si scelga n0 = 100/c)

• _{f (n) = 3n/(log}₂_n)_per _{n ≥ 1}⇒ f (n) ∈ o (n)

(per ogni c > 0si scelga n0 = )

(35)

Propriet`

a degli ordini di grandezza

Proposizione Si consideri il polinomioPk i =0aini conak > 0ek, ai costanti, ek ≥ 0. AlloraPk i =0aini ∈ Θ nk . Ad esempio: (n + 1)5∈ Θ n5 ([GTG14,R-4.21])

(36)

Proposizione

nk _{∈ o (a}n₎_se _{k > 0, a > 1}_{sono costanti.}

(37)

Proposizione

(log_bn)k ∈ o nh

(38)

Proposizione

Sea, b > 1sono costanti alloralogbn ∈ Θ (logan)

Osservazione 1: Grazie a questa propriet`a, la base dei logaritmi, se costante, si omette negli ordini di grandezza (a meno che il logaritmo non sia all’esponente).

Osservazione 2: Si noti che pera > 0

alog2n_{= 2}log2alog2n_{= n}log2a_.

(39)

Strumenti matematici

• (Parte bassa) ∀x ∈ <, si definiscebxc = pi`u grande intero ≤ x. Ad es.: b3/2c = 1;b3c = 3.

• (Parte alta) ∀x ∈ <, si definiscedxe = pi`u piccolo intero ≥ x. Ad es.: d3/2e = 2;d3e = 3.

• (Modulo)∀x, y ∈ Z, cony 6= 0, si definiscex mod y = resto della divisione intera x /y. (% in Java).

Ad es.: 39 mod 7 = 4;80 mod 4 = 0.

• (Sommatorie notevoli)∀n ∈ Z ea ∈ <, conn ≥ 0 ea > 0vale n X i =0 i = n X i =0 ai = n X ai =

(40)

Analisi di complessit`

a in pratica

Dato un algoritmo A e dettatA(n) la sua complessit`a al caso pessimo si cercano limiti asintotici superiori e/o inferiori atA(n).

Limite Superiore (Upper Bound)

tA(n) ∈ O (f (n))

Si prova argomentando che per ognin “abbastanza grande” e per ciascuna istanza di taglian l’algoritmo esegue ≤ cf (n)operazioni, conc costante (non serve determinarec)

(41)

Limite Inferiore (Lower Bound)

tA(n) ∈ Ω (f (n))

Si prova argomentando che per ognin “abbastanza grande”, esiste una istanza di taglian per la quale l’algoritmo esegue≥ cf (n)

operazioni, conc costante (non serve determinarla)

In alcuni casi `e comodo argomentare che per ciascuna istanza di taglian l’algoritmo esegue≥ cf (n)operazioni

In ogni caso, sia che si provitA(n) ∈ O (f (n)) o che si provi

tA(n) ∈ Ω (f (n))

• _{f (n)} _{deve essere il pi`}_{u vicino possibile alla complessit`}_{a vera}

(tight bound)

• _{f (n)} _{deve essere il pi`}_{u semplice possibile}⇒ no costanti, no termini additivi di ordine inferiore. Solo termini essenziali!

(42)

Terminologia per complessit`

a [GTG14, Par. 4.2]

• _logaritmica: _{Θ (log n)}_{, base} ₂_{o costante} _{> 1} • _lineare: _{Θ (n)} • _quadratica: _{Θ n}2 • cubica: Θ n3 • _polinomiale: _{Θ n}k_{, k ≥ 1} _costante • _{esponenziale:} _{Ω (a}n_{), a > 1}_costante 42

(43)

Esempio: Prefix Averages ([GTG14 ] pp. 164-165)

Si consideri il seguente problema computazionale: dato un array din

interiX [0 ÷ n − 1]calcolare un arrayA[0 ÷ n − 1]dove

A[i ] =   i X j =0 X [j ]   1 i + 1, per 0 ≤ i < n.

Nel prossimo lucido vedremo 2 algoritmi che risolvono in problema con complessità rispettivamente quadratica (algoritmo banale basato sulla definizione) e lineare (algoritmo efficiente che evita di ricalcolare più volte la stessa quantità). Per entrambi gli algoritmi vale la seguente specifica di input-output:

Input: X [0 ÷ n − 1]array dininteri Output: A[0 ÷ n − 1]: A[i ] = (Pi

(44)

Algoritmo prefixAverages1 for i ← 0to n − 1do a ← 0; for j ← 0toi do a ← a + X [j ]; A[i ] ← _{i +1}a ; returnA Complessit`a Algoritmo prefixAverages2 s ← 0; for i ← 0to n − 1do s ← s + X [i ]; A[i ] ← _{i +1}s ; returnA Complessit`a 44

(45)

Esercizio

SiaAun algoritmo che ricevuto in input un arrayX di ninteri esegue • c1noperazioni per ogni intero pari inX

• c2dlog2neoperazioni per ogni intero dispari inX,

dovec1ec2 sono costanti positive. Analizzare la complessit`a in tempo dell’algoritmo esprimendola conΘ (·).

(46)

(47)

Esercizio

Il seguente pseudocodice descrive l’algoritmo di ordinamento chiamato InsertionSort

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 }

(48)

Esercizio (continua)

1 Trovare delle opportune funzionif1(n),f2(n)ef3(n)tali che le seguenti affermazioni siano vere, per una qualche costante c > 0e pernabbastanza grande.

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

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

• Esiste una istanza di taglianper la quale l’algoritmo esegue

≥ cf3(n)operazioni.

La funzionef1(n)deve essere la pi`u piccola possibile, mentre le funzionif2(n)ef3(n)devono essere le pi`u grandi possibili.

2 SiatIS(n)la complessit`a al caso pessimo dell’algoritmo. Sfruttando le affermazioni del punto precedente trovare un upper boundO (·) e un lower bound Ω (·)pertIS(n).

(49)

Regola di buon senso

Complessit`a polinomiale (o migliore) ⇒ algoritmo efficiente Complessit`a esponenziale ⇒ algoritmo inefficiente

Giustificazione≈[GTG14,4.3.2]

Supponiamo che la complessit`atA(n) sia espressa in ns, e sia

nτ =max taglia eseguibile in tempo τ Per ottenerenτ, risolviamo tA(nτ) rispetto anτ Esempi • _log₂_n_τ _{= τ} ⇒ nτ = 2τ • nτ = τ • _n2 τ = τ ⇒ nτ = √ τ • ₂nτ _{= τ} _⇒ _n τ = log2τ

(50)

Complessit`a polinomiale (o migliore) ⇒ algoritmo efficiente Complessit`a esponenziale ⇒ algoritmo inefficiente

Giustificazione≈[GTG14,4.3.2]

Supponiamo che la complessit`atA(n) sia espressa in ns, e sia

nτ =max taglia eseguibile in tempo τ Per ottenerenτ, risolviamo tA(nτ) rispetto anτ

tA(n) nτ : τ = 109ns nτ : τ = 60 × 109ns nτ: τ = 3600 × 109ns

(1 sec) (1 min) 1 hour

log2n 2 109 = ∞ ∞ ∞ n 109 _{6 × 10}10 _{3.6 × 10}12 n2 104.5 ≈ 8 × 104.5 _{≈ 1.8 × 10}6 2n _{≈ 30} _{≈ 36} _{≈ 42}

N.B.: numero di atomi nell’universo =1078÷ 1082_{= 2}259_{÷ 2}272

(51)

un algoritmo

(o meglio la sua

assenza) ha rivoluzionato la

nostra società

un algoritmo

potrebbe

distruggerla

(52)

Esempio: sicurezza in internet

Crittografia a chiave pubblica

Alice&

Bob&

message&

m

Bob: chiave privatak1, chiave pubblicak2

• Alice invia a Bob un messaggiom cifrato con k2

• _{Bob decifra il messaggio ricevuto da Alice con}_k₁

(53)

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 dip, q) Chiave privata: N, d (d < N funzione dip, q) messaggiom:

• _cifratura: _{m → (m}e_{) mod N = ¯}_m

• decifratura: m →¯ m¯d_{mod N = m}

N.B.: pur conoscendoN ede, per conoscere d, necessario per la decifratura, mi serve conoscerep e q

Ottenerep e q daN `e difficile!

(54)

Algoritmo banale

forp ← 2tob√Ncdo

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

Sep, q ∈ Θ√N⇒la complessit`a `eΘ√N= Θ 2n2.

Esempio numerico

• n = 1024⇒2n2 = 2512≥ 10154

• Sul computer pi`u potente al mondo (≈ 1018 _{flop/sec) l’algoritmo} banale richiederebbe circa10154/1018= 10136sec

• 1 anno ha ≤ 108 _sec_⇒_{> 10}128 _{anni di calcolo ...}

Osservazione

Esistono algoritmi più efficienti ma sempre con complessità esponenziale. 2009: risolto problema conn = 768(2 anni di calcolo, centinaia di macchine). Non si può escludere l’esistenza di un algoritmo efficiente.

(55)

Dalla motivazione del A.M. Turing Award 2002 assegnato 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 communicate sensitive information like credit card numbers over an unsecure internet without having to agree on a shared secret key ahead of

time. Most people ordering items over the internet don’t know that the system is in use unless they notice the small padlock symbol in the corner of the screen. RSA is a prime example of an

(56)

Efficienza asintotica degli algoritmi

A,B che risolvonoΠ

tA(n), tB(n) complessit`a diA, B (rispettivamente) al caso pessimo

tA(n) ∈ o (tB(n)) ⇒A `e “asintoticamente pi`u efficiente” di B.

N.B.: n0 potrebbe essere molto grande!!

(57)

Caveat sull’analisi al caso pessimo

Caveat 1: il caso pessimo potrebbe essere costituito solo daistanze patologichementre per tutte le istanze di interesse la complessit`a potrebbe essere asintoticamente migliore (es: Quicksort)

Soluzioni

• restringere con opportune assunzioni il dominio delle istanze per mantenere quelle di interesse ed escludere quelle patologiche • analisi del caso medio o aggirare il caso pessimo probabilisticamente.

(58)

Caveat sull’analisi al caso pessimo

Caveat 2: Le costanti trascurate potrebbero avere un impatto cruciale in pratica.

Esempio

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

⇒t_A(n) = o (t_B(n))⇒A è più efficiente di B • in realtà: t_A(n) < t_B(n)solo sen > 10100

N.B.: 10100_>>_{numero di atomi dell’universo...} Esempio

• t_A(n) = 400 log₂n t_B(n) = log2₂n

t_A(n) < t_B(n)⇒log₂n > 400 ⇒n > 2400_{≥ 10}100_{. . .}

Soluzioni: dare una stima delle costanti nel caso siano molto elevate.