ALGORITMI
Dal problema al programma
Definizione di algoritmo
I dati e le istruzioni
La rappresentazione degli algoritmi
La programmazione strutturata
Dal problema al programma
Esempio: ordinamento dei nomi degli studenti nel registro di classe
1.
PROBLEMA REALE: dato un insieme di nomi e cognomi,
organizzarli in ordine alfabetico.
2.
DATI: cognome e nome degli studenti.
3.
TECNICA DI ELABORAZIONE: l’insieme delle operazioni
necessarie per ordinare un generico insieme di nomi in ordine
alfabetico.
4.
USO DELL’ELABORATORE: dopo aver introdotto le operazioni
e i dati, codificati in modo opportuno, il computer può
eseguire automaticamente l’ordinamento dei nomi degli
studenti.
2
Le fasi principali della
programmazione



Lettura del testo del problema
Analisi dei dati di input e di output
(tabella dei dati)
Organizzazione dell’algoritmo risolutivo
(tabella di traccia per testare l’algoritmo)

Stesura del programma (codifica)

Prove di esecuzione del programma (test)
3
Le fasi principali della
programmazione



Lettura del testo del problema
Analisi dei dati di input e di output
(tabella dei dati)
Organizzazione dell’algoritmo risolutivo
(tabella di traccia per testare l’algoritmo)

Stesura del programma (codifica)

Prove di esecuzione del programma (test)
4
Cos’è un algoritmo?
Un algoritmo è una sequenza di passi che devono essere eseguiti secondo un
ordine prefissato per arrivare al risultato partendo da dati noti.



Un algoritmo deve fornire la soluzione di un problema indipendentemente
dal linguaggio di programmazione che si utilizzerà per scrivere il
programma finale.
Il termine algoritmo si fa derivare dal nome del matematico arabo AlKhuwarizmi, vissuto nel IX secolo, ed è quindi un concetto che è sempre
stato utilizzato nella matematica come sinonimo di metodo per la
risoluzione di un problema generale.
Esempi di algoritmi che applichiamo per la soluzione di problemi di vita
quotidiana sono:




le istruzioni di uso di un elettrodomestico
la sequenza di passi da seguire per compilare un modulo
la realizzazione di una ricetta di cucina
ecc.
5
Esempio di algoritmo
Per descrivere in modo corretto un algoritmo è importante aver chiaro
qual è l’obiettivo da raggiungere, ossia i risultati da ottenere.
Esempio
per ottenere un buon piatto di pasta bisogna aver chiare tutte le informazioni
di partenza:
• il tipo di pasta (fa variare il tempo di cottura),
• il numero di persone che dovranno mangiare la pasta, per determinare la
quantità di pasta e, di conseguenza, la quantità di acqua e di sale.
La risoluzione del problema è data dai seguenti passi:
1. far bollire la quantità di acqua stabilita
2. aggiungere la quantità di sale stabilita
3. mettere nell’acqua bollente la quantità di pasta stabilita
4. far cuocere la pasta per i minuti stabiliti
6
Un algoritmo deve essere ....




FINITO: un algoritmo deve essere composto da un numero finito di passi
e deve presentare un punto di inizio e uno di fine, raggiunto il quale si
interrompe l’esecuzione delle operazioni.
DETERMINISTICO: l’algoritmo a fronte degli stessi dati di input deve
produrre gli stessi risultati (es. l’istruzione “moltiplica 2x5” produce sempre
il medesimo risultato, mentre l’istruzione “tira una freccia contro il
bersaglio” può avere risultati diversi anche se è rivolta al medesimo arciere
munito del suo solito arco).
NON AMBIGUO: i passi che compongono l’algoritmo devono essere
interpretati in modo univoco dall’esecutore, senza lasciar dubbi (es. “se il
numero è abbastanza grande allora dividilo per 3”  istruzione ambigua!)
REALIZZABILE: è necessario che esista un esecutore in grado di eseguire
ogni passo dell’algoritmo ed in un tempo finito (es. “calcola tutte le cifre
decimali di π ” non avrà mai fine in quanto tali cifre sono infinite).
7
Elementi fondamentali di un
algoritmo
1) dati iniziali e finali: sono gli elementi che vengono elaborati dall’algoritmo
(dati iniziali o di input) e i risultati prodotti dall’algoritmo (dati finali o di output).
Es. nell’algoritmo dell’addizione, i dati iniziali sono gli addendi, il dato finale è la
somma.
2) sequenza di azioni (istruzioni o passi elementari): un’azione è
un’istruzione (operazione elementare) che deve essere eseguita sui dati in
ingresso per ottenere i dati in uscita.
3) esecutore: è il soggetto che compie le azioni, cioè legge le istruzioni, le
interpreta e le esegue.
Le istruzioni quindi devono essere scritte in modo che l’esecutore possa
comprenderle ed eseguirle correttamente.
DATI DI
INPUT
ALGORITMO +
ESECUTORE
DATI DI
OUTPUT
8
I DATI
 Dati di INPUT: sono quelli che devono essere forniti dall’esterno per poter
risolvere il problema.
 Dati di OUTPUT: sono quelli che vengono comunicati all’esterno come
risultato della soluzione del problema.
 Dati INTERNI o di LAVORO: sono i dati utilizzati nella trasformazione
compiuta dall’algoritmo ma trasparenti all’utente (non sono forniti in output).
 Dati NUMERICI: dati che contengono numeri e sui quali si possono
effettuare operazioni aritmetiche. Possono essere ulteriormente suddivisi in:
 INTERI: dati numerici che non prevedono cifre decimali
 REALI: dati numerici che prevedono cifre decimali
 Dati ALFANUMERICI (o STRINGHE): sono i dati che contengono caratteri
alfabetici (A,B,...), caratteri speciali ($,%,&,...) e cifre (0,1,2,...) sulle quali
non sono possibili operazioni aritmetiche (ad esempio il codice fiscale).
9
DATI Costanti e Variabili


COSTANTE: il valore del dato rimane immutato durante l’esecuzione
dell’algoritmo
VARIABILE: il valore del dato può cambiare durante l’esecuzione
dell’algoritmo
Ad esempio: dobbiamo calcolare l’area di un cerchio di cui si conosce il raggio.
I dati su cui opera l’algoritmo sono: raggio, π, area
e l’istruzione da eseguire è: area = raggio * raggio * π
π è una costante, infatti il suo valore non deve cambiare
area e raggio sono delle variabili: il loro valore cambia in funzione del
particolare cerchio che si prende in considerazione.
Il concetto di variabile è molto importante nella definizione degli algoritmi:
una variabile è caratterizzata da un nome e dal tipo (numerico o stringa) del
dato che andrà a contenere.
10
Le ISTRUZIONI



LETTURA: assegna ad una variabile un valore immesso tramite la tastiera del
computer.
 leggi (raggio) : se dalla testiera è stato digitato 5, la variabile raggio
conterrà il valore 5
SCRITTURA: permette di visualizzare sul monitor del computer o sulla
stampante un messaggio o il valore di una variabile.
 scrivi (“benvenuto”) : visualizza sul video il messaggio scritto tra apici
 scrivi (raggio) : visualizza sul video il contenuto della variabile raggio,
ossia se raggio ha valore 5, sul video sarà visualizzato 5.
ASSEGNAZIONE: assegna un valore ad una variabile. Per indicare questa
operazione si usa il simbolo = o una freccia 
1)raggio = 5 : alla variabile raggio è assegnato il valore 5
2) raggio = R : alla variabile raggio viene assegnato il valore di un’altra
variabile di nome R
3) raggio = (R + 5)*2 : alla variabile raggio viene assegnato il risultato di
11
una espressione
La rappresentazione degli
algoritmi: il flow-chart



Per poter descrivere un algoritmo non è necessario conoscere
un linguaggio di programmazione; la sequenza delle istruzioni
può essere rappresentata con un linguaggio semiformale
mediante i diagrammi a blocchi che consentono all’utente di
seguire il flusso dell’esecuzione delle istruzioni, per questo
motivo questi diagrammi sono chiamati diagrammi di flusso o
flow-chart.
I flow-chart sono formati da SIMBOLI di forma diversa, ciascuno
con il proprio significato, all’interno di ogni simbolo è presente
un breve testo.
Le LINEE con FRECCE che uniscono i vari simboli indicano il
flusso delle operazioni.
12
I simboli dei flow-chart
INIZIO
FINE
questi simboli indicano il punto di partenza e
di terminazione dell’algoritmo
è il simbolo dell’elaborazione e contiene l’istruzione da
eseguire
è il simbolo per le operazioni di Input / Output
F
condizione
V
è il simbolo di decisione ed è usato per stabilire
se una proposizione è vera (V) o falsa (F)
13
INIZIO
Un esempio
raggio
I
INIZIO
F
raggio
I
raggio = 0
area = raggio * raggio * π
V
area = 0
area = raggio * raggio * π
area
O
area
FINE
O
FINE
14
ALGORITMO
Successione finita di istruzioni ciascuna
delle quali rappresenta un’operazione da
eseguire per risolvere un problema.
Occorre definire un insieme di regole e di linee guida
per organizzare il lavoro di creazione di un algoritmo
15
La programmazione strutturata

Un metodo per realizzare algoritmi:


l’algoritmo viene visto come un insieme di blocchi
di istruzioni ognuno fornito di un solo ingresso e di
una sola uscita;
ogni blocco è isolato dagli altri (non è possibile
saltare dall’interno di un blocco all’interno di un
altro).
16
Teorema di Böhm-Jacopini
Qualsiasi algoritmo può essere scritto utilizzando
esclusivamente le tre strutture di controllo
fondamentali:
SEQUENZA – SELEZIONE - ITERAZIONE
N.B. sono nomi equivalenti:
Selezione = Alternativa
Iterazione = Ripetizione
17
Struttura di sequenza
istruzione1
istruzione2
istruzione3
18
Struttura di selezione
F
istruzione1
condizione
V
istruzione2
19
Struttura di iterazione

Si deve eseguire un blocco di istruzioni
finché non si verifica una determinata
condizione.
Esempio: costruire un algoritmo che dati
in input 5 numeri ne determini la somma
20
Esempio: pseudocodice
Sequenza
INIZIO
Leggi (N1)
Leggi (N2)
Leggi (N3)
Leggi (N4)
Leggi (N5)
Somma  N1+N2+N3+N4+N5
Scrivi (Somma)
FINE

Iterazione
INIZIO
Somma  0
Conta  0
ESEGUI
Leggi (N)
Somma  Somma+N
Conta  Conta+1
RIPETI FINCHÉ Conta = 5
Scrivi (Somma)
FINE

21
Esempio: flow-chart
INIZIO
Somma  0
Conta  0
leggi (N)
Somma  Somma + N
Conta  Conta + 1
F
Conta = 5
V
scrivi (Somma)
FINE
22
Azioni comuni negli algoritmi (I)

Contare: nell’esempio abbiamo usato una sola
variabile per richiedere i numeri (N) 
dobbiamo “contare” quanti numeri stiamo
inserendo!
 variabile contatore di tipo numerico (cont)
 inizializzazione (cont = 0)
 incremento (cont = cont + 1)
23
Azioni comuni negli algoritmi (II)

Totalizzare: nell’esempio abbiamo usato la
variabile Somma che è stata aggiornata ogni
volta che si leggeva un numero  alla fine
dell’iterazione Somma contiene il valore della
somma totale dei 5 numeri!



variabile totalizzatore di tipo numerico (totale)
inizializzazione (totale = 0)
incremento (totale = totale + x)
24
Struttura di iterazione postcondizionale
istruzioni
F
La condizione è un’espressione
che rappresenta un valore Vero
o Falso.
Il ciclo viene ripetuto finché
l’espressione non diventa vera.
condizione
V
25
Struttura di iterazione precondizionale
condizione
V
F
La condizione è un’espressione
che rappresenta un valore Vero
o Falso.
Il ciclo viene ripetuto finché
l’espressione non diventa falsa.
istruzioni
26
Confronto tra le strutture di iterazione
Iterazione Finché (Until)
istruzioni
F
Iterazione Mentre (While)
condizione
F
V
condizione
istruzioni
V
27
Le iterazioni in Visual Basic.net
L’istruzione Do...Loop...
Iterazione postcondizionale:
Do
istruzioni
(pag. 155 del libro)
Iterazione precondizionale:
Do While condizione
istruzioni
Loop Until condizione
Loop
Do
Do Until condizione
istruzioni
Loop While condizione
istruzioni
Loop
28
Codifica esempio
“somma di 5 numeri”
Dim N As Integer
Dim Somma As Integer = 0, Conta As Byte = 0
Do
N = InputBox (“inserisci un numero”)
Somma = Somma+N
Conta += 1
‘equivale a scrivere Conta=Conta+1
Loop Until Conta = 5
MessageBox.Show (“La somma dei 5 numeri è: “ & Somma)
in alternativa:
Do While Conta < 5
N = InputBox (“inserisci un numero”)
Somma = Somma+N
Conta += 1
‘equivale a scrivere Conta=Conta+1
Loop
MessageBox.Show (“La somma dei 5 numeri è: “ & Somma)
29