Il calcolo del fattoriale

1

Ricorsione (capitolo 12)

2

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

4

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;

}

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  programmazione

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

8

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

10

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)

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

else if (n == 0) return 1;

else return n * factorial(n - 1); }

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

14

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

}}

16

Eliminare la ricorsione

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

20

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

22

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

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

26

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)

28

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

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

Esempio: ABC ACB BAC BCA CAB CBA

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

32

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

34

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

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

38

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] = ...;

40

Esercizio: torri di Hanoi (cfr. esercizio P12.13)

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

44

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

46 // 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

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);}

} }

52

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  non tutti gli algoritmi ricorsivi sono efficienti...

55

Ordinamento per selezione

56

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

58

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

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

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

62

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

È 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  

68

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");

} }

70

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!

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!

74

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

76

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

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²

80

È 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

82

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

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

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))  … C1 < f(n)/g(n) < C2 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)≈

86

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

 ...

 Quanto fa il totale??

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

88

Ordinamento per fusione (MergeSort)

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

92

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

94

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

} ...

}

È 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

98

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

100

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 è ininfluente, come tutte le costanti moltiplicative

 Nelle notazioni “O­grande” non si indica la base dei  logaritmi, perché log_a si può trasformare in log_b con un  fattore moltiplicativo, che va ignorato

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 logn)

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

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

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

104

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!

106

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  quella di selectionSort)

Prestazioni di insertionSort

Caso migliore: i dati sono già ordinati

Il ciclo più interno non esegue mai iterazioni

 richiede un solo accesso per la prima verifica

Il ciclo esterno esegue n-1 iterazioni

 ad ogni iterazione vengono eseguiti

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

•1 accesso (per verificare la condizione di terminazione  del ciclo interno)

T(n) = 3*(n-1) = O(n)

Prestazioni di insertionSort

Caso medio: i dati sono in ordine casuale

Ciascun nuovo elemento inserito richiede in media  lo spostamento di metà degli elementi alla sua  sinistra

T(n) = (2 + 3*1/2) + (2 + 3*2/2) + (2 + 3*3/2) + ... +

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

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