Algoritmi

Dr. Francesco FabozziCorso di Informatica

2

Programma• Un elaboratore è una macchina universale

in quanto può risolvere problemi di svariata natura– Gestione prestiti di una biblioteca, sistema di

prenotazione dei voli, risoluzione equazioni, …

• Ma non è una macchina intelligente– Occorre impartire dall’esterno la sequenza

delle istruzioni da eseguire per risolvere il problema (programma)

• Deve essere in un linguaggio comprensibile alla macchina (linguaggio di programmazione)

3

Analisi e programmazione• La risoluzione di un problema mediante un

elaboratore avviene in due fasi successive:– Analisi del problema

• Ha come obiettivo la definizione di una procedura che permetta di risolvere il problema (algoritmo)

– Programmazione• Ha come obiettivo la traduzione dell’algoritmo in un

programma

4

Algoritmo• L’algoritmo è una procedura che lavora su

dati d’ingresso e fornisce dati in uscita con le seguenti caratteristiche:– Generale– Finita– Completa– Non ambigua– Eseguibile

5

Caratteristiche di un algoritmo• Generale

– Deve risolvere una intera classe di problemi al variare dei dati che li caratterizzano

• Finito– Le istruzioni che lo compongono e il numero di

volte che ogni istruzione viene eseguita devono essere finiti

• Completo– Deve contemplare tutti i casi possibili

6

Caratteristiche di un algoritmo• Non ambiguo

– Ogni istruzione deve essere definita in modo univoco, senza paradossi, contraddizioni o ambiguità

• Eseguibile– Deve esistere un agente di calcolo in grado di

eseguire ogni istruzione in un tempo finito

7

Efficienza di un algoritmo• Uno stessa classe di problemi può essere

risolta da diversi algoritmi, tutti corretti

• Un algoritmo efficiente deve pervenire alla soluzione del problema impiegando poco tempo e poca memoria– Diversi algoritmi, anche se tutti corretti,

possono avere diversi gradi di efficienza

• In genere algoritmi molto efficienti rispetto al tempo tendono ad occupare più memoria e viceversa

8

Efficienza rispetto al tempo• Un algoritmo è veloce se arriva alla soluzione del

problema eseguendo un numero piccolo di passi• L’efficienza rispetto al tempo si esprime

indicando il numero di operazioni da compiere in funzione del numero n di dati in input

• Esempi: – Numero operazioni ~ n2

• algoritmo di complessità O(n2) (=complessità quadratica)

– Numero operazioni ~ 2n • algoritmo di complessità O(2n) (=complessità esponenziale)

9

Efficienza rispetto al tempo• Esempio:

– Tempo impiegato da una CPU di 100 MIPS per il calcolo di un algoritmo di complessità lineare, quadratica ed esponenziale per diverse quantità di dati in input

dati

compl.

10 20 50 60

n 10-7 s 2 10-7 s 5 10-7 s 6 10-7 s

n2 10-6 s 4 10-6 s 25 10-6 s 36 10-6 s

2n 10-5 s 6 10-2 s 1.6 107 s 1.6 1010 s

10

Efficienza rispetto al tempo• Un algoritmo di complessità polinomiale

O(nk) fornisce una soluzione al problema implementabile col calcolatore– Ancora migliori sono gli algoritmi di

complessità logaritmica O(logkn)

• Algoritmi di complessità esponenziale sono inutilizzabili

11

Efficienza rispetto alla memoria• Un algoritmo è efficiente rispetto alla memoria se

arriva alla soluzione del problema occupando un numero piccolo di locazioni

• L’efficienza rispetto alla memoria si esprime indicando il numero di locazioni occupate in funzione del numero n di dati in input

• Esempio: – Numero locazioni ~ n

• algoritmo O(n) nel numero di celle di memoria impiegate

12

Analisi del problema• La fase di analisi del problema ha come

scopo la definizione dell’algoritmo. Viene effettuata in tre passi:– Definizione del problema

• In questa fase non bisogna riferirsi al problema particolare (istanza) ma al caso generale cioè all’intera classe di problemi

– Scelta del metodo di soluzione più appropriato– Sviluppo e descrizione dell’algoritmo

13

Analisi del problema• Per problemi complessi è utile effettuare

l’analisi seguendo l’approccio top-down– Tale approccio si basa sulla scomposizione del

problema in sottoproblemi più elementari– Per ciascun sottoproblema viene definito un

algoritmo

• Il vantaggio di questo approccio è che esso porta a definire algoritmi per problemi elementari che possono ritrovarsi in molti problemi complessi

14

Un semplice algoritmo• Problema: confrontare le aree di due

rettangoli (A e B) dati i rispettivi lati

• AlgoritmoAcquisire lati di A in input

Calcolare l’area di A

Acquisire i lati di B in input

Calcolare l’area di B

Se l’area di A è maggiore dell’area di B:Comunica in output che Area(A) > Area(B)

Se l’area di B è maggiore dell’area di A:Comunica in output che Area(B) > Area(A)

15

Applicazione dell’algoritmo• Un algoritmo deve fornire la soluzione per

un’intera classe di problemi

• Per risolvere un singolo problema di una certa classe si applica l’algoritmo sui dati che lo caratterizzano– Nell’esempio precedente i dati sono i lati di

due particolari rettangoli da confrontare– L’insieme costituito da tutti i possibili dati

prende il nome di insieme di definizione dell’algoritmo

16

Algoritmo e dati• Un algoritmo interagisce con l’esterno in

due fasi:– Quando acquisisce i dati del particolare

problema da risolvere (fase di input)– Quando comunica messaggi o risultati (fase di

output)

Ambiente esterno

Dati del problema

Algoritmo

Messaggi / risultati

17

Costanti e variabili• I dati su cui opera un algoritmo possono

essere:– Costanti: il valore non può essere cambiato

durante l’esecuzione dell’algoritmo– Variabili: il valore può essere cambiato

18

Variabili scalari• Una variabile scalare è una coppia (nome,

valore)– Il valore della variabile è indeterminato in fase

di definizione dell’algoritmo– Il valore viene definito durante l’esecuzione

dell’algoritmo (valore attuale) mediante un’istruzione di assegnazione

Nome

Valore

Variabile scalare

19

Variabili vettore• Una variabile vettore (o array) è una coppia

(nome, insieme ordinato di valori)– I valori (elementi o componenti del vettore)

sono numerati a partire da 1 (o da 0)

• Si possono avere anche vettori di vettori– Vettori multidimensionali

20

Variabili vettore• Se nome_v è il nome di un vettore si indica

con nome_v( i ) la componente del vettore che è associata al numero intero i (indice del vettore)

V(4)V(4)V(1)V(1) V(2)V(2) V(3)V(3)

V(1), V(2), V(3), V(4) sono i 4 elementi del vettore

Vettore V

21

Assegnazione di una variabile• L’istruzione di assegnazione permette di

definire il valore attuale di una variabile

nome variabile ← espressione

• A destra della freccia: espressione costituita da variabili, costanti e operatori– Si valuta l’espressione sostituendo ai nomi di

variabile i rispettivi valori attuali e il valore calcolato sarà il valore attuale della variabile a sinistra della freccia

22

Assegnazione di una variabile• In un’assegnazione occorre rispettare la

regola dell’ordinamento– Una variabile che compare nell’espressione

deve essere già stata istanziata (cioè deve avere un valore attuale definito)

23

Assegnazione di una variabile• Esempio: area ← lunghezza * larghezza

Prima dell’assegnazione

• Esempio: x ← x + 2

larghezza

2

lunghezza

3

area6

larghezza

2

lunghezza

3

Dopo l’assegnazione

x5

x7

prima dopo

24

Istruzioni• La procedura di un algoritmo è descritta

per messo di una sequenza di istruzioni

• Esistono vari tipi di istruzioni:– Operative– Di controllo– Di salto– Di ingresso/uscita– Di inizio esecuzione– Di fine esecuzione

25

Tipi di istruzioni• Istruzioni operative

– La loro esecuzione provoca un risultato

• Istruzioni di controllo– Controllano il verificarsi di una certa

condizione– Il risultato del controllo determina il flusso di

istruzioni da eseguire successivamente

26

Tipi di istruzioni• Istruzioni di salto

– Alterano il normale ordine di esecuzione delle istruzioni specificando esplicitamente un salto a una specifica istruzione

– Istruzioni di salto condizionato• Il salto viene eseguito al verificarsi di una

condizione

– Istruzioni di salto incondizionato• Il salto viene eseguito sempre

– Nella programmazione strutturata il loro uso viene scoraggiato

27

Tipi di istruzioni• Istruzioni di ingresso/uscita

– Indicano la modalità di trasmissione dati o messaggi tra algoritmo e ambiente esterno

• Istruzione di inizio esecuzione– Indica inizio algoritmo

• Istruzione di fine esecuzione– Indica fine algoritmo

28

Descrizione di un algoritmo• L’algoritmo dell’esempio iniziale è stato

descritto usando il linguaggio naturale

• I linguaggi naturali sono:– Ambigui (una parola può avere più significati)– Ridondanti (una stessa operazione può essere

descritta in modi diversi)

29

Descrizione di un algoritmo• Per illustrare un algoritmo in maniera

precisa e sintetica sono introdotti dei formalismi (formalismi di codifica) che non hanno i difetti del linguaggio naturale

• Nel seguito mostreremo due esempi di formalismi: – diagrammi di flusso (flow-chart)– pseudocodifica

30

Diagrammi di flusso• Rappresentazione grafica degli algoritmi

• Indicano il flusso (o sequenza) delle istruzioni

• Ogni istruzione è rappresentata da un simbolo grafico (blocco elementare)– Simboli diversi per diversi tipi di istruzioni

• I blocchi sono collegati da linee di flusso– Frecce che indicano l’ordine con cui si

susseguono le istruzioni

31

Blocchi elementariinizio fine

istruzione

ingresso/uscita

Blocchi di inizio e fine algoritmo

Blocco di azione

Blocco contenente una istruzione di I/O

Linea di flusso

condizione Blocco di controllo

32

Caratteristiche di una flow-chart• Un diagramma di flusso possiede:

– 1 blocco di inizio algoritmo– 1 blocco di fine algoritmo– n ≥ 1 blocchi di azione o di I/O, n finito

• Ciascuno di questi blocchi ha una sola linea di flusso entrante e una sola linea di flusso uscente

– m ≥ 0 blocchi di controllo, m finito• Ciascuno di questi blocchi ha una sola linea di

flusso entrante e due linee di flusso uscenti

33

Caratteristiche di una flow-chart• In un diagramma di flusso:

– Una linea di flusso entra in un blocco o si inserisce in un’altra linea di flusso

– Ciascun blocco è raggiungibile dal blocco di inizio algoritmo

– Il blocco di fine algoritmo è raggiungibile da qualsiasi altro blocco

Blocco B raggiungibile dal blocco A

Esiste una sequenza di blocchi X1, …,Xn tali che A=X1, B=Xn e per ogni i=1, …, n-1 Xi è connesso con una freccia al blocco Xi+1

34

Schemi di flusso• In un algoritmo le sequenze di istruzioni si

possono raggruppare secondo schemi caratteristici detti schemi di flusso:– Schema di sequenza– Schema di selezione– Schema di iterazione

• La giustificazione è fornita dal Teorema di Böhm-Jacopini– Qualunque algoritmo è rappresentabile

utilizzando solo questi tre schemi di flusso

35

Schema di sequenza• Una semplice sequenza di istruzioni (o

anche di schemi di flusso)

istruzione 1

istruzione 2

istruzione n

S1

S2

Sn

Si = schemi di flusso

36

Schema di selezione• Due istruzioni (o anche schemi di flusso)

alternative da eseguirsi in base al verificarsi o meno di una certa condizione

istruzione 1 istruzione 2

condizioneF V

37

Schema di selezione• Altra possibilità

istruzione

condizioneF V

38

Condizione• Nello schema di selezione compare una

condizione – Il flusso delle istruzioni viene determinato in

base al verificarsi o meno della condizione

• Per esprimere in maniera formale una condizione dobbiamo introdurre alcuni elementi di logica

39

Proposizioni• Proposizione: costrutto linguistico di cui si

può asserire o meno la veridicità

• Esempi:– “8 è un numero pari” vera– “Potenza si affaccia sul mare” falsa

• Valore di verità di una proposizione: l’essere vera o falsa– Vero / Falso : valori logici o booleani

40

Predicati• Predicato: proposizione il cui valore di

verità dipende dal valore attuale di alcune variabili

• Esempi:– “la variabile x è un numero pari”– “l’angolo theta è minore di 90 gradi”

• Valutazione di un predicato: determinazione del suo valore di verità

41

Operatori relazionali• Si chiamano operatori relazionali degli

operatori che permettono di esprimere concisamente proposizioni e predicati

• Predicato semplice: predicato che contiene un solo operatore relazionale

uguale

> maggiore

≥ maggiore o uguale

≠ diverso

< minore

≤ minore o uguale

42

Negazione logicap = predicato

not p = negazione logica di p

Predicato con valore di verità opposto a quello di p

Esempio: not( x > 2) vero solo quando x ≤ 2

p not p

vero falso

falso vero

Tabella di verità per il not

43

Congiunzione logicap, q = predicati

p and q = congiunzione logica di p e q

Predicato con valore di verità vero quando p e q sono entrambi veri

Esempio: ( x > 2) and (x < 5)

p q p and q

falso falso falso

falso vero falso

vero falso falso

vero vero vero

Tabella di verità per l’and

44

Disgiunzione logicap, q = predicati

p or q = disgiunzione logica di p

Predicato con valore di verità vero quando almeno p o q è vero

Esempio: ( x < 2) or (x > 5)

p q p or q

falso falso falso

falso vero vero

vero falso vero

vero vero vero

Tabella di verità per l’or

45

La flow-chart dell’esempio iniziale

S(A)>S(B)F V

inizio

Leggi in input lato 1A di A S(B) 1B*2B

Leggi in input lato 2A di A

Leggi in input lato 1B di B

S(A) 1A*2A

Leggi in input lato 2B di B

Scrivi in output “Area di B maggiore di area di A”

Scrivi in output “Area di A maggiore di area di B”

fine

46

Schema di iterazione• Ripetizione di un’istruzione (o schema di flusso)

per un numero finito di volte– Lo schema da ripetersi si dice corpo dell’iterazione

• Deve essere in grado di modificare la condizione altimenti si entra in un “loop” infinito

Corpo dell’iterazione

condizioneF

V

Iterazione per falso

Controllo in coda(il corpo è eseguito almeno una volta)

47

Schema di iterazione• Altra possibilità

Corpo dell’iterazione

condizioneF

V

Iterazione per vero

Controllo in testa(il corpo può anche non essere mai eseguito)

48

Esempio di algoritmo con iterazione• Problema: calcolo di a4

Scrivi b inoutput

fineF V

inizio

Leggi a in input

b 1

b b*am m+1

m = 4

m 0

Variabile b che immagazzinail risultato del calcolo

Variabile m che conta il numero divolte che si effettua l’operazione(“contatore”)

49

Esempio di algoritmo con iterazione• Vediamo che l’algoritmo è OK in un caso

particolare– Input = 2 Output = 24 = 16

Iniziali # 1 # 2 # 3 # 4 Finali

a 2 2 2 2 2 2

b 1 2 4 8 16 16

m 0 1 2 3 4 4

Passi dell’iterazione

50

Esempio di algoritmo con iterazione• Verificare che il seguente algoritmo è

sbagliato per il calcolo di a4

F V

inizio

Leggi a in input

m 1

a a*am m+1

m = 4 Scrivi a inoutput

fine

51

Esempio di algoritmo con iterazione• Verifichiamo che l’algoritmo non è OK

usando un caso particolare– Input = 2 Output = 256 = 28

Iniziali # 1 # 2 # 3 Finali

a 2 4 16 256 256

m 1 2 3 4 4

Passi dell’iterazione

52

Pseudocodifica• L’algoritmo viene descritto mediante un

linguaggio formale e rigoroso– Vicino a un linguaggio di programmazione

• La descrizione mediante pseudocodifica si compone di due parti– Dichiarazione delle variabili usate

nell’algoritmo– Descrizione delle azioni

53

Pseudocodifica• Nella pseudocodifica:

– Si utilizzano parole chiave (in maiuscolo)• BEGIN, END, IF, …

– Si utilizzano operatori• +, *, -, >, …

– Si indentano le istruzioni• Rientro di tabulazione per gruppi di azioni che

appartengono a un certo schema di flusso

54

Tipo delle variabili• Indica l’insieme di definizione di una variabile (o

di una costante)– Cioè l’insieme dei valori che può assumere

• INTEGER– Una variabile a cui possono essere assegnati numeri

interi relativi– Una costante numero intero relativo

• Ex.: 2, -139

• REAL– Una variabile a cui possono essere assegnati numeri

razionali– Una costante numero razionale

• Ex.: 5.17, -0.345, 23.476 E-3

55

Tipo delle variabili• BOOLEAN

– Una variabile a cui possono essere assegnati valori logici

– Una costante true oppure false

• STRING-q– Una variabile a cui possono essere assegnate stringhe

(parole) di q caratteri– Una costante stringa di q caratteri

• Sono racchiuse tra apici• Ex.: ‘PIPPO’ è una costante STRING-5• Ex.: ‘?’ è una costante STRING-1• Ex.: ‘278’ è una costante STRING-3

56

Dichiarazione delle variabili• Elenco delle variabili su cui opera

l’algoritmo– Preceduto dalla parola chiave VAR

VAR i, j, k(10): INTEGER;p, q: REAL;cognome: STRING-20:ishigh: BOOLEAN.

I due punti separano l’elenco delle variabili dal loro tipo

Il punto e virgola termina la dichiarazione di variabili dello stesso tipo

Il punto termina la dichiarazione

La virgola separa variabili dello stesso tipo

57

Descrizione delle azioni• Regole

– La prima azione dell’algoritmo deve essere preceduta da BEGIN

– L’ultima azione dell’algoritmo deve essere seguita da END

– Un’azione di lettura si indica con READ– Un’azione di scrittura si indica con WRITE

• Si usano parole chiave per identificare gli schemi di flusso

58

Schema di sequenza

Istruzione 1Istruzione 2……Istruzione n

S1

S2

……Sn

59

Schema di selezione

IF condizioneTHEN istruzione 1ELSE istruzione 2

ENDIF

IF condizioneTHEN istruzione

ENDIF

60

Schema di iterazione

REPEAT corpo dell’iterazioneUNTIL condizione

ENDREPEAT

WHILE condizionecorpo dell’iterazione

ENDWHILE

Controllo in coda

Controllo in testa

61

Esempi di pseudocodificaVAR a1, a2, b1, b2, sa, sb: REAL.BEGIN

READ a1READ a2sa a1 * a2READ b1READ b2sb b1 * b2IF sa > sb

THEN WRITE“Area A maggiore area B”ELSE WRITE“Area B maggiore area A”

ENDIFEND

62

Esempi di pseudocodifica

VAR a, b: REAL;m: INTEGER.

BEGINREAD ab 1m 0REPEAT

b b * am m + 1UNTIL m = 4

ENDREPEATWRITE b

END