Il calcolo del fattoriale

1

Ricorsione (capitolo 12)

Il calcolo del fattoriale

La funzione fattoriale, molto usata nel calcolo  combinatorio, è così definita

dove n è un numero intero non negativo

0  

se    

0  

se     )!

1 (

! 1

>

=

 



= −

n n n

n n

3

Il calcolo del fattoriale

Vediamo di capire cosa significa…

  0! = 1

  1! = 1(1­1)! = 1∙0! = 1∙1 = 1   2! = 2(2­1)! = 2∙1! = 2∙1 = 2   3!  = 3(3­1)! = 3∙2! = 3∙2∙1 = 6   4!  = 4(4­1)! = 4∙3! = 4∙3∙2∙1 = 24   5!  = 5(5­1)! = 5∙4! = 5∙4∙3∙2∙1 = 120

Quindi, per ogni n intero positivo, il fattoriale di n è il  prodotto dei primi n numeri interi positivi

Il calcolo del fattoriale

Scriviamo un metodo statico per calcolare il fattoriale

public static int factorial(int n) { if (n < 0)

throw new IllegalArgumentException();

if (n == 0) return 1;

int p = 1;

for (int i = 2; i <= n; i++) p = p * i;

return p;

}

5

Il calcolo del fattoriale

Fin qui, nulla di nuovo… però abbiamo dovuto fare  un’analisi matematica della definizione per scrivere  l’algoritmo

Realizzando direttamente la definizione, sarebbe  stato più naturale scrivere

public static int factorial(int n) { if (n < 0)

throw new IllegalArgumentException();

else if (n == 0) return 1;

else

return n * factorial(n - 1);

}

Il calcolo del fattoriale

Si potrebbe pensare: “Non è possibile invocare un  metodo mentre si esegue il metodo stesso!”

Invece, come è facile verificare scrivendo un 

programma che usi factorial, questo è lecito in Java

  così come è lecito in quasi tutti i linguaggi di 

public static int factorial(int n) { if (n < 0)

throw new IllegalArgumentException();

else if (n == 0) return 1;

else

return n * factorial(n - 1);

}

7

Invocazione di un metodo  ricorsivo

Invocare un metodo ricorsivo

Invocare un metodo mentre si esegue lo stesso  metodo è un paradigma di programmazione che si  chiama

  ricorsione

e un metodo che ne faccia uso si chiama   metodo ricorsivo

La ricorsione è uno strumento molto potente per  realizzare alcuni algoritmi, ma è anche fonte di  molti errori di difficile diagnosi

9

Invocare un metodo ricorsivo

Per capire come utilizzare correttamente la 

ricorsione, vediamo innanzitutto come funziona

Quando un metodo ricorsivo invoca se stesso, la  macchina virtuale Java esegue le stesse azioni  che vengono eseguite quando viene invocato un  metodo qualsiasi

 sospende l’esecuzione del metodo invocante

 esegue il metodo invocato fino alla sua terminazione

 riprende l’esecuzione del metodo invocante dal  punto in cui era stata sospesa

Invocare un metodo ricorsivo

Invochiamo factorial(3) per calcolare 3!

 factorial(3) invoca factorial(2)

• factorial(2) invoca factorial(1) – factorial(1) invoca factorial(0)

»factorial(0) restituisce 1 – factorial(1) restituisce 1

• factorial(2) restituisce 2

 factorial(3) restituisce 6

Si crea quindi una  pila di metodi “in attesa”, che si  allunga e che poi si accorcia fino ad estinguersi

public static int factorial(int n)

11

La ricorsione: caso base

Prima regola

 il metodo ricorsivo deve fornire la soluzione del  problema in almeno un caso particolare, senza  ricorrere ad una chiamata ricorsiva

 tale caso si chiama caso base della ricorsione

 nel nostro esempio, il caso base è

a volte ci sono più casi base, non è necessario che  sia unico

if (n == 0) return 1;

La ricorsione: passo ricorsivo

Seconda regola

 il metodo ricorsivo deve effettuare la chiamata  ricorsiva dopo aver semplificato il problema

 nel nostro esempio, per il calcolo del fattoriale di n si  invoca la funzione ricorsivamente per conoscere il  fattoriale di n­1, cioè per risolvere un problema più  semplice

il concetto di “problema più semplice” varia di volta in  volta: in generale, bisogna avvicinarsi ad un caso  base

if (n > 0)

return n * factorial(n - 1);

13

La ricorsione: un algoritmo?

Queste due regole sono fondamentali per dimostrare  che la soluzione ricorsiva di un problema sia un 

algoritmo

 in particolare, che termini in un numero finito di passi

Si potrebbe pensare che le chiamate ricorsive si  susseguano una dopo l’altra, all’infinito. Invece se

 Ad ogni invocazione il problema diventa sempre più  semplice e si avvicina al caso base

 E la soluzione del caso base non richiede ricorsione

allora certamente la soluzione viene calcolata in un  numero finito di passi, per quanto complesso possa  essere il problema

Ricorsione infinita

Quanto detto ci suggerisce che non tutti i metodi  ricorsivi realizzano algoritmi

 se manca il caso base, il metodo ricorsivo continua ad  invocare se stesso all’infinito

 se il problema non viene semplificato ad ogni 

invocazione ricorsiva, il metodo ricorsivo continua ad  invocare se stesso all’infinito

Dato che la lista dei metodi “in attesa” si allunga  indefinitamente

 l’ambiente runtime esaurisce la memoria disponibile  per tenere traccia di questa lista

 ed il programma termina con un errore

15

Ricorsione infinita

Un programma che presenta ricorsione infinita:

Il programma terminerà con la segnalazione  dell’eccezione StackOverflowError

 il runtime stack è la struttura dati all’interno 

dell’interprete Java che gestisce le invocazioni in attesa

 stack significa pila

public class InfiniteRecursion

{ public static void main(String[] args) { main(args);

}}

Eliminare la ricorsione

17

La ricorsione in coda

Esistono diversi tipi di ricorsione

Il modo visto fino ad ora si chiama ricorsione in  coda (tail recursion)

 il metodo ricorsivo esegue una sola invocazione  ricorsiva e tale invocazione è l’ultima azione del  metodo

public void tail(...) { ...

tail(...);

}

Eliminare la ricorsione in coda

La ricorsione in coda può sempre essere 

agevolmente eliminata, trasformando il metodo  ricorsivo in un metodo che usa un ciclo

public int factorial(int n) { if (n == 0) return 1;

else return n * factorial(n - 1);

}

public int factorial(int n) { int f = 1;

while (n > 0) { f = f * n;

n--;

} return f;

19

Eliminare la ricorsione in coda

Allora, a cosa serve la ricorsione in coda?

Non è necessaria, però in alcuni casi rende il codice  più leggibile

È utile quando la soluzione del problema è 

esplicitamente ricorsiva (ad esempio nel calcolo della  funzione fattoriale)

In ogni caso, la ricorsione in coda è meno efficiente  del ciclo equivalente, perché il sistema deve gestire  le invocazioni sospese

Eliminare la ricorsione

Se la ricorsione non è in coda, non è facile eliminarla  (cioè scrivere codice non ricorsivo equivalente), però  si può dimostrare che ciò è sempre possibile

 deve essere così, perché il processore esegue 

istruzioni in sequenza e non può tenere istruzioni in  attesa

 In Java l’interprete si fa carico di eliminare la ricorsione  (usando il runtime stack)

 In un linguaggio compilato il compilatore trasforma il  codice ricorsivo in codice macchina non ricorsivo

21

Ricorsione multipla e  problemi di efficienza

La ricorsione multipla

Si parla di ricorsione multipla quando un metodo  invoca se stesso più volte durante la propria 

esecuzione

 la ricorsione multipla è ancora più difficile da eliminare,  ma è sempre possibile

Esempio: il calcolo dei numeri di Fibonacci

3  

se    

3 1

  se     ) 1 Fib(

) 2 Fib(

) 1

Fib( ≥

<

≤

 



− +

= −

n n n

n n

23

La classe FibTester

public class FibTester

{ private static int invcount = 0; // variabile statica public static void main(String[] args)

{ int n = 0;

if (args.length != 1)

{ System.out.println("Uso: $java FibTester <numero>");

System.exit(1); } try

{ n = Integer.parseInt(args[0]); } catch(NumberFormatException e)

{ System.out.println("Inserire un intero!");

System.exit(1); }

System.out.println("*** Collaudo iterativeFib ***");

for (int i = 1; i <= n; i++) { long f = iterativeFib(i);

System.out.println("iterativeFib(" +i+ ") = " + f);}

System.out.println("\n*** Collaudo recursiveFib ***");

for (int i = 1; i <= n; i++) { invcount = 0;

long f = recursiveFib(i);

System.out.println("recursiveFib(" +i+ ") = " + f);

System.out.println(invcount+" invocazioni"); } } //continua

La classe FibTester

public static long recursiveFib(int n) //continua { if (n < 1) throw new IllegalArgumentException();

System.out.println("Inizio recursiveFib(" + n +")");

invcount++;

long f;

if (n < 3) f = 1;

else f = recursiveFib(n-1) + recursiveFib(n-2);

System.out.println("Uscita recursiveFib(" + n + ")");

return f;

}

public static long iterativeFib(int n)

{ if (n < 1) throw new IllegalArgumentException();

long f = 1;

if (n >= 3)

{ long fib1 = 1;

long fib2 = 1;

for (int i = 3; i<=n; i++) { f = fib1 + fib2;

fib2 = fib1;

fib1 = f; } }

return f;

}

25

La ricorsione multipla

Il metodo fib realizza una ricorsione multipla

La ricorsione multipla va usata con molta attenzione,  perché può portare a programmi molto inefficienti

Eseguendo il calcolo dei numeri di Fibonacci di  ordine crescente

 Si nota che il tempo di elaborazione cresce molto  rapidamente 

 Sono necessarie quasi 3 milioni di invocazioni per  calcolare Fib(31) !!!!

 più avanti quantificheremo questo problema

Invece una soluzione iterativa risulta molto più  efficiente

Albero delle invocazioni di fib

Visualizziamo lo schema delle invocazioni di fib in  una struttura ad albero

Lo stesso valore viene calcolato più volte

 Molto inefficiente

27

Permutazioni

(cfr. sezione 12.2)

Esaminiamo un problema per il quale è 

(relativamente) facile trovare una soluzione ricorsiva  mentre è molto difficile trovarne una iterativa

Problema: determinare tutte le possibili 

permutazioni dei caratteri presenti in una stringa

 facciamo l’ipotesi che non ci siano caratteri ripetuti

Ricordiamo dalla matematica combinatoria che il  numero di permutazioni di N simboli è N!

Esempio: ABC

 ABC ACB BAC BCA CAB CBA

Permutazioni

29

La classe PermutationTester

Dobbiamo trovare una buona idea per scrivere il  metodo getPermutations…

import java.util.Scanner;

public class PermutationTester

{ public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.println("Inserire stringa");

String aString = in.nextLine();

String[] permutations = getPermutations(aString);

for (int i = 0; i < permutations.length; i++) System.out.println(permutations[i]);

}

public static String[] getPermutations(String word) {...}

Esiste un semplice algoritmo ricorsivo per trovare  le permutazioni di una stringa di lunghezza N

Se N vale 1, l’unica permutazione è la stringa stessa

Altrimenti

 Generiamo tutte le permutazioni che iniziano con il  primo carattere

 Generiamo tutte le permutazioni che iniziano con il  secondo carattere

 … e così via

 Otteniamo tutte le possibili permutazioni

Permutazioni

31

Permutazioni

Come si ottengono le permutazioni che iniziano con il  generico i­esimo carattere?

 Concatenando l’i­esimo carattere con tutte le 

permutazioni della stringa composta dai rimanenti N­1  caratteri

 Cioè risolvendo lo stesso problema per un dato di  dimensione più piccola

 Esempio: 

ABC ACB BAC BCA CAB CBA

Abbiamo ottenuto il passo di ricorsione!

Avevamo già il caso base

 Se N = 1 c’è una sola permutazione, la stringa stessa

Il passo di ricorsione semplifica il problema e si  avvicina al caso base

Il metodo getPermutations

public static String[] getPermutations(String word)

{ if (word == null || word.length() == 0) //precondizioni return new String[0]; // oppure return null if (word.length() == 1) // caso base

return new String[] {word};

int nperm = 1; // il n. di permutazioni da generare...

for (int i = 2; i <= word.length(); i++)

nperm *= i; // ... e` il fattoriale di word.length() String[] perm = new String[nperm];

for (int i = 0; i < word.length(); i++)

{ String subword = word.substring(0,i)+ word.substring(i+1);

// passo ricorsivo: permutazioni della sottosequenza String[] subperm = getPermutations(subword);

for (int j = 0; j < subperm.length; j++) perm[i*subperm.length+j] =

word.substring(i,i+1) + subperm[j];

}

return perm;

33

Permutazioni

Commenti sulla gestione delle pre­condizioni

 Il metodo riceve un riferimento ad una stringa: tale 

riferimento può essere null oppure la stringa può essere  vuota (cioè avere lunghezza zero)

 In alternativa al lancio di una eccezione si può restituire  null, o nel caso di un array è lecito restituire un array di  lunghezza zero in modo che il metodo invocante riceva  un array valido

 In questo modo, il codice seguente funziona…

 mentre non funzionerebbe se restituissimo null

//ATTENZIONE: stiamo sfruttando la //valutazione pigra dell'operatore OR if (word == null || word.length() == 0) return new String[0];

String[] permutations = getPermutations(“”);

for (int i = 0; i<permutations.length; i++) System.out.println(permutations[i]);

Permutazioni

Quando creiamo l’array che dovrà contenere le  permutazioni dobbiamo definirne la dimensione

La dimensione del vettore che conterrà le permutazioni  può essere calcolata sfruttando la nostra conoscenza  del problema

 Sappiamo che le permutazioni sono N!

// numero di permutazioni da generare int nperm = 1;

for (int i = 2; i <= word.length(); i++) nperm *= i;

String[] perm = new String[nperm];

35

Permutazioni

In alternativa potremmo sfruttare le informazioni  ottenute dall’invocazione ricorsiva

 Il  numero di permutazioni è uguale a

• la dimensione della stringa 

• moltiplicata per il numero di permutazioni generate da una  sottosequenza di lunghezza N­1

 Dovremmo effettuare la prima invocazione ricorsiva fuori  dal ciclo.

// numero di permutazioni da generare:

String subword = word.substring(0,0) + word.substring(1);

String[] subperm = getPermutations(subword);

String[] perm = new String[word.length() * subperm.length];

for (int j = 0; j < subperm.length; j++)

{ perm[j] = word.substring(0,1) + subperm[j]; }

Permutazioni

Per completare le permutazioni:

 concateniamo l’i­esimo carattere con tutte le posizioni  permutazioni della corrispondente sottosequenza

 Aggiungiamo nell’array le permutazioni ottenute

for (int i = 0; i < word.length(); i++) { // eliminiamo l'i-esimo carattere

subword = word.substring(0,i) + word.substring(i+1);

// passo ricorsivo: permutazioni della sottosequenza subperm = getPermutations(subword);

for (int j = 0; j < subperm.length; j++) { perm[i*subperm.length+j] =

word.substring(i,i+1) + subperm[j];

}}

37

Per ottenere subword stiamo sfruttando le proprietà  del metodo substring

Quando i vale 0, substring restituisce una stringa  vuota, che è proprio ciò che vogliamo

Quando i vale word.length( )­1 (suo valore  massimo), allora i+1 vale word.length( )

 in questo caso particolare, substring non lancia  eccezione, ma restituisce una stringa vuota, che è  proprio ciò che vogliamo

Permutazioni

word.substring(0,i) + word.substring(i+1);

word.substring(0,i) + word.substring(i+1);

Analizziamo meglio questa espressione dell’indice

Globalmente, tale indice deve andare da 0 a  (word.length())! (escluso)

Verifichiamo innanzitutto i limiti

 per i = 0 e j = 0, l’indice vale 0

 Per un generico i e j = subperm.length­1 l’indice vale

i*subperm.length +subperm.length­1 =  (i+1)*subperm.length ­1

 Per i =word.length()­1, j =subperm.length­1, l’indice vale  word.length()*subword.length ­ 1 

Permutazioni

perm[i*subperm.length+j] = ...;

39

Alla prima iterazione di i, l’indice varia tra 0 e  subword.length­1 (perché i vale 0)

Alla seconda iterazione di i, l’indice varia tra  1*subword.length+0 = subword.length 1*subword.length+shorterword.length­1 =       2*subword.length­1

Si osserva quindi che gli indici vengono generati 

consecutivamente, senza nessun valore mancante e  senza nessun valore ripetuto

Permutazioni

perm[i*subperm.length+j] = ...;

Esercizio: torri di Hanoi

(cfr. esercizio P12.13)

41

Torri di Hanoi

Scopo del gioco:

 Spostare la torre di dischi da un piolo “origine” ad un  piolo “destinazione”

Regole del gioco:

 Si può spostare un solo disco per volta

 In ogni istante un disco non può poggiare su un  disco più piccolo

Torri di Hanoi: soluzione ricorsiva

Cerchiamo una soluzione ricorsiva

Dobbiamo trovare 

 un caso base

 Un passo di ricorsione che semplifica il problema

Il caso base è semplice:

 Se la torre è composta da un solo disco la soluzione  è composta da una sola mossa, che sposta il disco  stesso dal piolo di origine al piolo di destinazione

43

Torri di Hanoi: soluzione ricorsiva

Cerchiamo il passo ricorsivo

 Ad un certo punto del gioco il disco più grande verrà  spostato dall’origine alla destinazione

 In quel momento tutti gli altri dischi devono essere  impilati sul piolo rimanente

• Ovvero in quel momento abbiamo risolto il problema  con n­1 dischi

 Dopo avere spostato il disco più grande dall’origine  alla destinazione, dobbiamo spostare tutti gli altri  dischi dal piolo rimanente alla destinazione

• Ovvero dobbiamo nuovamente risolvere il problema  con n­1 dischi

Torri di Hanoi

Realizziamo una classe DiskMover, il cui costruttore  riceve:

 il piolo sorgente from da cui prelevare i dischi (1, 2, 3) 

 il piolo destinazione target in cui inserire i dischi (1, 2, 3)

 il numero di dischi da spostare, disks

Se disks = 1, il DiskMover ha un metodo nextMove  che restituisce la mossa da effettuare

Un DiskMover che deve spostare più dischi deve  faticare di più, e ha bisogno di un altro oggetto di tipo  DiskMover che lo aiuti. 

 Nel costruttore, costruiremo un oggetto in questo modo: 

DiskMover(from, other, disks – 1), dove other è il piolo  diverso da from e da target.

45

Prima soluzione: la classe HanoiSolver

Scriviamo un metodo statico ricorsivo solveHanoi

public class HanoiSolver

{ public static void main(String[] args) {

if (args.length != 3)

{ System.out.println("uso: $java HanoiSolver from target disks");

System.out.println("con from e target tra 1 e 3, e disks > 0");

return;

} try

{ solveHanoi(Integer.parseInt(args[0]), Integer.parseInt(args[1]), Integer.parseInt(args[2]));

}

catch(NumberFormatException e)

{ System.out.println("Non hai inserito parametri di tipo int");

}

catch(IllegalArgumentException e)

{ System.out.println("Valore errato per from o target o disks");

} }

// continua

// continua

public static void solveHanoi(int from, int target, int disks) {

if (from==target || from<1 || from>3 || target<1 || target>3 || disks<0)

throw new IllegalArgumentException();

if (disks > 0)

{ int other = 6 - from - target;

solveHanoi(from, other, disks-1);

System.out.println("Sposta un disco dal piolo " + from + " al piolo " + target);

solveHanoi(other, target, disks-1);

} } }

Prima soluzione: la classe HanoiSolver

47

Approfondimento

Seconda soluzione: le classi  Diskmover e HanoiTester

(soluzione dell'esercizio P12.13)

La classe DiskMover

public class DiskMover

{ public DiskMover(int from, int target, int disks) {

if (from == target || from <1 || from > 3 || target < 1 || target > 3 || disks < 1) throw new IllegalArgumentException();

this.from = from;

this.target = target;

this.disks = disks;

state = BEFORE_LARGEST;

int other = 6 - from - target;

if (disks > 1)

mover = new DiskMover(from, other, disks - 1);

}

public boolean hasMoreMoves() {

return state != DONE;

}

// continua

49

La classe DiskMover

public int[] nextMove() // continua { if (!hasMoreMoves())

throw new IllegalStateException();

if (disks == 1) //caso base { state = DONE;

return new int[] {from, target};

}

if (state == LARGEST) //1o sottoproblema risolto: ora { //si sposta il disco maggiore e si state = AFTER_LARGEST;//imposta il 2o sottoproblema

int other = 6 - from - target;

mover = new DiskMover(other, target, disks -1);

return new int[] {from, target};

}

int[] r = mover.nextMove(); //passo ricorsivo

if (!mover.hasMoreMoves()) //se mover non ha piu` mosse, { //questo significa che

if (state ==BEFORE_LARGEST)//o il 1o sottopr. e` risolto state = LARGEST;

else //oppure il gioco e` finito state = DONE;

}

return r;

} // continua

La classe DiskMover

// continua //campi di esemplare

private int from;

private int target;

private int disks;

private DiskMover mover;

private int state;

//variabili (costanti) di classe

private static final int BEFORE_LARGEST = 1;

private static final int LARGEST = 2;

private static final int AFTER_LARGEST = 3;

private static final int DONE = 4;

}

51

La classe HanoiTester

public class HanoiTester

{ public static void main(String[] args) { DiskMover mover = null;

try{

int from = Integer.parseInt(args[0]);

int target = Integer.parseInt(args[1]);

int disks = Integer.parseInt(args[2]);

mover = new DiskMover(from, target, disks);

while(mover.hasMoreMoves())

{ int[] move = mover.nextMove();

System.out.println("Sposta un disco dal piolo "

+ move[0] + " al piolo " + move[1]);

} }

catch(NumberFormatException e){ System.out.println(e);}

catch(IllegalArgumentException e){ System.out.println(e);}

catch(ArrayIndexOutOfBoundsException e)

{System.out.println(e);}

}}

53

Ordinamento e ricerca

[e analisi delle prestazioni]

(capitolo 13)

Motivazioni

Problema molto frequente nella elaborazione dei dati

 Ordinamento dei dati stessi, secondo un criterio  prestabilito

 Ad esempio: nomi in ordine alfabetico, numeri in ordine  crescente…

Studieremo diversi algoritmi per l’ordinamento, 

introducendo anche uno strumento analitico per la  valutazione delle loro prestazioni

Su dati ordinati è poi possibile fare ricerche in modo  molto efficiente, e studieremo algoritmi adeguati

Studieremo degli algoritmi ricorsivi ed efficienti, ma 

55

Ordinamento per selezione

Ordinamento per selezione

Per semplicità, analizzeremo prima gli algoritmi per  ordinare un insieme di numeri (interi) memorizzato  in un array

 vedremo poi come si estendono semplicemente al caso  in cui si debbano elaborare oggetti anziché numeri

Prendiamo in esame un array a da ordinare in senso  crescente 

11 9 17 5 12

a[0] a[1] a[2] a[3] a[4]

5 9 11 12 17

a[0] a[1] a[2] a[3] a[4]

57

5

Ordinamento per selezione

Per prima cosa, bisogna trovare l’elemento  dell’array contenente il valore minimo, come  sappiamo già fare

 in questo caso è il numero 5 in posizione a[3]

Essendo l’elemento minore, la sua posizione corretta  nell’array ordinato è a[0]

 in a[0] è memorizzato il numero 11, da spostare

 non sappiamo quale sia la posizione corretta di 11

• lo spostiamo temporaneamente in a[3]

 quindi, scambiamo a[3] con a[0]

11 9 17 12

a[0] a[1] a[2] a[3] a[4] 5 9 17 11 12

Ordinamento per selezione

La parte sinistra dell’array è già ordinata e non  sarà più considerata

 Dobbiamo ancora ordinare la parte destra

Ordiniamo la parte destra con lo stesso algoritmo

 cerchiamo l’elemento contenente il valore minimo, che  è il numero 9 in posizione a[1]

 dato che è già nella prima posizione a[1] della parte  da ordinare, non c’è bisogno di fare scambi

5 9 17 11 12

a[0] a[1] a[2] a[3] a[4]

la parte colorata dell’array è  già ordinata

5 9 17 11 12

59

11

Ordinamento per selezione

Proseguiamo per ordinare la parte di array che  contiene gli elementi a[2], a[3] e a[4]

 il valore minimo è il numero 11, contenuto  nell’elemento a[3]

 scambiamo a[3] con a[2]

5 9 17 12

a[0] a[1] a[2] a[3] a[4]

5 9 11 17 12 5 9 11 17 12

a[0] a[1] a[2] a[3] a[4]

17

Ordinamento per selezione

Ora l’array da ordinare contiene a[3] e a[4]

 Il valore minimo è il numero 12, contenuto  nell’elemento a[4]

 scambiamo a[4] con a[3]

A questo punto la parte da ordinare contiene un  solo elemento, quindi è ovviamente ordinata

5 9 11 12

a[0] a[1] a[2] a[3] a[4]

5 9 11 12 17 5 9 11 12 17

a[0] a[1] a[2] a[3] a[4]

61

Ordinamento per selezione

= accesso in lettura = accesso in scrittura

12 11

17 9

11 17 5 12 5 9 17 11 12

9

5 11 12 5 9 17 11 12

17 9

5 12 5 9 11 17 12

17 11

9

5 5 9 11 12 17

La classe ArrayAlgs

Riprendiamo la nostra classe ArrayAlgs

 L'abbiamo introdotta quando abbiamo studiato  semplici algoritmi su array

 Contiene una collezione di metodi statici per  l’elaborazione di array

• Per ora trattiamo array di numeri interi

• Più avanti tratteremo generici array di Object

In particolare ArrayAlgs conterrà le realizzazioni dei  vari algoritmi di ordinamento e ricerca da noi 

studiati

È una “classe di utilità”, come la classe Math

63

Il metodo selectionSort

public class ArrayAlgs{...

public static void selectionSort(int[] v, int vSize) {

for (int i = 0; i < vSize - 1; i++)

{ int minPos = findMinPos(v, i, vSize-1);

if (minPos != i) swap(v, minPos, i);

}

} //abbiamo usato due metodi ausiliari, swap e findMinPos private static void swap(int[] v, int i, int j)

{ int temp = v[i];

v[i] = v[j];

v[j] = temp;

}

private static int findMinPos(int[] v, int from, int to) { int pos = from;

int min = v[from];

for (int i = from + 1; i <= to; i++) if (v[i] < min)

{ pos = i;

min = v[i]; } return pos;

} ...}

Ordinamento per selezione

L’algoritmo di ordinamento per selezione è corretto  ed è in grado di ordinare qualsiasi array

 allora perché studieremo altri algoritmi di  ordinamento?

 a cosa serve avere diversi algoritmi per risolvere  lo stesso problema?

Vedremo che esistono algoritmi di ordinamento  che, a parità di dimensioni del vettore da ordinare,  vengono eseguiti più velocemente

65

È tutto chiaro? …

1. Perché nel metodo swap serve la variabile  temp? Cosa succede se si assegna 

semplicemente a[j] ad a[i] e a[i] ad a[j]?

2. Quali sono i passi compiuti da selectionSort per  ordinare la sequenza 654321?

Rilevazione delle 

prestazioni

67

Rilevazione delle prestazioni

Le prestazioni di un algoritmo vengono valutate in  funzione della dimensione dei dati trattati

 Per valutare l’efficienza di un algoritmo si misura il  tempo in cui viene eseguito su insiemi di dati di  dimensioni via via maggiori

Il tempo non va misurato con un cronometro,  perché parte del tempo reale di esecuzione non  dipende dall’algoritmo

 caricamento della JVM

 caricamento delle classi del programma

 lettura dei dati dallo standard input

 visualizzazione dei risultati  

Rilevazione delle prestazioni

Il tempo di esecuzione di un algoritmo va misurato  all’interno del programma

Si usa il metodo statico

System.currentTimeMillis()

  che, ad ogni invocazione, restituisce un numero di  tipo long che rappresenta

 il numero di millisecondi trascorsi da un evento di  riferimento (la mezzanotte del 1 gennaio 1970)

Ciò che interessa è la differenza tra due valori

 si invoca System.currentTimeMillis( ) prima e dopo  l’esecuzione dell’algoritmo (escludendo le operazioni  di input/output dei dati)

69

La classe SelSortTester

import java.util.Scanner;

public class SelSortTester

{ public static void main(String[] args) {

Scanner in = new Scanner(System.in);

System.out.print("Dimensione dell'array? ");

int n = in.nextInt();

// costruisce un array casuale

int[] a = ArrayAlgs.randomIntArray(n, 100);

int aSize = a.length;

// usa System.currentTimeMillis() per misurare il tempo long time = System.currentTimeMillis();

ArrayAlgs.selectionSort(a, aSize);

time = System.currentTimeMillis() -time;

System.out.println("Tempo trascorso: " + time + " ms");

} }

Rilevazione delle prestazioni

Eseguiamo l’ordinamento  di array con diverse 

dimensioni (n), contenenti  numeri interi casuali

Si nota che l’andamento  del tempo di esecuzione  non è lineare

 se n diventa il doppio, il  tempo diventa circa il  quadruplo!

71

Rilevazione delle prestazioni

Le prestazioni dell’algoritmo di ordinamento per  selezione hanno quindi un andamento quadratico  in funzione delle dimensioni dell’array

Le prossime domande che ci poniamo sono

 è possibile valutare le prestazioni di un algoritmo  al punto di vista teorico?

• (ovvero senza realizzare un programma e senza 

eseguirlo molte volte, per rilevarne i tempi di esecuzione  ed osservarne l’andamento)

 esiste un algoritmo più efficiente per  l’ordinamento?

Analisi teorica delle 

prestazioni

73

Analisi teorica delle prestazioni

Il tempo d’esecuzione di un algoritmo dipende da  numero e tipo di istruzioni macchina eseguite dal  processore

 Che a loro volta dipendono in generale dalla  dimensione dei dati da elaborare

• Ad esempio, nel caso di selectionSort, la lunghezza  dell’array da ordinare

Vogliamo stimare una funzione T(n) che descrive il  tempo di esecuzione T in funzione della dimensione n  dei dati

 Tramite analisi teorica, senza esperimenti numerici

 Anzi, senza realizzare e compilare un algoritmo!

Analisi teorica delle prestazioni

Facciamo alcune assunzioni ed alcune semplificazioni  drastiche

 Cerchiamo di stimare per eccesso il tempo di esecuzione  T(n), ovvero di ottenere una stima nel caso peggiore

• Ad es., per un algoritmo di ordinamento il caso peggiore è  quello in cui l’array da ordinare è ordinato alla rovescia

 La stima di T(n) è ottenuta stimando il numero di 

operazioni primitive di Java (o altro linguaggio ad alto  livello) eseguite

• Assumiamo quindi che tutte le operazioni primitive di Java  abbiano stessi tempi di esecuzione (anche se non è 

esattamente vero)

75

Analisi teorica delle prestazioni

Cosa si intende per “operazione primitiva”?

Si intende una qualsiasi istruzione che abbia un tempo  di esecuzione (circa) costante. Ad esempio

 Istruzioni di assegnazione

 Operazioni aritmeriche o logiche

 Accessi ad elementi di un array

 ... 

Ad esempio, nel caso di selectionSort facciamo un  conteggio del numero di accessi in lettura o scrittura  ad un elemento dell’array

Prestazioni di selectionSort

Esaminiamo il codice java del metodo selectionSort

Contiamo gli accessi all’array nella prima iterazione  del ciclo esterno (ovvero per i=0)

 per trovare l’elemento minore si fanno n accessi

 per scambiare due elementi si fanno quattro accessi

• trascuriamo il caso in cui non serva lo scambio

 in totale, (n+4) accessi

A questo punto dobbiamo ordinare la parte rimanente,  cioè un array di (n­1) elementi

 serviranno quindi ((n­1) + 4) accessi

E via così fino al passo con (n­(n­2))=2 elementi,  incluso

77

Prestazioni di selectionSort

Il conteggio totale degli accessi in lettura/scrittura è  quindi

T(n) = (n+4)+((n-1)+4)+…+(3+4)+(2+4) = n+(n-1)+…+3+2 + (n-1)*4

= n*(n+1)/2 - 1 + (n-1)*4 = 1/2*n² + 9/2*n - 5

Si ottiene quindi un’equazione di secondo grado in  n, che giustifica l’andamento parabolico dei tempi  rilevati sperimentalmente

n+(n-1)+…+3+2+1 = n*(n+1)/2

Andamento asintotico delle prestazioni

Facciamo un’ulteriore semplificazione, tenendo 

presente che ci interessano le prestazioni per valori  elevati di n (andamento asintotico)

Se n vale 1000

 1/2*n² vale 500000

 9/2*n - 5 vale 4495, circa 1% del totale quindi diciamo che l’andamento asintotico  dell’algoritmo in funzione di n è 1/2*n²

1/2*n² + 9/2*n - 5

79

Andamento asintotico delle prestazioni

Facciamo un’ulteriore semplificazione

 ci interessa soltanto valutare cosa succede al tempo  d’esecuzione T(n) se n, ad esempio, raddoppia

 Nel caso in esame il tempo d’esecuzione quadruplica T(n) = 1/2*n²

T(2n) = 1/2*(2n)² = 1/2*4*n² = 4*T(n)

Si osserva che T(2n) = 4*T(n)

 In generale nel caso in cui T(n) = n²

 Indipendentemente dal fatto che sia presente un  fattore moltiplicativo 1/2, o qualsiasi altro fattore  moltiplicativo

1/2*n²

È tutto chiaro? …

1. Se si aumenta di 10 volte la dimensione dei dati, 

come aumenta il tempo richiesto per ordinare i 

dati usando selectionSort?

81

Notazione “O­grande”

Si dice quindi che 

 per ordinare un array con l’algoritmo di selezione si  effettua un numero di accessi che è dell’ordine di n²

Per esprimere sinteticamente questo concetto si usa  la notazione O­grande e si dice che il numero degli  accessi è O(n²)

Dopo aver ottenuto una formula che esprime 

l’andamento temporale dell’algoritmo, si ottiene la  notazione “O­grande” considerando soltanto il  termine che si incrementa più rapidamente 

all’aumentare di n, ignorando coefficienti costanti

Notazione “O­grande”, “ ”, “ ” Ω Θ

La notazione f(n)=O(g(n)) significa: f non cresce più  velocemente di g

 Ma è possibile che f cresca molto più lentamente

 Esempio: f(n) = n² + 5n – 3 è O(n³), ma è anche O(n¹⁰)

Esistono ulteriori notazioni per descrivere il modo in cui  una funzione cresce

 f(n)=Ω(g(n)) significa: f non cresce più lentamente di g

• Ovvero g(n) = O(f(n)) 

 f(n)=Θ(g(n)) significa: f cresce con la stessa velocità di g

83

Notazione “O­grande”, “ ”, “ ” Ω Θ

f(n) = O(g(n))  esiste una costante C>0 tale che  f(n)/g(n) < C definitivamente

f(n) = Ω(g(n))  … f(n)/g(n) > C definitivamente

f(n) = Θ(g(n))  … C₁ < f(n)/g(n) < C₂ definitivamente

Ordini di complessità

Un algoritmo può essere classificato in funzione delle  proprie prestazioni

 Un algoritmo è considerato efficiente se il suo tempo di  esecuzione (caso peggiore) è al più polinomiale

 Un algoritmo è considerato inefficiente se il suo tempo  di esecuzione (caso peggiore) è almeno esponenziale

Un problema algoritmico può essere classificato in  funzione della propria complessità (ovvero le 

prestazioni del più veloce algoritmo che lo risolve)

 Un problema è considerato trattabile se la sua  complessità è al più polinomiale

 Un problema è considerato non trattabile se la sua  complessità è almeno esponenziale

85

Ordini di complessità

Supponiamo che una istruzione di Java venga  eseguita in 10^­6 s …

Un numero a 728 cifre di secoli Un numero

a 185 cifre di secoli Un numero

a 70 cifre di secoli 3.3 trilioni

di anni 2.8

n ⁿ ore

Un numero a 75 cifre di secoli 400 trilioni

di secoli 35.7

anni 1

secondi 1/1000

secondi

2ⁿ

28.1 giorni 2.8

ore 5.2

minuti 3.2

secondi 1/10

secondi

n ⁵

9/100 secondi 1/100

secondi 1/400

secondi 1/2500

secondi 1/10000

secondi

n ²

n=300 n=100

n=50 n=20

f(n) n=10

Problemi   non trattabiliProblemi trattabili  (polinomiali)

(1 anno   3E7 secondi)≈

Cicli annidati: analisi delle prestazioni

Riesaminiamo la struttura di SelectionSort

 È realizzato tramite due cicli annidati di questo tipo

Per stimare il tempo di esecuzione di due cicli annidati  come questi dobbiamo stimare quante volte vengono  eseguite le operazioni primitive nel ciclo più interno

 Per i = 0 vengono eseguite n volte

 Per i = 1 vengono eseguite n­1 volte

 ...

for (int i = 0; i < n; i++) //... operazioni primitive for (int j = i; j < n; j++) //... operazioni primitive

87

Il totale delle operazioni primitive nel ciclo interno è

Quindi due cicli annidati del tipo appena esaminato  hanno sempre prestazioni O(n²)

Dimostrazione di questa uguaglianza

 Basta disporre gli addendi in questo ordine

1 + 2 + 3 + ... + n/2 + n + (n-1) + (n-2) + ... + (n/2+1) ___________________________________

n+1 + n+1 + n+1 + ... + n+1

Cicli annidati: analisi delle prestazioni

n/2 volte

... = O(n²)

Ordinamento per fusione

(MergeSort)

89

Presentiamo ora un algoritmo di ordinamento “per  fusione” (MergeSort) che vedremo avere 

prestazioni migliori di quelle dell’ordinamento per  selezione

Dovendo ordinare il vettore seguente

Lo dividiamo in due parti (circa) uguali

MergeSort

5 7 9 1 8

5 7 9 1 8

Supponiamo che le due parti siano già ordinate

 Allora è facile costruire il vettore ordinato, togliendo  sempre il primo elemento da uno dei due vettori,  scegliendo il più piccolo

MergeSort

5 7 9 1 8 1

5 7 9 1 8 1 5

5 7 9 1 8 1 5 7

5 7 9 1 8 1 5 7 8

5 7 9 1 8 1 5 7 8 9

91

Ovviamente, nel caso generale le due parti del  vettore non saranno ordinate

Possiamo però ordinare ciascuna parte ripetendo  il processo

 dividiamo il vettore in due parti (circa) uguali

 supponiamo che siano entrambe ordinate

 uniamo le due parti nel modo appena visto

• questa fase si chiama fusione (merge)

Continuando così, arriveremo certamente ad una  situazione in cui le due parti sono davvero 

ordinate

 quando contengono un solo elemento!

MergeSort

MergeSort

Si delinea quindi un algoritmo ricorsivo per ordinare  un array, chiamato MergeSort

 Caso base: se l’array contiene meno di due elementi, è  già ordinato

 Altrimenti

• si divide l’array in due parti (circa) uguali

• si ordina la prima parte usando MergeSort

• si ordina la seconda parte usando MergeSort

• si fondono le due parti ordinate usando l’algoritmo di  fusione (merge)

93

Realizzazione di mergeSort

public class ArrayAlgs { ...

public static void mergeSort(int[] v, int vSize) {

if (vSize < 2) return; // caso base

int mid = vSize / 2; //dividiamo circa a meta’

int[] left = new int[mid];

int[] right = new int[vSize - mid];

System.arraycopy(v, 0, left, 0, mid);

System.arraycopy(v, mid, right, 0, vSize-mid);

// passi ricorsivi: ricorsione multipla (doppia) mergeSort(left, mid);

mergeSort(right, vSize-mid);

// fusione (metodo ausiliario) merge(v, left, right);

}

// continua

Realizzazione di mergeSort

// continua private static void merge(int[] v, int[] v1, int[] v2) {

int i = 0, i1 = 0, i2 = 0;

while (i1 < v1.length && i2 < v2.length) if (v1[i1] < v2[i2])

// prima si usa i, poi lo si incrementa...

v[i++] = v1[i1++];

else

v[i++] = v2[i2++];

while (i1 < v1.length) v[i++] = v1[i1++];

while (i2 < v2.length) v[i++] = v2[i2++];

} ...

}

95

È tutto chiaro? …

1. Eseguire manualmente l’algoritmo mergeSort  sull’array 87654321

Prestazioni di MergeSort

97

Prestazioni di MergeSort

Rilevazioni sperimentali delle  prestazioni mostrano che 

l’ordinamento con MergeSort  è molto più efficiente di quello  con selectionSort

Cerchiamo di fare una  valutazione teorica delle  prestazioni

 Chiamiamo T(n) il numero di  accessi richiesti per ordinare  un array di n elementi

Prestazioni di MergeSort

Le due invocazioni di System.arraycopy richiedono  complessivamente 2n accessi

 tutti gli n elementi devono essere letti e scritti

Le due invocazioni ricorsive richiedono T(n/2)  ciascuna

La fusione richiede

 n accessi per scrivere gli n elementi dell’array ordinato

• ogni elemento da scrivere richiede la lettura di due 

elementi, uno da ciascuno dei due array da fondere, per  un totale di 2n accessi

99

Prestazioni di MergeSort

Sommando tutti i contributi si ottiene   T(n) = 2T(n/2) + 5n

Un’equazione di questo tipo per T(n) viene detta  equazione di ricorrenza

La soluzione di questa equazione per ottenere T(n) in  funzione di n non è semplice 

La troviamo per sostituzioni successive

  T(n) = 2( 2T(n/4) + 5(n/2) ) + 5n = 4T(n/4) + 2*5n =           = … = 2^kT(n/2^k) + k*5n

Se k = log₂n, ovvero se 2^k = n otteniamo   T(n) = n + 5n*log₂n

Prestazioni di MergeSort

Per trovare la notazione “O­grande” osserviamo che

 il termine 5n*log₂n cresce più rapidamente del termine n 

 il fattore 

5

 Nelle notazioni “O­grande” non si indica la base dei 

logaritmi, perché 

log

log

In conclusione, le prestazioni dell’ordinamento MergeSort  hanno un andamento

e sono quindi migliori di O(n²)

T(n) = n + 5n*log

n

T(n) = O(n log n)

101

Ordinamento per inserimento (cfr. argomenti avanzati 13.1)

Ordinamento per inserimento

L’algoritmo di ordinamento per inserimento

 inizia osservando che il sottoarray di lunghezza 

unitaria costituito dalla prima cella dell’array  è ordinato  (essendo di lunghezza unitaria)

 estende verso destra la parte ordinata, includendo nel  sottoarray ordinato il primo elemento alla sua destra

• per farlo, il nuovo elemento viene spostato verso sinistra  finché non si trova nella sua posizione corretta, spostando  verso destra gli elementi intermedi

9 8 5 7 6

103

6 7

5 8

Ordinamento per inserimento

9 5 7 6 8 9 5 7 6

9

8 7 6 5 8 9 7 6

9 8

5 6 5 7 8 9 6

9 8

7

5 5 6 7 8 9

= accesso in lettura = accesso in scrittura

Realizzazione di insertionSort

public class ArrayAlgs { ...

public static void insertionSort(int[] v,int vSize) { // il ciclo inizia da 1 perché il primo

// elemento non richiede attenzione for (int i = 1; i < vSize; i++)

{

int temp = v[i]; //nuovo el. da inserire // j va definita fuori dal ciclo perche` il // suo valore finale viene usato in seguito int j;

//sposta di uno verso destra tutti gli el. a // sin. di temp e > di temp, partendo da destra for (j = i; j > 0 && temp < v[j-1]; j--) v[j] = v[j-1];

v[j] = temp; // inserisci temp }

} ...

105

Prestazioni di insertionSort

Ordiniamo con inserimento un array di n elementi

Il ciclo esterno esegue n-1 iterazioni

 ad ogni iterazione vengono eseguiti

• 2 accessi (uno prima del ciclo interno ed uno dopo)

• il ciclo interno

Il ciclo interno esegue 3 accessi per ogni sua  iterazione

 ma quante iterazioni esegue?

• dipende da come sono ordinati i dati!

Prestazioni di insertionSort

Caso peggiore: i dati sono ordinati a rovescio

Ciascun nuovo elemento inserito richiede lo 

spostamento di tutti gli elementi alla sua sinistra, perché  deve essere inserito in posizione 0

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

(2 + 3*3) + ... + (2 + 3*(n-1)) = 2(n-1) + 3[1+2+...+(n-1)]

= 2(n-1) + 3n(n-1)/2 = O(n²)

Osservazione: la struttura di insertionSort è quella dei  due cicli annidati esaminati in precedenza (analoga a