Supponiamo che f(n) sia la funzione che Algoritmi esponenzialilaurap/didattica/... · da un...

1

Algoritmi esponenziali


• Supponiamo che f(n) sia la funzione che rappresenta il numero di operazioni eseguite da un algoritmo e supponiamo che il tempo necessario per compiere una operazione sia un microsecondo: 1µs = 10-6sec.

• Vogliamo vedere che per valori di n non elevati gli algoritmi impiegano un tempo troppo elevato per poter essere utilizzati: gli algoritmi esponenziali sono impraticabili.


• Vediamo questa tabella dove riportiamo, al variare di n, il tempo impiegato da alcune funzioni di n

n log2(n) 100*n 10*n2 n3 2n

10 2.3 µs 1ms 1ms 1ms 1024µs

~ 1ms

20 2.99µs 2ms 4ms 8ms 1.048sec

60 4.09µs 6ms 36ms 0.21sec 260µs

~ 366 secoli


260µs ~ 366 secoli, vediamo come mai

260µs ~ 10 60×0.3µs ~ 1018µs~ 1012 sec (1.1529 ×1012)

(1µs = 10-6sec )

• Quanti secondi in un anno?

1 minuto = 60 secondi 1 ora = 3600 secondi

1 giorno = 86400 secondi 1 secolo = 3.15×109 secondi

secondi 1.1529 ×1012

secoli = = = 366

secondi in un secolo 3.15×109

2


• Esistono degli algoritmi che sono intrinsecamente esponenziali:• calcolare le permutazioni di n elementi:

n! ~ nn

• Ci sono problemi che sono risolti da un algoritmo deterministico esponenziale, ma il cui algoritmo non deterministico è polinomiale. L’algoritmo non deterministico è un algoritmo ideale che può essere simulato pensando di poter eseguire scelte contemporanee; è rappresentabile su un albero: la profondità dell’albero può essere proporzionale alla dimensione del problema. Tali problemi si chiamano NP (Non deterministico Polinomiale).


• Esempio.

• Consideriamo la formula logica

F(x1, x2, x3) = (x1 e x2 e x3) o (non x1 e non x2)

e ci chiediamo se esiste una scelta di valori per le variabili x1, x2, x3 che renda vera F.

• Un algoritmo deterministico prova tutte le possibilità e poiché il valore di xi può essere vero o falso, le possibilità sono 23.


• In generale considerando F(x1, x2, .., xn) il problema può essere risolto in un tempo O(2n).

• L’algoritmo non deterministico è in grado di scegliere il valore di xi che porta alla soluzione. Per simulare tale comportamento si può costruire un albero: ogni nodo rappresenta una variabile della formula; da ogni nodo partono due rami che rappresentano il vero e il falso.


• Se potessimo esplorare l’albero in modo da poter percorrere contemporaneamente i due rami V e F, in n passi arriveremmo alle foglie. Quindi l’algoritmo non deterministico è O(n).

v f

x1

x2

x3

……

. . . . . . . . . . . . . .

x1

x2 x2

x3x3 x3x3

3

Complessità asintotica

• Le considerazioni fatte sulla complessitàvalgono solo se

n →∞ e F(n) →∞

• Se invece n si mantiene limitato anche un algoritmo esponenziale può essere utilizzato; per lo stesso motivo anche la costante moltiplicativa, che solitamente trascuriamo nella notazione O-grande, può invece essere fondamentale nella scelta.

Complessità asintotica

• Esempio.

f1(n) = 1000 * n f2(n) = 10 * n2

f1 è O(n) f2 è O(n2)

• Quindi:

• se n →∞ è preferibile f1

• se n ≤10 è preferibile f2 , infatti:

1000 * n ≤ 1000*10 = 104

10 * n2 ≤ 10*100 = 103

Ordinamento per inserimento


• L’idea è quella di inserire una componente in ordine rispetto ad una sequenza di componenti già ordinate.

• Esempio. Vogliamo inserire 6 nella sequenza:

2 5 7 9 10

• La cosa più efficiente è partire dall’ultima posizione e slittare verso destra le componenti che sono maggiori si 6: in tale modo quelle più piccole restano “ferme”:

2 5 7 7 9 10

ora c’è posto per inserire 6.

4


• Per effettuare l’ordinamento si parte dalla seconda componente che si inserisce in ordine rispetto alla prima, poi si considera la terza, che si inserisce in ordine rispetto alle prime due, in generale: si vuole inserire la k-esima componente in ordine rispetto alle k-1 già ordinate.

• Poiché il numero di componenti non aumenta, per poter slittare in avanti le componenti che precedono nella sequenza, è necessaria una variabile di appoggio x per salvare il valore:

2 5 9 11 3 1 20

x

2 3 5 9 11 1 20

Ordinamento per inserimento• Bisogna non uscire dall’array se si deve inserire un

valore prima della prima componente. Ci sono varie strategie per realizzare ciò, una di queste è sfruttare la “valutazione pigra dei predicati”:

……………for(k=1; k<=n-1; k++) //v[0] è già

//in ordine

x=v[k];

i=k;

while((i!=0) && (x < v[i-1]))

v[i]=v[i-1];

i--; //fine while

v[i]=x;

//fine for


• Complessità.

• Caso favorevole: array già ordinato

1 3 8 10 20

il predicato del ciclo interno è sempre falso, ( x < v[i-1] è falso), quindi il numero di operazioni è

proporzionale a n : Ω (n).

• Caso peggiore: array in ordine inverso

20 10 9 7 4 1

il ciclo interno viene sempre eseguito per valori crescenti di i=k:

1 + 2 + 3 + …. + (n-1) = n (n-1)/2 : O(n2/2)

Divide et impera

5

Divide et impera

• La tecnica detta “divide et impera” è una strategia generale per impostare algoritmi.

• Consideriamo un problema P e sia n la dimensione dei dati, la strategia consiste nel:

• suddividere il problema in k sottoproblemi Pi di dimensione inferiore (ciascuno di dimensione ni) e successivamente riunire i risultati ottenuti dalle k soluzioni.

• La frase è attribuita a Filippo il Macedone e fu un principio politico: mantenere divise le popolazioni dominate per poter governare con più facilità.

Divide et impera

• Se i k sottoproblemi sono “formalmente” simili al problema di partenza, si ottiene una scomposizione ricorsiva. Ci deve pertanto essere una dimensione hdel problema che porti ad una risoluzione diretta, vale a dire che non necessiti della ricorsione.

• Indichiamo con:

• S l’insieme dei dati

• k il numero dei sottoproblemi

• h la dimensione limite

• Si può scrivere uno schema generale per la scomposizione.

Divide et impera

algoritmo DIVETIMP (S, n)

se n < h

allora risolvere direttamente il problema P

altrimenti dividere S in k sottoinsiemi

risolvere separatamente i k

sottoproblemi P1, …, Pk:

DIVETIMP(S1,n1), … ,

DIVETIMP(Sk,nk)

riunire i risultati ottenuti

//finese

//fine algoritmo

Divide et impera: complessità• Indichiamo con T(n) la complessità del

problema P sull’insieme dei dati di dimensione n; poiché l’algoritmo è ricorsivo si ottengono delle formule “di ricorrenza”:

T(n) = costante n<h

T(n) = D(n) + C(n) + T(n1) + T(n2) + … T(nk)

• D(n): complessità dell’algoritmo per dividerel’insieme

• C(n): complessità dell’algoritmo per riunire i risultati

• T(ni): complessità dell’algoritmo sull’insieme di dimensione ni.

6

Quicksort

• L’idea è la seguente:

• è più conveniente ordinare due array di s e tcomponenti piuttosto che un array di ncomponenti (s + t = n)

• si aumenta l’efficienza dell’ordinamento scambiando elementi lontani tra loro.

(Argomenti avanzati 13.3)

• Verifichiamo la prima idea; supponiamo s=t=n/2 e prendiamo la formula n(n-1)/2 che rappresenta la complessità dell’ordinamento nel caso peggiore e riscriviamola per n/2 invece che n.

Quicksort

2·[(n/2) (n/2 – 1) /2] = n2 /4 – n/2

n2 /4 – n/2 < n2 /2 – n/2 = (n2 – n)/2 =

= n ·(n-1) /2

• Verifichiamo la seconda idea; supponiamo di avere un array ordinato in senso inverso; scambiando gli elementi opposti (il primo con l’ultimo, il secondo con il penultimo, ecc.) in n/2 operazioni ordiniamo l’array. Questi elementi sono “lontani” tra loro: quelli piùgrandi sono al posto di quelli più piccoli.

Quicksort

• Dobbiamo ora dividere l’insieme in due parti e vogliamo sfruttare la seconda idea: scambiare elementi lontani. Scegliamo un elemento dell’arrayper eseguire i confronti e lo chiamiamo conf; dividiamo l’insieme in modo tale che gli elementi piùpiccoli di conf possano essere messi a sinistra di confe quelli più grandi a destra, rispettando così l’ordine. A questo punto l’insieme è diviso in due partiindipendenti e l’elemento conf è al suo posto.

≤ conf ≥

Quicksort

• Si potrà proseguire in maniera ricorsiva fino a considerare un array di dimensione 1, che non dovràessere ulteriormente suddiviso. Se “guardiamo”(riunire i risultati) l’array dalla prima componente all’ultima, vediamo che l’array è ordinato.

• Scriviamo il progetto dell’algoritmo secondo lo schema “divide et impera” per ordinare un array vdalla componente n1 alla componente n2 (alla prima invocazione del metodo n1 ed n2 saranno la prima e ultima componente).

7

Quicksort

algoritmo quicksort(n1,n2,v)

se n1 < n2

allora chiamare l’algoritmo

partizione(n1, n2, v) che restituisce

il valore k della posizione di conf

chiamare quicksort(n1, k-1, v)

chiamare quicksort(k+1, n2, v)

//finese

//fine quicksort

• Quando n1=n2 l’array ha un solo elemento e pertanto la ricorsione ha termine.

Quicksort

• Come scegliere l’elemento conf?

• Dobbiamo stabilire un criterio che si possa facilmente ripetere in tutte le suddivisioni successive.

• Stabiliamo di scegliere la prima componente di quella porzione di array (da n1 a n2) che vogliamo ordinare: v[n1].

• Ci sono varie scritture dell’algoritmo quicksort, alcune ottimizzano il numero di confronti, ma lasciano inalterata la complessità.

Quicksort

• Per realizzare la partizione avremo bisogno due indici: un indice i che scorre l’array con valori crescenti e che parte dalla posizione successiva a quella di conf (i=n1+1), un altro indice k che descrive l’array con valori decrescenti e parte dall’ultima posizione (k=n2).

• Quando questi due indici saranno uguali avremo terminato la partizione e si potrà “sistemare” conf al suo posto.

• Vediamo un progetto per l’algoritmo di partizione.

Quicksort

algoritmo partizione(n1, n2, v)

conf ← v[n1]

i ← n1+1

k ← n2

mentre i ≠ k eseguire

menre v[i] ≤conf e i ≠ k eseguire

i ← i+1

//fine mentre

mentre v[k] ≥conf e i ≠ k eseguire

k ← k-1

//fine mentre

scambiare v[i] con v[k]

8

Quicksort

//fine mentre: ciclo esterno

//sistemare conf nella posizione k=i: è al suo posto

se v[k] > conf

allora k ←k-1

//finese

scambiare v[n1] con v[k]

//fine partizione

• E necessario il confronto tra conf e v[k]?

Quicksort

• Esempio.

10 5 11 1 13 2 20

conf i=2 i=3 k=6 k=7

10 5 2 1 13 11 20

i=4 i=5

k=5

i = k = 5 termina anche il ciclo esterno

v[k]>conf (10>13) quindi k-1

1 5 2 10 13 11 20

Quicksort

• Esempio.

20 3 1 10 9 7 11conf i=2 i=3 i=4 i=5 i=6 i=7= k

i = k = 7 termina anche il ciclo esterno

v[k]>conf falso : k non varia

11 3 1 10 9 7 20

Quicksort

• L’algoritmo del libro è scritto diversamente:

from=n1 to=n2

i=n1-1 k=n2+1 (esterni), conf=pivot

il ciclo esterno ha predicato i<k ; all’inizio del ciclo i++ ; il confronto v[i]<conf è falso (sono uguali) quindi si passa al secondo ciclo e conf viene messo come ultimo (non necessariamente al suo posto). Manca il confronto i≠k, perché in fondo c’è conf.

Nella versione con conf al centro è necessario il predicato i ≠ k per non uscire dall’array (se conf è il più grande elemento, come nel secondo esempio).

9

Quicksort

• Complessità. Contiamo i confronti tra conf e gli elementi v[i]:

0 se n = 0,1 (n1<n2)

T(n) =

D(n) + C(n) + T(k-1) + T(n-k)

D(n) = complessità dell’algoritmo partizione

C(n) = 0 “guardare” le due parti dell’array

D(n) è O(n): n-1 confronti nei predicati dei cicli interni + 1 confronto per sistemare conf.

Quicksort

• Caso peggiore: vettore ordinato, la partizione èsbilanciata:

T(n) = n + T(0) + T(n-1) = n + T(n-1) =

= n + (n-1 + T(0) + T(n-2)) = n + n-1 + T(n-2) =

= n + (n-1) + (n-2) + T(n-3) =

= ….. = n + (n-1) + + 1 + T(0) + T(n – (n-1)) =

= n (n-1)/2

Quicksort

• Caso favorevole: conf sempre al centro: la partizione è bilanciata:

T(n) = n + T(n/2) + T(n/2) = n + 2T(n/2) =

= n + 2(n/2 + 2T(n/4)) = 2n + 22T(n/22) =

= ….. = k·n + 2k·T(n/2k)

se n = 2k allora k = log2n O(n·log2n)

Mergesort

• L’idea è la seguente:

• dividere l’insieme in due parti uguali di n/2 componenti

n/2 n/2

• se fossero già ordinate le potremmo riunirecon un algoritmo di fusione (merge)

10

Mergesort

Esempio. Consideriamo i due array ordinati A e B e costruiamo l’array MG che contiene gli elementi di A e B (con eventuali ripetizioni) in ordine: si considerano le prime componenti, quella più piccola viene inserita nell’array MG, e si considera la sua successiva; quando uno dei due è terminato, basta ricopiare l’altro.

A: 1 5 6 8 10

B: 0 1 3 4

MG: 0 1 1 3 4 5 6 8 10

Mergesort

• Per ordinare le due parti di n/2 componenti, usiamo in maniera ricorsiva la stessa strategia: dividere a metà, per poi fondere le parti ordinate, proseguendo fino ad un array di un solo elemento.

• La dimensione limite è h=2: se n<2 c’è un solo elemento.

• Vediamo quindi il progetto dell’algoritmo mergesort per ordinare un array v dalla componente p alla componente q (par.13.4).

Mergesort

algoritmo mergesort(v, p, q)

se p<q

allora medio ← (p+q)/2 //troncata

chiamare mergesort(v, p, medio)

chiamare mergesort(v, medio+1, q)

chiamare merge(v, p, medio, q)

//finese

//finemergesort

• Per gestire la fusione pensiamo all’array diviso in due parti, da p a medio, e da medio+1 a q; inoltre usiamo un array di supporto s per “appoggiare” le componenti di v in ordine.

Mergesort

algoritmo merge(v,p,medio,q)

h ← p

i ← p

k ← medio+1

mentre h ≤ medio e k ≤ q eseguire

se v[h] ≤ v[k]

allora s[i] ← v[h]

h ← h+1

altrimenti s[i] ← v[k]

k ← k+1

//finese

i ← i+1

11

Mergesort

//finementre

//ricopiare la parte di array non esaminata

se h = medio+1

allora copiare in s la seconda parte

altrimenti copiare in s la prima parte

//finese

ricopiare s sul v

//fine merge

• Esercizio. Implementare gli algoritmi quicksort e mergesort ed eseguire le prove dei tempi o contare le chiamte ricorsive.

Mergesort

• Complessità. Contiamo i confronti tra gli elementi dell’array:

0 se n = 0,1

T(n) =

D(n) + C(n) + T(n/2) + T(n/2)

D(n) = 0 calcolo di medio

C(n) = complessità dell’algoritmo di fusione

C(n) è O(n): vengono considerati tutti gli elementi delle due parti lunghe n/2

Mergesort

• Il numero di confronti è sempre lo stesso perchéanche se l’array è ordinato si esegue sempre la divisione a metà e la fusione delle due parti; le partizioni sono bilanciate:

T(n) = n + T(n/2) + T(n/2) = n + 2T(n/2) =

= n + 2(n/2 + 2T(n/4)) = 2n + 22T(n/22) == ….. = k·n + 2k·T(n/2k)

se n = 2k allora k = log2n O(n·log2n)

Mergesort e Quicksort

• Confrontiamo i due algoritmi.

• L’algoritmo mergesort ha la complessità piùbassa nel caso peggiore O(nlog2n); esegue però molte ricopiature per eseguire la fusione.

• L’algoritmo quicksort ha caso peggiore O(n2/2), ma nel caso favorevole e medio èO(nlog2n).

• In Java l’algoritmo sort implementa l’ordinamento per inserimento per n<7, e quicksort negli altri casi.

12

Mergesort

• Albero delle chiamate ricorsive.

v0 v1 v2 v3 v4 v5 v6 v7

1 0 8 5 4 3 -1 9

1 0 8 5 4 3 -1 9

1 0 8 5 4 3 -1 9

1 0 8 5 4 3 -1 9

0 1 5 8

0 1 5 8

Il meccanismo della ricorsione

• Schematizziamo un algoritmo ricorsivo nel modo seguente:

algRicorsivo(parametri)

α

se P

allora β

altrimenti γ

chiama algRicorsivo(nuoviparametri)

δ

//finese

ritorno

//fine algRicorsivo


dove α, β , γ , δ sono gruppi di istruzioni, P è il predicato che governa la ricorsione, ritorno indica ritorno al chiamante (ci può essere uno scalare oppure void).

• Vediamo il funzionamento:

• α (P vero) β ritorno

• α (P falso) γ chiama [α (P vero) β ritorno] δ

ritorno

• Supponiamo che P sia falso 3 volte e indichiamo solo le istruzioni α, β , γ , δ


falso falso falso vero ritorno ritorno ritorno

α γ α γ α γ α β δ δ δ

• Le istruzioni δ devono essere eseguite con i valori dei parametri al momento in cui le operazioni α γ hanno effettuato la chiamata: vengono salvati nel RunTimeStack.

• Dallo schema si vede che una scomposizione ricorsiva si può sempre trasformare in iterativa.

13


• Se l'istruzione δ non c'è, la ricorsione si scioglie facilmente:

α (P falso) γ α (P falso) γ α (P falso) γ α (P vero) β

e si trasforma nella seguente struttura iterativa dove (non P) è il valore di predicato che effettua la chiamata:

α

mentre non P eseguire

γ

costruire nuoviparametri

α

//finementre

β


• Esempio. Stampare i primi numeri naturali in ordine decrescente: n, n-1, n-2, …, 1.

algoritmo stamparic( intero n)

se n>0

allora stampare n

chiamare stamparic(n-1)

//finese

//fine algoritmo

• manca δ; l’algoritmo è semplice, manca l’istruzione α, e manca β pertanto la chiamata è per n>0.


• Trasformiamo l’algoritmo: se la chiamata viene eseguita quando n>0, pertanto questo sarà il predicato del ciclo:

mentre n>0 eseguire

stampare nn← n-1 //costruire nuovi parametri

//finementre

• Esercizio. Stampare i numeri in ordine crescente. Costruire “manualmente” lo Stack per memorizzare δ.

Matrici: array a due dimensioni

14

Matrici

• Vogliamo rappresentare informazioni omogenee (dello stesso tipo) ma descritte da una coppia di indici (Argomenti avanzati 7.2):

aik i=1, 2, …, n

k=1, 2, … , m

matrice A di n righe e m colonne:

a11 a12 … a1m

A = ………….

an1 an2 …. anm

Matrici

• Molti problemi matematici fanno uso di matrici; uno dei problemi più frequenti è la risoluzione di un sistema lineare di nequazioni in n incognite (estensione del

sistema 2××××2 che rappresenta il determinare il punto di intersezione di due rette del piano) e che si può rappresentare algebricamente come

“prodotto matrice ×××× vettore”:

A x = b

Matrici

• Come si definiscono le matrici in Java.

• Una matrice è un array di array:int a[][]; // a è la referenza

per creare l’oggetto si deve usare new:

a = new int [5][4];

• La matrice a ha le seguenti componenti:

a[0][0] . . . a[0][3]

a[1][0] . . . a[1][3]

. . .

a[4][0] . . . a[4][3]

Matrici

• Per accedere ad un elemento di un arraybidimensionale si devono indicare entrambi gli indici:

a[2][1] = 5;

e tali indici devono essere compatibili con la dimensioni dell’array. Nel nostro esempio le righe sono 5 e quindi l’indice varia da 0 a 4, le colonne sono 4 e l’indice delle colonne varia da 0 a 3.

15

Matrici

• Per conoscere il valore delle due dimensioni si usa il campo length:

• il numero di righe è a.length

• il numero di colonne è a[0].length

• Cosa è a[0]? Cosa “vede” a?

• a[0] è una referenza ad un array di interi che rappresenta la prima riga;

• a è una referenza ad un array di referenze (o come si dice: un array bidimensionale è un array di array).

Matrici

a

a[0]

a[1]

a[2]

a[3]

a[4]

a[0][0] … a[0][3]

a[4][0] … a[4][3]

Matrici

• Se n=m la matrice si dice quadrata. Queste sono le matrici maggiormente usate nella matematica.

• Gli elementi con indice uguale individuano un arrayche si chiama diagonale della matrice:

diagA = [a11, a22, …, ann]

• Se due matrici A e B hanno lo stesso numero di righe e colonne si può costruire la matrice somma C:

C=A+B cik = aik + bik

Matrici

• Date due matrici A (n ×××× p) e B (p ×××× m) se il numero di colonne di A è uguale al numero di righe di B allora si può definire la matrice C = A ×××× B “prodotto righe ×××× colonne”:

p

cik = ∑ ait · btkt =1

• Consideriamo matrici quadrate.• La matrice A possiede n2 elementi, quindi

difficilmente gli algoritmi su matrici avranno una complessità inferiore a O(n2).

16

Matrici

• L’algoritmo per costruire la somma di due matrici èΘ(n2).

• L’algoritmo per costruire il prodotto, applicando la definizione, è Θ(n3); ne esistono di complessità O(nα) con 2< α < 3.

• L’algoritmo per risolvere il sistema lineare Ax=b(data la matrice A e il vettore b determinare il vettore x) noto come “regola di Cramer” ha complessitàO(n!); esistono “metodi diretti” con i quali si trasforma la matrice in una equivalente, per il problema di risolvere il sistema lineare, e che richiedono O(n3) operazioni e “metodi iterativi” che approssimano la soluzione in O(n2) operazioni.

Matrici

• L’identità del prodotto tra matrici si chiama “matrice identica” I ed è una matrice con 1 sulla diagonale e 0 altrove.

• Esercizio. Scrivere un algoritmo per costruire la matrice identica che esegua n2 + n assegnazioni • non eseguire l’ovvio controllo:

se i ≠k

allora ….0

altrimenti … 1

che porterebbe a n2 assegnazioni + n2 confronti

Matrici

• Il prodotto tra matrici non è commutativo:

A ×××× B ≠ B ×××× A

fatta eccezione del caso in cui una delle due sia la matrice I oppure che le due matrici siano uguali.

• La matrice costruita a partire dalla matrice A scambiando le righe con le colonne si chiama “matrice trasposta” di A, e si indica con AT:

aTik = aki

Matrici

• Una matrice si dice simmetrica se:

aik = aki ∀∀∀∀ i,k

• Se A = AT allora A è simmetrica.

• Due matrici A e B sono uguali se:

aik = bik ∀∀∀∀ i,k

• Esercizio. Scrivere un algoritmo (efficiente) per verificare che due matrici sono uguali o che una matrice è simmetrica.• Suggerimento: se una proprietà deve essere verificata per

ogni elemento, essa è falsa se esiste un solo elemento che non la verifica.

17

Matrici

• Esercizi per imparare ad usare gli indici delle matrici.

1) date due matrici A(n ×××× m) e B(p ×××× q) verificare se B è contenuta in A

1 2 3 5 0 -1

A = 4 0 -1 7 B =

3 2 1 4 2 1

invece 1 2 non è contenuta

3 2

Matrici

2) Dato un cruciverba A(n××××m), matrice di caratteri, e una parola P composta da q caratteri verificare se la parola P sta nel cruciverba per righe o per colonne; verificare che le dimensioni siano compatibili, cercare la prima componente di P se è presente in A ed eseguire la verifica solo se la lunghezza della parola non supera il numero di righe o di colonne che restano da verificare.

Matrici

3) Dati n numeri a1, a2, a3, …, an determinare quanti sono minori a1, quanti minori di a2, di a3, … e in quali posizioni si trovano (per ogni i si deve poter memorizzare un array di indici) e quali sono (per ogni i si deve poter memorizzare un array di valori) .

Altri algoritmi per Fibonacci

18


• I due seguenti algoritmi si basano sulle matrici.

• Consideriamo la matrice A e la matrice An-1:

si può dimostrare per induzione

che la matrice An-1 = A ×××× A ×××× .. ××××A

n-1 volte

1 1

A=1 0

1 1 n-1 Fn Fn-1

An-1 = =

1 0 Fn-1 Fn-2


• Esercizio. Verificare la formula per n=2, 3, 4.

• Si può allora costruire un algoritmo che calcola la potenza n-esima di A, matrice M, e restituisce il primo elemento di M, corrispondente a Fn:

intestazione metodo fibonacci4 (n intero)

intero i

M ← I //matrice identità

per i da 1 a n-1 eseguire

M ←M * A

//fineper

restituire M[0][0]

//finealgoritmo


• La complessità di tempo è O(n): infatti c’èuna struttura iterativa per calcolare il prodotto tra due matrici di dimensione 2×2 (un numero finito di prodotti e somme)

• La complessità di spazio è O(1): le matrici A, M, I occupano una quantità di spazio costante.

• Il prossimo algoritmo è una ottimizzazione dell’algoritmo precedente: si può eseguire la potenza n-esima con un algoritmo basato sui quadrati.


• Esempio. Vogliamo calcolare 48.

48 = 4 · 4 · …. · 4

8

42 = 16 162 = 44 = 256 2562 = 48

quindi in 3= log28 passi abbiamo eseguito il calcolo.

• In generale:

Mn = ( M n/2)2

con n pari

19


poiché la divisione è troncata, se n è dispari

(n/2) · 2 è uguale a

((n-1)/2) · 2 = (n-1)

occorre perciò un’altra moltiplicazione per M.

intestazione metodo fibonacci5 (n intero)

M ← I

chiama potenzamatrice(M, n-1)

restituire M[0][0]

//finealgoritmo


intestazione algoritmo potenzamatrice(matrice M, intero n)

se n>1

allora potenzamatrice(M, n/2)

M ← M * M

//finese

se n è dispari

allora M ←M * A

//finese

//finealgoritmo

• La complessità di tempo è O(log2n)

• La complessità di spazio è O(1).

Trasformare arrayparalleli in array di

oggetti

Trasformare array paralleli in array di oggetti

• Un array è una struttura di dati omogenea: gli elementi dell’array sono tutti dello stesso tipo (che è il tipo dell’array).

• A volte è necessario gestire informazioni di tipo diverso ma riferite allo stesso concetto.

• Supponiamo di voler memorizzare delle informazioni riguardanti gli impiegati di una ditta: nome, stipendio, età. Possiamo pensare di costruire tre array distinti, uno per ogni tipo di informazione (Consigli per la qualità 7.2).

20


String nome[] = new String[1000];

double stipendio[]=

new double[1000]; i

int eta[]= new int[100];

Per avere informazioni nome stipendio età

sull’impiegato i-esimo

accediamo alla componente

i-esima di ciascuno dei tre array.


• I tre array sono strettamente correlati tra loro: devono avere la stessa lunghezza, un algoritmo che elabora le informazioni su un impiegato deve avere i tre arraytra i suoi parametri, se si volesse aggiungere un’ulteriore informazione, si dovrebbe tenere presente l’organizzazione comune ai tre array (l’i-esimo impiegato sta all’i-esimo posto).

• Linguaggi come Java mettono a disposizione la possibilità di considerare l’impiegato come un concetto e di considerarlo un’unica informazione suddivisa in tre campi.


• Questo tipo di informazione nei linguaggi di programmazione si chiama record e rappresenta una collezione di elementi di tipo diverso. La parola record (registrazione) è una parola “antica” dei linguaggi di programmazione, così come la parola file (archivio). Sono parole nate in riferimento alla registrazione di dati su supporti fisici come i nastri magnetici (o i dischi); l’archivio che contiene l’insieme delle informazioni registrate prendeva il nome di file di dati.


• Noi possiamo realizzare un concetto “impiegato” ed utilizzare una classe, i cui campi saranno le informazioni che caratterizzano l’impiegato:

public class Impiegato

String nome;

double stipendio;

int eta;

21


• Possiamo costruire un array ditta le cui componenti sono di tipo Impiegato:

Impiegato ditta[] =

new Impiegato[100];

• In tale modo invece di avere tre array paralleli abbiamo un array di record, detto anche tabella, e per accedere all’i-esimo impiegato utilizzeremo la componente i-esima dell’array:

ditta[i]


• Per accedere ai campi si può scrivere

ditta[i].nome

ditta[i].stipendio

ditta[i].eta

• Secondo le regole della programmazione ad oggetti noi, invece, definiremo private i campi della classe Impiegato e costruiremo dei metodi di accesso:

ditta[i].nome()

ditta[i].stipendio()

ditta[i].eta()


• Esercizio. Costruire e stampare una tabella archivio per contenere le informazioni sugli studenti iscritti al Corso di Informatica 2-3.

• Soluzione. Costruiamo una classe Stud che contiene informazioni minime su uno studente:• nome

• cognome

• matricola

• La classe conterrà il costruttore e i metodi di accesso; poi costruiremo una classe di prova.


/**Classe minima per uno studente:

contiene il nome e cognome e la matricola dello studente e i metodi per l'accesso ai campi */

public class Stud

private String nome;

private String cognome;

private int matricola;

public Stud (String n, String c, int m)

nome = n;

cognome = c;

matricola = m;

//fine costruttore

22


/**restituisce il numero di matricola*/

public int matricola ()

return matricola;

/**restituisce il nome */

public String nome ()

return nome;

/**restituisce il cognome */

public String cognome ()

return cognome;

//fine Stud


import java.util.Scanner;

public class ProvaStud

public static void main(String[] args)

Scanner in = new Scanner(System.in);

Stud corso23[]= new Stud [120];

int i = 0;

String nome, cognome;

int matricola;

while(in.hasNext())

nome = in.next();

cognome = in.next();

matricola = in.nextInt();


if(matricola%10==2 || matricola%10==3)

corso23[i]=

new Stud(nome,cognome, matricola);

i++;

else System.out.println("\nlo studente “

+ cognome + " " + nome +

" appartiene ad altro corso");


System.out.println("\nStampa archivio");

for (int k=0 ;k<i;k++)

System.out.print(corso23[k].nome()+" ");

System.out.print(corso23[k].cognome());

System.out.println

(" " + corso23[k].matricola());

//fine for

//fine main

• Attenzione: i dati nel file devono essere coerenti con l’acquisizione dei dati: scambiare il nome con il cognome è un errore logico.

Supponiamo che f(n) sia la funzione che Algoritmi esponenzialilaurap/didattica/... · da un...

Documents

Transcript of Supponiamo che f(n) sia la funzione che Algoritmi esponenzialilaurap/didattica/... · da un...