Algoritmi
1
Definizione di algoritmo

Metodo per risolvere un problema
 Sequenza
ordinata di passi
 Passi eseguibili

Es.: elencare tutti i numeri reali
 Passi

non ambigui
Deve terminare
2
Algoritmi, programmi e processi
Programma: descrizione di un algoritmo in
un linguaggio di programmazione
 Processo: esecuzione dell’algoritmo
descritto da un programma

3
Rappresentazione di un algoritmo



Varie notazioni:
 Linguaggio naturale
 Immagini
 Diagrammi di flusso
 Pseudocodice
Linguaggio di programmazione:
 Insieme di primitive (passi singoli)
 Regole che dicono come combinare le primitive per
descrivere passi piu’ complessi
Primitiva: sintassi (simbolo/i) + semantica (significato)
4
Immagini per descrivere un
algoritmo -- 1
5
Immagini per descrivere un
algoritmo -- 2
6
Primitive per gli origami
7
Quali primitive?

Istruzioni del linguaggio macchina
 Non
ambigue
 Algoritmo pronto per essere eseguito
 Ma troppo a basso livello

Pseudocodice: versione meno formale di
un linguaggio di programmazione
8
Pseudocodice
Nomi per indicare valori
 Associazione nome-valore:

espressione
 Assegna a nome il valore di espressione
 Es.: temperatura-oggi  temperatura-ieri +10
 Nome
9
If then else
Scelta tra due alternative, se una
condizione e’ vera
 If (condizione) then (attivita’) else (attivita’)
 If (condizione) then (attivita’)
 Es.: if (ci sono biglietti) then (compra un
biglietto)

10
While do

Eseguire un’attivita’ purche’ una
condizione rimanga vera:
While (condizione) do (azione)

Es.: while (ci sono biglietti) do (vendi un
biglietto)
11
Ciclo
While (condizione) do (azione)







Controlla la condizione: vera
Esegui l’azione
Controlla la condizione: vera
Esegui l’azione
....
Controlla la condizione: falsa
Stop
12
Fasi del ciclo
Inizializzazione: stato iniziale, che verra’
modificato dall’azione
 Controllo della condizione di terminazione:
confronto tra stato corrente e condizione,
terminazione se uguali
 Modifica dello stato: per andare verso la
condizione di terminazione

13
Esempio di pseudocodice
Nome del pezzo (procedura) di
pseudocodice  possiamo
chiamare questo pezzo per
nome all’interno di un altra procedura
Procedure Saluti
Conta 3;
While (Conta > 0) do
(stampa il messaggio “Saluti” e
Conta  Conta - 1)
Inizializzazione: Conta  3
Condizione di terminazione: conta <0 o conta =0
Modifica stato: Conta  Conta -1
14
Parametri
Pseudocodice piu’ generico possibile
 Es.: procedure Ordina (Lista)
 Lista e’ un nome generico per una
qualsiasi lista di numeri
 Ogni volta che useremo la procedura
Ordina decideremo che lista considerare

15
Ricerca sequenziale



Verificare se un elemento e’ presente in un elenco di
elementi
Supponiamo ordine crescente (alfabetico o numerico)
Scorriamo tutto l’elenco dall’inizio alla fine finche’ troviamo
l’elemento o non ci sono piu’ elementi da guardare o gli
elementi rimasti sono maggiori
Procedure Cerca (lista, valorecercato)
if (elenco vuoto)
then (stampa no)
else (valore  primo-elemento;
while (valorecercato > valore e ci sono ancora elementi)
do (valore  elemento successivo);
if (valorecercato = valore)
then (stampa si)
else (stampa no))
16
Attenzione alle fasi di un ciclo
numero  1;
while (numero =/= 6) do
(numero  numero +2)
Condizione di terminazione: numero = 6
Non verra’ mai raggiunta!
17
While e repeat
while (condizione) do (azione): prima si
controlla la condizione e poi si effettua
l’azione
 repeat (azione) until (condizione): prima
esecuzione dell’azione, poi controllo
condizione  azione sempre eseguita
almeno una volta

18
while
repeat
19
Ordinamento
Vogliamo ordinare una lista di nomi
 Es.: Fred, Alice, David, Bill, Carol
 Ordine alfabetico da sinistra a destra 
Alice, Bill, Carol, David, Fred

20
Esempio
Il pezzo “Fred” e’ ordinato, ma “Fred-Alice” no  scambio
21
Esempio
22
Esempio
23
In generale ...






Scelgo il primo elemento della parte non
ordinata (pivot)
Faccio scorrere verso il basso gli elementi
ordinati maggiori del pivot
Inserisco il pivot nella posizione vuota
All’inizio: pivot  secondo elemento
Ad ogni passo: pivot  elemento successivo
Ordinamento per inserimento
24
Pseudocodice
procedure Ordina(Lista)
N  2;
while (N ≤ lunghezza-lista) do
(pivot  elemento-n;
sposta pivot in posizione temporanea lasciando
uno spazio vuoto);
while (c’e’ un elemento > pivot sopra lo spazio
vuoto) do
(sposta elemento verso il basso);
sposta pivot nello spazio vuoto;
N  N+1
)
25
Strutture ricorsive
Ciclo: iterazione di una sequenza di passi
 Ricorsione: ripetizione di tutte le istruzioni
come sottocompito su dati parziali
 Esempio: telefonata all’interno di un’altra

26
Esempio: algoritmo di ricerca
binaria (in un insieme ordinato)

Tecnica che usiamo spesso pr cercare una voce
in un dizionario:
 Apriamo
il dizionario in un punto (a meta’)
 Se non c’e’ la voce che cerchiamo, andiamo nella
prima parte o nella seconda

Finche’
la voce cercata  si
 Guardiamo un pezzo con un elemento singolo e non
e’ la voce cercata  no
 Troviamo
27
Esempio
28
Pseudocodice 1
if (lista vuota)
then fallimento
else
(elemento-test  elemento-a-meta’;
Scelta fra tre casi:
Caso 1: elemento-cercato = elemento-test
(successo)
Caso 2: elemento-cercato < elemento-test
(cerca nella parte prima di elemento-test)
Caso 3: elemento-cercato > elemento-test
(cerca nella parte dopo elemento-test)
)
29
Pseudocodice 2: nome della procedura
Procedure Ricerca(lista, elemento-cercato)
if (lista vuota)
then fallimento
else
(elemento-test  elemento-a-meta’;
Scelta fra tre casi:
Caso 1: elemento-cercato = elemento-test
(successo)
Caso 2: elemento-cercato < elemento-test
(Ricerca(parte prima di elemento-test,ec))
Caso 3: elemento-cercato > elemento-test
(Ricerca(parte dopo elemento-test,ec))
)
30
Esempio 1



Cerchiamo Bill nella lista (Alice, Bill, Carol,
David, Evelyn, Fred, George)
Seleziono David
David =/= Bill  cerco nella prima meta’ (Alice,
Bill, Carol)
 Sospendo
l’esecuzione di Ricerca in corso, e attivo
un’altra esecuzione della procedura Ricerca
 Seleziono Bill
 Bill = Bill  si

Ritorno nella prima esecuzione  si
31
Esempio 1
32
Esempio 2




Cerchiamo David nella lista (Alice, Carol,
Evelyin, Fred, George)
Seleziona Evelyin
Evelyin =/= David  cerca nella prima meta’
(Alice, Carol)
 Seconda esecuzione:
 Seleziona Carol
 Carol =/= David  cerca nella lista vuota
 Terza esecuzione, su lista vuota 
fallimento
 Finisce la terza esecuzione
 Finisce la seconda esecuzione (fallimento)
Finisce la prima esecuzione (fallimento)
33
34
35
36
Riassunto
Divide la lista in due parti
 Cerca su una delle due parti
 Ricerca binaria
 Ogni volta ricerca su una parte piu’ piccola
 prima o poi arrivera’ a trvare l’elemento
o a cercare nella lista vuota

37
Ricerca sequenziale e binaria




In entrambi i casi: ripetere una sequenza di
istruzioni
Ricerca sequenziale: ciclo => ripete la sequenza
sulla stessa lista con diverso stato iniziale
Ricerca binaria: ripete la sequenza come
sottocompito della ricerca in corso  ricorsione
Varie attivazioni della procedura
 Una attiva, le altre sospese
 Ogni attivazione sospesa attende che un’altra
termini per continuare
38
Sistema ricorsivi






Condizione di terminazione (caso base)
Istruzioni che assicurano che verra’ soddisfatta
prima o poi
Inizializzazione, modifica, verifica terminazione
Di solito verifica del caso base prima della
ripetizione
Non verificata altra attivazione su un
sottoproblema piu’ vicino alla terminazione
Verificata  termina l’attivazione corrente e non
ne attiva altre
39
Nell’esempio ...




Inizializzazione: attivazione di ricerca su intera
lista
Caso base: trovare valore cercato o cercare su
lista vuota
Modifica: nuove attivazioni, stesso valore da
cercare in una lista piu’ piccola
Lista finita, ogni fase ricorsiva su una lista piu’
piccola  prima o poi valore trovato o lista
vuota  termina sempre
40
Esercizio

Ricerca di Joe nella lista (Alice, Bob,
Carol, David, Evelyin, Fred, George,
Henry, Irene, Joe, Karl, Larry, Mary,
Nancy, Oliver)
 Quali

nomi vengono esaminati?
Henry, Larry, Joe
41
Esercizio










Numero massimo di voci esaminate in una lista
di 200 voci?
Una  100
Due  50
Tre  25
Quattro  12
Cinque  6
Sei  3
Sette  1
Otto
Nota: 28 = 256, 27 = 128
42
Da while a repeat
contatore  2;
while (contatore < 7) do
(stampa valore di contatore;
contatore  contatore +1)
contatore  2;
repeat (stampa contatore; contatore  contatore
+1)
until contatore = 7
43
Da repeat a while
contatore  1;
repeat
(stampa valore di contatore;
contatore  contatore +1)
until (contatore = 5)
contatore  1;
while contatore < 5 do
(stampa contatore; contatore  contatore +1)
44
Sequenza di Fibonacci
ultimo  0;
corrente  1;
while (corrente < 100) do
(stampa valore di corrente;
temp  ultimo;
ultimo  corrente;
corrente  ultimo + temp)
1.
2.
3.
4.
5.
6.
Corpo del ciclo?
Inizializzazione?
Modifica?
Terminazione?
Verifica?
Numeri stampati?
45
Esercizio
Ricerca binaria, ricerca di J nella lista
A,B,C,D,E,F,G,H,I,J,K,L,M,N,O
 Quali lettere vengono esaminate?
 H, L, J
 Quali se si cerca Z?
 H, L, N, O

47
Esercizio
Contatore  1;
while (Contatore =/= 7) do
(stampa Contatore;
Contatore  Contatore +3)
1.
2.
Quante volte viene eseguito il corpo del ciclo?
Se il test fosse (Contatore =/= 6)?
48
Esercizio
procedure Test1(Contatore)
if (Contatore =/= 5)
then (stampa Contatore; Test1(Contatore+1))
procedure Test2(Contatore)
if (Contatore =/= 5)
then (Test2(Contatore+1); stampa Contatore)
Ingresso 1: che uscita dalle due procedure?
Test1: 1,2,3,4
Test2: 4,3,2,1
49
Ricerca sequenziale e binaria






Lista (A,B,C,D,E,F,G,H,I)
Ricerca sequenziale o binaria piu’ veloce per
cercare G?
Per A?
Per Bi?
Per S?
Quante voci esaminate da ricerca sequenziale di
E? E da ricerca binaria?
50
Fattoriale - 1
Fattoriale(0)=1
 Fattoriale(n) = n x fattoriale(n-1)
 Es.:
fatt(3)=3xfatt(2)=3x2xfatt(1)=3x2x1xfatt(0)
=3x2x1x1=6
 Algoritmo ricorsivo per calcolare il
fattoriale di n

51
Fattoriale - 2
procedure Fatt(n,k)
if n=0 then
(k  1)
else
(attiva Fatt(n-1,k1);
k  n x k1)
52
Efficienza degli algoritmi





Ricerca su una lista (es. 30.000 elementi)
Ricerca sequenziale: in media esamina meta’
elementi (es.: 15.000)
Se 10millisec per ogni elemento, in media 150
sec. (2.5 minuti)
Ricerca binaria: prima 30.000, poi 15.000, poi
7.500, poi 3.750, ... Al massimo 15 voci
esaminate
Se 10 millisec per ogni elemento, al massimo
15/10 sec.
53
Analisi generica






Qualunque lista, di lunghezza arbitraria
Caso migliore, peggiore, medio
Nell’esempio: caso medio per ricerca
sequenziale, caso peggiore per ricerca binaria
In generale, per liste con n elementi:
Ricerca sequenziale: in media n/2 elementi
Ricerca binaria: al massimo log2(n) elementi
54
Esempio: ordinamento per
inserimento


Caso migliore: ogni pivot e gia’ al suo posto 
n-1 confronti
Caso peggiore: ogni pivot deve essere
confrontato con tutti i precedenti (lista in ordine
inverso all’inizio)
 Primo pivot: confronto con 1 elemento
 Secondo pivot: con 2 elementi, ...
 Numero totale di confronti: 1+2+...+(n-1) =
n(n-1)/2 = ½(n2-n)
 Esempio: lista con 10 elementi  45 confronti
nel caso peggiore
55
Esempio di caso peggiore
56
Caso medio
Meta’ dei confronti del caso peggiore 
¼(n2-n)
 Esempio: per liste con 10 elementi, 22,5
confronti
 Caso migliore, medio, peggiore:
approssimano il tempo (numero di passi)
per eseguire l’algoritmo

57
Grafico del caso peggiore: ½(n2-n)
All’aumentare del numerto di elementi, il tempo aumenta anche di piu’
 Algoritmo meno efficiente all’aumentare della lunghezza della lista
58
Grafico per ricerca binaria
(caso pessimo: log2(n))
All’aumentare del numero di elementi, il tempo aumenta, ma meno
 algoritmo piu’ efficiente all’aumentare della lunghezza della lista
59
Forma dei grafici





Dipende dall’espressione matematica
Espressione lineare  linea retta
Espressioni quardatiche  curva parabolica
Espressioni logaritmiche  forma logaritmica
Forma identificata con la espressione piu’ semplice che
la identifica




Parabola: O(n2)
Logaritmica: O(log2n)
Notazione O: caso pessimo
Confronto tra algoritmi
60
Esercizi
Algoritmi per somma e moltiplicazione di
numeri decimali con n cifre
 Somma, caso pessimo: n+1 somme 
O(n)
 Moltiplicazione, caso pessimo: nxn 
O(n2)

61