LABORATORIO DI INFORMATICACorso di laurea in Scienze della Formazione Primaria

a.a.2014/2015

A cura del Prof. Sergio Miranda

LEZIONE N.6Algoritmi2

Laboratorio di Informatica

GLI ALGORITMI (1/5)

Un algoritmo è una sequenza di istruzioni la cui

esecuzione consente di realizzare un particolare

trattamento dell’informazione o più in generale di

risolvere uno specifico problema:

Calcolare la somma di due numeri

Calcolare la lunghezza dell’ipotenusa di un triangolo

rettangolo

Risolvere una equazione di secondo grado

Una ricetta di cucina

Le istruzioni per montare un mobile

…

3

Laboratorio di Informatica

IL TERMINE ALGORITMO DERIVA

DA …

4

Laboratorio di Informatica

GLI ALGORITMI (2/5)

Un algoritmo presuppone la presenza di qualcuno (o qualcosa) in grado di eseguirlo: l’esecutore (in informatica è il calcolatore) Ogni esecutore ha il suo modello di elaborazione ed il suo

ciclo di esecuzione: Es. Macchina di Turing, Macchina di Von Neumann

L’algoritmo viene letto dall’esecutore il quale, partendo dai dati in input, esegue, in un ben preciso ordine, le istruzioni in esso riportate giungendo, al termine, a ottenere i dati in output

Per essere eseguito, l’algoritmo deve essere formulato in un linguaggio comprensibile dall’esecutore

Un esecutore può eseguire un algoritmo formulato in un linguaggio che non conosce a patto che l’algoritmo stesso sia preventivamente tradotto in un linguaggio che invece gli è noto 5

Laboratorio di Informatica

UN ESEMPIO DI

ALGORITMO

Procedura per fare la frittata

6

Laboratorio di Informatica

GLI ALGORITMI (3/5)

L’algoritmo deve prevedere soltanto istruzioni elementari, che richiedono all’esecutore la conduzione di operazioni elementari (operazioni che egli sa compiere senza bisogno di ulteriori specificazioni)

Un algoritmo può richiedere l’esecuzione di altri algoritmi precedentemente specificati all’esecutore

L’algoritmo deve essere formulato in un linguaggio non ambiguo, in cui cioè ogni istruzione caratterizzi univocamente una delle operazioni che l’esecutore è in grado di compiere

L’algoritmo deve specificare senza ambiguità l’ordine di esecuzione delle istruzioni cui l’esecutore deve attenersi scrupolosamente 7

Laboratorio di Informatica

8

Area di una campana (1)

h2

h1

B

r=b/

2

b

Problema

h2b

h1

B

Sottoproblema 1

Sottoproblema 2

Sottoproblema 3

soluzione elementare:

s = ½ r 2

soluzione

elementare:

s = b h 2

r

Scomposizione del

problema in tre

sottoproblemi

soluzione

elementare:

s = ??

soluzione

elementare:

s = ??

8

Laboratorio di Informatica

9

Area di una campana (2)

Sottoproblema 3h1

bh1

½ (B–b)

h1

½ (B–b)

Sottoproblema 3.1

soluzione

elementare:

s =½ (½(B–b) h1)

Sottoproblema 3.2soluzione

elementare:

s = b h1

soluzione effettiva:

s = ½ (½(B–b) h1) +

b h1 +

½ (½(B–b) h1)Sottoproblema 3.3

soluzione

elementare:

s =½ (½(B–b) h1)

Scomposizione del sottoproblema 3

in tre ulteriori sottoproblemi

Composizione delle soluzioni dei tre

sottoproblemi 3.1, 3.2 e 3.3 per

risolvere il sottoproblema 3

h1

B

b

9

Laboratorio di Informatica

1

0

Area di una campana (3)

h2

h1

B

r=b/

2

b

Problema

h2b

h1

B

Sottoproblema 1

Sottoproblema 2

Sottoproblema 3

soluzione elementare:

s = ½ r2

soluzione

elementare:

s = b h2

r

soluzione effettiva:

s = ½ (½(B–b) h1) +

b h1 +

½ (½(B–b) h1)

soluzione effettiva:

s = ½ r2 +

b h2 +

½ (½(B–b) h1) +

b h1 +

½ (½(B–b) h1)

Composizione delle

soluzioni dei tre

sottoproblemi 1, 2 e

3 per risolvere il

problema originario

10

Laboratorio di Informatica

GLI ALGORITMI (4/5)

L’algoritmo deve essere formulato in un numero

finito di istruzioni

L’esecuzione di un algoritmo deve terminare

fornendo i dati in output in un tempo finito

L’algoritmo deve essere deterministico:

eseguendo lo stesso algoritmo più volte sugli

stessi dati di input, l’esecutore deve generare

sempre gli stessi dati di output

08

/06

/201

5

11

Dott. F

ran

cesco

Orciu

oli

Laboratorio di Informatica

GLI ALGORITMI (5/5)

Un algoritmo parametrico è un algoritmo che,

facendo riferimento ai dati di input

È in grado di risolvere non un solo problema ma una

classe di problemi

Algoritmo per risolvere 12 + 24

Algoritmo parametrico per risolvere X + Y dove X e Y

possono essere rimpiazzati da qualsiasi numero

X e Y si dicono variabili e funzionano come registri di

memoria nei quali si possono scrivere e leggere dati

08

/06

/201

5

12

Dott. F

ran

cesco

Orciu

oli

Laboratorio di Informatica

LE VARIABILI

Sono contenitori

Occorre stabilire che tipo di «contenuto» possono

contenere

Il tipo di contenuto è fisso

Il loro contenuto può variare

Le variabili contengono dati

Il «senso» che le fa diventare informazioni si

aggiunge con la programmazione…

08/0

6/2

015

13

Pro

f. Serg

io M

iran

da