algoritmo obiettivo: dato un problema –definire un procedimento che possa essere eseguito...
TRANSCRIPT
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