La formalizzazione dell’informazione:

Dati e Diagrammi di Flusso

Codifica degli algoritmi

Algoritmo formulato per essere comunicato tra esseri

umani – chiaro, sintetico e intuitivo – codificato in linguaggi informali o semi-formali (linguaggio

naturale, diagrammi di flusso, …)

Algoritmo formulato per essere eseguito

automaticamente – preciso ed eseguibile – codificato in linguaggi formali comprensibili dagli esecutori

automatici (linguaggio macchina o linguaggio di programmazione di alto livello)

- 2 -

Algoritmo = dati + istruzioni

Composto da

- 3 -

Dati

Iniziali

Dati

Finali

(soluzione)

Algoritmo

Dati Istruzioni che operano sui dati

Dati e istruzioni

Tipi di dati – Numeri naturali, interi, reali (1, -2, 0.34) – Caratteri alfanumerici (A, B, -,^,3) – Dati logici o booleani (Vero, Falso) – Array o vettori di n elementi ({1,2,3}) – Matrici di mxn elementi ( 1 2 3 4 5 6 )

Istruzioni – Operazioni di Input/Output (es. leggi, scrivi) – Operazioni Aritmetico-logiche (es. max = A + B) – Strutture di controllo (es. SE, RIPETI )

- 4 -

Criteri di classificazione dei dati

Visibilità da parte dell’utente – visibile (di ingresso o uscita) – trasparente (dati temporanei di supporto)

Variabilità nel tempo – costanti – variabili (acquisizione dall’esterno o assegnazione)

Struttura – elementari o scalari (interi, alfanumerici, booleani, …) – strutturati (array, matrici, …)

- 5 -

Operazioni elementari

Operazioni aritmetiche e assegnamenti di valori a singole

variabili – Es. C (A + B)

Condizioni sul valore di singole variabili – se (A > B) allora … altrimenti …

Lettura e scrittura di variabili – “Leggi A” oppure “Stampa B”

- 6 -

Rappresentazione degli Algoritmi

1. Linguaggio naturale

2. Diagramma di flusso

3. Pseudo-codice

4. Linguaggio di programmazione

- 7 -

Rappresentare gli algoritmi

- 8 -

Linguaggio naturale

- Sollevare il ricevitore

- Attendere il segnale di linea libera

- Comporre il numero

- …

Pseudo codice Input A,B

Tot 0

While A!=0 Do

Tot Tot + B

A A – 1

Output Tot

Ling. programmazione

#include <stdio.h>

Int main (void){

puts(“ciao mondo!”);

return Exit_success;

}

DF

Sì

Passo P1

Inizio

Lettura

a e b

c a – b

c> 0? No

Scrittura

“max è a”

Scrittura

“max è b”

Passo P2

Fine

Passo P0

Diagrammi di flusso

- 9 -

Inizio Fine Operazioni di ingresso/uscita

Sìpredicato

No

Elaborazione Selezione a due vie Sottoprogramma

Diagrammi di flusso

I blocchi sono collegati fra loro da archi orientati:

– L’arco identifica la sequenza delle operazioni

– La freccia identifica il flusso della esecuzione

I circoletti indicano la ricongiunzione di

diversi ‘percorsi’, MAI una biforcazione (lo fa la

selezione a due vie)

- 10 -

SI’ NO

Il maggiore fra 2 numeri interi x, y

Algoritmo max

1. Leggi i valori di x e y dall’esterno

2. Calcola la differenza d fra x e y (d=x-y)

3. Se d è maggiore di 0 vai al passo 5 altrimenti prosegui in

sequenza

4. Stampa ‘il massimo è …’ seguito dal valore di y e vai a 6

5. Stampa ‘il massimo è …’ seguito dal valore di x

6. Termina l’esecuzione

- 11 -

Diagramma di Flusso di max

- 12 -

d > 0 ?

Inizio

Fine

Leggi x e y

d = x - y

Scrivi ‘max è x’ Scrivi ‘max è y’

Si No

Diagramma di Flusso di max

- 13 -

d > 0 ?

Inizio

Fine

Leggi x e y

Si No

d = x - y

Scrivi ‘max è x’ Scrivi ‘max è y’

Passo 1

Passo 2

Passo 3

Passo 5 Passo 4

Passo 6

Determinare il massimo fra N numeri interi

Algoritmo max_N

1. Leggi il valore di N dall’esterno

2. Leggi i primi due numeri

3. Trova il maggiore m fra i primi due numeri (con max)

4. Finchè (hai esaminato meno di N numeri)

a. Leggi un nuovo numero x

b. Trova il maggiore fra m e x con l’algoritmo max

c. Assegna il valore del maggiore a m

5. Stampa ‘il massimo è…’ ed il valore di m e termina

- 15 -

Supponiamo N fissato

sottoprogramma

DF per il massimo di N numeri (versione 1)

- 16 -

Ancora numeri

da esaminare ?

Inizio

Fine

Leggi i primi due numeri x1 e x2

e memorizzali nelle variabili a e b

Si No

m = max(a,b)

Leggi il nuovo numero in a Scrivi ‘max è m’

m = max(a,m)

DF e programmi (1)

I DF sono un primo passo verso la formalizzazione di un

algoritmo in modo non ambiguo

Per ottenere una codifica interpretabile direttamente

dalla macchina dobbiamo però specificare molti più

dettagli: – trasformare tutte le ‘frasi’ in variabili e modifiche su di

esse:

• es : ‘ancora numeri da esaminare’ deve essere

tradotto in qualcosa di calcolabile dalla macchina

usando solo le operazioni elementari

- 17 -

DF per il massimo di N numeri (versione 2)

- 18 -

I = 2

I < N

Inizio

Fine

Leggi N e i primi due numeri a e b

Si No

m = max(a,b)

Leggi il nuovo numero in a Scrivi ‘max è m’

m = max(a,m)

I = I + 1

Supponiamo N >= 2

DF e programmi (2)

Per ottenere una codifica interpretabile direttamente

dalla macchina dobbiamo anche :

– decidere come codificare l’informazione

• non banale in esempi più complessi del nostro, ad

esempio se voglio codificare un’immagine o un

video

– scrivere il tutto con una codifica ‘leggibile’ dalla macchina

• … ma la macchina lavora molto a basso livello

(linguaggio macchina, codificato mediante bit) !!!!

- 19 -

DF e programmi (3)

… soluzione…. – usare linguaggi di ‘livello’ più alto (linguaggi di

programmazione ad alto livello) – usare dei programmi appositi per far tradurre i nostri

programmi in linguaggio macchina (i compilatori)

Importante: – I tipici linguaggi (C, Java, Fortran, Basic…) permettono di

definire sequenze di operazioni e strutture di controllo del tutto analoghe a quelle contenute nei diagrammi di flusso che abbiamo visto finora

- 20 -