1 Master in BIOINFORMATICA Corso propedeutico di Informatica DOCENTE: Elisa Tiezzi UNIVERSITA DI...

transcript

Master in BIOINFORMATICA

Corso propedeutico di InformaticaDOCENTE:

Elisa Tiezzi

UNIVERSITA’ DI SIENA

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

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

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

INFORMATICAAlla metà del 900 il MONDO dell’INFORMAZIONE diviene importante. INFORMATICA = insieme degli strumenti teorici e praticiche 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.

L’informatica ha quindi due significati:

• Insiste sull’oggetto = PROCEDURA EFFETTIVA O ALGORITMO

• Insiste sullo strumento = CALCOLATORE ELETTRONICO

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.

ALGORITMO

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

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

P 0 3 9 21

A 7 3 1 0

B 3 6 12 24

P 0 0 0 12 36

A 12 6 3 1 0

B 3 6 12 24 48

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

Proprietà degli algoritmi

• FINITI

• NON AMBIGUI

• GENERALI

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.

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.

Blocchi elementari

output

azione

Cverofalso

Esempio su ax2+bx+c=0

a, b, c

b2-4ac

FV x1=-b/2a

x2=-b/2a

x1=(-b+)/2a

x2=(-b-)/2a

radici c.c. x1, x2

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.

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.

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

Soluzione del gioco delle monete

1, 2, 3, 4 : 5, 6, 7, 8

1, 2, 5 : 3, 4, 6 1, 2, 5 : 3, 4, 6

9, 10 : 11, 1

1:2 7:8 1:2

1L 2L 3L 4L5P 6P 7P 8P

1P 2P 3P 4P5L 6L 7L 8L

9L 10L 11L 12L9P 10P 11P 12P01L 2L 6P 5P 3L 4L 5L 3P 4P 7L 8L 1P 2P 6L

9L 10L 11P12L 12P 0

9P 10P 11l

7:8 3:4 3:4

6P 2L 8P imp 7P 3L 5P 4L 4P 5L 3P 7L imp 8L 2P 6L

12:1 9:10

11P 10L 12L 12P 10P 11L 9P

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)

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

HardwarePezzi fisici tangibili che supportano l’elaborazione (chip di silicio, fili elettrici, tastiera, dischi, stampanti….)SoftwareI componenti hardware sono inutili se non ricevono precise istruzioni. Un programma è una serie di istruzioni che l’hardware esegue in sequenza.

Componenti hardware principali

• Dispositivi di input– Ad es.: mouse, tastiera

• Dispositivi di output– Ad es.: monitor, stampante

• Insieme in uno stesso contenitore– Processore (CPU)

• Central Processing Unit• Interpreta e esegue le

istruzioni

– Memoria

Organizzazione hardware standard

Memoria

Processore(CPU)

Dispositividi input

Dispositivi di output

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

Indirizzo Dato

3021 1111 0000

3022 1100 1100 Dato 1: 2 byte

3023 1010 1010 Dato 2: 1 byte

3024 1100 1110

3025 0011 0001

3026 1110 0001

Dato 3: 3 byte

3027 0110 0011

3028 1010 0010 Dato 4: 2 byte

3029 … Etc.

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

Radice

Organizzazione della Memoria Ausiliaria

File Directory Directory

File FileDirectory

Directory

Programma

• Insieme di istruzioni che il calcolatore deve eseguire

Calcolatore

Programma

Input Output

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

Informazione

Esistono due formati per memorizzare l’informazione:ANALOGICO DIGITALE

L’informazione analogica è continua La tecnologia digitale spezza e cresce proporzionalmente alla l’informazione in tanti pezzisorgente di informazione che rappresenta come numeriEs: termometro di mercurio, segnali Es: compact discelettrici

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.

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

In generale i sistemi numerici posizionali in base b2 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

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

Storia Moderna

• PASCAL (1970)

• Programming in Logic (1971)

• C (1974)

• ADA(1980)

Storia Contemporanea

• C++ (1985)

• Java (1994)

Tipi di programmazione

• Funzionale

• Logica

• Procedurale

• Orientata agli oggetti

Traduttori

traduttore

programma

macchina

Codice in l. macchina

macchina

Codice in l. macchina risultati

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

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

L’ambiente Java

Programma Java

Compilatore Java

Programma inByte-Code

Dati in input

Esecuzione

Interprete

Programmi precedentementecompilati

Output del Programma Java

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

Compilatori tradizionali

codice sorgente

compilatore Windows

compilatore Linux

compilatore MacOS

codice eseguibile Windows

codice eseguibile Linux

codice eseguibile MacOS

Compilatore Java

codice sorgente

compilatore Windows

compilatore Linux

compilatore MacOS

interprete bytecode Windows

interprete bytecode Linux

interprete bytecode MacOS

Java bytecode

Programmazione

• Concetti base:– dati

– istruzioni

• Dati:– variabili

– tipi

• Istruzioni: – istruzioni base

– strutture di controllo

– sotto-programmi

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

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

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

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

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

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;

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

Due tipi di tipi di dati in Java

primitivi• I tipi più semplici

• Non possono essere decomposti in altri tipi

• Contengono solo valori

• Esempi:int - interodouble - realechar - carattere

classi• Più complessi

• Composti di altri tipi (primitivi o classi)

• Contengono sia dati che metodi

• Esempio:IntegerString

Tipi di Dati Primitivi

Tipo di valore

Memoria usata

Insieme di valori

byte intero 1 byte da -128 a 127

short intero 2 byte da -32768 a 32767

int intero 4 byte da -2,147,483,648 a 2,147,483,647

long intero 8 byte da -9,223,372,036,854,775,808 a 9,223,374,036,854,775,808

float reale 4 byte da +/- 3.4028… x 10+38 a +/- 1.4023… x 0-45

double reale 8 byte da +/- 1.767… x 10+308 a +/- 4.940… x 0-324

char carattere (Unicode) 2 byte tutti i caratteri Unicode

boolean true oppure false 1 bit

Quali sapere per ora

• int– semplicemente numeri interi

– possono essere positivi e negativi

– nessun punto decimale• char

– semplicemente un singolo carattere

– utilizza le virgolette singole• per esempio, `A`;

• double– 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

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

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.

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

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)

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.

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

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

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)

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

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

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

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

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

Conversione di carattere in intero

• La conversione di un valore di tipo char produce il suo codice Unicode

• Ad esempio, eseguendo le seguenti istruzionichar answer = `7`;

int intAnswer = answer;il valore di intAnswer sarebbe 55 (non 7) in quanto 55 è il codice Unicode del carattere ‘7’

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

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

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

Espressione Java (forma preferita)

Espressione Java con tutte le parentesi

rate2 + delta rate*rate + delta (rate*rate) + delta

2(salary + bonus) 2 * (salary + bonus) 2 * (salary + bonus)

3mass time

1/(time + 3 * mass) 1/(time + (3 * mass))

(a - 7) / (t + 9 * v) (a - 7) / (t +( 9 * v))

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, dopoint count=5;int n = 2*(++count);int m = 2*(count++); sia n che m hanno il valore 12, mentre count ha il valore 7

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

Strutture Java• Sequenza

– di default

Selezione» if» if-else» switch

Ripetizione» while» do-while» for

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

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?

Operatori di confronto

Notazione matematica Java Esempio

= (uguale a) == utile == 0 (diverso da) != utile tax> (maggiore di) > ricavi > costi (maggiore di oppure uguale a) >= voto >= 60< (minore di) < pressione < max (minore di oppure uguale a) <= ricavi <= costi

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.

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.

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 |

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

Precedenze e associatività

Unario++ -- + - !

Unario postfisso++ --

assegnazione= += -= *= /= %= &= |= ^=

Uguaglianza= = !=

Relazionale< <= > >=

Additivo+ -

Moltiplicativo* / %

Conversione(type)

Operatori Associatività Tipo

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

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 bloccocalorieLess = 500;calorieAllotment = calorieAllotment-

calorieLess; //fine del blocco

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_Booleanatrue

Blocco_1

Prossima_Istruzione

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 =

calorieAllotment-500;calorieBreakfast = calorieAllotment/3;

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

Blocco_2 //esegui solo se falsa

Prossima_Istruzione; //sempre eseguita

Diagramma di flusso

Espressione_Booleanatrue

Blocco_1

Blocco_2

Prossima_Istruzione

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;

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_1else if (Espressione_Booleana_2) Blocco_2 .else if (Espressione_Booleana_ n) Blocco_nelse Blocco_Default

Esempioif (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’;

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

• 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

Diagramma di flusso

Espressione_Di_Controllo = Etichetta_Caso_1true

Sequenza_Istruzioni_1

break?

Espressione_Di_Controllo = Etichetta_Caso_2

Sequenza_Istruzioni_2

Sequenza_Istruzioni_Defaultdefault?

Esempioswitch (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’;

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

Esempio

• max = (n1>n2)?n1:n2;

• Equivale a:

if (n1>n2)max = n1;

elsemax = n2;

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

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

trueBlocco

Diagramma di flusso

Espressione_Booleana

Prossima_Istruzione

Esempio• Ciclo che calcola la somma dei primi 10 numeri

interi

int total = 0;int count = 1;while (count <= 10) total = total + count; count++;

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;

Ciclo do-while • Sintassi:

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

Diagramma di flusso

Prossima_Istruzione

Blocco

Esempio

int next;

int total = 0;

next = (int)(Math.random()*100)-50;

total = total + next;

while (next >= 0);

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;

Ciclo for• Struttura:

– azione di inizializzazione– condizione di ripetizione– corpo del ciclo– azione di continuazione

• Sintassi:for (Inizializzazione; Espressione_Booleana; Continuazione) Blocco Prossima_Istruzione

Diagramma di flusso

Inizializzazione

Continuazione

Bloccotrue

Prossima_Istruzione

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;

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)

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

• Istruzione if:if (Espressione_Booleana)Blocco

• Istruzione if-else:if (Espressione_Booleana)Blocco elseBlocco

• Istruzione switch:switch (Espressione_Di_Controllo)

case Etichetta_1:Sequenza_Istruzioni_1

case Etichetta_2: Sequenza_Istruzioni_2

...case Etichetta_n:

Sequenza_Istruzioni_ndefault:

Sequenza_Istruzioni_Default

• Istruzione while:while (Espressione_Booleana)Blocco

• Istruzione do-while:do Blocco while (Espressione_Booleana);

• Istruzione for:for (Inizializzazione ; EB; Continuazione) Blocco

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

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

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

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

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;

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

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

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

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

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

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

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

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

Scomporre e comporre

• Principio del divide et impera

• Suddividere per isolare parti il più possibile autonome ed indipendenti

• Parti potenzialmente riutilizzabili

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

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

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

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

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

Struttura di un programma

• Procedura principale

• Più procedure asservite a quella principale

• Ciascuna di quest’ultime, a sua volta, ne può usare altre

Una visione grafica

proceduraprincipale

proceduraasservita P1

A BA usa B

Realizzazione in Java

• Procedura principale– procedura main

• Per ciascuna procedura asservita– interfaccia

• dichiarazione

– implementazione• definizione del corpo

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

Struttura (parziale)

isApparent isProper isFETS isFBTS computeRN computeRD

computeGCD

Frazioni apparenti e proprie

boolean isApparent(int n, int d)return (n % d == 0);

boolean isProper(int n, int d)return (n < d);

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

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;

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

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

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;

Algoritmo di Euclide

• Proprietà:– se r è il resto della divisione di a per b (ab),

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)

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;

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

Ricorsione in matematica

• Le formule matematiche sono spesso espresse in termini ricorsivi

• Esempio: definizione di fattoriale

N!=N * (N-1)!

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

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

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)

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

Implementazione ricorsiva

int computeFib(int n)

if (n == 0)

return 0;

if (n == 1)

return 1;

return computeFib(n-1)+computeFib(n-2);

Numero di invocazioni

• Numero totale di invocazioni cresce esponenzialmente

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;

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

Le torri di Hanoiinventato 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

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

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

Programmazione OO

• Concetti base:– dati

– istruzioni

• Dati:– variabili

– tipi

• Istruzioni: – istruzioni base

– strutture di controllo

– sotto-programmi

Dati Istruzioni = Metodi

Programmazione Procedurale

Dati Metodi = Classi

Programmazione a Oggetti

Cosa è un oggetto

Metodi(comportamenti)

Variabili(stato)

Un oggetto è una “scatola” software contenente variabili (che descrivono lo stato di un oggetto) e metodi (detti suoi membri, definiscono i comportamenti)

Esempio: i numeri razionali

Variabili di istanza (campi):contengono i valori (lo stato) delnumero razionale

Istanza:un preciso oggetto

Metodi di istanza:agiscono sul numero razionale

isBigg

isEqual

sub div

razionale 3/4

Cosa è un messaggio

altro oggetto utilizzatodal programma

razionale 3/4

numden

isBigger(razionale di confronto)

Gli oggetti interagiscono e comunicano tra loro usando i messaggiper ottenere maggiori funzionalità e comportamenti più complessi

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

Cosa è una classe

Una classe è un “prototipo” che definisce le variabilie 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.

Esempio

isBigg

isEqual

sub div

classe Rational

int numint den

Tutti gli oggetti di tipo Rational possiedono i due campi interi num e den ed almeno i 6 metodi riportati

isBigg

isEqual

sub div

int num=8int den=15

oggetto 8/15istanza di Rational

isBigg

isEqual

sub div

int num=4int den=5

oggetto 4/5istanza di Rational

Dichiarare una classe

• class nome_classe

// definizione variabili// definizione metodi

• Esempio:class Rational

int num;int den;// definizione metodi

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

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)

Fondere le due fasi

Rational primoNumero;primoNumero = new Rational(3,4);

è equivalente a

Rational primoNumero = new Rational(3,4);

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)

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

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

• Esempio:class RationalTest

public static void main(String args)

/* corpo del metodo main */

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

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;

Un esempio riassuntivoclass Rational

int num, den; // variabili di istanzaRational(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 aritmeticheboolean isBigger(Rational r) // confronto se maggiore

return (num * r.den > den * r.num);// altre operazioni di confronto

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

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 myMethod(int i) è diverso da int yourMethod(int i)• int myMethod(int i) è diverso da int myMethod(int i, double j)• int myMethod(int i, double j) è diverso da int 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)

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

Esempioclass MethodOverload int square(int x) return x*x; double square(double y) return y*y; int square(double x) return x*x;

…………

sovraccaricamento

errore segnalatodal compilatore

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

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.

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.

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

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

• Le variabili e i metodi dichiarati private sono accessibili soltanto dai metodi della classe in cui sono definiti

Il modificatore private

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

class shapeTest

public static void main( String[] args )

TwoDimensionalShape s = new TwoDimensionalShape();

s.width = s.generate( 100 ); ERRORE DOPPIOs.setRandomWidth( 100 );System.out.println( s.getWidth( ) );

Caratteristiche dell’OOPOccultamento 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

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;

………

• 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

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

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;

Una libreria di classi è un insieme di classi che aiuta il programmatore nello sviluppo del software.Un compilatore spesso viene distribuito conuna libreria di classi fondamentali.Si possono ottenere separatamentedelle librerie commerciali.Tecnicamente una libreria non fa parte della definizione del linguaggio.La libreria standard viene distribuita con qualsiasi ambiente di sviluppo.

Librerie di classi

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.

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.*

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

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!

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 trueSystem.out.println(u==v); // stampa false

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!

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!

Indice di un carattere• È un intero che, a partire da 0 per il primo

carattere, specifica la posizione del carattere all’interno della stringa H e l l o !

0 1 2 3 4 5

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

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

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)

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

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

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

Terminologia

temperature[n + 2]Nome

temperature[n + 2]

Indice - deve essere un int, - oppure un’espressione che ritorna un int

temperature[n + 2]

Variabili indicizzata o elemento

temperature[n + 2] = 32;

Valore della variabile indicizzata o elemento

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 .lengthString[] message = new String[20];

System.out.println(message.length);

• Determinata al momento della dichiarazione– non può essere modificata a meno di ridichiarare l’array

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

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 1 2 3 Valore: 97 86 92 71

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

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;

Array, classi e metodiDato array di oggetti, i metodi della classe

corrispondente possono essere usati sui singoli elementi

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

dichiara array di Rational

ogni elemento è unaistanza di Rational

usa il metodo add della classe Rational

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)

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

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

Esempio

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;

l'argomento del metodo è il nome di un array di razionali

usa length per evitare eccezioni dovute ad indice fuori del dominio

usa length per controllare il ciclo

Array ed operatore =int[] a = new int[3];

int[] b = new int[3];

for(int i; i < a.length; i++)

a[i] = i;

b = a;

System.out.println(a[2] + " " + b[2]);

a[2] = 10;

System.out.println(a[2] + " " + b[2]);

Non crea una copia dell'array a matrasforma b in un altro nome per l'array a

Output:2 210 10

Un valore cambiato in aè lo stesso valore ottenuto con b

Array ed operatore ==int i;int[] a = new int[3];int[] b = new int[3];for(i=0;i<a.length;i++) a[i] = 0;for(i=0;i<b.length;i++) b[i] = 0;if(b == a) System.out.println("a equals b");else System.out.println("a does not equal b");

a e b sono entrambi array di 3 elementi di tipo int

a tutti gli elementi di a e b viene assegnato il valore 0

verifica se gli indirizzi di a e b sono uguali, non se i valori degli array sono uguali

L'output di questo codice sarà a does not equal b perché gli indirizzi dei due array non sono uguali

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;

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

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

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

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

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

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

Il codicepublic 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;

Esempioa[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

7 6 11 17 3 15 5 19 30 14

3 6 11 17 7 15 5 19 30 14

3 5 11 17 7 15 6 19 30 14

3 5 6 17 7 15 11 19 30 14

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 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.

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.

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.

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

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 e tralasciando a volte anche le costanti moltiplicative.

Complessità in tempo e 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 .

Perché si studia la complessità asintotica

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.

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.

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.

Complessità in spazio

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.

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.

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.

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.

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

Notazioni

g(n)O(f(n)) tradizionalmente si legge “g(n) è di ordine f(n)” e fornisce un limite superiore al comportamento asintotico della funzione.

O(f(n)) è l’insieme di tutte le funzioni g(n) tali che esistono due costanti positive c e n0 per cui g(n)<=cf(n) per ogni n>= n0

Ω(f(n)) è l’insieme di tutte le funzioni g(n) tali che esistono due costanti positive c e n0 per cui g(n)>=cf(n) per ogni n>= n0.

g(n)Ω(f(n)) tradizionalmente si legge “g(n) è di ordine Ω f(n)” e fornisce un limite inferiore al comportamento asintotico della funzione.

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

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.

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.

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

Proprietà di O, e

• g O(f) implica (f+g) O(f) • f1O(g1), f2O(g2) implica f1+ f2O(g1+g2)

• O e sono relazioni riflessive e transitive

• è una relazione di equivalenza

• fO(g) se e solo se g (f)

Possiamo dividere ora gli algoritmi in classi, ponendo nella stessa classe quelli che hanno complessità asintotica dello stesso ordine di grandezza O.

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

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

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

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;

Esempioa[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

7 6 11 17 3 15 5 19 30 14

3 6 11 17 7 15 5 19 30 14

3 5 11 17 7 15 6 19 30 14

3 5 6 17 7 15 11 19 30 14

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.

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.

Programmi ricorsivi

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.

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.

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.

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.

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.

RELAZIONI DI RICORRENZA

FibonacciUna 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 Fibonacci.

F3=2 la prima coppia procrea una seconda

• •

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.

F1=1 al mese 1 c’è solo una coppia

F2=1 al mese 2 ancora la prima coppia non può procreare

Condizioni iniziali

Fn=Fn-1+Fn-2 Relazione di ricorrenza

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.

Sostituiamo in Fn=Fn-1+Fn-2 la soluzione ipotizzata.

cz n cz n 1 cz n 2

cz n cz n 1 cz n 2 0

cz n 2 (cz n

cz n 2

cz n 1

cz n 2 1) 0

cz n 2 (z n n2 z n 1 n2 1) 0

cz n 2 (z 2 z 1) 0

Possiamo quindi affermare che czn è una soluzione della relazione di ricorrenza in uno dei seguenti tre casi:

z 0banale, si avrebbe Fn 0

z 2 z 1 0 z1,2 1 5

Quindi Fn ammette le due soluzioni Fn=c1z1

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 +c2z2

Imponendo le condizioni iniziali:

c1(1 5) 12

c2 (1_ 5) 1

c1(1 5)2 14

c2 (1_ 5)2 1

Si ottiene dopo facili calcoli :

Si ottiene quindi:

E' prevalente dato che z

1>1 mentre z

detta formula di Binet

4 51 5 2 5 1 5 2 5 1

Si ha quindi :

2 51 5 1 5 1

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 h cioé 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 1

b)Relazioni lineari di ordine h

( con ah = 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 np b

con n pm e m intero, n 1

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

e) Relazioni con partizioni di dati

C(1) d

C(n) = aC nb c1n c2

con n bk e k intero, n 1

Soluzionia) C(n) O(k n )

b) C(n) O(n)

c) C(n) O(log n) se a = 1

C(n) O(nlog

) se a 1

d) C(n) O(n2 )

e) C(n) O(n) se a p

C(n) O(nlog n) se a p

C(n) O(nnlog

) se a p

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.

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=2C(n)=2C(n/2)+2 per n>2Questo modo di impostare l’algoritmo si chiama DIVIDE ET IMPERA (prossima lezione)

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

) = O(n)

C(n) aC np b a aC n

a a aC np3

a a aC npm

amc b am 1 am 2 1

Soluzione di c) per sostituzioni successive

Quindi abbiamo

C(n) amc b am 1 am 2 1 Se a 1

C(n) = c + b(1++1)m volte

Dato che n pm si ha che logpn = m per cui

C(n) = c + blogpn O(log n)

Osservazione :

Se n pm n1 e n2 t.c. n1 n n2 e n1 pm e n2 pm1

Dato che C(n) é crescente in n si ha che

C(n) O(logpn2 ).

Ma n2 n1 p da cui

logpn2 logp pn1 logp pn 1 logpn

Quindi C(n) O(logpn 1)

Se a > 1

Partiamo sempre da C(n) amc b am 1 am 2 1

Osserviamo che a i

am 1a 1

Dato che m logpn logpa logan si ha che

C(n) = amc bam 1

alogpalogan

nlogpa

O nlogpa

Osservazione :

Se n pm n1 e n2 t.c. n1 n n2 e n1 pm e n2 pm1

Dato che C(n) é crescente con n si ha che :

C(n1 ) C(n) C(n2 )

per cui C(n) < n2

con n2 n1 p

Di conseguenza C(n) < n2

(n1 p)logpa n1

logpaa n logpaa

Abbiamo quindi dimostrato che n

Se a 1 C(n) O(logp

Se a 1 C(n) O(nlog

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

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.

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.

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/xA e x< A[h]A2=x/xA 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.

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.

• 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, 5A2=45,38,50,40,35

Saranno trattati ricorsivamente nello stesso modo.

POSIZIONI 1 2 3 4 5 6 7 8 9 10 30 40

25 50 15 45 38 5 10 35

25 50 15 45 38 5 40 35

25 5 15 45 38 50 40 35

25 5 30 45 38 50 40 35

I colori giallo e verde indicano rispettivamente i cursori p e q

Evoluzione dell’array A durante le partizioni intorno al perno

Codice per Quicksortpublic 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;

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;

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.

Relazione di ricorrenza per il Quicksort

C(n) 0 n 0,1

C(n) P(n) C(q 1) C(n q)

q indica la posizione del perno

Complessità di perno

Complessità su A1

Complessità su A2

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)

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:

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

CM (n) n 1 1n

(CM ( j 1) CM (n j))j1

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 :

CM (n) 2(n 1)1

n1 2(n 1)(log(n 1) log2)

Quindi CM (n) O(nlogn)

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,

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.

Caso pessimo QuicksortIn 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

j (n 2)(n 1)

2 3 O(n2

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.

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.

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.

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)

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

C(1) 0

C(n) 2C(n2) M(n)

M(n) n nel caso pessimo

C(n) O(nlogn)

Numero di confronti richiesto dal Merge

Studio della complessità per il Mergesort

Mergesort è un algoritmo ottimo anche nel caso pessimo: il motivo è ancora da ricercarsi nel fatto che la partizione operata da Mergesort è sempre bilanciata!

1 Master in BIOINFORMATICA Corso propedeutico di Informatica DOCENTE: Elisa Tiezzi UNIVERSITA DI...

Documents