Master in
BIOINFORMATICA
Corso propedeutico di
Informatica
DOCENTE:
Elisa Tiezzi
UNIVERSITA’ DI SIENA
1
Programma
Introduzione all’informatica
•
•
•
•
•
•
•
•
•
Cos’è l’informatica
Introduzione al concetto di algoritmo
Struttura dell’elaboratore
Introduzione al concetto di programma
Esecuzione delle istruzioni
L’organizzazione dell’unità centrale di elaborazione (CPU)
La memoria centrale
La memoria secondaria
Dispositivi di input/output
Linguaggi di programmazione
Introduzione ai linguaggi di programmazione
2
Elementi del Linguaggio Java
Ambiente di lavoro
 Struttura di un programma
 Tipi di dati fondamentali
 Istruzioni di input/output
 Costrutto decisionale if-then-else
 I cicli con contatore for
 Cicli condizionali while
 Dati strutturati: stringhe e vettori
 Cicli for annidiati
 Classi e oggetti
 Implementazioni di algoritmi

Introduzione alla Complessità



Complessità di problemi
Analisi del caso medio e caso pessimo
Valutazione della complessità: relazioni di ricorrenza
Progetto e analisi di alcuni algoritmi di Ordinamento




Ricorsività
Divide et impera
Mergesort
Quicksort
Sistemi operativi

Windows
3
LIBRO UTILI
• JAVA Fondamenti di Progettazione software
John Lewis, William Loftus
ADDISON-WESLEY
• Java: An introduction to computer science and
programming, 2 edizione
Walter Savitch
Prentice-Hall, Inc
4
INFORMATICA
Alla metà del 900 il MONDO dell’INFORMAZIONE diviene
importante.
INFORMATICA = insieme degli strumenti teorici e pratici
che hanno lo scopo di elaborare l’informazione.
Il termine corrisponde al francese INFORMATIQUE
(contrazione di INFORMATION AUTOMATIQUE) che
compare verso la metà degli anni sessanta.
In realtà l’informatica si occupa non solo dell’elaborazione dei
dati ma anche della scienza e dell’ingegneria dei calcolatori.
Gli anglosassoni usano il termine COMPUTER SCIENCE per
sottolineare questa seconda accezione.
5
L’informatica ha quindi due significati:
• Insiste sull’oggetto = PROCEDURA EFFETTIVA O
ALGORITMO
• Insiste sullo strumento = CALCOLATORE
ELETTRONICO
6
ALGORITMO
Le radici dell’algoritmica sono antiche. Anche se il
suo assetto teorico definitivo è stato raggiunto
nella prima metà di questo secolo e le tecniche di
progetto ed analisi di algoritmi hanno segnato
progressi enormi con la recente diffusione di
calcolatori elettronici, i primi esempi di algoritmi
risalgono alle origini della storia dell’uomo e sono
registrati in documenti di matematica antica. La
parola ALGORITMO fu creata nel latino medievale
per assonanza con il nome del matematico
persiano Al-Khuwarizmi.
7
Informalmente la parola algoritmo indica la specificazione dei
passi elementari che un esecutore deve compiere per giungere
alla soluzione di un problema.
ALGORITMO = complesso di istruzioni….
• precisamente determinato in maniera da non consentire
situazioni di dubbio
• universalmente comprensibile nel senso che chiunque possa
applicarle
• abbastanza generali da potersi applicare ad ogni problema di
una data classe
• tali che applicate ai dati forniscano criteri per determinare
quando la soluzione è raggiunta e questo avvenga in un
numero finito di passi
8
Alcuni algoritmi
I più antichi algoritmi non banali conosciuti oggi furono
registrati dallo scriba egizio Ahmes (1650 a.c.)
Algoritmo moltiplicazione (dati A E B risultato P)
-poni P=0
assegnazione
-finché A≠0 ripeti la sequenza
iterazione
se A è dispari allora addiziona B a P
esecuzione
dimezza A trascurando il resto
condizionata
raddoppia B
9
P
0
3
9
21
A
7
3
1
0
B
3
6
12
24
10
P
0
0
0
12
36
A
12
6
3
1
0
B
3
6
12
24
48
11
Definizione intuitiva di algoritmo
• Elenco finito di istruzioni che specificano
una serie di operazioni, eseguendo le quali
e’ possibile risolvere ogni istanza di un
problema di un dato tipo
12
Proprietà degli algoritmi
• FINITI
• NON AMBIGUI
• GENERALI
13
Soluzione di ax2+bx+c=0
1. inizio dell’algoritmo;
2. acquisire dall’esterno i valori dei coefficienti a, b e c;
3. calcolare il valore b2-4ac;
4. se , allora non esistono radici reali: eseguire 8;
5. se , allora x1=x2=-b/2a: eseguire 7;
6. se , allora x1=(-b+)/2a e x2=(-b-)/2a;
7. comunicare all’esterno i valori di x1 ed x2;
8. fine dell’algoritmo.
14
Descrizione degli algoritmi
Diagramma a blocchi (flow chart): rappresentazione
grafica di un algoritmo che indica il flusso delle
trasformazioni descritte dall’algoritmo che devono
essere eseguite a partire dai dati iniziali per ottenere i
risultati finali.
15
Blocchi elementari
input
azione
begin
falso
end
C
vero
output
16
Esempio su ax2+bx+c=0
begin
a, b, c
b2-4ac
V

F
x1=-b/2a
V

F
x1=(-b+)/2a
x2=(-b-)/2a
x2=-b/2a
x1, x2
radici c.c.
end
17
Il gioco dei quindici
Quindici oggetti, ad esempio fiammiferi, sono su una
tavola. Il primo giocatore ne raccoglie 1, 2 o 3. Il secondo
giocatore ne raccoglie a sua volta 1, 2 o 3. Quindi è
ancora il primo giocatore a raccogliere 1, 2 o 3
fiammiferi. I giocatori alternano le loro mosse finchè sul
tavolo non esistono più fiammiferi. Il giocatore che è
costretto a raccogliere l’ultimo fiammifero è il perdente.
Descrivere una strategia vincente per il primo giocatore.
18
Problema delle dodici monete
Tra 12 monete di identico aspetto potrebbe
nascondersene una falsa e pertanto di peso diverso.
Disponendo di una bilancia a 2 piatti per confrontare
gruppi di monete, si vuole individuare la moneta
falsa e stabilire se essa pesi più o meno delle altre,
mediante non più di 3 pesate.
19
Soluzione del gioco dei quindici
Siano A il primo giocatore e B il secondo
1. Prima mossa: A raccoglie 2 fiammiferi
2. Mosse successive: se B raccoglie k fiammiferi (k<=3),
allora A raccoglie 4-k fiammiferi
20
Soluzione del gioco delle monete
1, 2, 3, 4 : 5, 6, 7, 8
1L 2L 3L 4L
5P 6P 7P 8P
9L 10L 11L 12L
9P 10P 11P 12P
0
1, 2, 5 : 3, 4, 6
1L 2L 6P
1:2
1L 6P 2L
5P 3L 4L
7P 8P
7:8
3:4
8P imp 7P 3L 5P
4L
9L 10L 11P
9:10
9L
9, 10 : 11, 1
12L 12P 0
12:1
1P 2P 3P 4P
5L 6L 7L 8L
1, 2, 5 : 3, 4, 6
5L 3P 4P
7L 8L
3:4
7:8
4P 5L 3P 7L
imp 8L
1P 2P 6L
1:2
2P 6L 1P
9P 10P 11l
9:10
11P 10L 12L 0 12P 10P 11L
9P
21
Breve storia dei calcolatori
• Primi strumenti di calcolo meccanici
– Abaco
• 1600
– Pascal (somma e sottrazione)
– Leibniz (moltiplicazione e divisione)
• 1800
– Babbage (quadrato e stampa)
– Babbage (macchina analitica)
• Ada Augusta Lovelace (prima programmatrice)
– Schede perforate utilizzate nel 1890 (inizio di IBM)
22
• 1944
– Mark I (primo calcolatore elettromeccanico)
• 1946
– ENIAC
• 1949
– EDSAC (macchina di tipo Von Neumann)
• Anni successivi
– Stessa architettura ma tecnologia più avanzata
• 1960
– Internet (fine anni sessanta per esigenze militari, si
chiamava Arpanet)
• 1989
– www (word wide web: enorme enciclopedia)
23
Hardware
Pezzi fisici tangibili che supportano
l’elaborazione (chip di silicio, fili elettrici,
tastiera, dischi, stampanti….)
Software
I componenti hardware sono inutili se non
ricevono precise istruzioni. Un programma
è una serie di istruzioni che l’hardware
esegue in sequenza.
24
Componenti hardware principali
• Dispositivi di input
Organizzazione hardware
standard
– Ad es.: mouse, tastiera
• Dispositivi di output
– Ad es.: monitor, stampante
• Insieme in uno stesso
contenitore
Memoria
– Processore (CPU)
Dispositivi
di input
Processore
(CPU)
Dispositivi
di output
• Central Processing Unit
• Interpreta e esegue le
istruzioni
– Memoria
25
Due Tipi di Memoria
• Principale
– area di lavoro
– mantiene temporaneamente programmi e dati (mentre il
programma è in esecuzione)
• Ausiliaria
– permanente
– salva programmi e risultati
– Esempi: floppy & hard disk, CD, nastri
26
Organizzazione della Memoria
Principale
• Bit = una cifra binaria
– valori: 0 o 1
• Byte = 8 bit
• La memoria principale è
una lista di locazioni
numerate ciascuna di un
byte
• Il numero di byte
utilizzato per memorizzare
un dato varia con il tipo di
dato
Indirizzo
Dato
3021
1111 0000
3022
1100 1100
3023
1010 1010
3024
1100 1110
3025
0011 0001
3026
1110 0001
3027
0110 0011
3028
1010 0010
3029
…
Dato 1: 2 byte
Dato 2: 1 byte
Dato 3: 3 byte
Dato 4: 2 byte
Etc.
27
Organizzazione della
Memoria Ausiliaria
Radice
File
File
Directory
Directory
File
Directory
File
Directory
Directory
File
Directory
File
28
Programma
• Insieme di istruzioni che il calcolatore deve eseguire
Programma
Input
Calcolatore
Output
29
Tipi di Programmi
• Sistema Operativo
– Programma supervisore
• DOS, Windows, MacOS, UNIX, Linux
• Applicazioni esistenti
– word-processor/editor
– web browser
– compilatori o assembler
• Applicazioni create dall’utente
30
Informazione
Esistono due formati per memorizzare
l’informazione:
ANALOGICO
DIGITALE
L’informazione analogica è continua
e cresce proporzionalmente alla
sorgente di informazione
Es: termometro di mercurio, segnali
elettrici
La tecnologia digitale spezza
l’informazione in tanti pezzi
che rappresenta come numeri
Es: compact disc
31
I computer moderni sono digitali:
Ogni tipo di informazione è spezzato in
blocchi. Ogni blocco è rappresentato da un
numero e l’informazione è memorizzata sotto
forma di sequenza di numeri.
Il computer digitale memorizza l’informazione
sotto forma di numeri binari (base 2).
La singola cifra binaria si chiama bit (binary
digit). La base del sistema indica quante cifre
si hanno a disposizione e il valore posizionale
di ogni cifra in un numero.
32
Sistemi posizionali
Il sistema di numerazione decimale è basato
sull’alfabeto decimale {0,1,2,3,4,5,6,7,8,9} ed
ogni numero è rappresentato come sequenza di
simboli di tale alfabeto. Ad ogni simbolo è
associato un peso a seconda della posizione.
Es:
2863=2x103 +8x102+6x101+3x100
33
In generale i sistemi numerici posizionali in base
b2 rappresentano ogni numero con m cifre in
base b:
N=cm-1…….c0
Dove i ci denotano elementi di un insieme di b
simboli che corrispondono ai primi b numeri
naturali 0…..b-1.
Vale N=∑cibi
Es:11002=1x23+1x22+0x21+0x20
34
Come comunicare
• Linguaggio macchina:
– sequenze di 0 ed 1
– rigoroso
– essenziale
• Linguaggio assembler:
– simbolico
– semplice traduzione aggiuntiva
• Linguaggio naturale:
– linguaggio preferito dall’essere umano
– ambiguo, ridondante, non preciso
• Linguaggio di programmazione ad alto livello
35
Storia Moderna
• PASCAL (1970)
• Programming in Logic (1971)
• C (1974)
• ADA(1980)
36
Storia Contemporanea
• C++ (1985)
• Java (1994)
37
Tipi di programmazione
• Funzionale
• Logica
• Procedurale
• Orientata agli oggetti
38
Traduttori
macchina
traduttore
programma
Codice in l.
macchina
macchina
dati
Codice in l.
macchina
risultati
39
Compilatori ed interpreti
• Compilatore
– programma che traduce un programma in
linguaggio ad alto livello in un programma in
linguaggio più semplice che il calcolatore può
eseguire (più o meno) direttamente.
• Interprete
– programma che traduce ed esegue una dopo
l’altra le istruzioni che compongono il
programma sorgente
40
L’approccio di Java
• Sia compilato che interpretato
• Codice intermedio: “Byte Code”
– codice a basso livello portabile
– simile al codice assembler ma indipendente
dall’hardware
– invisibile ai programmatori Java
• L’interprete traduce dal byte code in un programma nel
linguaggio macchina della macchina specifica
41
L’ambiente Java
Programma Java
Programmi precedentemente
compilati
Dati in input
Compilatore Java
Programma in
Byte-Code
Interprete
Esecuzione
Output del Programma Java
42
Cosa è Java
• Linguaggio di programmazione familiare
– Simile a C e C++
• Linguaggio di programmazione orientato a oggetti
– Facile da modificare e altamente riutilizzabile
• Linguaggio robusto
– Restrizioni per evitare che le applicazioni generino errori
• Linguaggio ad alte prestazioni
– Strumenti per la gestione di più processi
• Linguaggio portabile
– Applicazioni eseguibili su Windows, Linux o MacOS
• Linguaggio semplice
– Pochi strumenti base e molte librerie
43
Compilatori tradizionali
compilatore Windows
codice sorgente
compilatore Linux
compilatore MacOS
codice eseguibile Windows
codice eseguibile Linux
codice eseguibile MacOS
44
Compilatore Java
compilatore Windows
codice sorgente
compilatore Linux
compilatore MacOS
interprete bytecode Windows
Java bytecode
interprete bytecode Linux
interprete bytecode MacOS
45
Programmazione
• Concetti base:
– dati
– istruzioni
• Dati:
– variabili
– tipi
• Istruzioni:
– istruzioni base
– strutture di controllo
– sotto-programmi
46
Variabili e tipi
• Variabile:
– locazione di memoria a cui è dato un nome con cui
chiamarla ed utilizzarla
• programmatore usa il nome senza necessariamente sapere che
esso faccia riferimento ad una locazione di memoria
• Tipo:
– ogni variabile ha un tipo che indica che genere di dati la
variabile può contenere
• una variabile può contenere dati di tipo intero (ad es., 15 o
2038), oppure dati di tipo carattere (ad es., ‘a’ o ‘£’) oppure
dati di tipo stringa (ad es., “java” o “pascal”)
47
Istruzioni base
• Assegnazioni ed espressioni:
– comandi per leggere e scrivere dati in una
variabile e per fare calcoli
• esempio: interest = amount * 0.07;
• Input/Output:
– comandi per ricevere dati dall’utente o da un
file su disco e comandi per inviare dati
nell’altra direzione
48
Strutture di controllo
• Un programma è una sequenza di istruzioni
• Il calcolatore esegue le istruzioni nell’ordine in cui esse appaiono, una
dopo l’altra
– molto limitato
• Le strutture di controllo sono istruzioni speciali che consentono di
modificare il normale flusso di istruzioni
• Due tipi base di strutture di controllo
– cicli
• permettono di ripetere una sequenza di istruzioni
– diramazioni
• permettono di decidere tra due o più diverse alternative di proseguimento
49
Sotto-programmi
• I programmi sono spesso abbastanza complessi da dover essere
scomposti in “pezzi” più maneggevoli
• Un sotto-programma consiste di istruzioni per svolgere un certo
compito raggruppate insieme in un’unità a cui è dato un nome
• il nome può essere usato come sostituto dell’intero insieme di istruzioni
• Esempio
– uno dei compiti del programma consiste nel disegnare un rettangolo sullo
schermo
• scrivere le necessarie istruzioni e raggrupparle in un sotto-programma di nome
drawRect
• ogni volta che il programma deve disegnare un rettangolo, lo può fare con una
semplice istruzione: drawRect();
• Vantaggi:
• risparmio di scrittura, organizzazione, riutilizzo
50
Che cosa è una variabile?
• Una locazione in cui memorizzare dati ed a cui è assegnato
un nome
– un contenitore di dati
• Può contenere un solo tipo di dati
– per esempio, solo numeri interi, solo numeri reali
oppure solo caratteri
51
Creazione di variabili
• Tutte le variabili devono essere dichiarate prima di poterle utilizzare
• Una dichiarazione di variabile associa un nome alle locazioni di
memoria ad essa corrispondenti e specifica il tipo di dati che la
variabile conterrà:
Tipo Variabile_1, Variabile_2, …;
• Per esempio, per creare tre variabili che memorizzino il numero di
cesti, il numero di uova per cesto ed il numero totale di uova:
int numberOfBaskets, eggsPerBasket, totalEggs;
52
Nomi di variabili: identificatori
Regole
- devono essere rispettate
•
•
•
•
tutti gli identificatori Java devono
obbedire alle stesse regole
non devono cominciare con una
cifra
devono contenere solo numeri,
lettere, simboli ‘_’ e ‘$’ (ma è
meglio evitare ‘$’, in quanto è
riservato per scopi particolari)
sono sensibili alle maiuscole
(ThisName e thisName sono
due diversi nomi di variabili)
Regole di programmazione
- dovrebbero essere rispettate
•
•
•
•
usare sempre nomi che abbiano un
significato (ad esempio,
eggsPerBasket invece di n o di
count)
iniziare i nomi di variabile con una
lettera minuscola
iniziare le parole interne al nome con
una lettera maiuscola (meglio
eggsPerBasket di
eggsperbasket)
evitare di usare ‘$’ in quanto è riservato
a scopi particolari
53
Due tipi di tipi di dati in Java
primitivi
classi
• I tipi più semplici
• Non possono essere decomposti in
altri tipi
• Contengono solo valori
• Esempi:
int - intero
double - reale
char - carattere
• Più complessi
• Composti di altri tipi (primitivi o
classi)
• Contengono sia dati che metodi
• Esempio:
Integer
String
54
Tipi di Dati Primitivi
Nome
byte
Tipo di valore
intero
Memoria usata
1 byte
Insieme di valori
da -128 a 127
short
intero
2 byte
da -32768 a 32767
int
intero
4 byte
long
intero
8 byte
float
reale
4 byte
double
reale
8 byte
char
carattere (Unicode)
2 byte
da -2,147,483,648 a
2,147,483,647
da -9,223,372,036,854,775,808
a 9,223,374,036,854,775,808
da +/- 3.4028… x 10+38 a
+/- 1.4023… x 0-45
da +/- 1.767… x 10+308 a
+/- 4.940… x 0-324
tutti i caratteri Unicode
boolean
true oppure false
1 bit
55
Quali sapere per ora
• double
• int
– semplicemente numeri interi
– possono essere positivi e
negativi
– nessun punto decimale
• char
– semplicemente un singolo
carattere
– utilizza le virgolette singole
• per esempio, `A`;
– numeri reali, sia positivi che
negativi
– ha un punto decimale (parte
frazionaria)
– due formati
• numero con punto
decimale, a.e. 514.061
• notazione e o scientifica,
a.e. 5.14061 e2, che
significa 5.14061 x 102
56
Assegnare valori alle variabili
• Istruzione di assegnazione
– variabile = espressione;
• esempio: answer = 42;
• Operatore di assegnazione: “=“
– non lo stesso dell’algebra
– significa: “assegna il valore dell’espressione alla destra del segno di
uguale alla variabile alla sinistra.”
– se numberOfCards ha il valore 7 e handicap ha il valore 2, allora la
seguente istruzione imposta il valore di score a 9:
score = numberOfCards + handicap;
• La variabile può apparire in entrambi i lati:
int count = 10;
count = count - 1;
– nuovo valore di count = 10 - 1 = 9
57
Assegnare valori iniziali alle variabili
• I valori iniziali possono o meno essere assegnati quando le variabili
sono dichiarate:
int totalEggs, numberOfBaskets, eggsPerBasket;
oppure
int totalEggs = 0;
int numberOfBaskets = 0;
int eggsPerBasket = 0;
• Suggerimento: è una buona regola di programmazione inizializzare
sempre le variabili.
58
Cambiare il valore di una variabile
• Generalmente il valore viene cambiato (è assegnato un
valore diverso) in qualche parte del programma
• Può essere calcolato a partire da altri valori:
totalEggs = numberOfBaskets * eggsPerBasket;
• Oppure può essere letto in input
– vedremo più avanti
59
Operatori di assegnazione specializzati
• Un’abbreviazione per eseguire un’operazione ed assegnare un nuovo
valore ad una variabile
• Forma generale: var <op>= expression;
– equivalente a: var = var <op> (expression);
– <op> è +, -, *, /, or %
• Esempi:
amount += 5;
//amount = amount + 5;
amount *= 1 + interestRate;
//amount = amount * (1 + interestRate);
• La parte destra è trattata come una singola unità (come se vi fossero
delle parentesi)
60
Costanti
•
•
•
Le costanti sono simili alle variabili, ma possono
contenere un solo valore per tutta la durata della loro esistenza.
In Java si dichiarano le costanti premettendo
la parola chiave final.
E’ convenzione usare lettere maiuscole.
Es.: final int NUMERO_MASSIMO_POSTI = 427
•
E’ buona pratica usare costanti invece
di valori numerici (letterali)
perche’ si evita di modificarli inavvertitamente.
61
Valore di ritorno
• Le espressioni ritornano valori: il numero prodotto da
un’espressione è il “valore di ritorno”
int numberOfBaskets, eggsPerBasket, totalEggs;
numberOfBaskets = 5;
eggsPerBasket = 8;
totalEggs = numberOfBaskets * eggsPerBasket;
– nell’ultima linea numberOfBaskets ritorna il valore 5 e
eggsPerBasket ritorna il valore 8
– numberOfBaskets * eggsPerBasket è un’espressione
che ritorna il valore intero 40
62
Conversione di tipo
• La conversione di tipo cambia il tipo di dato di un valore
– Non è possibile assegnare un valore di un tipo ad una variabile di
un tipo diverso, a meno che non lo si converta in modo da
coincidere con il tipo della variabile
• La conversione di tipo modifica solo il tipo del valore di
ritorno, non il tipo della variabile
– ad esempio:
double x;
int n = 5;
x = n;
• poiché n è un int ed x è un double, il valore ritornato da n (non n)
deve essere convertito in un double prima di essere assegnato ad x
63
Conversione implicita
• La conversione di tipo è eseguita implicitamente (in modo
automatico) quando un tipo “più basso” viene assegnato ad
un tipo “più alto” secondo la seguente gerarchia:
byte --> short --> int --> long --> float -->
double
• Ad esempio:
double x;
int n = 5;
x = n;
– il valore di ritorno di n è convertito (in modo implicito) in un
double, e quindi assegnato ad x
– x contiene 5.0
– il tipo di dato della variabile n è invariato (ovvero ancora int)
64
Ancora conversione implicita
• Alcune espressioni includono valori di tipo diverso
• Tutti i valori sono automaticamente (in modo implicito) fatti avanzare
al livello più alto prima di eseguire il calcolo del valore di ritorno
• Ad esempio:
double a;
int n = 2;
float x = 5.1;
double y = 1.33;
a = (n * x)/y;
– i valori di n ed x sono automaticamente convertiti al tipo
double prima di eseguire la moltiplicazione e la divisione
65
Conversione esplicita
• La conversione esplicita è necessaria in tutti i casi non
coperti da quella implicta
• Ad esempio:
int points;
double distance = 9.0;
points = distance;
– l’ultima istruzione è illegale (anche se la parte frazionaria è 0)
• Porre di fronte al valore il cui tipo deve essere convertito il
nuovo tipo tra parentesi:
points = (int)distance;
– quest’istruzione è legale
66
Troncamento
• Conversione da reale ad intero non arrotonda, ma tronca
– la parte frazionaria viene semplicemente ignorata
• Ad esempio:
int numberOfDollars;
double dinnerBill = 26.99;
numberOfDollars = (int) dinnerBill;
– il valore di numberOfDollars è ora 26
67
Divisione reale e divisione intera
• Se almeno uno dei valori che occorrono nella divisione è di
tipo float o double, allora non si ha nessun
troncamento (tutti i valori sono convertiti al tipo più alto)
• Il troncamento si verifica se tutti i valori sono interi
• Ad esempio:
int a = 4, b =5, c;
double x = 1.5, y;
y = b/x;
c = b/a;
– il valore di y è 3.333... mentre quello di c è 1
68
Caratteri come interi
•
Il tipo di dati char memorizza un singolo carattere stampabile
•
Ad esempio:
char answer = `y`;
•
I caratteri sono in realtà memorizzati come interi secondo un codice speciale
– ogni carattere stampabile (lettera, cifra, segno di interpunzione, spazio e
tabulazione) ha associato un codice intero distinto
– i codici sono distinti a seconda delle maiuscole o delle minuscole
• ad esempio, 97 potrebbe essere il codice di ‘a’ e 65 quello di ‘A’
•
•
•
ASCII e Unicode sono due codici molto frequenti
Unicode include tutti i codici ASCII più altri codici per linguaggi con alfabeto
diverso da quello italiano
Java usa Unicode
69
Conversione di carattere in intero
• La conversione di un valore di tipo char produce il suo
codice Unicode
• Ad esempio, eseguendo le seguenti istruzioni
char answer = `7`;
int intAnswer = answer;
il valore di intAnswer sarebbe 55 (non 7) in quanto
55 è il codice Unicode del carattere ‘7’
70
Imprecisione di numeri in virgola mobile
• I calcolatori memorizzano i numeri utilizzando un numero
fissato di bit, per cui non tutti i numeri reali possono essere
codificati in modo esatto
– un numero infinito di bit sarebbe richiesto per rappresentare in
modo esatto ogni numero reale
– ad esempio, se il calcolatore può rappresentare solo 10 cifre dopo il
punto decimale, allora il numero reale 1/3=0.33333... sarebbe
memorizzato come 0.3333333333 (che non è esattamente 1/3)
• Gli interi, al contrario, sono memorizzati in modo esatto
– se il valore 2 è assegnato ad una variabile di tipo int, il suo valore
è esattamente 2
71
L’operatore di modulo: %
• Usato con i tipi interi
• a%b restituisce il resto della divisione di b per a
• Ad esempio:
int a = 14; b = 4, c;
c = a%b;
– c ora ha il valore 2, che è il reso della divisione di 14 per 4
• Ha molte applicazioni
– consente di contare modulo 2, 3 o qualsiasi altro numero
• consente di distinguere numeri pari da numeri dispari
– consente di eseguire un’operazione solo in corrispondenza dei
multipli di un dato numero
72
Precedenze e parentesi
• Le espressioni Java soddisfano regole simili all’algebra dei numeri
reali
• Si usano le parentesi per forzare la precedenza
– Tranne i casi in cui la precedenza è corretta ed ovvia, conviene usare le
parentesi per facilitare la lettura dell’espressione
Espressioni
matematiche
rate2 + delta
Espressione Java
(forma preferita)
rate*rate + delta
Espressione Java
con tutte le parentesi
(rate*rate) + delta
2(salary + bonus)
2 * (salary + bonus)
2 * (salary + bonus)
1/(time + 3 * mass)
1/(time + (3 * mass))
(a - 7) / (t + 9 * v)
(a - 7) / (t +( 9 * v))
1
time  3mass
a -7
t  9v
73
Operatori di incremento e decremento
• Utilizzati per aumentare o diminuire il valore di una variabile di 1
• Incremento
– ++
• ad esempio, count++;
• Decremento
– -• ad esempio, count--;
• La variabile può essere incrementata (o decrementata) prima o dopo
aver usato il suo valore attuale. Ad esempio, dopo
int count=5;
int n = 2*(++count);
int m = 2*(count++);
sia n che m hanno il valore 12, mentre count ha il valore 7
74
Controllo del flusso
• Flusso di esecuzione: ordine in cui le istruzioni di
un programma sono eseguite
• Salvo contrordini, è in sequenza
• Due possibili alterazioni:
– selezione: sceglie un’azione da una lista di due o più
azioni possibili
– ripetizione: continua ad eseguire un’azione fino a
quando non si verifica una condizione di termine
75
Strutture Java
•
Sequenza

– di default
Selezione
» if
» if-else
» switch

Ripetizione
» while
» do-while
» for
76
Valori Booleani
• boolean: tipo di dato primitivo in Java
che può assumere valore true oppure
false
• Variabili (o espressioni) il cui valore è di
tipo boolean sono chiamate variabili (o
espressioni) Booleane
– Il valore di una variabile (o espressione)
Booleana è true oppure false
77
Espressioni Booleane
• Esprimono una condizione che risulta
essere vera o falsa
• Esempio (A e B sono due dati non
necessariamente dello stesso tipo):
– A è maggiore di B?
– A è uguale a B?
– A è minore di oppure uguale a B?
78
Operatori di confronto
Notazione matematica
= (uguale a)
 (diverso da)
> (maggiore di)
 (maggiore di oppure uguale a)
< (minore di)
 (minore di oppure uguale a)
Java
==
!=
>
>=
<
<=
Esempio
utile == 0
utile  tax
ricavi > costi
voto >= 60
pressione < max
ricavi <= costi
79
Confronto tra caratteri e stringhe
• Si può confrontare caratteri: sono infatti basati
su Unicode che definisce un ordinamento per
tutti i possibili caratteri che possono essere
usati. Dato che in Unicode, per esempio, il
carattere ‘a’ viene prima di ‘b’, si può dire che
‘a’ è minore di ‘b’.
• Non si possono usare operatori di confronto e di
uguaglianza tra stringhe.
80
Confronto tra valori in virgola
mobile
• Raramente si usa l’operatore di uguaglianza
tra due valori in virgola mobile.
• Per testare l’uguaglianza di due valori in
virgola mobile si può calcolare il valore
assoluto della loro differenza e confrontare
il valore così ottenuto con un valore di
tolleranza, ad esempio 0,00001.
81
Operatori logici
• AND: &&
– congiunge due espressioni
– valore di ritorno true se e solo se entrambi le
espressioni sono vere
• OR: ||
– disgiunge due espressioni
– valore di ritorno false se e solo se entrambi le
espressioni sono false
• Valutazione della seconda espressione
condizionata
– per avere valutazione completa, usare & e |
82
Altri operatori logici
• NOT: !
– nega un’espressione
– valore di ritorno true se e solo se
l’espressione è falsa
• XOR: ^
– disgiunge due espressioni in modo esclusivo
– valore di ritorno true se e solo se le due
espressioni hanno diversi valori di ritorno
– esprimibile mediante AND, OR e NOT
83
Precedenze e associatività
Operatori
Associatività
++ -++ -- + - !
(type)
*/%
+< <= > >=
= = !=
&
^
|
&&
||
= += -= *= /= %= &= |= ^=













Tipo
Unario postfisso
Unario
Conversione
Moltiplicativo
Additivo
Relazionale
Uguaglianza
AND
XOR
OR
AND
OR
assegnazione
84
Esempio
•
score < min/2 – 10 || score > 90
•
score < (min/2) – 10 || score > 90
•
score < ((min/2) – 10) || score > 90
•
(score < ((min/2) – 10)) || (score > 90)
•
((score < ((min/2) – 10)) || (score > 90))
85
Blocchi di istruzioni
• Insiemi di istruzioni racchiuse tra parentesi
graffe
– corrispondono ad un’azione
– parentesi non necessarie se include una sola
istruzione
• Esempio:
{ //inizio del blocco
calorieLess = 500;
calorieAllotment = calorieAllotment-calorieLess;
} //fine del blocco
86
Istruzione if
• Selezione semplice:
– esegue un’azione se solo se una certa condizione è verificata
• Sintassi:
if (Espressione_Booleana)
Blocco_1 //esegui solo se vera
Prossima_Istruzione; //sempre eseguita
Espressione_Booleana
true
Blocco_1
false
Prossima_Istruzione
87
Esempio
• Se il peso è superiore a quello ideale allora
diminuisci il numero totale di calorie che si
possono assumere di 500.
• Successivamente, imposta il numero di
calorie da assumere per colazione ad un
terzo del numero totale di calorie
• if(weight > ideal)
calorieAllotment = calorieAllotment500;
calorieBreakfast = calorieAllotment/3;
88
Istruzione if-else
• Selezione doppia:
– esegue un’azione oppure un’altra in base al valore di
una condizione
• Sintassi:
if (Espressione_Booleana)
Blocco_1 //esegui solo se vera
else
Blocco_2 //esegui solo se falsa
Prossima_Istruzione; //sempre eseguita
89
Diagramma di flusso
Espressione_Booleana
true
Blocco_1
false
Blocco_2
Prossima_Istruzione
90
Esempi
• Esempio con una singola istruzione:
if(balance >=0)
balance=balance+(INTEREST_RATE*balance)/12;
else
balance=balance-OVERDRAWN_PENALTY;
• Esempio con un’istruzione composta:
if(balance >=0)
{
interest=(INTEREST_RATE*balance)/12;
balance=balance+interest;
}
else
{
interst=OVERDRAWN_PENALTY;
balance=balance-interest;
}
91
Istruzioni if-else annidate
• Annidamento di istruzioni if-else:
– tratta situazioni con più di due possibilità
– Attenzione : ogni else si riferisce all’if più vicino
• Sintassi:
if (Espressione_Booleana_1)
Blocco_1
else if (Espressione_Booleana_2)
Blocco_2
.
else if (Espressione_Booleana_ n)
Blocco_n
else
Blocco_Default
92
Esempio
if (score >= 90)
grade = ‘A’;
else if (score >= 80)
grade = ‘B’;
else if (score >= 70)
grade = ‘C’;
else if (score >= 60)
grade = ‘D’;
else
grade = ‘E’;
93
Istruzione switch
• Selezione multipla
• Sintassi:
switch(Espressione_Di_Controllo)
{
case Etichetta_Caso_1:
Sequenza_Istruzioni_1
break;
case Etichetta_Caso_2:
Sequenza_Istruzioni_2
break;
...
}
default:
Sequenza_Istruzioni_Default
94
• Espressione_Di_Controllo deve essere
char, int, short o byte
• Espressione_Di_Controllo e le varie
Etichette_Caso_* devono essere dello stesso
tipo
• L’istruzione break, che può essere omessa, fa,
passare il controllo alla prima istruzione dopo
l’istruzione switch
– se break non è inclusa, allora l’esecuzione procede
con le istruzioni del caso successivo
95
Diagramma di flusso
Espressione_Di_Controllo = Etichetta_Caso_1
true
Sequenza_Istruzioni_1
false
break?
true
false
Espressione_Di_Controllo = Etichetta_Caso_2
true
Sequenza_Istruzioni_2
false
break?
...
false
true
default?
false
true
...
Sequenza_Istruzioni_Default
96
Esempio
switch (seatLocationCode)
{
case 1:
type=‘O’;
price = 40.00;
break;
case 2:
type=‘M’;
price = 30.00;
break;
case 3:
case 4:
type=‘B’;
price = 15.00;
break;
default:
type=‘U’;
}
97
L’operatore condizionale
• È l’unico operatore ternario di Java
• Sintassi:
– (Espressione Booleana)?
Espressione_1:Espressione_2;
• Il valore di ritorno è quello di Espressione_1
se Espressione Booleana è vera, altrimenti
è quello di Espressione_2
98
Esempio
• max = (n1>n2)?n1:n2;
• Equivale a:
if (n1>n2)
max = n1;
else
max = n2;
99
Ripetizione: i cicli
• Struttura:
– corpo del ciclo
– condizione di terminazione del ciclo
• Organizzazione logica
– cicli controllati da condizioni
– cicli controllati da contatori
• Istruzioni Java per realizzare cicli
– while
– do-while
– for
100
Ciclo while
• Sintassi:
while (Espressione_Booleana)
Blocco //corpo del ciclo
Prossima_Istruzione
• Espressione_Booleana rappresenta la
condizione di ripetizione del ciclo
– si esce dal ciclo, quando è falsa
• Blocco rappresenta il corpo del ciclo
• Istruzioni di inizializzazione precedono
generalmente il ciclo
101
Diagramma di flusso
Espressione_Booleana
true
Blocco
false
Prossima_Istruzione
102
Esempio
• Ciclo che calcola la somma dei primi 10 numeri
interi
int total = 0;
int count = 1;
while (count <= 10)
{
total = total + count;
count++;
}
103
Minimo numero di iterazioni
• Il numero minimo di iterazioni di un ciclo while
è 0 dato che la condizione di ingresso può essere
immediatamente falsa
• Esempio:
int next;
int total = 0;
next = (int)(Math.random()*100)-50;
while (next >= 0)
{
total = total + next;
next = (int)(Math.random()*100)-50;
}
104
Ciclo do-while
• Sintassi:
do
Blocco //corpo del ciclo
while (Espressione_Booleana);
Prossima_Istruzione
• Il corpo del ciclo è eseguito almeno una volta dato
che la condizione di ripetizione è posta dopo il
corpo stesso
105
Diagramma di flusso
Blocco
true
Espressione_Booleana
false
Prossima_Istruzione
106
Esempio
int next;
int total = 0;
do
{
next = (int)(Math.random()*100)-50;
total = total + next;
}
while (next >= 0);
107
Cicli infiniti
• Cause principali:
– errata espressione Booleana
– errata (o assente) alterazione delle variabili coinvolte
nell’espressione Booleana
• Esempio:
int total = 0;
int count = 1;
while (count != 10)
{
total = total + count;
count += 2;
}
108
Ciclo for
• Struttura:
–
–
–
–
azione di inizializzazione
condizione di ripetizione
corpo del ciclo
azione di continuazione
• Sintassi:
for (Inizializzazione;
Espressione_Booleana;
Continuazione)
Blocco
Prossima_Istruzione
109
Diagramma di flusso
Inizializzazione
Espressione_Booleana
false
true
Blocco
Continuazione
Prossima_Istruzione
110
Esempio
• Sommare separatamente i numeri pari e quelli
dispari compresi tra 1 e 100
int sumEven = 0, sumOdd = 0;
for (int count = 1; count <= 99; count+=2)
{
sumOdd = sumOdd + count;
sumEven = sumEven + count + 1;
}
111
Considerazioni pratiche
• Errori comuni:
– cicli infiniti (non intenzionali)
– cicli con contatore che non eseguono il numero di
iterazioni desiderato (scarto di uno).
• Testare soprattutto la condizione di ripetizione di
un ciclo per evitare possibili errori
• Mantenere traccia dei valori delle variabili
(facendo uso di stampe su video)
112
Questioni di stile
• Blocchi:
{
Sequenza_Istruzioni
}
– inserire le parentesi graffe anche se il blocco è
costituito da una sola istruzione
– indentare tutte le istruzioni incluse nella
sequenza
113
• Istruzione if:
if (Espressione_Booleana)
Blocco
• Istruzione if-else:
if (Espressione_Booleana)
Blocco else
Blocco
114
• Istruzione switch:
switch (Espressione_Di_Controllo)
{
case Etichetta_1:
Sequenza_Istruzioni_1
case Etichetta_2:
Sequenza_Istruzioni_2
...
case Etichetta_n:
Sequenza_Istruzioni_n
default:
Sequenza_Istruzioni_Default
}
115
• Istruzione while:
while (Espressione_Booleana)
Blocco
• Istruzione do-while:
do
Blocco while (Espressione_Booleana);
• Istruzione for:
for (Inizializzazione ; EB; Continuazione)
Blocco
116
Sotto-programmi
• Necessità di scomporre programmi complessi
• Sotto-programma: insieme di istruzioni a cui è dato un nome
• il nome usato come sostituto dell’intero insieme di istruzioni
• Esempio
– generare un numero intero casuale compreso tra 1 e 100
• raggruppare le necessarie istruzioni in un sotto-programma di nome
randomNumber
• ogni volta che il programma deve generare un numero intero casuale compreso
tra 1 e 100, lo può fare con una semplice istruzione: randomNumber()
• Vantaggi:
• risparmio di scrittura, organizzazione, riutilizzo
117
Sotto-programmi in Java
• In Java, i sotto-programmi sono chiamati
metodi
• Interfaccia (sintattica) di un metodo:
– nome del metodo
– input richiesto
– output fornito
• Sintassi della dichiarazione:
Tipo_Output Nome_Metodo(Lista_Input)
Blocco // corpo del metodo
118
Tipologie di metodi
• Alcuni metodi (talvolta, detti funzioni) eseguono
un’azione e ritornano un singolo valore
– esempio: il metodo randomNumber genera un
numero intero casuale compreso tra 1 e 100 e ne ritorna
il valore
• Altri metodi (talvolta, detti procedure) si limitano
ad eseguire un’azione
– esempio: il metodo printWelcomeMessage stampa
un messaggio di benvenuto
119
Tipo di ritorno dei metodi
• Sempre specificato
• Può essere:
– tipo di dato primitivo (come char oppure int)
– classe (come String)
– void se nessun valore viene ritornato
• Un metodo (non void) può essere usato ovunque
è lecito usare il suo tipo di ritorno
– esempio:
int r = randomNumber();
120
Istruzione return
• I metodi che ritornano un valore devono eseguire,
all’interno del corpo, un’istruzione return che
include il valore da ritornare
• Esempio:
int randomNumber()
{
int r = 1+(int)(Math.random()*99);
return r;
}
121
Esempio di metodo void
• Definizione del metodo
printWelcomeMessage:
void printWelcomeMessage()
{
System.out.println(``Hello!’’);
System.out.println(``Welcome to paradise!’’);
}
• Questo metodo esegue un’azione (stampa
un messaggio di benvenuto) ma non ritorna
alcun valore
122
Nomi di metodi
• Buone regole di programmazione:
– verbi per nominare metodi senza un valore di ritorno
• realizzano un azione
• esempio: printIntegerNumber
– nomi per nominare metodi con un valore di ritorno
• creano (ritornano) un dato, ovvero una cosa
• esempio: randomNumber
– iniziare il nome di un metodo con una lettera minuscola
123
Parametri di un metodo
• Metodi più flessibili (e quindi più utili) con valori
di input (detti valori passati o parametri)
• Parametri e loro tipi di dato specificati all’interno
delle parentesi tonde successive al nome del
metodo
– questi sono i parametri formali
• lista di parametri separati da virgole
• Invocando un metodo, vanno inseriti (all’interno
delle parentesi tonde) valori del tipo specificato e
nell’ordine specificato
– questi sono gli argomenti, o parametri attuali
124
Esempio
• Dichiarazione:
int randomNumber(int min, int max)
{
return min+(int)(Math.random()*(max-min));
}
– parametri formali: min e max
• Invocazione:
int m = 10;
int M = 20;
int r = randomNumber(m, M);
– argomenti: m ed M
125
Passaggio per valore
• Parametri formali sono locali al loro metodo
– variabili usate come argomenti non possono essere modificate dal
metodo
• metodo riceve solo il loro valore
• Quando un metodo è invocato, il valore di ciascun
argomento è copiato nel (assegnato al) corrispondente
parametro formale
– numero di argomenti uguale a numero di parametri formali
– tipo di dati degli argomenti uguale a quello dei corrispondenti
parametri formali
– parametri formali inizializzati con i valori passati
126
Variabili locali ad un blocco
• Variabile dichiarata all’interno di un blocco:
– vista solo all’interno del blocco
• locale al blocco, per cui è chiamata variabile locale
• se il blocco è il corpo di un metodo, la variabile è detta essere
una variabile locale del metodo
– quando il blocco termina l’esecuzione, le variabili locali
spariscono
• riferimenti a variabili locali fuori del blocco corrispondente
causano errori di compilazione
• Variabile dichiarata nell’inizializzazione di un
for è locale al ciclo for
– non può essere usata fuori del ciclo
127
Quando e dove
• Dichiarare una variabile fuori di tutti i blocchi ma
all’interno di un metodo la rende disponibile a tutti
i blocchi del metodo
• Buone regole di programmazione
– dichiarare le variabili immediatamente prima di
utilizzarle
– inizializzare le variabili al momento della dichiarazione
– non dichiarare variabili all’interno di cicli
• richiede tempo la creazione e la distruzione di una variabile
• eccezione: variabili dichiarate nell’inizializzazione di un ciclo for
128
Programmazione procedurale
• Obiettivo
– Concepire la costruzione di programmi di grande
dimensione e complessità come composizione di
componenti (procedure)
• costruite ad hoc
• esistenti
• Vantaggi
– dominare la complessità
– ridurre i costi
– aumentare parallelismo nello sviluppo
129
Scomporre e comporre
• Principio del divide et impera
• Suddividere per isolare parti il più possibile
autonome ed indipendenti
• Parti potenzialmente riutilizzabili
130
Autonomia ed indipendenza
• Ogni parte deve avere una sua coesione da
un punto di vista logico
– deve rappresentare un’astrazione significativa
• Ogni parte deve essere il più possibile
indipendente dalle altre parti
131
Procedura
• È una parte del sistema complessivo
• Deve avere, rispetto alle altre parti,
un’interfaccia ben definita
– interfaccia: tutto ciò che è necessario conoscere
per poter usare la procedura
132
Procedure e metodi
• Un metodo Java può essere considerato
come una procedura
• La sua interfaccia è specificata
nell’intestazione
• È bene che non modifichi variabili che non
sono locali
– indipendenza dalle altre procedure
133
Relazione di utilizzo
• Procedura A usa procedura B se, per
svolgere il proprio compito, deve accedere
alla procedura B attraverso quanto definito
nell’interfaccia di quest’ultima
– esempio: se il metodo F invoca il metodo G,
allora F usa G
134
Interfaccia/implementazione
• Occorre distinguere tra questi due aspetti
• Interfaccia
– dice ciò che le altre procedure possono
conoscere
• Implementazione
– è come ciò che viene offerto attraverso
l’interfaccia è effettivamente realizzato
135
Struttura di un programma
• Procedura principale
• Più procedure asservite a quella principale
• Ciascuna di quest’ultime, a sua volta, ne
può usare altre
136
Una visione grafica
A usa B
A
B
procedura
asservita P1
procedura
asservita P5
procedura
principale
procedura
asservita P2
procedura
asservita P3
procedura
asservita P4
137
Realizzazione in Java
• Procedura principale
– procedura main
• Per ciascuna procedura asservita
– interfaccia
• dichiarazione
– implementazione
• definizione del corpo
138
Esempio
• Programma che genera due frazioni
• Decide se sono
– apparenti: numeratore multiplo di denominatore
– proprie: numeratore minore di denominatore
•
•
•
•
Confronta le due frazioni
Riduce le due frazioni ai minimi termini
Riduce le due frazioni allo stesso denominatore
Esegue le quattro operazioni
139
Struttura (parziale)
main
isApparent
isProper
isFETS
isFBTS
computeRN
computeRD
computeGCD
140
Frazioni apparenti e proprie
boolean isApparent(int n, int d)
{
return (n % d == 0);
}
boolean isProper(int n, int d)
{
return (n < d);
}
141
Confronto tra frazioni
boolean isFETS(int n1,int d1,int n2,int d2)
{
return (n1*d2 == n2*d1);
}
boolean isFBTS(int n1,int d1,int n2,int d2)
{
return (n1*d2 > n2*d1);
}
142
Calcolo del MCD (1)
int computeGCD(int n, int d){
int count = 2, min = n, GCD = 1;
if (n > d) min = d;
while (count <= min) {
if ((n%count == 0) && (d%count == 0))
GCD = count;
++count;
}
return GCD;
}
143
Semplificazione di frazioni
int computeRN(int n, int d)
{
return (n / computeGCD(n, d));
}
int computeRD(int n, int d)
{
return (d / computeGCD(n, d));
}
144
Procedura principale
void main()
{
int n1 = 1+(int)(Math.random()*99);
int d1 = 1+(int)(Math.random()*99);
int n2 = 1+(int)(Math.random()*99);
int d2 = 1+(int)(Math.random()*99);
...
}
145
Calcolo del MCD (2)
int computeGCD(int n, int d){
int GCD = n;
if (n > d) GCD = d;
while (GCD > 1) {
if ((n%GCD == 0) && (d%GCD == 0))
break;
--GCD;
}
return GCD;
}
146
Algoritmo di Euclide
• Proprietà:
– se r è il resto della divisione di a per b (ab),
allora i divisori comuni di a e b coincidono con
quelli di b ed r
– MCD(a, b) = MCD(b, r) dove r = a mod b
• Algoritmo:
– se b=0, allora MCD(a, b) = a, altrimenti
MCD(a, b) = MCD(b, a mod b)
147
Calcolo del MCD (3)
int computeGCD(int n, int d)
{
int temp = 0;
while (d > 0) {
temp = d;
d = n % d;
n = temp;
}
return n;
}
148
Ricorsione
• Strumento potente per definizioni
matematiche
• Possibilità di definire insieme infinito di
oggetti con regola finita
– possibilità di descrivere un insieme infinito di
computazioni con un programma finito
149
Ricorsione in matematica
• Le formule matematiche sono spesso
espresse in termini ricorsivi
• Esempio: definizione di fattoriale
1!=1
N!=N * (N-1)!
150
Metodi ricorsivi
• Contengono riferimenti espliciti a sé stessi
– direttamente ricorsivi
• Un metodo ne invoca un altro e
l’esecuzione di quest’ultimo porta ad un
certo punto ad invocare nuovamente
(direttamente o indirettamente) il metodo
originale
– indirettamente ricorsivi
151
Ricorsione infinita
• Requisito fondamentale:
– chiamata ricorsiva subordinata ad una condizione che
ad un certo istante deve divenire non soddisfatta
• Qualsiasi definizione ricorsiva deve avere
una parte non ricorsiva, detta base della
ricorsione, che permette alla ricorsione
stessa di terminare
• Nell’esempio precedente del fattoriale la
base è 1! che è posto uguale ad 1
152
Variabili in metodi ricorsivi
• Ogni invocazione genera un nuovo insieme
di variabili locali
• Ogni parametro riceve un valore iniziale in
base alla nuova invocazione
• Ogni volta che il metodo termina si ritorna
al metodo che lo ha chiamato ( che potrebbe
essere lo stesso)
153
Numeri di Fibonacci
• Schema più complicato di composizione
ricorsiva che potrebbe (e dovrebbe) essere
tradotto in forma iterativa
• Definizione:
– fib0 = 0
– fib1 = 1
– fibn+1 = fibn + fibn-1
154
Implementazione ricorsiva
int computeFib(int n)
{
if (n == 0)
return 0;
if (n == 1)
return 1;
return computeFib(n-1)+computeFib(n-2);
}
155
Numero di invocazioni
5
4
3
2
3
2
1
1
2
1
1
0
1
0
0
• Numero totale di invocazioni cresce
esponenzialmente
156
Implementazione iterativa
int computeFib(int n)
{
int i = 1, x = 1, y = 0;
while (i < n) {
i = i+1;
x = x+ y;
y = x -y;
}
return x;
}
157
Considerazioni
• Ricorsione deve essere evitata se esiste una
soluzione iterativa ovvia
• Non vuol dire evitare la ricorsione a
qualunque costo
– esistono molte buone applicazioni della
ricorsione
– algoritmi per loro natura ricorsivi vanno
implementati con metodi ricorsivi
158
Le torri di Hanoi
inventato nel 1880 da Lucas
• Tre aste (o torri) ed n dischi di dimensioni diverse
(con buco per inserirli nelle aste)
• All’inizio tutti i dischi sono nell’asta 1
– in ordine decrescente di grandezza
• Obiettivo: portarli nella torre 3 rispettando le
regole seguenti
–
–
–
–
nessun disco mai sopra uno più piccolo
si può spostare un solo disco alla volta
dischi sempre collocati su una torre (non a parte)
solo disco in cima ad una torre può essere spostato
159
Algoritmo ricorsivo
• Obiettivo: spostare k dischi da torre 1 a torre 3
• Algoritmo:
– Spostare k-1 dischi da torre originale a torre
temporanea
– Spostare 1 disco da torre originale a torre di
destinazione
– Spostare k-1 dischi da torre temporanea
a torre di destinazione
160
Implementazione 1
void moveTowers(int k, int o,int d)
{
if (k > 0)
{
moveTowers(k-1, o, 6-o-d);
System.out.println("Sposta da "+o+"a"+d);
moveTowers(k-1,6-o-d,d);
}
}
161
Programmazione OO
• Concetti base:
Dati  Istruzioni = Metodi
– dati
– istruzioni
• Dati:
– variabili
– tipi
Programmazione Procedurale
Dati  Metodi = Classi
• Istruzioni:
– istruzioni base
– strutture di controllo
– sotto-programmi
Programmazione a Oggetti
162
Cosa è un oggetto
Variabili
(stato)
Metodi
(comportamenti)
Un oggetto è una “scatola” software contenente
variabili (che descrivono lo stato di un oggetto)
e metodi (detti suoi membri, definiscono
i comportamenti)
163
Esempio: i numeri razionali
razionale 3/4
Istanza:
un preciso oggetto
Variabili di istanza (campi):
contengono i valori (lo stato) del
numero razionale
add
3
num
div
4
Metodi di istanza:
agiscono sul numero razionale
164
Cosa è un messaggio
Gli oggetti interagiscono e comunicano tra loro usando i messaggi
per ottenere maggiori funzionalità e comportamenti più complessi
isBigger(razionale di confronto)
num
den
altro oggetto utilizzato
dal programma
razionale 3/4
165
Usare gli oggetti
•
•
•
Inviare un messaggio ad un oggetto significa invocare un metodo
dell’oggetto
Accedere alle variabili di istanza di un oggetto significa poter
manipolare o ispezionare il loro valore
Sintassi per invocare un metodo/accedere alle variabili di istanza di
un oggetto:
–
all’interno della definizione di un oggetto:
metodo(lista_di_parametri)
variabile
–
all’esterno della definizione di un oggetto (operatore ‘.’):
riferimentoOggetto.metodo(lista_di_parametri)
riferimentoOggetto.variabile
166
Cosa è una classe
Una classe è un “prototipo” che definisce le variabili
e i metodi comuni a tutti gli oggetti di un certo tipo.
Una classe è solo il modello di un oggetto e
pertanto non riserva spazio di memoria per i suoi
dati.
Ogni oggetto ha il suo spazio dati, un oggetto è
un’istanza di una classe.
167
Esempio
classe Rational
Tutti gli oggetti di tipo Rational
possiedono i due campi interi
num e den ed almeno i 6
metodi riportati
add
int num
int den
168
oggetto 8/15
istanza di Rational
add
int num=8
int den=15
oggetto 4/5
istanza di Rational
add
int num=4
int den=5
169
Dichiarare una classe
• class nome_classe
{
// definizione variabili
// definizione metodi
}
• Esempio:
class Rational
{
int num;
int den;
// definizione metodi
}
170
Dichiarare un oggetto
• Sintatticamente la dichiarazione di un oggetto è
del tutto analoga alla dichiarazione di una
variabile di tipo primitivo
• Esempio:
– Rational primoNumero;
essendo Rational una classe
• La variabile dichiarata di tipo classe è un indirizzo
ad un’area di memoria contenente l’oggetto vero e
proprio
171
Istanza di un oggetto
• L’operatore new crea un oggetto del tipo “indicato” dal metodo che
immediatamente segue
• Sintassi:
– riferimentoOggetto = new NomeClasse(lista_di_parametri);
essendo riferimentoOggetto una variabile di tipo NomeClasse
• L’esecuzione di una tale istruzione comporta:
– l’allocazione della memoria necessaria a contenere l’oggetto
– l’assegnazione a riferimentoOggetto dell’indirizzo di inizio dell’area di
memoria allocata
– l’inizializzazione delle variabili di istanza dell’oggetto dettate dalla lista di
parametri del metodo NomeClasse(lista_di_parametri)
172
Fondere le due fasi
Rational primoNumero;
primoNumero = new Rational(3,4);
è equivalente a
Rational primoNumero = new Rational(3,4);
173
Oggetti e metodi
• Un metodo può ritornare il riferimento ad
un oggetto del tipo dichiarato dal valore di
ritorno del metodo
– NomeClasse nomeMetodo(lista_input)
• Un metodo può avere un parametro formale
di tipo classe. Al momento dell’invocazione
di un tale metodo, il parametro è
inizializzato con la copia
– Rational mul(Rational number)
174
Tipi primitivi e tipo classe
• Un metodo non può cambiare il valore di una
variabile di un tipo primitivo passatagli come
argomento
• Un metodo può cambiare i valori delle variabili di
istanza dell’oggetto indirizzato dalla variabile tipo
classe che gli è passata come parametro
175
Il metodo main
• main è un metodo speciale dal quale le
applicazioni Java iniziano automaticamente
l’esecuzione
• Sintassi:
public static void main(String args)
• È buona norma non includere il metodo main
nella definizione di una classe il cui scopo è
esclusivamente quello di definire un tipo
– eccezione: per debugging
176
• Esempio:
class RationalTest

public static void main(String args)

/* corpo del metodo main */


177
I costruttori
• Un costruttore è un metodo speciale designato a
inizializzare le variabili di istanza
– nome uguale a quello della classe
• Viene richiamato automaticamente quando l’oggetto è
creato
– new NomeClasse(lista_di_parametri)
• Un costruttore con una lista di argomenti vuota è detto
costruttore di default
• Se nella classe non è presente un costruttore, Java crea
automaticamente un costruttore di default
178
Definizione dei Costruttori
• La dichiarazione di un costruttore non include un tipo di ritorno che è
comunque un indirizzo
– è un errore anteporre la parola chiave void
• Esempio:
class Rational

int num, den;
Rational(int n, int d)



...
num = n;
den = d;
179
Un esempio riassuntivo
class Rational

int num, den; // variabili di istanza
Rational(int n, int d) // costruttore

num = n;
den = d;

Rational mul(Rational r) // operazione di moltiplicazione

return new Rational(num*r.num,den*r.den);

// altre operazioni aritmetiche
boolean isBigger(Rational r) // confronto se maggiore

return (num * r.den > den * r.num);

// altre operazioni di confronto
}
180
class RationalTest

public static void main(String args)

Rational firstNum = new Rational(3,5);
Rational secondNum = new Rational(2,3);
boolean isBiggerResult;
isBiggerResult = firstNum.isBigger(secondNum);
System.out.println (“Primo>secondo:“+isBiggerResult);


181
Firma (signature) di un metodo
• La firma di un metodo è data dal nome del metodo e dal numero, tipo
e ordine dei suoi parametri
– Esempio di firme diverse:
• int
int
• int
int
• int
int
myMethod(int i) è diverso da
yourMethod(int i)
myMethod(int i) è diverso da
myMethod(int i, double j)
myMethod(int i, double j) è diverso da
myMethod(double j, int i)
• Il valore di ritorno di un metodo non fa parte della firma del metodo
stesso
– Esempio di firme uguali:
• int myMethod(int i) ha la stessa firma di
double myMethod(int j)
182
Sovraccaricamento
• Lo stesso nome di un metodo ha più di una
definizione all’interno della stessa classe
• I metodi sovraccarichi hanno lo stesso nome
ma firme diverse tra loro
– I costruttori sono spesso sovraccaricati
183
Esempio
class MethodOverload

int square(int x)

return x*x;

double square(double y)

return y*y;

int square(double x)

return x*x;

sovraccaricamento
errore segnalato
dal compilatore
…………

184
Sovraccaricamento e conversione
• Se non si ha la corrispondenza con una
qualche firma, Java effettua conversioni di
tipo automatiche per trovare un’eventuale
corrispondenza
– una versione indesiderata del metodo può
essere eseguita
185
INCAPSULAMENTO
• Le variabili contenute in un oggetto dovrebbero essere
modificate solo dal suo interno, solo i metodi
dovrebbero essere gli unici responsabili del
cambiamento delle variabili.
• Un oggetto dovrebbe essere incapsulato rispetto a tutto
il resto del sistema e dovrebbe interagire con le altre
parti del programma solo attraverso un insieme
specifico di metodi che definiscono i servizi che
fornisce.
186
MODIFICATORI
• Un modificatore è una parola chiave di Java
usata per specificare delle caratteristiche
particolari di un costrutto del linguaggio.
• Alcuni modificatori sono chiamate
modificatori di visibilità perché controllano
fino a quale punto del programma è
possibile usare un membro della classe.
187
Il modificatore public
• Il modificatore public indica la totale assenza di
restrizioni di visibilità
• Le classi dichiarate public possono essere
referenziate ovunque
public class TwoDimensionalShape

…………

class shapeTest

TwoDimensionalShape myShape;
…………
}
188
• I campi ed i metodi dichiarati public sono accessibili ovunque
public class A

public int x;
public int getX()  return x; 

class B

public static void main(String[] args)
{
A a = new A();
a.x = 3;
System.out.println(a.getX());

}
189
Il modificatore private
• Le variabili e i metodi dichiarati private sono
accessibili soltanto dai metodi della classe in cui
sono definiti
190
Esempio
public class TwoDimensionalShape

private int width, height;
private int generate( int n )

return 1+(int)( Math.random*n );

public void setRandomWidth( int n )

width = generate( n );

public int getWidth( )
{
return width;
}
}
191
class shapeTest

public static void main( String[] args )
{
TwoDimensionalShape s = new TwoDimensionalShape();
s.width = s.generate( 100 ); ERRORE DOPPIO
s.setRandomWidth( 100 );
System.out.println( s.getWidth( ) );

}
192
Caratteristiche dell’OOP
Occultamento delle
informazioni
• protegge i dati all’interno
di un oggetto
– usa variabili di istanza
private
• non permette un loro
accesso diretto
– usa metodi public per
accedere alle variabili
Incapsulamento
• gli oggetti incapsulano
attributi e metodi
• nasconde i dettagli di una
definizione di classe
separando
– interfaccia (API)
– implementazione
193
La parola chiave static
• Una variabile definita static è detta variabile di
classe
• Essa rappresenta informazioni valide per l’intera
classe ed è condivisa da tutte le istanze della classe
• Esempio:
public class A

static int x;
………

194
• Un metodo definito static è detto metodo di classe
• Esso definisce un comportamento identico per tutte le
istanze della classe ossia indipendente dagli oggetti
• Esempio:
Math.random()
• E’ un errore di sintassi per un metodo static chiamare
un metodo di istanza o accedere ad una variabile di istanza
195
Accedere a membri static
•
•
I membri static di una classe esistono
indipendentemente dall’esistenza di una
istanza di tale classe
Due tipi di accesso


NomeClasse.nomeMetodo(lista_parametri)
NomeClasse.nomeVariabile
rifOggetto.nomeMetodo(lista_parametri)
rifOggetto.nomeVariabile
essendo rifOggetto un riferimento a un oggetto di tipo
NomeClasse
196
La parola chiave final
• La parola chiave final riferita a una variabile
indica che essa non può essere modificata
– Sintassi:
final tipo NOME = costante;
– Esempio
final double PI = 3.14159;
197
Librerie di classi
Una libreria di classi è un insieme di classi che aiuta
il programmatore nello sviluppo del software.
Un compilatore spesso viene distribuito con
una libreria di classi fondamentali.
Si possono ottenere separatamente
delle librerie commerciali.
Tecnicamente una libreria non fa parte della
definizione del linguaggio.
La libreria standard viene distribuita con qualsiasi
ambiente di sviluppo.
198
API e package
•Una libreria di classi è composta da gruppi di classi tra loro
collegate, spesso indicate collettivamente come API
(Application Programmer Interface). E’ possibile per
esempio riferirsi al Java Database API quando si parla
dell’insieme delle classi che permettono di interagire con
una base di dati.
• Le classi della libreria standard di Java sono raggruppate in
package che, come le API, permettono di indicare con un
unico nome delle classi tra loro collegate. Ad esempio la
classe String fa parte del package java.lang.
199
La clausola IMPORT
• Le classi del package java.lang sono automaticamente rese
disponobili durante la scrittura di un programma.
• Se si vogliono usare le classi appartenenti ad altri package,
occorre specificare il nome della classe insieme al nome del
package, oppure usare la clausola import.
• Es.: java.util.Random
import java.util.Random
import java.util.*
200
La classe String
• Una stringa è una sequenza di caratteri
• La classe String è utilizzata per memorizzare caratteri
• La classe String ha metodi che consentono di operare su
stringhe
• Costanti di tipo String: uno o più caratteri racchiusi tra
doppi apici
• Esempi:
char charVariable = `a`; // apici singoli
String stringVariable = “a”; // doppi apici
String sentence = “Hello, world”;
201
Variabili di tipo String
• Dichiarare una variabile di tipo String:
– String greeting;
• Assegnare un valore alla variabile:
– greeting = “Hello!”;
• Utilizzare la variabile come parametro di
tipo String nella chiamata di un metodo:
– System.out.println(greeting);
• stampa sullo schermo la stringa Hello!
202
Costruttori
• String(stringa):
– greeting = new String("Hello!");
• Alloca memoria per ogni stringa anche se il
parametro è lo stesso
– diverso da non usare il costruttore
String s = "Hello!";
String t = "Hello!";
String u = new String("Hello!");
String v = new String("Hello!");
System.out.println(s==t); // stampa true
System.out.println(u==v); // stampa false
203
Metodi
• length(): ritorna la lunghezza della stringa
– greeting.length() ritorna 6
• toLowerCase(): ritorna la stringa con tutti
caratteri minuscoli
– greeting.toLowerCase() ritorna hello!
• toUpperCase(): ritorna la stringa con tutti
caratteri maiuscoli
– greeting.toUpperCase() ritorna HELLO!
204
Indice di un carattere
• È un intero che, a partire da 0 per il primo
carattere, specifica la posizione del carattere
H e l
l
o !
all’interno della stringa
0

1
2
3
4
5
Metodo charAt(int p): ritorna il carattere nella
posizione specificata
» greeting.charAt(0) ritorna il carattere H mentre
greeting.charAt(2) ritorna il carattere l

Metodo substring(int s, int e): ritorna la
sotto-stringa dalla posizione s alla posizione e
(esclusa)
» greeting.substring(4,6) ritorna la stringa o!
205
Concatenazione di stringhe
• Operatore +:
String name = “I am Elisa”;
System.out.println(greeting+” “+name);
sullo schermo appare:
Hello! I am Elisa
• ricordarsi di includere gli spazi per una corretta
viualizzaziome
206
Sequenze escape
• Come stampare caratteri speciali?
– Esempio: The word is “hard”
• System.out.println(“The word is “hard””);
– Errore di compilazione: vede la stringa The word is ed è confuso da
quello che segue
• Usare il carattere backslash (ovvero, \) per indicare il
significato speciale dei doppi apici interni
– System.out.println(“The word is \“hard\””);
– la sequenza \” è detta essere una sequenza escape
207
Commenti
• Scrivere commenti comprensibili ed utili
• Non commentare ciò che è ovvio
• Assumere che il lettore ha una conoscenza
ragionevole
• Tipi di commenti:
– // per commenti di una singola linea
– /* … */ per commenti di più linee
– /** … */ per commenti che producano
documentazione HTML (appendice 10)
208
Array
• Nome unico per collezione di valori tutti dello stesso
tipo di dati
• Più di un tipo primitivo, meno di un oggetto
– metodi invocati con una notazione speciale
– comportamento simile ad oggetti se usati come argomenti o
come tipi di ritorno
– niente ereditarietà
– simili ad una classe Java non completamente implementata
• Adatti per cicli (in particolare, cicli for)
209
Creazione ed accesso
• Sintassi generale per la dichiarazione:
Tipo_Base[] Nome_Array = new Tipo_Base[Lunghezza];
• Esempi:
array di 80 caratteri:
char[] symbol = new char[80];
array di 100 reali:
double[] reading = new double[100];
array di 100 stringhe:
String[] message = new String[100];
210
Uso delle parantesi quadre
• Per creare un nome di tipo
– esempio: int[] intArrayName; crea un nome di tipo
"array di int"
• tipo int diverso da tipo array di int
• tipo del nome intArrayName, non tipo dei dati inclusi nell’array (che
comunque sono di tipo int)
• Per creare un nuovo array
– esempio: numArray = new int[100];
• Per accedere ad uno specifico elemento dell’array
– esempio:
System.out.println(numArray[3]);
211
Terminologia
Nome
temperature[n +
2]
temperature[n + 2]
Indice
- deve essere un int,
- oppure un’espressione che ritorna un int
Variabili indicizzata o elemento
temperature[n + 2]
Valore della variabile indicizzata o
elemento
temperature[n + 2] = 32;
212
Lunghezza di un array
• Specificata dal numero dentro le parentesi quadre al momento della
dichiarazione
– determina la quantità di memoria allocata per gli elementi dell’array
• memoria allocata anche se agli elementi non è stato assegnato alcun valore
– determina il massimo numero di elementi che l’array può contenere
• Ottenuta mediante la sintassi .length
String[] message = new String[20];
System.out.println(message.length);
• Determinata al momento della dichiarazione
– non può essere modificata a meno di ridichiarare l’array
213
Inizializzazione di array
• Gli elementi di un array possono essere inizializzati
nell’istruzione di dichiarazione mediante una lista di valori
(separati da virgole) all’interno di parentesi graffe
– elementi non inizializzati ricevono un valore di default (ad
esempio, ‘ ‘ per array di char)
– lunghezza di array determinata automaticamente se i valori sono
inizializzati esplicitamente nella dichiarazione
• Esempio:
double[] readings = {5.1, 3.02, 9.65};
System.out.println(readings.length);
- stampa 3, ovvero la lunghezza dell’array readings
214
Dominio di indicizzazione
• Indicizzazione di array usa numerazione a partire da
0
–
–
–
–
primo elemento: indice 0
secondo elemento: indice 1
n-esimo elemento: indice n-1
ultimo elemento: indice length-1
• Esempio:
int[] scores = {97, 86, 92, 71};
Indice: 0
Valore: 97
1
86
2
92
3
71
215
Errore di indice fuori del dominio
• Usare un indice più grande di length-1 causa un errore
in fase di esecuzione (non di compilazione)
– viene rigettata un'eccezione di tipo
ArrayOutOfBoundsException
• Altri linguaggi di programmazione (come C e C++) non
causano neanche un errore in fase di esecuzione
– una delle caratteristiche più "pericolose" di questi linguaggi è
proprio il fatto che consentono di usare indici fuori del dominio
216
Inizializzazione con ciclo
• Elaborazione di array facile da fare in un
ciclo
• Ciclo for spesso usato per inizializzare un
array
• Esempio:
int[] a = new int[10];
for(int i = 0; i < a.length; i++)
a[i] = 0;
217
Array, classi e metodi
Dato array di oggetti, i metodi della classe
corrispondente possono essere usati sui singoli
elementi
dichiara array di Rational
ogni elemento è una
istanza di Rational
Rational[] numbers = new Rational[4];
numbers[0] = new Rational(3, 4);
numbers[1] = new Rational(1, 4);
numbers[2] = new Rational(4, 5);
numbers[3] = new Rational(1, 5);
Rational tot = numbers[0];
for (int i = 1; i < numbers.length; i++)
{
tot = numbers[i].add(tot);
}
System.out.println(tot.num+”/”+tot.den);
usa il metodo add della
classe Rational
218
Array, elementi ed argomenti
• Array ed elementi possono essere usati
come argomenti di un metodo e come tipi di
ritorno
– sia un elemento che un nome di array possono
essere un argomento di un metodo
– i metodi possono ritornare un valore di un array
oppure un nome di array (incluse le parentesi
quadre)
219
Esempio
nome di array come tipo di ritorno
un elemento di a è un argomento
del metodo add
il nome v è un argomento del
metodo computeSum
static Rational[] createArray()
{
Rational[] numbers = new Rational[4];
numbers[0] = new Rational(3, 4);
numbers[1] = new Rational(1, 4);
numbers[2] = new Rational(4, 5);
numbers[3] = new Rational(1, 5);
return numbers;
}
static Rational computeSum(Rational[] a)
{
Rational tot = a[0];
for (int i = 1; i < a.length; i++)
tot = tot.add(a[i]);
return tot;
}
public static void main(String[] a)
{
Rational[] v = createArray();
Rational r = computeSum(v);
System.out.println(r.num+”/”+r.den);
}
220
Nomi di array come argomenti
• Quando si usa un intero array come argomento di
un metodo:
– si indica solo il nome dell'array senza le parentesi
quadre
– il metodo ha accesso all'array originale e può
modificare i valori dei suoi elementi
– la lunghezza dell'array passato come argomento può
essere diversa ad ogni invocazione
• quando si definisce il metodo non si sa la lunghezza dell'array
che verrà passato
– utilizzare length all'interno del metodo per evitare una
eccezione di tipo ArrayIndexOutOfBoundsException
221
Esempio
l'argomento del metodo è il nome
di un array di razionali
Rational computeSum(Rational[]
a)
{
if (a.length==0)
return null;
Rational tot = a[0];
for (int i=1; i<a.length;
i++)
tot = tot.add(a[i]);
return tot;
}
usa length per evitare eccezioni
dovute ad indice fuori del dominio
usa length per controllare il
ciclo
222
Array ed operatore =
int[] a = new int[3];
int[] b = new int[3];
for(int i; i < a.length; i++)
a[i] = i;
Non crea una copia dell'array a ma
trasforma b in un altro nome per l'array a
b = a;
System.out.println(a[2] + " " + b[2]);
a[2] = 10;
System.out.println(a[2] + " " + b[2]);
Output:
2 2
10 10
Un valore cambiato in a
è lo stesso valore ottenuto con b
223
Array ed operatore ==
int i;
a e b sono entrambi array
int[] a = new int[3];
di 3 elementi di tipo int
int[] b = new int[3];
a tutti gli elementi di a e b
for(i=0;i<a.length;i++)
viene assegnato il valore 0
a[i] = 0;
for(i=0;i<b.length;i++)
verifica se gli indirizzi di a e b sono uguali,
b[i] = 0;
non se i valori degli array sono uguali
if(b == a)
System.out.println("a equals b");
else
System.out.println("a does not equal b");
L'output di questo codice sarà a does not equal b
perché gli indirizzi dei due array non sono uguali
224
Uguaglianza tra array
• Per verificare se due
array sono uguali
bisogna definire un
metodo equals che
ritorna il valore
true se e solo se gli
array hanno la stessa
lunghezza e tutti gli
elementi
corrispondenti sono
uguali
public boolean equals(int[] a, int[] b)
{
boolean match;
if (a.length != b.length)
match = false;
else
{
match = true;
int i = 0;
while (match && (i<a.length))
{
if (a[i] != b[i])
match = false;
i++;
}
}
return match;
}
225
Metodi che ritornano un array
• Un altro esempio di passaggio per
riferimento
• In pratica, non viene restituito l'array, ma il
suo indirizzo
• Il nome della variabile a cui l'array viene
assegnato è semplicemente un altro nome
per l'array ritornato dal metodo
226
Buone regole di programmazione
• Usare nomi singolari piuttosto che plurali
migliora la leggibilità
– sebbene un array contenga molti elementi, l'uso
più frequente del suo nome sarà per indicizzare
un singolo elemento
• Non affidarsi ai valori iniziali di default per
gli elementi di un array
– inizializzare esplicitamente gli elementi nella
dichiarazione oppure in un ciclo
227
Ricerca in un array
• Esistono molte tecniche per cercare un particolare
valore all'interno di un array
• Ricerca sequenziale:
– partire dall'inizio dell'array e procedere in sequenza finché
il valore viene trovato oppure la fine dell'array viene
raggiunta
• oppure, partire dalla fine dell'array e procedere a ritroso finché il
valore viene trovato oppure l'inizio dell'array viene raggiunto
– non è il modo più efficiente, ma funziona ed è facile da
programmare
228
Esempio
public boolean inArray(int[] a, int x)
{
boolean found = false;
int i = 0;
while ((! found) && (i<a.length))
{
if (x==a[i]) found = true;
else i++;
}
return found;
}
229
Ordinare un array
• Ordinare un elenco di elementi è un compito
molto frequente
– ordinare numeri in modo crescente
– ordinare numeri in modo decrescente
– ordinare stringhe in modo alfabetico
• Vi sono molti modi per ordinare un elenco
• Selection sort
– uno dei più facili
– non il più efficiente, ma facile da capire e da
programmare
230
Algoritmo Selection Sort
• Per ordinare un array di interi in modo crescente:
– cerca nell'array il numero più piccolo e scambialo con il
primo elemento dell'array
• la parte ordinata dell'array è ora il primo elemento, mentre
quella non ancora ordinata sono i rimanenti elementi
– cerca nella parte non ordinata il numero più piccolo e
scambialo con il secondo elemento dell'array
– ripeti la ricerca e lo scambio fino a quando tutti gli
elementi sono al posto giusto
• ogni iterazione aumenta di 1 la lunghezza della parte ordinata e
diminuisce di 1 quella della parte non ordinata
231
Il codice
public void selectionSort(int[] a)
{
int i, j, indexOfNextSmallest, min, temp;
for (i = 0; i < a.length - 1; i++)
{
min = a[i];
indexOfNextSmallest = i;
for (j = i+1; j < a.length; j++)
if (a[j] < min)
{
min = a[j];
indexOfNextSmallest = j;
}
temp = a[i];
a[i] = a[indexOfNextSmallest];
a[indexOfNextSmallest] = temp;
}
}
232
Esempio
a[0]
7
a[1]
6
a[2]
11
a[3]
17
a[4]
3
a[5]
15
a[6]
5
a[7]
19
a[8]
30
a[9]
14
7
6
11
17
3
15
5
19
30
14
3
6
11
17
7
15
5
19
30
14
3
6
11
17
7
15
5
19
30
14
3
5
11
17
7
15
6
19
3
5
11
17
7
15
6
19
30
14
3
5
6
17
7
15
11
19
30
14
30
14
233
Il metodo main
• Il parametro formale di un metodo main è
sempre un array di oggetti di tipo String.
• La macchina virtuale java invoca il metodo
main nell’applicazione che viene passata
all’interprete
• Il parametro di tipo array di stringhe, che
solitamente viene chiamato args, rappresenta
l’insieme di argomenti passati tramite la linea di
comando all’interprete Java quando viene
234
invocato.
• Qualsiasi informazione passata dalla linea di
comando viene memorizzata nell’array args
per poter essere successivamente usata dal
programma.
• Il parametro del metodo main è sempre un
array di oggetti di tipo String, per cui se si ha
bisogno di passare dalla riga di comando
informazioni in altro formato, ad esempio
numerico, il programma dovrà convertirle in
formato stringa.
235
Complessità computazionale
Per risolvere un problema spesso sono
disponibili molti algoritmi diversi .
Come scegliere il migliore?
In genere si valuta la bontà di un algoritmo o
si confrontano più algoritmi sulla base del
comportamento che questi presentano al
crescere della dimensione del problema.
236
Si vuole caratterizzare tale dimensione mediante
un intero n che è precisamente identificato nella
macchina di Turing come la lunghezza della
porzione di nastro che contiene i dati di ingresso.
Impiegando un elaboratore ed un suo linguaggio
di programmazione, la dimensione n è lo spazio
occupato, nella memoria dell’elaboratore, dei
dati relativi al problema da risolvere, o più in
generale un numero proporzionale a questo
spazio.
237
Esempi:
• se si opera su un insieme, n sarà il numero dei
suoi elementi
• se si opera su un grafo, n sarà il numero dei
nodi o il numero di archi o la somma dei due
numeri
• se si opera su matrici n sarà il numero dei suoi
elementi
238
Complessità in tempo e complessità asintotica
Fissata la dimensione n, il tempo che un
algoritmo impiega a risolvere il problema si
chiama complessità in tempo: nostro obiettivo
principale sarà esprimere la complessità in tempo
come funzione di n e spesso ci limiteremo a
studiare il comportamento di tale funzione al
crescere di n (complessità asintotica o
semplicemente complessità) considerando così i
soli termini prevalenti per n e tralasciando a
volte anche le costanti moltiplicative.
239
Perché si studia la complessità asintotica
Lo studio della complessità asintotica è
motivato dal fatto che gli algoritmi sono
sempre definiti per n generico: se per valori
piccoli di n due algoritmi possono avere
efficienza confrontabile, è sempre quello che ha
il termine massimo di grado più basso a
richiedere minor tempo di esecuzione per un
numero illimitato di valori di n superiori ad un
opportuno valore n0 .
240
ATTENZIONE!!!
Non saremo mai in grado di valutare il tempo
effettivamente impiegato da un algoritmo, si
dovrebbe mettere in bilancio il tempo di
esecuzione delle singole frasi su uno specifico
elaboratore.
241
Quello che faremo
Ci limiteremo a contare le operazioni
eseguite o alcune operazioni chiave o
preminenti ammettendo che il tempo
complessivo di esecuzione sia proporzionale
al numero di tali operazioni.
Tratteremo spesso come non significative le
costanti moltiplicative e studieremo le
funzioni di complessità nel loro ordine di
grandezza.
242
Complessità in spazio
La complessità in spazio è il massimo spazio
invaso dalla memoria durante l’esecuzione
dell’algoritmo, il quale può costruire insiemi di
dati intermedi o di servizio, oltre ad operare sui
dati iniziali e finali.
Anche in questo caso ci si limita in genere allo
studio della complessità asintotica.
Poiché abbiamo a disposizione memorie
grandissime a basso costo, studieremo la
complessità in tempo.
243
Complessità e configurazioni
La complessità di un algoritmo non può
sempre essere caratterizzata da una sola
funzione di complessità. A parità di
dimensione di dati, il tempo di esecuzione
può
dipendere
dalla
specifica
configurazione dei dati. Si considerano di
solito tre differenti tipi di complessità:
complessità nel caso medio, ottimo e
pessimo.
244
Complessità media
• Valore della complessità di un algoritmo,
mediato su tutte le possibili occorrenze
iniziali dei dati.
• Si usa spesso la probabilità.
• Il calcolo è spesso difficile.
245
Complessità nel caso ottimo
Si ottiene considerando, a parità di dimensione
dei dati, la configurazione che dà luogo alminimo
tempo di esecuzione.
Tale complessità è perlopiù di interesse
secondario anche se è abbastanza facile da
determinare.
246
Complessità nel caso pessimo
• Si intende la complessità relativa a quella
particolare occorrenza iniziale dei dati per cui
l’algoritmo ha comportamento pessimo.
• Tale funzione di complessità fornisce un
limite superiore alla complessità, entro cui il
funzionamento dell’algoritmo è sempre
garantito.
247
Crescita asintotica della complessità
Le funzioni considerate rappresentano
tempi di elaborazione e spazi di memoria e
sono intrinsecamente non negative ( ed in
genere crescenti con la dimensione dei dati
n che è un intero non negativo). In genere
ci interesseremo al limite della funzione
complessità quando n∞ (studio della
complessità in ORDINE DI GRANDEZZA).
248
Notazioni
O(f(n)) è l’insieme di tutte le
funzioni g(n) tali che esistono due
costanti positive c e n per cui
g(n)<=cf(n) per ogni n>= n
0
0
g(n)O(f(n)) tradizionalmente si legge
“g(n) è di ordine f(n)” e fornisce un
limite superiore al comportamento
asintotico della funzione.
249
Ω(f(n)) è l’insieme di tutte le funzioni
g(n) tali che esistono due costanti
positive c e n per cui g(n)>=cf(n) per
ogni n>= n .
0
0
g(n)Ω(f(n)) tradizionalmente si legge
“g(n) è di ordine Ω f(n)” e fornisce un
limite
inferiore
al
comportamento
asintotico della funzione.
250
(f(n)) è l’insieme di tutte le funzioni
g(n) che sono sia Ω f(n) sia Of(n).
g(n)(f(n)) tradizionalmente si legge
“g(n) è di ordine  f(n)”; la g si comporta
asintoticamente esattamente come la f, per
cui l’andamento di f caratterizza
precisamente quello di g.
251
Applicata alla funzione di complessità, la
notazione O ne delimita superiormente la
crescita e fornisce un indicatore di bontà
dell’algoritmo.
La notazione Ω limita inferiormente la
complessità, indicando così che il
comportamento dell’algoritmo non è
migliore di un comportamento assegnato.
252
Esempi:
• la funzione h(n)=3n2 +3n-1 è di ordine
n2 perché esistono le costanti c=4 e n0=3
per cui h(n)<4n2 per n>=3.
•Notiamo che qualsiasi polinomio di
grado k è di ordine nk e,in accordo con
la definizione, è anche di ordine nj con
j>k.
253
• g(n)=3n2+2n+1 è O(n2) e anche O(n3)
ma è anche di ordine (4n2), (n2),
(n); Infine è di ordine (n2), (4n2), ma
non di ordine (n) e neppure di ordine
(n3)
254
Proprietà di O,  e 
• g  O(f) implica (f+g)  O(f)
• f1O(g1), f2O(g2) implica f1+ f2O(g1+g2)
• O e  sono relazioni riflessive e transitive
•  è una relazione di equivalenza
• fO(g) se e solo se g  (f)
255
Possiamo dividere ora gli algoritmi in
classi, ponendo nella stessa classe quelli
che hanno complessità asintotica dello
stesso ordine di grandezza O.
256
Classi principali
• funzioni di ordine costante
• di ordine inferiori ad n, o sottolineari
• di ordine nlogn (la base del logaritmo è
inessenziale perché logaritmi in basi diverse
differiscono per una costante moltiplicativa:
logay=logab x logby)
• di ordine n2,n3 ecc., o in genere polinomiali
• di ordine kn,nn..o in genere esponenziali
257
Un esempio:Ordinare un array
• Ordinare un elenco di elementi è un compito molto
frequente
– ordinare numeri in modo crescente
– ordinare numeri in modo decrescente
– ordinare stringhe in modo alfabetico
• Vi sono molti modi per ordinare un elenco Selection
sort
– uno dei più facili
– non il più efficiente, ma facile da capire e da programmare
258
Algoritmo Selection Sort
• Per ordinare un array di interi in modo crescente:
– cerca nell'array il numero più piccolo e scambialo con il
primo elemento dell'array
• la parte ordinata dell'array è ora il primo elemento, mentre
quella non ancora ordinata sono i rimanenti elementi
– cerca nella parte non ordinata il numero più piccolo e
scambialo con il secondo elemento dell'array
– ripeti la ricerca e lo scambio fino a quando tutti gli elementi
sono al posto giusto
• ogni iterazione aumenta di 1 la lunghezza della parte
ordinata e diminuisce di 1 quella della parte non ordinata
259
Il codice
public void selectionSort(int[] a)
{
int i, j, indexOfNextSmallest, min, temp;
for (i = 0; i < a.length - 1; i++)
{
min = a[i];
indexOfNextSmallest = i;
for (j = i+1; j < a.length; j++)
if (a[j] < min)
{
min = a[j];
indexOfNextSmallest = j;
}
temp = a[i];
a[i] = a[indexOfNextSmallest];
a[indexOfNextSmallest] = temp;
}
}
260
Esempio
a[0]
7
a[1]
6
a[2]
11
a[3]
17
a[4]
3
a[5]
15
a[6]
5
a[7]
19
a[8]
30
a[9]
14
7
6
11
17
3
15
5
19
30
14
3
6
11
17
7
15
5
19
30
14
3
6
11
17
7
15
5
19
30
14
3
5
11
17
7
15
6
19
3
5
11
17
7
15
6
19
30
14
3
5
6
17
7
15
11
19
30
14
30
14
261
Complessità del Selection sort
L’ordinamento per selezione ha un ciclo più
esterno e uno più interno con proprietà simili,
sebbene con scopi differenti. Il ciclo più
esterno viene eseguito una volta per ogni
valore nella lista e quello più interno
confronta il valore scelto dal ciclo più esterno
con molti, se non tutti, i valori rimanenti
nella lista. Quindi esegue n2 confronti ove n è
il valore di elementi della lista. Selection sort
è quindi di ordine n2.
262
Programmi ricorsivi
Secondo lo stile ricorsivo un programma
risolve un problema facendo ricorso a chiamate
dello stesso programma che risolvono un
problema sui dati originali opportunatamente
ridotti. I risultati ottenuti con le singole
chiamate vengono poi combinati per ottenere il
risultato finale.
263
E’ responsabilità di chi formula l’algoritmo
porvi in posizione opportuna la clausola di
chiusura per assicurarsi che le chiamate
successive della procedura abbiano termine.
E’ responsabilità del sistema di elaborazione
organizzare i calcoli richiesti dalla procedura
che devono essere eseguiti aggregando man
mano dati elementari.
264
Ogni parametro di una procedura ricorsiva
può assumere allo stesso tempo valori
indipendenti. Il valore impiegato in
un’esecuzione muore con il completamento
di questa ed è sostituito dal valore relativo
all’ultima esecuzione lasciato in sospeso.
Tali assegnazioni come i problemi lasciati in
sospeso sono i problemi dell’elaboratore.
265
Il programmatore formula l’algoritmo dal
generale al particolare descrivendo la funzione
sulla globalità dei dati in termini della funzione
stessa sui dati disgregati.
L’algoritmo viene poi eseguito dal particolare
al generale. Vengono infatti lasciate in sospeso
le operazioni globali e il calcolo vero e proprio
inizia dai dati atomici.
266
Possiamo pensare alle operazioni effettuate
prima e dopo le chiamate ricorsive come ad un
LAVORO DI COMBINAZIONE dei risultati
parziali in cui si fa confluire l’eventuale lavoro
di preparazione dei dati per le chiamate ricorsive
stesse.
267
RELAZIONI DI RICORRENZA
Quando un algoritmo è scritto in maniera
ricorsiva può risultare relativamente facile
caratterizzare in modo compatto e semplice le
funzioni di complessità. Le relazioni di
ricorrenza nascono infatti quando un elemento
generico di una sequenza può essere espresso
in funzione dei termini precedenti.
Si usa classificare le più importanti relazioni di
ricorrenza anche in base alla forma del lavoro
di combinazione.
268
Fibonacci
Una delle prime relazioni di ricorrenza fu posta da
Fibonacci .
Problema dei conigli:
Al tempo 1, origine dei tempi, c’è una coppiua di
conigli neonati. Al tempo successivo la coppia
diventata adulta, inizia il processo di
riproduzione: ogni coppia genera una nuova
coppia ogni mese, ma ogni nuova coppia non è in
grado di procreare durante il primo mese.
Quante coppie vi sono al mese n?
Il numero cercato è l’n-esimo numero di
269
Fibonacci.
F1=1 al mese 1 c’è solo una coppia
F2=1 al mese 2 ancora la prima coppia non può procreare
Condizioni
iniziali
F3=2 la prima coppia procrea una seconda
•
•
Fn=Fn-1+Fn-2
Relazione di ricorrenza
al mese n vi sono le coppie del mese precedente, Fn-1, più quelle generate
nell’ultimo mese che sono quelle esistenti nel mese ancora precedente, Fn-2.
270
Cerchiamo di esprimere Fn in funzione di n,
cercando quindi una soluzione per la
relazione di ricorrenza.
La legge generale conterrà delle costanti da
determinare imponendo delle condizioni
iniziali.
Ipotizziamo che ci sia una soluzione del tipo
Fn=czn
dove c e z sono costanti.
271
Sostituiamo in Fn=Fn-1+Fn-2 la soluzione
ipotizzata.
cz  cz
n 1
 cz
n2
cz  cz
n 1
 cz
n2
n
n
0
n 1
cz
cz
cz ( n  2  n 2  1)  0
cz
cz
n 2
n  n 2
n 1n  2
cz (z
z
 1)  0
n
n 2
cz
n 2
(z  z  1)  0
2
272
Possiamo quindi affermare che czn è una
soluzione della relazione di ricorrenza in uno
dei seguenti tre casi:
c0
banale, si avrebbe Fn  0
z0
1 5
z  z 1  0  z1,2 
2
2
273
Quindi Fn ammette le due soluzioni
Fn=c1z1n
Fn=c2z2n
Purtroppo non generano tutti i numeri di
Fibonacci al variare di n dato che nessuna
delle due è in grado di soddisfare le due
condizioni iniziali.
In virtù della linearità di Fn=Fn-1+Fn-2 una
combinazione lineare delle due soluzioni è
ancora una soluzione della relazione.
In particolare consideriamo:
Fn= c1z1n +c2z2n
274
Imponendo le condizioni iniziali:
1
1
c1 (1  5)  c2 (1_ 5)  1
2
2
1
1
2
c1 (1  5)  c2 (1_ 5)2  1
4
4
Si ottiene dopo facili calcoli :
1
c1 
5
1
c2  
5
275
Si ottiene quindi:
1 1  5 
1 1  5 
Fn 

 


5  2 
5  2 
n
n
E' prevalente dato
che z >1 mentre z 1
1
2
detta formula di Binet
276
Si ha quindi :
1 1  5 1 1  5
F1 



 
5  2  5  2 
1

1  5  1  5  1
2 5
2
2
1 1  5
1 1  5
F2 

 

 
5  2 
5  2 
1

1  5  2 5  1  5  2 5  1
4 5
277
RELAZIONI DI RICORRENZA CON LAVORO di
COMBINAZIONE COSTANTE E COEFFICIENTI
COSTANTI
Quelle relazioni in cui il lavoro di combinazione é
indipendente dalla dimensione dei dati :
a) Relazioni lineari di ordine hcioé del tipo
C(1)  c1
C(h)  ch
C(n) = a1C(n  1)   ahC(n  h)  b
con n intero, n  h, h  1 e almeno 2 degli ai  1278
b)Relazioni lineari di ordine h
( con a h = 1 e a j = 0 j con 1  j  h - 1)
C(1)  c1
C(h)  ch
C(n) = C(n  h)  b
c) Relazioni con partizioni di dati
C(1)  c
 
C(n) = aC n p  b
con n  p e m intero, n  1
m
279
RELAZIONI DI RICORRENZA CON LAVORO di
COMBINAZIONE LINEARE E COEFFICIENTI
COSTANTI
Quelle relazioni in cui il lavoro di combinazione é
dipendente dalla dimensione dei dati :
d) Relazioni lineari di ordine h
C(1)  c1
C(h)  ch
C(n) = C(n  h)  bn + d
con n intero, n  h, h  1
280
e) Relazioni con partizioni di dati
C(1)  d
 
C(n) = aC n b  c1n  c2
k
con n  b e k intero, n  1
281
a)
b)
c)
Soluzioni
C(n) O(k )
C(n) O(n)
C(n) O(log n) se a = 1
n
C(n) O(n
d)
e)
log a
p
) se a  1
C(n) O(n )
C(n) O(n) se a  p
C(n) O(nlog n) se a  p
2
C(n) O(nn
log a
p
) se a  p
282
Esempio: PRIMSEC algoritmo ricorsivo che
determina il primo e il secondo elemento di un
insieme secondo un ordine assegnato.
Sia A un vettore di n elementi distinti con un
ordine prefissato.
Si divide in due metà il vettore e si applica
ricorsivamente l’algoritmo fino a che non si
arriva a due coppie alle quali si applica il
confronto.
283
Sotto l’ipotesi che n=2h i due insiemi iniziali si
dividovo esattamente in due ad ogni passo
finché dopo h-1 suddivisioni si ottengono
insiemi elementari di due elementi.
Valutiamo il numero di confronti eseguiti per
calcolare la funzione di complessità.
Avremo che:
C(n)=1 per n=2
C(n)=2C(n/2)+2 per n>2
Questo modo di impostare l’algoritmo si chiama
DIVIDE ET IMPERA (prossima lezione)
284
Non abbiamo il numero esatto dei confronti
ma abbiamo l’ordine di grandezza della
nostra funzione di complessità che essendo
nel caso c) con a>1 risulta essere
C(n) O(n
log 2
2
) = O(n)
285
Soluzione di c) per sostituzioni successive
 
 n  
n
C(n)  aC p  b  a aC 2   b  b 
  p  
  n   
 aa aC p 3  b  b b 
  
  
   n  
 aa  aC p m   b 
 
   
 a m c  ba m1  a m 2 
 
 b  b 
 
 1
286
Quindi abbiamo
C(n)  a c  ba
m
m1
a
m 2

 1
Se a  1
C(n) = c + b(1+
+ 1)
m volte
Dato che n  p si ha che logp n = m per cui
m
C(n) = c + blogp n O(log n)
287
Osservazione :
Se n  p  n1 e n2 t.c. n1  n  n2 e n1  p e n2  p
m
m
m 1
Dato che C(n) é crescente in n si ha che
C(n) O(logp n2 ).
Ma n2  n1  p da cui
logp n2  logp pn1  logp pn  1  logp n
Quindi C(n) O(log p n  1)
288
Se a > 1
Partiamo sempre da C(n)  a c  ba
m
m 1
a
m 2
 1

a 1
Osserviamo che i= 0a 
a 1
Dato che m  logp n  logp a  loga n si ha che
m-1
m
i
m

a  1
m
C(n) = a c  b
 
 a  1 
log alog n 
b  b
p
a
a
c 


 a  1 a  1
log p a 
log p a
b  b
n
c 

O n
 a  1 a  1
 
289
Osservazione :
Se n  p  n1 e n2 t.c. n1  n  n2 e n1  p e n2  p
m
m
m 1
Dato che C(n) é crescente con n si ha che :
C(n1 )  C(n)  C(n2 )
log a
per cui C(n) < n2
p
con n2  n1  p
log a
Di conseguenza C(n) < n2
p
 (n1 p)
log p a
 n1
log p a
an
log p a
290
a
Abbiamo quindi dimostrato che n
Se a  1 C(n) O(log n 1)
p
Se a  1 C(n) O(n
log a
p
1) dove :
Se a<p la funzione di complessità è
SOTTOLINEARE.
Ciò avviene per quei problemi ove è possibile
scartare (ricorsivamente ad ogni passo) alcuni
dati sui quali non si dovrà mai operare. Es: se
a=2 e b=3 sarà sufficiente considerare solo 2
sottoinsiemi contenenti ciascuno un terzo dei dati
e non considerare mai il rimanente terzo. Ciò
vuol dire ridurre i dati ad ogni chiamata
291
Se a=p la funzione di complessità è LINEARE.
Ed infine se a>p la funzione è SOPRALINEARE
anche se non cresce in genere come un
polinomio di grado elevato a causa della
funzione logaritmica che appare all’esponente.
Ciò avviene quando si deve operare più volte
sugli stessi dati. Es: se a=3 e b=2 si avrà bisogno
di tre chiamate su sottoinsiemi di n/2 dati e cioè
sovrapposizione.
292
Algoritmi di ordinamento
Problema: Sia A un array di n elementi tra i quali é definita
una relazione di ordine totale <. Si vuole permutare tali
elementi in maniera tale che risulti :
A[1]< A[2]<……< A[n]
Dove con A[i] indichiamo il valore dell’ennesimo elemento
dell’array.A.
293
QUICKSORT
Algoritmo:
• si sceglie a caso un elemento detto perno A[h].
• si confronta con A[h] tutti gli altri elementi di A e si
costruiscono due insiemi A1 e A2 tali che:
A1={x/xA e x< A[h]}
A2={x/xA e x> A[h]}
• si trasferiscono gli elementi di A1 all’inizio dell’array, seguiti dal
perno, seguiti dagli elementi di A2.
•Si ripete ricorsivamente quicksort.
294
Esempio:
A[1]=30 A[2]=40 A[3]=25 A[4]=50 A[5]=15 A[6]=45 A[7]=38
A[8]=5 A[9]=10 A[10]=35.
• Se la distribuzione iniziale è casuale posso scegliere come perno
anche A[1].
• Si scorrerà l’array A dal secondo elemento con due cursori p e q:
p punterà inizialmente ad A[2] e si sposterà verso destra; q punterà
ad A[n] ( nell’esempio A[10]) e si sposterà verso sinistra.
• Il movimento dei cursori si arresta non appena:
A[1]<A[p] e A[1]> A[q]
• A questo punto si scambiano di posto A[p] e A[q] e si riprende il
moto dei cursori, iterando il procedimento finché i cursori si
incontrano in posizione intermedia.
295
• Si scambia allora di posto A[1] con l’elemento minore più a
destra ottenendo così una permutazione di A in cui si trovano
all’inizio gli elementi minori del perno, quindi il perno e infine
tutti gli elementi maggiori del perno.
• I sottoinsiemi:
A1={15, 10, 25, 5}
A2={45,38,50,40,35}
Saranno trattati ricorsivamente nello stesso modo.
296
Evoluzione dell’array A durante le partizioni intorno al perno
30
40
25
50
POSIZIONI
5
6
15
45
30
10
25
50
15
45
38
5
40
35
30
10
25
5
15
45
38
50
40
35
15
10
25
5
30
45
38
50
40
35
1
2
3
4
7
8
9
10
38
5
10
35
I colori giallo e verde indicano rispettivamente i cursori p e q
297
Codice per Quicksort
public static void quicksort(int[] A)
{ quicksort (A,0,A.lenght-1);}
public static void quicksort(int[] A, int i, int j)
{
if (i >=j)return;
int p= perno(A,i,j);
if (i <(p-1)) quicksort(A,i,p-1);
if ((p+1)<j) quicksort(A,p+1,j);
}
public static int perno(int[] A, int i, int j)
{
int p=i+1;
int q=j;
298
while ((p<q) && (p<=j))
{
while ((p<=j) && (A[i]>=A[p])) p++;
while (A[i]<A[q]) q--;
if (p<q)
{
int temp;
temp=A[p];
A[p]=A[q];
A[q]=temp;
p++;
q--;
}
}
int temp;
temp=A[i];
A[i]=A[q];
A[q]=temp;
return q;
}
299
L’algoritmo, scritto qui con sintassi java, ha un metodo
perno non ricorsivo. E’ chiamato su un array di interi A
partiziona le parti comprese tra i e j attorno al perno
generico A[i]. I due cursori sono p e q e partono appunto
dalle posizioni i+1 e j (nell’esempio A[2] e A[10]).
Il metodo perno restituisce la posizione del perno. Il
metodo quicksort(A,i,j) richiama perno
ricorsivamente provocando l’ordinamento dell’array tra i e j.
Il metodo quicksort(A) provoca l’ordinamento
dell’intero array.
300
Relazione di ricorrenza per il Quicksort
C(n)  0 n  0,1
C(n)  P(n)  C(q 1)  C(n  q)

Complessità
di perno

Complessità
su A1

Complessità
su A2
q indica la posizione del perno
301
Analizzando il metodo perno ci accorgiamo che il ciclo
esterno si ferma quando p>q cioè p=q+1 cioè
quando A[p] è l’elemento più a sinistra maggiore del perno
e A[q] è l’elemento più a destra minore del perno. Ciò
significa che tutti gli elementi (n-1 elementi se non contiamo il
perno) vengono confrontati 1 volta sola con il perno tranne
A[p] e A[q] che sono in genere confrontati 2 volte con li
perno. Abbiamo quindi:
P(n)  (n  3)  4  n 1
quindi la relazione diventa :
C(n)  0 n  0,1
C(n)  n  1  C(q 1)  C(n  q)
302
Caso medio per Quicksort
Dato che il valore j prodotto dal metodo perno può essere con
la stessa probabilità 1/n in ciascuna posizione tra 1 e n
abbiamo per il caso medio:
CM (n)  0
n  0,1
1 n
CM (n)  n  1   (CM ( j  1)  CM (n  j))
n j 1
303
Tale relazione dopo una serie di calcoli che saranno svolti a
lezione e che potete trovare nel libro “Algoritmi e strutture
dati” di Fabrizio Luccio diventa la seguente funzione esplicita
in n :
1
CM (n)  2(n 1)   2(n  1)(log(n 1)  log2)
k 3 k
Quindi CM (n) O(nlogn)
n1
L’algoritmo quindi stabilisce una relazione di ordinamento tra
moltissime coppie senza confrontarle direttamente ma inferendo
tale relazione da confronti fatti con altri elementi.
Infatti se si eseguissero tutti i possibili confronti tra coppie di
elementi si avrebbe CM(n)=n(n-1)/2 cioè quante sono le coppie
distinte di n elementi,
304
Il comportamento medio di tale algoritmo si avvantaggia del
fatto che le successive partizioni di dati sono mediamente
bilanciate. Supponiamo infatti che l’elemento perno abbia il
valore centrale di A. Il metodo perno mette il perno al centro e
costruisce i due insiemi A1 e A2 di dimensione metà
dell’insieme originale: il metodo corre perfettamente secondo
partizioni bilanciate dell’insieme. Si eseguono n+1 confronti
per tutte le chiamate di perno ad ogni livello di ricorrenza, ma
tali livelli sono meno quando le successive partizioni
dell’insieme sono perfettamente bilanciate! Ecco che nel caso
ottimo il perno ha il valore centrale e C(n) é dell’ordine
nlogn.
305
Caso pessimo Quicksort
In questo caso il perno è sull’elemento che risulta il minimo ( o il
massimo) degli elementi di A.
In questo caso si ha che A1 è vuoto mentre A2 contiene n-1 elementi.
Abbiamo quindi:
C(n)  n  1  C(n  1) 
 (n  1)  (n)  C(n  2) 
 (n  1)  (n)  (n  1)  C(n  3) 
 ......................... 
 (n  1)  n  (n  1)  (n  2)  ..  3 
n 1
(n  2)(n  1)
  j
 3 O(n 2 )
j 3
2
306
Nel caso pessimo quindi il numero dei confronti ha un numero assai
maggiore che nel caso medio, questo dipende dal completo
sbilanciamento della partizione di A, che obbliga essenzialmente ad
eseguire tutti i possibili confronti tra coppie di elementi.
Da osservare che Quicksort opera con massima inefficienza quando
l’insieme è già ordinato.
307
MERGESORT
Non abbiamo comunque individuato un metodo di ordinamento
che operi O(nlogn) confronti anche nel caso pessimo (il limite
inferiore al numero di confronti generato con l’albero di
decisione è O(nlogn) sia nel caso medio che nel caso pessimo);
la possibilità di raggiungere questo risultato appare legato alla
costruzione di un algoritmo che lavori su partizione dell’insieme
bilanciate in ogni caso: il Mergesort.
308
Il Mergesort , chiamato anche metodo di ordinamento per
fusione, si basa sull’idea di dividere l’insieme da ordinare A (o
meglio l’array nel nostro codice) di n elementi in due sottoinsiemi
di n/2 elementi ciascuno, ordinare poi ciascuna sequenza e
fondere insieme le due unità ordinate in un’unica sequenza. In
realtà nella versione ricorsiva qui presentata Mergesort si applica
all’intero array e ne costruisce l’ordinamento mediante la fusione
di due semi-insiemi ordinati ricorsivamente nello stesso modo.
Nel Mergesort le chiamate ricorsive si susseguono l’una dentro
l’altra finchè si raggiungono insiemi elementari di due elementi
su cui iniziare le vere e proprie operazioni di confronto e
ordinamento, con la fusione di due sottoinsiemi di un elemento
ciascuno (procedura Merge non ricorsiva). Da qui si passa via via
alla fusione di sottoinsiemi più grandi: le operazioni iniziano
sempre su dati elementari.
309
Codice per Mergesort
public static void mergesort(int[] A)
{ aus=new int[A.lenght]
mergesort(A,0,A.lenght-1);}
public static void mergesort(int[] A, int i, int j)
{
if (i >=j)return;
int m= (i+j)/2;
mergesort(A,i,m);
mergesort(A,m+1,j);
merge(A,i,j,m)
}
310
public static void merge(int[] A, int i, int j,int m)
{
int p=i;
int q=m+1;
int k=i;
while ((p<=m) && (q<=j))
{ if (A[p]<A[q]) {aus[k]=A[p]; p++; }
else {aus[k]=A[q]; q++; }
k++; }
if (p<=m)
{p=m;
for(int k1=j;k1>=k;k1--)
{A[k1]=A[p];p--;}}
for(int k1=i;k1<k;k1++)
{A[k1]=aus[k];
}
311
Studio della complessità per il Mergesort
C(1)  0
C(n)  2C( n 2 )  M(n)

Numero di confronti
richiesto dal Merge
M(n)  n nel caso pessimo
C(n) O(nlogn)
312
Mergesort è un algoritmo ottimo anche nel caso pessimo: il
motivo è ancora da ricercarsi nel fatto che la partizione operata da
Mergesort è sempre bilanciata!
313