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 RAPPRESENTAZIONEoggetto identificatoreoperazione operatore, funzionedirettiva istruzioneflusso di controllo costrutti di controlloalgoritmo 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

• Blocco di inizio

• Blocco di terminazione

• Flusso di controllo delle operazioni

• Blocco condizionale

• Blocco di ingresso dati

• Blocco di uscita dati

operazione

Inizio

Fine

Condizionevera 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)

• Da ogni blocco condizionato devono uscire due frecce contrassegnate dalle indicazioni vero (si) e falso (no)

Condizionevera falsa

Inizio

operazione

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

• In tutti i casi -in esecuzione- è unica la scelta del blocco successivo da eseguire

Condizionevera falsa

operazione1 operazione2

Condizionevera falsa

operazione1 operazione2

Esempio Prodotto di due numeri interi positivi

Diagramma di flusso con direttive in italiano

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

Moltiplica intero W per intero Y e denota

il risultato con 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 2Prodotto 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)

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

SP:=SP+W

NS:=NS-1

NS>0

nosi

Z:=SP

Acquisizione dei dati in ingresso e attribuzione dei loro valori a W e Y

Inizializzazione delle variabili ausiliarie

Corpo del ciclo

Valutazione della condizione di uscita dal ciclo

Emissione del risultato

Schema a Blocchi con ciclo a condizione finale (l’algoritmo è corretto se Y>0)

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)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

SP:=SP+W

NS:=NS-1

NS>0

no

si

Z:=SP

SP:=SP+W

NS:=NS-1

NS>0no

si

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; /*inizializzazione*/

ns=y; /*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; /*inizializzazione*/

ns=y; /*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

Inizio

Leggi(W)

Scrivi (Z)

Leggi(Y)

SP:=0

Fine

NS:=Y

Z:=SP

SP:=SP+W

NS:=NS-1

NS>0no

si

Y>=0 nosi

Scrivi: “Secondo fattoreNegativo”

Ipotesi: l’algoritmo non calcola il prodotto nei casi in cui Y è < 0

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)

Scrivi (Z)

Leggi(Y)

NS:=Y

Fine

CS:=1

Z:=SP

SP:=SP+W

NS:=NS-1

NS> 0?nosi

nosi Y>=0 ?

NS:=-Y

CS:=-1

CS=1? nosi

Z:=-SP

SP:=0

Codifica in Cmain ()

{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?

Calcolare la lunghezza dei lati

Calcolare il perimetro come somma delle lunghezze

Scrivere il valore del perimetro

Vuoi continuare?

Fine

Scrivere “il triangolo è degenere”

SI

NO

NO

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

Leggere coord. punto A

PERIMETRO:= LAB+LBC+LCA

LAB:=distanza(A,B)LBC:=distanza(B,C)LCA:=distanza(C,A)

Fine

Inizio

Scrivere “il triangolo è degenere”

si

Leggere coord. punto B

Leggere coord. punto C

Coincidono (A,B)?

Coincidono (B,C)?

Coincidono (C,A)?

Allineati (A,B,C)?

si

si

sino

no

no

no

Scrivere il valore del perimetro

Scrivere “Vuoi Continuare(s/n)”?

Leggere carattere RISP

RISP=‘s’?si

Raffinamento della lettura dei valori delle coordinate

Raffinamento della valutazione della condizione di triangolo degenere

Raffinamento della valutazione della condizione “Vuoi continuare?”

Raffinamento del calcolo della lunghezza dei lati e del perimetro

Direttive ComplesseIntroduzione 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 coord. punto A

Leggere coord. punto B

Leggere coord. punto C

Leggere valore reale AX

Leggere valore reale AY

Leggere valore reale BX

Leggere valore reale BX

Leggere valore reale CX

Leggere valore reale CY

Coincidono (A,B)? si

no

AX=BX?

no

si

AY=YX? si

no

no

Raffinamento 2 - seguito

Coincidono (A,B,C)? si

no

DYAB:=AY-BYDXAB:=AX-BXDYAC:=AY-CYDXAC:=AX-CX

DYAB*DXAC=DXAC*DYAC?si

no

BA

C

DXAB DYAB

DXAC

DYAC

X

Y

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

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