Algoritmi, programmazione strutturata e complessità APPLICATA E SISTEMI... · Algoritmi,...

Algoritmi, programmazione

strutturata e complessità

INFORMATICA APPLICATA E SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI

Lezione II - InfSisElabInf 1 27/03/2013

Che cos’è un algoritmo

27/03/2013 Lezione II - InfSisElabInf 2

DEFINIZIONE: Un algoritmo è una soluzione formale di un

problema

Se nella precedente lezioni abbiamo imparato a capire come le

informazioni sono rappresentate all'interno dell'elaboratore,

non dimentichiamo che l'informatica si occupa soprattutto

della loro elaborazione

Gli algoritmi rappresentano quindi in maniera formale il

modo in cui tale elaborazione possa essere possibile all'interno

di un calcolatore (e.g. data la rappresentazione informatizzata

di una mappa stradale, l'algoritmo di Dijkstra trova il percorso

minimo fra due località)

Un esempio di algoritmo (1)


Formalizziamo l’algoritmo risveglio

Algoritmo 1: risveglio

1. Alzarsi dal letto

2. Togliersi il pigiama

3. Fare la doccia

4. Vestirsi

5. Fare colazione

6. Prendere il bus per andare a lavoro

Nota

I passi sono eseguiti in sequenza e l’ordine delle istruzioni è

essenziale per la correttezza dell’algoritmo



Non basta organizzare i passi in sequenza




3. Fare la doccia

4. Vestirsi

5. Fare colazione

6. Se piove

Prendere ombrello

7. Prendere il bus per andare a lavoro



Ulteriore forma di flusso..




3. Fare la doccia

4. Vestirsi

5. Fare colazione

6. Se sciopero mezzi pubblici Prendere macchina

altrimenti Prendere il bus

Un ulteriore esempio: misura della

pressione arteriosa


Gli algoritmi sono applicabili anche in campo biomedico: spesso sono inclusi nei protocolli e nelle line guida.

Algoritmo 2: misuraPressioneArteriosa (Metodo ascoltatorio)

1. far sedere comodamente il paziente

2. mettere attorno al braccio il manicotto a 2 cm di distanza dalla piegatura del gomito

3. insufflare fino ad un valore sicuramente superiore alla pressione massima del paziente (per esempio 250 mmHg)

4. appoggiare l'audiofono del fonendoscopio a valle del bracciale nel punto di passaggio dell'arteria omerale

5. Svitare lentamente la valvola

6. Mentre scende la colonna 1. Ascoltare il primo battito che indica la sistolica (o massima)

2. Ascoltare l'ultimo battito che indica la diastolica (o minima)

7. Misurazione conclusa

Osservazioni sugli algoritmi (1)


Un algoritmo è una procedura che consta di un numero finito di passi, finalizzata a risolvere un problema in maniera automatica, che ricevendo in ingresso un insieme di valori restituisce in uscita un altro insieme di valori

Chiunque sappia comprendere ed eseguire le operazioni può eseguire l’algoritimo risveglio o misurare la pressione arteriosa. E’ quindi essenziale che i passi che costituiscono un algoritmo siano eseguibili: l'algoritmo deve essere un metodo effettivo

L'esecutore può non conoscere quello che l'algoritmo calcola. Talune istruzioni manipolano le variabili che rappresentano delle quantità che nell'esecuzione dell'algoritmo possono cambiare valore

Osservazioni sugli algoritmi (2)


Ad ogni passo del procedimento di calcolo deve essere

possibile applicare al più una istruzione: non sono quindi

ammesse scelte non deterministiche

Non si pone alcun limite al tempo necessario ad eseguire

il calcolo, né allo spazio di memoria richiesto: è sufficiente

che siano finiti

La nozione di algoritmo focalizza l'attenzione sul metodo

di soluzione e non sul linguaggio o sul modo utilizzato

per descrivere tale metodo: il linguaggio naturale non è un

buon linguaggio per descrivere algoritmi soprattutto a

causa della sua ambiguità

Calcolatore elettronico

Lezione II - InfSisElabInf 10

Una macchina che fa calcoli costruita con dispositivi

elettronici

Fa calcoli: essenzialmente somma, sottrae, moltiplica,

divide e esegue operazioni logiche

È una macchina: non è dotata di intelligenza, ma esegue

molto rapidamente i compiti impartiti (i calcoli)

27/03/2013

Procedimento automatizzabile: algoritmo


Procedimento: una sequenza di passi di elaborazione

che a partire da un’informazione in ingresso (input)

producono un’informazione di uscita (output)

Elaborazione Input Output

Informazione (dati) in ingresso Informazione (dati) in uscita

Algoritmo: procedimento eseguibile dal calcolatore

27/03/2013

Algoritmo prescinde dal linguaggio di

programmazione

Abbiamo descritto i precedenti algoritmi senza far

esplicito riferimento ad un linguaggio di programmazione

Anche perché ancora non abbiamo definito cosa sia un

linguaggio di programmazione

Pertanto un algoritmo prescinde dallo specifico linguaggio di

programmazione

Piuttosto, un medesimo algoritmo può essere implementato

attraverso diversi linguaggi di programmazione


implementare: che significa?

27/03/2013

Linguaggio di programmazione

Linguaggio in cui traduco l’algoritmo affinché questo possa

essere eseguito dal calcolatore

Un algoritmo codificato in un linguaggio di programmazione è

un programma (anche detto “software”)

Un programma contiene quindi una serie di istruzioni da impartire al

calcolatore affinché esso possa eseguire il mio algoritmo

In sintesi l’informatica tratta la progettazione e la realizzazione

di programmi per elaboratore elettronico (computer)

Ecco perché l’informatica propriamente detta non riguarda

l’uso di programmi come Word, Excel, …

Bensì l’informatica riguarda la loro realizzazione


Paradigmi di programmazione

Esistono svariati linguaggi di programmazione:

C , C++, Java, Pascal, Fortran, C#, … (no HTML, no XML);

Paradigmi di programmazione

“paradigma” = “modello”: il modello a cui lo specifico

linguaggio di programmazione si riconduce;

I più usati:

Paradigma della programmazione strutturata:

Adottato da linguaggi quali C, Fortran, Pascal, Matlab;

Paradigma della programmazione ad oggetti:

OOP – Object Oriented Programming

Più recente e più potente rispetto alla programmazione strutturata

Adottato da linguaggi quali Java, C++, C#;


Algoritmo, paradigma e linguaggio di

programmazione

In quale relazione si trovano?

Per progettare un algoritmo è necessario conoscere quali

sono i componenti di base che posso impiegare, i

“mattoni” col quale costruirlo

Il paradigma di programmazione definisce i mattoni

Un volta che ho progettato un algoritmo che aderisce ad

uno specifico paradigma, potrò implementarlo attraverso

qualsiasi linguaggio aderente al medesimo paradigma


Input, elaborazione, output: architettura

di un calcolatore

Dispositivi di INPUT

Tastiera, mouse,

touchpad, microfono,

webcam, …

Dispositivi di OUTPUT

Monitor, stampante, casse

audio, …

Unità di elaborazione

CPU (Central Processing Unit)

Memoria RAM

(Random Access

Memory)

Control

Unit

ALU

(Arithmetic

Logic Unit)

(Architettura di Von Neumann)

Dispositivi attraverso

cui l’utente fornisce

l’informazione (i dati)

in ingresso

Dispositivi attraverso

cui l’utente riceve

l’informazione (i dati)

in uscita

Il calcolatore esegue

calcoli su numeri e

operazioni logiche

La CPU si appoggia

alla RAM per

memorizzare i

programmi e i dati

intermedi


Programmazione strutturata

Il programma/algoritmo viene realizzato componendo

opportunamente una serie di strutture

Come vedremo, la composizione è possibile perché ogni

struttura ha un unico punto di ingresso e un unico punto

di uscita

Le strutture sono:

Struttura di sequenza

Strutture di selezione (una o più)

Strutture di iterazione (una o più)


La struttura di sequenza

leggi a:

b = a * 2;

c = b + 3;

stampa c;

Serie ordinata di istruzioni (o strutture) che vengono eseguite

in sequenza: prima istruzione, seconda istruzione, ... L’algoritmo

1preparaCaffè è un sequenza di istruzione come le sequenza qui

riportata:

Nota: al termine di ogni istruzione il

calcolatore è in uno stato stabile e ben

definito

Unico punto di ingresso

Unico punto di uscita


La struttura di selezione

leggi a;

if a > 10 then

b = a – 10;

else

b = a;

End if

stampa b;

Struttura(e) che permette la selezione tra due o più

istruzioni (o strutture) da eseguire.

Unico punto di ingresso



Il prodotto fra due numeri


Supponiamo di avere a disposizione un calcolatore capace di fare solo la somma di due numeri interi, e vogliamo costruire un algoritmo che esegue il prodotto fra due numeri a e b

Per fare questo, sfrutto il fatto che

Algoritmo 3 prodotto(int a, int b) int

Require: a>0, b>0

1. prodotto 0

2. for b volte do

3. prodotto prodotto+a

4. End for

5. Return prodotto

Il prodotto fra due numeri (2)


Siano a=3 e b=4

Require: a>0, b>0

1. prodotto 0

2. for b volte do

3. prodotto prodotto+a

4. End for

5. Return prodotto

Inizialmente (linea 1) prodotto

= 0

La linea 3 viene iterata 4 volte

(linea 2):

1. prodotto = 0 + 3 = 3

2. prodotto = 3 + 3 = 6

3. prodotto = 6 + 3 = 9

4. prodotto = 9 + 3 = 12

Infine, si restituisce il risultato

(linea 5)

L’iterazione (ciclo for)


Una istruzione del tipo for ... do ... end for è

detta iterativa o ciclo, in quanto permette di

ripetere l'esecuzione di alcune istruzioni per

un certo numero di volte

La struttura di iterazione

leggi a;

m = 1;

for a > 1 do

m = m * a;

a = a – 1;

End for

stampa m;

Struttura(e) che permette la

ripetizione dell’esecuzione di

istruzioni (o strutture) Unico punto di ingresso



for generale


L’elevamento a potenza


Utilizzando l’algoritmo prodotto(a,b) visto in precedenza vogliamo costruire l’algoritmo che costruisce l’elevamento a potenza di due numeri interi a e b.

Per fare questo sfrutto il fatto:

Algoritmo 4 potenza(int a, int b) int

1. Require: a>0,b>0

2. potenza 1

3. for b volte do

4. potenza prodotto(potenza, a)

5. end for

6. return prodotto

La divisione fra due numeri (1)


Supponiamo di avere a disposizione un calcolatore capace di fare solo la sottrazione di due numeri interi, e vogliamo costruire un algoritmo che divide il numero a per il numero b

Per tale calcolo, l'algoritmo conta quante volte b è contenuto in a

Algoritmo 5 divisione(int a, int b) int

1. Require: a>0, b>0, a>b

2. divisione 0

3. while a>b do

4. divisione divisione + 1

5. a a – b

6. end while

7. return divisione

La divisione fra due numeri (2)


Siano a=20 e b=6

Algoritmo 5 divisione(int a, int b) int

1. Require: a>0, b>0, a>b

2. divisione 0

3. while a>b do

4. divisione divisione + 1

5. a a – b

6. end while

7. return divisione

Inizialmente (linea 1) divisione

= 0

Quindi:

1. a = 20; b = 6 a > b

divisione = 1; a = 20 - 6 = 14

2. a = 14; b = 6 a > b

divisione = 2; a = 14 - 6 = 8

3. a = 8; b = 6 a > b divisione =

3; a = 8 - 6 = 2

4. a = 2; b = 6 a < b linea 6

Si restituisce il risultato

L’iterazione (ciclo while)


Una istruzione del tipo while ... do ... end while è

ancora una volta iterativa, ma differentemente dal

ciclo for, il numero di volte per cui alcune istruzioni

vengono ripetute dipende da una condizione

vero/falso

Il numero di iterazioni non è quindi noto a priori

come nel caso del ciclo for, ma dipende dal verificarsi

della condizione booleana

while generale


Componibilità delle strutture

leggi a;

if a > 0 then

m = 1;

while a > 1 do

m = m * a;

a = a – 1;

end while

else

m = 0;

End if

stampa m;

Ogni struttura può essere considerata come una singola istruzione. Possiamo allora combinarle in maniera gerarchica e comporle a piacimento per creare l’algoritmo.


Sequenza

Sele

zione

Itera

zione

27/03/2013

L’istruzione condizionale


Una istruzione del tipo if ... then ... else ... end if è

detta istruzione condizionale, in quanto regola

l'esecuzione dell'algoritmo al verificarsi di

determinate condizioni

if-elseif generale


Rappresentazioni di

algoritmo/programma

Pseudocodice

Simile a linguaggio (codice) di programmazione

leggi a;

if a > 0 than

m = 1;

while a > 1 do

m = m * a;

a = a – 1;

end while

else

m = 0;

End if

stampa m;

Diagramma di flusso (a blocchi)

Evidenzia graficamente il flusso

delle operazioni


Elementi (blocchi) del diagramma di

flusso

Si inizia sempre con un

(unico) blocco di inizio

Si termina sempre con un

(unico) blocco di fine

Nota: può anche essere chiamato

“flow chart” o “diagramma a

blocchi”

Blocco di elaborazione

Blocco di controllo

Nel mezzo c’è una

composizione di


Esercizi


Produrre lo pseudocodice e il digramma di flusso

dell’algoritmo misuraPressioneArteriosa.

Esercizio produrre pseudocodice e diagramma di flusso

del diagnosi di ipercolesterolemia familiare avente per

ingresso i parametri età, sesso, peso ed altezza e che

restituisce in uscita il valore vero o falso.

Complessità


Definizione: La complessità di un algoritmo si misura

(tipicamente) come il tempo di esecuzione dell'algoritmo,

in termini di numero di operazioni eseguite, in funzione

delle variabili in ingresso

Per la precisione, l'unità di misura della complessità è il

numero di istruzioni eseguite

Complessità (2)


Valutiamo la complessità dell'algoritmo che calcola il prodotto fra due numeri, contando il numero di istruzioni che esegue

Quando si parla di complessità, si ignorano le costanti (siano esse additive o moltiplicative) e si fa riferimento al solo termine di grado superiore

Quindi, affermiamo che l'algoritmo che calcola il prodotto fra due numeri ha complessità O(b)

Require: a>0, b>0

1. prodotto 0

2. for b volte do

3. prodotto

prodotto+a

4. End for

5. Return prodotto

Nel caso in esame, vengono

eseguite:

• Una volta la linea 1

• b volte la linea 3

• Una volta la linea 5

per un totale di 2+b linee di codice

eseguite

Perché valutare la complessità?


Valutare la complessità di un algoritmo è importante,

perché mi permette di capire che, ad esempio:

se voglio calcolare a=1, b = 3 O(3) passi

se invece voglio calcolare a=3, b = 120 O(120) passi !

La valutazione di complessità permette di valutare

l’efficienza di un algoritmo, ed eventualmente

individuare misure migliorative

La valutazione della complessità è quindi lo

strumento usato per l'analisi degli algoritmi

Il prodotto fra due numeri (migliorato)


Algoritmo 6 prodotto(int a, int b) int

Require a>0, b>0

1. prodotto 0

2. if a < b then

3. for a volte do

4. prodotto prodotto + b

5. end for

6. else

7. for b volte do

8. prodotto prodotto + a

9. end for

10. end if

11. return prodotto

Complessità


Valutiamo la complessità del nuovo algoritmo prodotto:

In sintesi, l'algoritmo ha complessità O(min{a,b})

prodotto ← 0

if a < b then

for a volte do

prodotto ← prodotto + b

end for

else

for b volte do

prodotto ← prodotto + a

end for

end if

return prodotto

Se a < b eseguiamo

l'istruzione 4 per a

volte, quindi è O(a)

Se a > b eseguiamo

l'istruzione 8 per b

volte, quindi è O(b)

Un algoritmo ricorsivo (1)


Un ulteriore esempio è il calcolo dei numeri di Fibonacci

Tale algoritmo prende in ingresso un numero intero n > 0

e restituisce in uscita il numero di Fibonacci 𝐹𝑛 così

definito

𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 𝑠𝑒 𝑛 > 3

1 𝑠𝑒 𝑛 = 1,2

𝐹1 = 1

𝐹2 = 1

𝐹3 = 𝐹2 + 𝐹1 = 2

𝐹4 = 𝐹3 + 𝐹2 = 3

Tale definizione è ricorsiva, in quanto il valore al passo n è

definito sulla base di uno (o più) passi precedenti



𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 𝑠𝑒 𝑛 > 3

1 𝑠𝑒 𝑛 = 1,2

Algoritmo 7 fibonacci(int n) int

Require: n > 0

1. if n = 1 or n = 2 then

2. return 1

3. else {caso generale}

4. return fibonacci(n-1) + fibonacci(n-2)

5. end if



Supponiamo di voler calcolare 𝐹5


Require: n > 0

1. if n = 1 or n = 2 then

2. return 1

3. else {caso generale}

4. return fibonacci(n-1) + fibonacci(n-2)

5. end if



Senza entrare nel merito della

dimostrazione, la complessità

di questo algoritmo è

estremamente elevata

Ad esempio, il calcolo di

fibonacci(58) su un Pentium IV

1700Mhz impiega ≈ 4 ore

Il motivo dipende dal fatto che

ripeto troppo spesso gli stessi

calcoli

Dall’algoritmo ricorsivo all’iterativo



Require: n > 0

1. a ← 1

2. b ← 1

3. c ← 1

4. for i = 3 to n do

5. c ← a + b

6. a ← b

7. b ← c

8. end for

9. return c

... non entriamo nella spiegazione del nuovo algoritmo

tuttavia, è interessante valutare la complessità di tale algoritmo per

metterla a confronto con quella del precedente

Complessità dell’algoritmo iterativo


Calcoliamo la complessità per l’algoritmo iterativo

Il numero totale di istruzioni eseguite è quindi

1 + 1 + 1 + (n - 2) + (n - 2) + (n - 2) + 1 = 3n - 2

La complessità dell'algoritmo è quindi O(n)

1. a ← 1

2. b ← 1

3. c ← 1

4. for i = 3 to n do

5. c ← a + b

6. a ← b

7. b ← c

8. end for

9. return c

• L'istruzione 1 è eseguita 1 volta



• L'istruzione 5 è eseguita n - 2 volte




Complessità a confronto


Per rendersi conto di come sono migliorate le cose:

Riassumendo


Un algoritmo è una soluzione formale ad un

problema

La progettazione di un algoritmo ha come scopo

quello di trovare una soluzione

L'analisi di un algoritmo ha come scopo quella di

valutare l'efficienza di una soluzione

La complessità è la «misura» dell‘efficienza di un

algoritmo

Algoritmi, programmazione strutturata e complessità APPLICATA E SISTEMI... · Algoritmi,...

Documents

Transcript of Algoritmi, programmazione strutturata e complessità APPLICATA E SISTEMI... · Algoritmi,...