Gli algoritmi
L’elaboratore come macchina universale
•	L’elaboratore è uno strumento digitale, elettronico e automatico

•	Digitale  tutta l’informazione è rappresentata mediante cifre sulle quali è possibile effettuare operazioni logicomatematiche
•	Elettronico  tecnologie di tipo elettronico sono utilizzate per la realizzazione degli elaboratori
•	Automatico  l’elaboratore è capace di eseguire una determinata successione di operazioni, quando sia stato opportunamente programmato, senza intervento esterno

•	Il programma è una sequenza di operazioni atte a predisporre l’elaboratore alla soluzione di una classe di problemi
•	L’elaboratore è una macchina universale, poiché può essere utilizzato per risolvere tutti i problemi la cui soluzione può essere descritta sotto forma di programma

Analisi e programmazione  1
•	Tramite un elaboratore si possono risolvere problemi di varia natura: emissione di certificati anagrafici, gestione dei c/c di un istituto di credito, prenotazioni ferroviarie…

•	Il problema deve essere formulato in modo opportuno, perché sia possibile utilizzare un elaboratore per la sua soluzione

•	Per analisi e programmazione si intende l’insieme delle attività preliminari atte a risolvere problemi utilizzando un elaboratore, dalla formulazione del problema fino alla predisposizione dell'elaboratore
•	Scopo dell’analisi: definire un algoritmo
•	Scopo della programmazione: definire un programma
Analisi e programmazione  2
Analisi e programmazione  3
Le fasi del procedimento di analisi e programmazione

Algoritmi: definizione
•	Algoritmo deriva dal nome del matematico arabo Al Khuwarizmi, vissuto nel IX secolo d.C.; esempi di algoritmo sono stati ritrovati in Mesopotamia su tavolette babilonesi risalenti al 18001600 a.C.
•	Un algoritmo è una successione di istruzioni o passi che definiscono le operazioni da eseguire sui dati per ottenere i risultati; un algoritmo fornisce la soluzione ad una classe di problemi
•	Lo schema di esecuzione di un algoritmo specifica che i passi devono essere eseguiti in sequenza, salvo diversa indicazione 
•	Ogni algoritmo è concepito per interagire con l’ambiente esterno per acquisire dati e comunicare messaggi o risultati; i dati su cui opera un’istruzione sono forniti dall’esterno o sono frutto di istruzioni eseguite in precedenza

Esempio: Il gioco dell’undici 
•	Problema: Undici fiammiferi sono disposti su un tavolo: il primo giocatore (A) può raccogliere da 1 a 3 fiammiferi, il secondo (B) ne raccoglie a sua volta 1, 2 o 3; i giocatori alternano le loro mosse finché sul tavolo non ci sono più fiammiferi; il giocatore che è costretto a raccogliere l’ultimo fiammifero è il perdente

•	Algoritmo: Strategia vincente per il giocatore A che gioca per primo
•	prima mossa: A raccoglie 2 fiammiferi
•	mosse successive: se B raccoglie k fiammiferi (k  3), allora A raccoglie 4k fiammiferi 
Esempio: Ordinamento di un mazzo di carte 
Esempio: Calcolo delle radici di equazioni di 2° grado 
Esempio: Calcolo del M.C.D.  1 
Esempio: Calcolo del M.C.D.  2 
Proprietà degli algoritmi
Algoritmi 
Costanti e variabili  1
•	I dati su cui opera un algoritmo sono costanti e variabili 
•	Un dato è costante quando il suo valore non può essere aggiornato durante l’esecuzione dell’algoritmo 
•	Una variabile è una coppia <nome, valore>: può essere immaginata come una scatola sulla quale è scritto un nome e che può contenere un valore
Costanti e variabili  2
Assegnazione  1
•	L’istruzione di assegnazione definisce il valore attuale di una variabile, che resta inalterato fino all’assegnazione successiva
•	L’assegnazione si rappresenta con il simbolo “”: 
nome di variabile  espressione
       che si legge assegna alla variabile “nome di variabile” il valore di “espressione” ; l’espressione a destra di  è costituita da variabili, costanti e operatori
•	L’assegnazione viene così eseguita:
•	si valuta l’espressione a destra di , sostituendo ai nomi di variabile i loro valori attuali; il risultato deve appartenere all’insieme di definizione della variabile a sinistra di 
•	il valore calcolato diventa il nuovo valore della variabile il cui nome appare a sinistra di 
Assegnazione  2
Assegnazione  3
Le istruzioni  1
Le istruzioni  2
Proposizioni e predicati  1
Proposizioni e predicati  2
•	La valutazione di un predicato è l’operazione che permette di determinare se il predicato è vero o falso, sostituendo alle variabili i loro valori attuali
•	I valori vero e falso sono detti valori logici o booleani
•	Proposizioni e predicati possono essere espressi concisamente per mezzo degli operatori relazionali:
   		= (uguale)			 (diverso)
  		> (maggiore)			< (minore)
       	 (maggiore o uguale) 		 (minore o uguale)

•	I predicati che contengono un solo operatore relazionale sono detti semplici
Proposizioni e predicati  3
Proposizioni e predicati  4
Vettori e matrici  1
•	Le variabili, definite come coppie <nome, valore >, sono scalari
•	Una coppia <nome, insieme di valori > è una variabile vettore o array e può essere immaginata come un contenitore diviso in scomparti; ciascun scomparto può contenere un valore, detto elemento o componente del vettore
•	Ciascuna componente è individuata dal nome del vettore, seguito dal relativo numero progressivo, racchiuso fra parentesi tonde: l’indice del vettore 
•	La dimensione di un vettore è il numero dei suoi elementi
•	I vettori sono particolarmente utili per collezionare dati fra loro correlati, sui quali devono essere effettuate le stesse operazioni
Vettori e matrici  2
•	L’utilizzo di variabili vettoriali, in un algoritmo, presuppone la dichiarazione esplicita della loro dimensione
•	La dimensione del vettore costituisce un limite invalicabile per la selezione delle componenti del vettore
•	Esempio: V(100) asserisce che il vettore V è costituito da 100 elementi; possono essere selezionati V(12),V(57),V(89), ma non V(121) o V(763), che non esistono  
Vettori e matrici  3
•	Il concetto di matrice è un’estensione del concetto di vettore
•	Una matrice è costituita da un insieme di valori, ciascuno dei quali viene individuato per mezzo della sua posizione, espressa da più indici
•	Ad esempio, se una matrice M ha due dimensioni, i suoi elementi sono disposti su righe e colonne ed ogni suo elemento M(i,j) è individuato da due indici, con i indice di riga e j indice di colonna
I diagrammi a blocchi  1
•	Il linguaggio dei diagrammi a blocchi è un possibile formalismo per la descrizione di algoritmi

•	Il diagramma a blocchi, o flowchart, è una rappresentazione grafica dell’algoritmo

•	Un diagramma a blocchi descrive il flusso delle operazioni da eseguire per realizzare la trasformazione, definita nell’algoritmo, dai dati iniziali ai risultati

•	Ogni istruzione dell’algoritmo è rappresentata all’interno di un blocco elementare, la cui forma grafica è determinata dal tipo di istruzione 

•	I blocchi sono collegati tra loro da linee di flusso, munite di frecce, che indicano il susseguirsi di azioni elementari
I diagrammi a blocchi  2
I diagrammi a blocchi  3

•	Un diagramma a blocchi è un insieme di blocchi elementari composto da:

•	un blocco iniziale
•	un blocco finale
•	un numero finito n (n1) di blocchi di azione e/o di blocchi di lettura/scrittura
•	un numero finito m (m  0) di blocchi di controllo
I diagrammi a blocchi  4
•	L’insieme dei blocchi elementari che costituiscono un algoritmo deve soddisfare le seguenti condizioni:
•	ciascun blocco di azione o di lettura/scrittura ha una sola freccia entrante ed una sola freccia uscente
•	ciascun blocco di controllo ha una sola freccia entrante e due frecce uscenti
•	ciascuna freccia entra in un blocco oppure si inserisce in un’altra freccia
•	ciascun blocco è raggiungibile dal blocco iniziale
•	il blocco finale è raggiungibile da qualsiasi altro blocco

•	Un blocco B è raggiungibile a partire da un blocco A se esiste una sequenza di blocchi X1,X2,…,Xn, tali che A=X1, B=Xn e  Xi, i=1,…,n1, Xi è connesso con una freccia a Xi+1
    
Analisi strutturata  1
•	L’analisi strutturata favorisce la descrizione di algoritmi facilmente documentabili e comprensibili

•	I blocchi di un diagramma a blocchi strutturato sono collegati secondo i seguenti schemi di flusso:
•	Schema di sequenza – più schemi di flusso sono eseguiti in sequenza
•	Schema di selezione – un blocco di controllo subordina l’esecuzione di due possibili schemi di flusso al verificarsi di una condizione 
•	Schema di iterazione – si itera l’esecuzione di un dato schema di flusso
Analisi strutturata  2
•	Un diagramma a blocchi strutturato è un diagramma a blocchi nel quale gli schemi di flusso sono strutturati

•	Uno schema di flusso è strutturato quando soddisfa una delle seguenti proprietà…
•	 …è uno schema elementare o uno schema di sequenza
Analisi strutturata  3
•	…è uno schema di selezione

•	Nel primo caso, lo schema S viene eseguito solo se la condizione C è vera; se C è falsa, non viene eseguita alcuna azione
•	Nel secondo caso, viene eseguito solo uno dei due schemi Sv o Sf, in dipendenza del valore di verità della condizione
Analisi strutturata  4

•	…è uno schema di iterazione

•	Nel primo caso, S può non venire mai eseguito, se la condizione C è subito falsa; nel secondo caso, S viene eseguito almeno una volta
•	Quando lo schema S viene eseguito finché la condizione C si mantiene vera si parla di iterazione per vero; si ha un’iterazione per falso quando S viene eseguito finché C è falsa
Analisi strutturata  5
•	Gli schemi di flusso sono aperti quando consentono una sola esecuzione di una sequenza di blocchi elementari, sono chiusi quando permettono più di un’iterazione della sequenza di blocchi 
•	Gli schemi di sequenza e di selezione sono aperti, lo schema di iterazione è chiuso
•	Ogni diagramma a blocchi non strutturato è trasformabile in un diagramma a blocchi strutturato equivalente 
•	Due diagrammi a blocchi sono equivalenti se, operando sugli stessi dati, producono gli stessi risultati
•	L’uso dell’analisi strutturata garantisce:
•	facilità di comprensione e modifica dei diagrammi a blocchi 
•	maggiore uniformità nella descrizione degli algoritmi

Gli algoritmi iterativi  1

•	Note: 
•	La variabile somma è un contenitore di somme parziali, finché non si ottiene la somma totale richiesta
•	La soluzione del problema viene raggiunta eseguendo azioni simili per un numero opportuno di volte 
Gli algoritmi iterativi  2
•	Il ciclo o loop  è uno schema di flusso per descrivere, in modo conciso, situazioni in cui uno gruppo di operazioni deve essere ripetuto più volte
Gli algoritmi iterativi  3

•	Note: 
•	La fase di inizializzazione riguarda la somma e l’indice del ciclo
•	Il controllo di fine ciclo viene effettuato in coda 
Gli algoritmi iterativi  4
•	Un ciclo è definito quando è noto a priori quante volte deve essere eseguito; un ciclo definito è detto anche enumerativo 

•	Un contatore del ciclo tiene memoria di quante iterazioni sono state effettuate; può essere utilizzato in due modi:
•	incremento del contatore: il contatore viene inizializzato ad un valore minimo (ad es. 0) e incrementato ad ogni esecuzione del ciclo; si esce dal ciclo quando il valore del contatore eguaglia il numero di iterazioni richieste
•	decremento del contatore: il contatore viene inizializzato al numero di iterazioni richiesto e decrementato di uno ad ogni iterazione; si esce dal ciclo quando il valore del contatore raggiunge 0
Gli algoritmi iterativi  5
•	Un ciclo è indefinito quando non è possibile conoscere a priori quante volte verrà eseguito

•	La condizione di fine ciclo controlla il valore di una o più variabili modificate da istruzioni che fanno parte dell’iterazione

•	Comunque, un ciclo deve essere eseguito un numero finito di volte, cioè si deve sempre verificare la terminazione dell’esecuzione del ciclo

Gli algoritmi iterativi  6
Gli algoritmi iterativi  7
Gli algoritmi iterativi  8
•	L’utilità dei vettori consiste nel poter usare la tecnica iterativa in modo da effettuare la stessa operazione su tutti gli elementi del vettore
•	Usando la variabile contatore di un ciclo come indice degli elementi di un vettore è possibile considerarli tutti, uno alla volta, ed eseguire su di essi l’operazione desiderata 
Gli algoritmi iterativi  9
Ancora esempi…
Ancora esempi…
La pseudocodifica  1

•	La pseudocodifica è un linguaggio per la descrizione di algoritmi secondo le regole della programmazione strutturata

•	La descrizione di un algoritmo in pseudocodifica si compone di due parti...

•	la dichiarazione delle variabili usate nell’algoritmo
•	la descrizione delle azioni dell’algoritmo
La pseudocodifica  2

•	Tipo delle variabili 
•	Il tipo di una variabile indica l’insieme dei valori che possono essere assegnati a quella variabile

•	Su costanti e variabili di un tipo è possibile effettuare le operazioni che sono proprie di quel tipo e tutte le operazioni di confronto

•	Sono permessi i seguenti 4 tipi: integer, real, boolean, stringq

La pseudocodifica  3
•	integer: sono le variabili cui possono essere assegnati numeri interi; le costanti di tipo integer sono numeri interi, ad es. 1, 3, 150
•	real: sono le variabili cui possono essere assegnati numeri razionali; le costanti real possono essere rappresentate in notazione decimale, con un “.” che separa la parte intera dalla parte decimale (ad es., 5.17, 12.367, 123., 0.005) o in notazione scientifica (23.476E+2=2347.6, 456.985E4=0.0456985)
•	boolean: sono le variabili cui possono essere assegnati i valori logici; le costanti logiche sono true e false
•	stringq: sono le variabili cui possono essere assegnate parole (o stringhe) costituite da q caratteri; le costanti stringq sono costituite da parole di q caratteri racchiusi tra apici (che non fanno parte della costante); ad es., ‘FABIO’ è una costante string5,‘+’ è una costante string1 e ‘124’ string3
La pseudocodifica  4
•	Dichiarazione delle variabili
•	La dichiarazione delle variabili nella pseudocodifica è un elenco, preceduto dalla parola var, delle variabili sulle quali l’algoritmo opera
•	Le variabili sono suddivise per tipo: quelle dello stesso tipo sono separate l’una dall’altra da una “,”; l’elenco delle variabili dello stesso tipo è seguito dai “:” e dall’indicazione del tipo; gli elenchi di variabili di tipo diverso sono separati dal “;”, l'ultimo elenco è seguito da un “.”
•	Esempio: 
    				var i, j, a(20): integer; 
        			     p, q: real; 
         			     nome: string20;
         			     sw: boolean. 
La pseudocodifica  5
•	Descrizione delle azioni
•	Gli schemi di flusso fondamentali sono descritti utilizzando convenzioni linguistiche: ad ogni schema di composizione corrisponde una convenzione linguistica
•	La descrizione di un algoritmo deve soddisfare le seguenti regole:
•	La prima azione dell’algoritmo è preceduta dalla parola begin;
•	L’ultima azione dell’algoritmo è seguita dalla parola end;
•	L’azione di lettura è rappresentata dalla parola read;
•	L’azione di scrittura è rappresentata dalla parola write;
•	Lo schema di sequenza di n flussi S1, S2,…, Sn è rappresentato come
S1;
S2;

Sn; 
La pseudocodifica  6
•	Gli schemi di selezione sono rappresentati come:

•	Gli schemi di iterazione sono rappresentati come:

La pseudocodifica  7
•	Esistono convezioni linguistiche alternative in relazione a particolari schemi di flusso
•	Esempio: Ciclo enumerativo 
La pseudocodifica  8
•	Esempio: Algoritmo per il calcolo del vettore somma di due vettori di numeri razionali 

La pseudocodifica  9
•	Esempio: Algoritmo per il calcolo del massimo elemento di un vettore di numeri razionali  

La pseudocodifica  10
•	Esempio: Algoritmo per il calcolo delle radici di equazioni di 2° grado 
	
Ancora esempi…
Ancora esempi…
Gli algoritmi ricorsivi  1
•	Un algoritmo si dice ricorsivo quando è definito in termini di se stesso, cioè quando una sua istruzione richiede una nuova esecuzione dell’algoritmo stesso

•	La definizione ricorsiva di un algoritmo è suddivisa in due parti:
•	l’inizio della ricorsione, che stabilisce le condizioni iniziali, cioè il risultato che si ottiene per i dati iniziali (in generale per 0 e/o 1)
•	la regola di ricorsione, che definisce il risultato per un valore n, diverso dal valore (/i) iniziale per mezzo di un’espressione nella quale si richiede il risultato dell’algoritmo calcolato per n1
Gli algoritmi ricorsivi  2
•	Esempio: Prodotto di numeri interi 

•	Secondo la definizione ricorsiva si ha:
3  2 = 3  1 + 3 = 3  0 + 3 + 3 = 0 + 3 + 3 = 6

•	L’esecuzione di un algoritmo ricorsivo termina sempre: la regola di ricorsione prevede nuove esecuzioni su dati decrescenti, fino ad ottenere i dati di inizio ricorsione

Gli algoritmi ricorsivi  3

•	Esempio: Calcolo del fattoriale di un numero (intero)
•	Il fattoriale di un numero intero n è il prodotto di tutti gli interi da 1 ad n, cioè n! = n  (n1)  (n2) … 2  1
•	Per definizione, 0! = 1