Algoritmo
• Obiettivo: dato un problema
– definire un procedimento che possa essere
eseguito automaticamente da un esecutore per
risolvere il problema
Definizione di Algoritmo
Dato un problema e un esecutore, l’algoritmo è:
• una successione finita di passi elementari (operazioni
e direttive)
• eseguibili senza ambiguità dall’esecutore
• che risolve il problema dato
Proprietà degli Algoritmi
• Procedimenti sequenziali: un passo dopo l’altro
secondo un ordine specificato (flusso di
esecuzione)
• I passi elementari devono essere eseguiti in modo
univoco dall’esecutore
– devono essere descritti in una forma eseguibile per
l’esecutore
• La descrizione di un algoritmo per un esecutore deve
avere una formulazione generale
– la soluzione individuata non deve dipendere solo da
valori predefiniti dei dati, cosi che l’algoritmo sia
utilizzabile nel maggior numero possibile di casi
– gli algoritmi prevedono particolari passi destinati ad
acquisire i valori dei dati da utilizzare ed elaborare in
ogni particolare esecuzione
• L’esecutore deve terminare in tempo finito per ogni
insieme di valori in ingresso
• L’esecutore deve essere in grado di eseguire
l’algoritmo con le risorse a sua disposizione
(informazioni + tecnologia)
Proprietà degli Algoritmi
Ogni operazione o direttiva deve:
• terminare entro un intervallo finito di tempo
– Es.: calcolare le cifre decimale di , NO!
• produrre un effetto osservabile (stato prima
dell’esecuzione, stato dopo l’esecuzione)
– Es.: pensare al numero 5, NO!
• Produrre lo stesso effetto ogni volta che viene
eseguita a a partire dalle stesse condizioni iniziali
– Es. X=5, y=10  x+y=15
Elementi degli Algoritmi
• Oggetti: le entità su cui opera l’algoritmo
– Dati iniziali del problema, informazioni ausiliarie, risultati
parziali e finali
– Le informazioni sono dette dati (anche i risultati parziali e
finali) e possono essere variabili o costanti
• Operazioni: Interventi da effettuare sui dati
– Calcoli, confronti, ricopiature,acquisizioni, emissioni, ecc.
• Flusso di controllo: l’indicazione delle possibili
successioni dei passi dell’algoritmo
– La correttezza dei risultati dipende non solo dalla corretta
esecuzione delle singole operazioni, ma anche dalla
corretta sequenza con cui sono eseguite
NOTA:
–
–
Flusso di controllo: la descrizione a priori di tutte le possibili
sequenze nell’esecuzione dei passi dell’algoritmo, in particolare
di operazioni in alternativa e di operazioni da ripetere più volte
ciclicamente
Flusso di esecuzione: la sequenza di operazioni effettivamente
seguita durante una particolare esecuzione dell’algoritmo e che
dipende dai particolari valori che i dati assumono in
quell’esecuzione
Rappresentazione di un algoritmo destinato
all’esecuzione automatica
• Rappresentazione di un algoritmo
– Descrizione, univoca per l’esecutore, di tutte le
possibili sequenze di operazioni da eseguire per
risolvere il problema dato
– Descrizione del flusso di controllo, delle
operazioni eseguibili, e degli oggetti su cui
agiscono le singole operazioni
• E’ necessario un formalismo di rappresentazione,
cioè un linguaggio costituito da:
– Vocabolario: insieme di elementi per la descrizione
di oggetti, operazioni e flusso di controllo
– Sintassi: insieme di regole di composizione degli
elementi in frasi eseguibili e costrutti di controllo
(istruzioni)
– Semantica: insieme di regole per l’interpretazione
degli elementi e delle istruzioni sintatticamente
corrette
Linguaggi di descrizione di algoritmi
• Formalismi descrittivi costituiti da LINGUAGGI
(artificiali) DI PROGRAMMAZIONE
• Oggetti rappresentati tramite nomi simbolici
(identificatori)
– Variabile: una rappresentazione simbolica dei
dati a cui si possono attribuire diversi valori di un
certo tipo
• Operazioni rappresentate mediante operatori (es.
+) o funzioni (es. cos(x))
• Sequenza di operazioni (flusso di controllo)
con appositi costrutti di controllo
Corrispondenza tra concetti e loro rappresentazione nei
linguaggi di rappresentazione
CONCETTO
oggetto
operazione
direttiva
flusso di controllo
algoritmo
RAPPRESENTAZIONE
identificatore
operatore, funzione
istruzione
costrutti di controllo
programma
Linguaggi di descrizione
• I linguaggi per descrivere gli algoritmi devono essere
noti all’uomo che progetta gli algoritmi e al calcolatore
che deve eseguirli
• Fasi iniziali di progetto: struttura generale dell’algoritmo
– descrizione rigorosa del flusso di controllo
– descrizione semplificata delle direttive, per es.
mediante l’uso di linguaggio naturale
• Due esempi di linguaggi semiformali:
– schemi a blocchi (o diagrammi di flusso)
• elementi grafici per indicare il flusso di controllo e
i tipi di operazioni
• elementi testuali per descrivere le operazioni e gli
oggetti
– pseudo-codice
• completamente testuale
• costrutti di controllo descritti con la forma e le
parole chiave dei linguaggi di programmazione
• le operazioni possono essere descritte in modo
informale
Schemi a Blocchi
Elementi di base
• Blocco esecutivo
operazione
• Blocco di inizio
Inizio
• Blocco di terminazione
Fine
• Flusso di controllo delle operazioni
• Blocco condizionale
• Blocco di ingresso dati
• Blocco di uscita dati
vera
Condizione
falsa
Operazione di ingresso
Operazione di uscita
Schemi a blocchi
• Variabili: rappresentate tramite nomi simbolici
– Le operazioni descritte possono essere eseguite di
volta in volta sui diversi valori assegnabili alle
variabili (formulazione generale)
• Variabile: contenitore di valori
– Proprietà: una variabile non può essere vuota,
cioè ad una variabile è sempre associato un
valore
• Negli schemi a blocchi operazioni e condizioni
sono rappresentate in modo testuale e tramite
simboli che rappresentano gli operatori aritmetici, di
confronto, ecc.
Regole di composizione ed
interpretazione degli elementi
Composizione degli elementi
flusso di controllo dell’algoritmo, cioè tutte le possibili
sequenze di blocchi da eseguire
• Un solo blocco di inizio
• Almeno un blocco di terminazione
• Dal blocco di inizio e da ogni blocco esecutivo deve
uscire una sola freccia
– Se per ogni blocco c’e’ un solo blocco successivo: flusso
di controllo sequenziale (sequenza)
Inizio
operazione
• Da ogni blocco condizionato devono uscire due frecce
contrassegnate dalle indicazioni vero (si) e falso (no)
vera
Condizione
falsa
Regole di composizione ed
interpretazione degli elementi
• Il flusso di controllo non è più sequenziale se
dopo un blocco si possono presentare diverse
alternative. In questo caso si usa un blocco di
selezione
• Dal blocco di selezione escono due frecce che
devono essere contrassegnate dal valore vero
o falso.Il successivo blocco da eseguire
dipende dal valore della condizione
vera
Condizione
operazione1
falsa
operazione2
• In tutti i casi -in esecuzione- è unica la scelta
del blocco successivo da eseguire
vera
Condizione
operazione1
falsa
operazione2
Esempio
Prodotto di due numeri interi positivi
Diagramma di flusso con direttive in italiano
Inizio
Leggi(W)
Leggi(Y)
Moltiplica intero W
per intero Y e denota
il risultato con Z
Scrivi (Z)
Fine
Acquisizione dall’utente dei particolari
valori da considerare per i due fattori
del prodotto e da assegnare alle
variabili W e Y
Operazioni di elaborazione, valide per
qualsiasi valore dei dati
Emissione all’utente del risultato
dell’elaborazione
Variabili W, Y, Z intere
W, Y, fattori di ingresso
Z risultato in uscita
Operatori ed espressioni
• Operatori aritmetici: +, -, , /, ...
– agiscono sugli operandi (variabili o costanti)
– producono un valore numerico
• Operatori di confronto: >, =, <, …
– agiscono sugli operandi (variabili o costanti)
– producono un valore logico (vero o falso)
• Funzioni: cos(x), log(x), …
– agiscono su valori detti parametri (variabili oppure
costanti)
– producono un valore
• Procedure: Leggi(X), Scrivi(N), …
– agiscono su valori detti parametri
– effettuano operazioni
• Espressione: 5+cos(Y), ...
– composizione di operatori, funzioni, variabili e
costanti
– ad essa è associato un valore
• Assegnamento: X := 6, Y := X, Z := X+6, ...
– Il valore dell’espressione a destra dell’operatore di
assegnamento è assegnato alla variabile a sinistra
Esempio 2
Prodotto di due interi tramite somme
ripetute
• Algoritmo: somma W a se stesso tante volte
quanto vale Y
• Variabili:
– W,Y intere (valori in ingresso)
– Z intera (valore in uscita)
• Variabili ausiliari:
– NS intera (contatore del numero di somme
ancora da eseguire)
– SP intera (valore della somma parziale)
Schema a Blocchi con ciclo a condizione
finale (l’algoritmo è corretto se Y>0)
Inizio
Leggi(W)
Acquisizione dei dati in ingresso e
attribuzione dei loro valori a W e Y
Leggi(Y)
SP:=0
Inizializzazione delle variabili ausiliarie
NS:=Y
SP:=SP+W
Corpo del ciclo
NS:=NS-1
NS>0
si
Valutazione della condizione di
uscita dal ciclo
no
Z:=SP
Scrivi (Z)
Fine
Emissione del risultato
Flusso di controllo ciclico
• Permette di esprimere l’iterazione di un insieme
di istruzioni (corpo del ciclo)
• Il corpo del ciclo è ripetuto un numero finito di
volte
• La ripetizione è controllata dalla valutazione
della condizione di permanenza del ciclo
• variabile di controllo del ciclo
– inizializzata prima di entrare nel ciclo
• condizione di permanenza
– funzione della variabile di controllo
• corpo del ciclo
– contiene la modifica della variabile di controllo
• CICLO A CONDIZIONE FINALE
• CICLO A CONDIZIONE INIZIALE
Schema a blocchi con ciclo a condizione iniziale
(l’algoritmo è corretto per Y>=0)
Inizio
Leggi(W)
Leggi(Y)
SP:=0
NS:=Y
no
SP:=SP+W
si
SP:=SP+W
NS:=NS-1
NS>0
no
Z:=SP
Scrivi (Z)
Fine
NS>0
si
NS:=NS-1
Algoritmo con esecutore calcolatore
per l’esempio precedente
(ciclo a condizione finale)
main ()
{
int w,y,z,sp,ns;
/*dichiarazione delle variabili */
leggi(w);
leggi(y);
sp=0;
ns=y;
/*inizializzazione*/
/*inizializzazione*/
/*ciclo a condizione finale: l’algoritmo e’
corretto solo nell’ipotesi y>0 */
do
{
sp=sp+w;
ns=ns-1;
}while (ns>0);
z=sp;
scrivi (z);
}
Algoritmo con esecutore calcolatore
per l’esempio precedente
(ciclo a condizione iniziale)
main ()
{
int w,y,z,sp,ns;
/*dichiarazione delle variabili */
leggi(w);
leggi(y);
sp=0;
ns=y;
/*inizializzazione*/
/*inizializzazione*/
/*ciclo a condizione iniziale: l’algoritmo
e’ corretto solo nell’ipotesi y>=0 */
while (ns>0)
{
sp=sp+w;
ns=ns-1;
}
z=sp;
scrivi (z);
}
Raffinamenti Successivi
• Nelle prime fasi di progetto si trascurano i dettagli
• Man mano che il progetto evolve si conosce
meglio il problema
• Uno dei raffinamenti tipici:
VERIFICA DEI DATI IN INGRESSO
– L’utente può commettere errori nell’immissione dei
dati
– si verifica che i dati immessi siano accettabili
rispetto alle ipotesi di correttezza dell’algoritmo
– Esempio precedente: l’algoritmo non fornisce
valori corretti per valori negativi di Y
– Y >= 0 ?
ESEMPIO: verifica dei dati in ingresso
Ipotesi: l’algoritmo
non calcola il prodotto
nei casi in cui Y è < 0
Inizio
Leggi(W)
Leggi(Y)
si
Y>=0
Scrivi: “Secondo fattore
Negativo”
SP:=0
NS:=Y
no
no
NS>0
si
SP:=SP+W
NS:=NS-1
Z:=SP
Scrivi (Z)
Fine
Flusso di controllo condizionale
• Costrutto di selezione semplice
– Si utilizza quando alcune operazioni possono essere o
non essere eseguite, in dipendenza del verificarsi di
una condizione
– Si esprime tramite un un blocco condizionale. Lungo
uno dei due rami uscenti sono collocati i blocchi che
descrivono le operazioni da eseguire; l’altro riguarda
le operazioni da non eseguire
• Costrutto di selezione doppia
– Si utilizza quando, in dipendenza del verificarsi di una
condizione, si devono eseguire operazioni alternative
– Si esprime tramite un blocco condizionale. Lungo uno
dei due rami uscenti sono collocati i blocchi che
descrivono le operazioni da eseguire in un caso; l’altro
riguarda le operazioni da eseguire in alternativa
Ipotesi: i due fattori
possono essere positivi,
nulli o negativi
Inizio
Leggi(W)
Leggi(Y)
si
Y>=0 ?
no
NS:=Y
NS:=-Y
CS:=1
CS:=-1
SP:=0
no
NS> 0?
si
SP:=SP+W
NS:=NS-1
si
CS=1?
Z:=SP
no
Z:=-SP
Scrivi (Z)
Fine
Codifica in C
main ()
{int w,y,z,sp,ns,cs;/*dichiarazione
variabili*/
leggi(w);
leggi(y);
if (y>=0)
{ ns=y;
cs=1;
}
else /*y è negativo*/
{ ns=-y;
cs=-1;
}
sp=0; /*inizializzazione*/
while (ns>0)
{ sp=sp+w;
ns=ns-1;
}
if (cs==1)
{z=sp;}
else
{z=-sp;}
scrivi(z);
}
Esempio
Problema: date le coordinate di tre punti corrispondenti ai
vertici di un triangolo, riconoscere se si tratta di un triangolo
degenere o no, e nel caso di triangolo non degenere
calcolare il suo perimetro
Inizio
Leggere i valori delle
coordinate dei vertici
Triangolo degenere?
SI
NO
Calcolare la lunghezza dei
lati
Calcolare il perimetro come
somma delle lunghezze
Scrivere “il triangolo
è degenere”
Scrivere il valore del
perimetro
Vuoi continuare?
NO
Fine
SI
Stesura iniziale in pseudo-codice
• Costrutti di controllo e parole chiave del linguaggio C
– main ()
– do {} while ();
– if () {} else {}
• Operazioni in linguaggio naturale
main () /*inizio dell’algoritmo*/
{
do
{
leggi (coordinate);
if (triangolo degenere)
{
scrivi (“Il triangolo è degenere”);
}
else
{
calcola lunghezza dei lati;
perimetro = somma dei lati;
scrivi (perimetro);
}
} while (si vuole continuare);
} /*fine dell’algoritmo*/
Raffinamento 1
Inizio
Leggere coord. punto A
Raffinamento della
lettura dei valori delle
coordinate
Leggere coord. punto B
Leggere coord. punto C
Coincidono (A,B)?
si
no
Coincidono (B,C)?
si
no
Coincidono (C,A)?
no
si
Allineati (A,B,C)?
no
si
LAB:=distanza(A,B)
LBC:=distanza(B,C)
LCA:=distanza(C,A)
Raffinamento della
valutazione della
condizione di triangolo
degenere
Raffinamento del
calcolo della lunghezza
dei lati e del perimetro
PERIMETRO:= LAB+LBC+LCA
Scrivere il valore del
perimetro
Scrivere “Vuoi
Continuare(s/n)”?
Leggere carattere RISP
si
RISP=‘s’?
Fine
Scrivere “il triangolo
è degenere”
Raffinamento della
valutazione della
condizione “Vuoi
continuare?”
Direttive Complesse
Introduzione al concetto di sottoprogramma
• Operazioni elementari: direttamente eseguibili
dall'esecutore
• Direttive complesse: devono essere raffinate ed
espresse in termini di operazioni elementari
• Raffinamento di direttive complesse: realizzabile a
parte rispetto all'algoritmo principale
• Le direttive complesse possono essere considerate
come sottoproblemi da risolvere con un algoritmo
dedicato
• Sottoprogrammi: descrizioni di questi algoritmi
"accessori"
• Direttive Complesse: sono chiamate ai
sottoprogrammi all'interno dei programmi
principali
Vantaggi nell'impiego dei sottoprogrammi
• Chiarezza del programma principale
– Tutti i dettagli sono descritti nei sottoprogrammi
– Il programma principale descrive la struttura di
controllo generale
• Si evitano ripetizioni
– Alcuni sottoproblemi devono essere affrontati piu'
volte nella soluzione
di un problema
principale
– il sottoprogramma può essere richiamato tutte le
volte che sia necessario
• Disponibilità di "sottoprogrammi" prefabbricati
– Sottoproblemi ricorrenti gai' sviluppati da
programmatori esperti, raccolti nelle cosiddette
"librerie" di sotoprogrammi
Raffinamento 2:
espansione delle direttive complesse
Leggere valore reale AX
Leggere coord. punto A
Leggere valore reale AY
Leggere coord. punto B
Leggere valore reale BX
Leggere coord. punto C
Leggere valore reale BX
Leggere valore reale CX
Leggere valore reale CY
no
no
Coincidono (A,B)?
no
si
AX=BX?
si
AY=YX?
no
si
Raffinamento 2 - seguito
Y
C
A
B
DYAC
DXAC
DXAB
DYAB
X
Se i punti A, B, e C sono allineati vale la proporzione
DYAB:DXAB=DYAC:DXAC
In cui il prodotto dei medi è uguale al prodotto degli estremi
Coincidono (A,B,C)?
si
no
DYAB:=AY-BY
DXAB:=AX-BX
DYAC:=AY-CY
DXAC:=AX-CX
DYAB*DXAC=DXAC*DYAC?
si
no
LAB:=distanza(A,B)
LBC:=distanza(B,C)
LCA:=distanza(C,A)
LAB:=radiceq(quad(AX-BX)+quad(AY-BY)
LBC:=radiceq(quad(BX-CX)+quad(BY-CY)
LCA:=radiceq(quad(CX-AX)+quad(CY-AY)
quad(N) indica N*N
radiceq(N) indica
N