Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Che cosa e' un algoritmo e
come vogliamo studiare gli algoritmi?
Vedi:
• D.E. Knuth, The art of computer programming, Vol. 1,
Fundamental Algorithms, Addison-Wesley, cap. 1, Basic
concepts
• E. Horowitz, S. Sahni, Computer algorithms, Computer Science
Press, cap. 1, Introduction
Copyright © 2006-2009 by Claudio Salati.
Lez. 1
1
ALGORITMO (o algorismo)
• Il nuovissimo Melzi, 1950
• Aritmetica col sistema arabo
(dal matematico arabo Al-Kuarismi, del IX secolo)
• Processo del calcolo
• Grande Dizionario Enciclopedico UTET, 1954
• Qualunque procedimento di calcolo
• Questa strana parola nasce dal nome del matematico arabo
Al Khovarizmi … passo' ad indicare le regole di calcolo
• Cosi' si dice anche oggi Algoritmo di Euclide per indicare il
procedimento di calcolo che serve per la ricerca del
massimo comun divisore
• The Concise Oxford Dictionary, 1976
• Arabic (decimal) notation of numbers
• Process or rules for (esp. machine) calculation
2
ALGORITMO: aritmetica col sistema arabo
• Sistema arabo-indiano: basato sulla notazione posizionale e su cifre
relative ad una base, e.g. in base 10:
nm nm-1 ... n1 n0 = nm*10m+ nm-1*10m-1+ ... +n1*101+ n0*100
• Le operazioni su numeri qualsiasi si basano sulla capacita’ di operare
sulle singole cifre
• Algoritmo di addizione
typedef digit[MAXDIGIT] numero;
// numero rappresentato come sequenza di MAXDIGIT digit,
// il digit 10k in posizione k nella sequenza
void addizione(numero op1, numero op2, numero somma) {
unsigned riporto = 0, pot, parziale;
for (pot = 0; pot < MAXDIGIT; pot += 1) {
parziale = op1[pot] + op2[pot] + riporto;
riporto = parziale / 10;
parziale = parziale % 10;
digit[pot] = parziale;
}
assert(riporto==0); // altrimenti overflow
}
3
Algoritmo
Microsoft® Encarta® Enciclopedia. © 1993-2002 Microsoft Corporation. Tutti i diritti riservati.
• Termine che formalizza il concetto intuitivo di procedura generale, di
metodo sistematico valido per risolvere una certa classe di problemi.
• In matematica, è la soluzione di un problema basata sull'uso ripetuto di
un semplice metodo computazionale
(ne è un esempio comune il procedimento dell'operazione di divisione
in aritmetica - in realta' il procedimento di tutte le 4 operazioni
nell’aritmetica basata sui numeri arabi, quella in notazione posizionale).
• In informatica, indica, in generale, una sequenza di passi successivi,
ciascuno dei quali specifica un'azione (o istruzione) eseguibile in modo
meccanico.
La sequenza completa permette di risolvere un problema, una volta che
siano assegnate le condizioni iniziali.
• In informatica, la nozione di algoritmo contiene due concetti impliciti,
fondamentali ai fini dell'esecuzione dell'algoritmo stesso:
• quello di automa, l'esecutore meccanico dell'algoritmo, e
• quello di linguaggio in cui l'algoritmo è scritto, che l'automa
4
riconosce.
Algoritmo
Microsoft® Encarta® Enciclopedia. © 1993-2002 Microsoft Corporation. Tutti i diritti riservati.
• L'algoritmo deve rispettare alcune proprietà fondamentali:
• effettività, vale a dire deve essere effettivamente eseguibile da
un automa (o, in linguaggio dei computer, deve essere
programmabile);
• finitezza di espressione (statica), ovvero il numero di
istruzioni da eseguire deve essere finito;
• finitezza della procedura (dinamica), ovvero deve essere
possibile concludere il calcolo, per qualsiasi situazione dei dati
iniziali;
• determinismo, ovvero a ogni passo della procedura deve
essere definita una e una sola operazione da eseguire.
• L'algoritmo può essere scritto con espressioni logiche o termini
matematici, o in forma lessicale.
5
ALGORITMO (in informatica!)
• Definizione 1
UN METODO PRECISO
UTILIZZABILE DA UN CALCOLATORE
PER LA SOLUZIONE DI UN PROBLEMA
• Definizione 2
DESCRIZIONE DI UNA
SEQUENZA ORDINATA E FINITA (staticamente e dinamicamente)
DI AZIONI BEN DEFINITE ED EFFICACI
CHE A PARTIRE DA UN INSIEME I DI DATI DI INGRESSO
CHE SODDISFANO ALL'INSIEME DI CONDIZIONI P
PRODUCE UN INSIEME O DI VALORI DI USCITA
CHE GODONO DELL'INSIEME DI PROPRIETA' C
6
ALGORITMO: PAROLE CHIAVE 1
• TEMPO FINITO: IL VINCOLO REALE E' MOLTO PIU'
STRINGENTE: ABBASTANZA PICCOLO!
 EFFICIENZA DEGLI ALGORITMI
• AZIONI BEN DEFINITE: e.g.: COSA SIGNIFICA -8 DIV -5?
CI SONO ALMENO 2 DEFINIZIONI DIVERSE:
-8 : -5 = +2
+2
oppure
-8 : -5 = +1
-3
• AZIONI EFFICACI: consideriamo una azione efficace quando e'
eseguibile in tempo finito da un calcolatore.
 quando ci riferiamo ad un calcolatore ci riferiamo a qualcosa di
simile a quello che teniamo sulla scrivania e usiamo solitamente
 NON SI PUO' MOLTIPLICARE O DIVIDERE O ... PER , ma
solo per una sua approssimazione finita
7
ALGORITMO: PAROLE CHIAVE 2
• INPUT: I, P(I)
• OUTPUT: O, C(O)
} problema ben definito
• SEQUENZA ORDINATA: STIAMO ASSUMENDO UN
PARTICOLARE MODELLO COMPUTAZIONALE, IL
 MODELLO DI VON NEUMANN
• DESCRIZIONE: e' un testo che descrive staticamente (tramite
istruzioni) una successione di azioni da eseguire dinamicamente
• La distinzione statico vs. dinamico e' fondamentale.
 Noi ragioneremo sul testo statico e non sul/i processo/i
dinamico/i che lo interpreta/no.
• Un processo dinamico e' condizionato dagli specifici dati in
ingresso, il testo statico no
(se non per le proprieta' generali P(I)).
8
PROBLEMA
Template: TROVARE UN ALGORITMO
CHE A PARTIRE DA UN INSIEME I DI DATI DI INGRESSO
CHE SODDISFANO ALL'INSIEME DI CONDIZIONI P
PRODUCA UN INSIEME O DI RISULTATI DI USCITA
CHE GODONO DELL'INSIEME DI PROPRIETA' C
 Ogni problema che affrontiamo deve, in linea di principio, poter
essere espresso secondo la formula indicata dal template
 MINIMA VULGARIA:
SE NON C'E' UN PROBLEMA (FORMULABILE CHIARAMENTE)
NON PUO' ESISTERE L'ALGORITMO CHE LO RISOLVE.
9
Citazioni
Ludwig Wittgenstein, Tractatus logico-philosophicus, Einaudi
6.2.4 Il metodo della matematica per pervenire alle sue equazioni e’ il
metodo di sostituzione.
Infatti le equazioni esprimono la sostituibilita’ di due
espressioni, e noi procediamo da un certo numero di equazioni
a nuove equazioni sostituendo espressioni con altre,
corrispondentemente alle equazioni.
6.5
Di una risposta che non si puo’ formulare non puo’ formularsi
neppure la domanda.
L’enigma non v’e’.
Se una domanda puo’ porsi, puo’ pure aver risposta.
(warning: Goedel: "purtroppo Wittgenstein si e' sbagliato")
?
Cio’ che si puo’ dire, lo si puo’ dire chiaramente (citazione
approssimata).
7
Su cio’ di cui non si puo’ parlare, si deve tacere.
10
Modello computazionale di Von Neumann - 1
E’ il modello computazionale dei processori hardware tradizionali:
 stato del programma o dati vs. azioni o istruzioni,
ciascuna delle quali istruzioni
 modifica lo stato del programma e/o
 determina quale e' la prossima istruzione del programma
da eseguire
 lo stato del programma e' rappresentato
 dal contenuto delle celle di memoria (memoria centrale del
calcolatore = array di celle ad accesso diretto o random) e
dei registri del processore
 dall'indirizzo della prossima istruzione da eseguire
 di norma la prossima istruzione da eseguire e' quella che segue
quella correntemente in esecuzione nel testo del programma
(sequenza dinamica = sequenza statica),
salvo che l'istruzione in esecuzione non trasferisca
esplicitamente il controllo ad un'istruzione diversa
11
Modello di Von Neumann o imperativo - 2
 anche il programma e' memorizzato nella memoria del
calcolatore
(ma di norma non e' modificabile durante l'esecuzione)
 nei linguaggi di programmazione imperativi si adotta
sostanzialmente lo stesso modello:

stato del programma  variabili

istruzione fondamentale  assegnamento

istruzioni di controllo di flusso
12
ALGORITMO DI EUCLIDE
//
//
//
//
//
//
1a
PER IL CALCOLO DEL MCD DI DUE NUMERI
NATURALI > 0
I = {i1, i2}
P = {ikN, ik>0 : k{1, 2}}
O = {gcd},
C = {gcdN, gcd=MCD(i1, i2)}
unsigned euclide_1 (unsigned i1,
unsigned i2) {
unsigned r, gcd;
unsigned k1 = i1;
unsigned k2 = i2;
01
02
03
04
05
13
ALGORITMO DI EUCLIDE
1b
assert((i1>0) && (i2>0));
assert((k1>0) && (k2>0));
if (k2>k1) { r = k1; k1 = k2; k2 = r; }
assert((k1>=k2) && (k2>0));
r = k1 % k2;
while (r!=0) {
k1 = k2;
k2 = r;
r = k1 % k2;
}
gcd = k2;
return(gcd);
}
06
07
08
09
10
11
12
13
14
15
14
ALGORITMO DI EUCLIDE
Stiamo considerando una successione di triple:
k1<1> k2<1> r<1>
k1<2> k2<2> r<2>
k1<3> k2<3> r<3>
. . .
k1<m>
1c
k2<m>
r<m>
in cui (definizione ricorsiva):
k1<1> = i1, k1<j+1> = k2<j>
k2<1> = i2, k2<j+1> = r<j>
r<j> = k1<j> % k2<j>
• Quando: r<j> = 0 noi affermiamo che: MCD(i1, i2) = k2<j>
• N.B.: se nm0 e n%m=0 e' evidente che MCD(n, m) = m
• m e' un divisore di n
• m e' un divisore, il massimo divisore, di se stesso
• Quello che stiamo asserendo e' che, per qualunque valore di j,
MCD(i1,i2) = MCD(k1<1>,k2<1>) = MCD(k1<j>,k2<j>) 15
Parentesi

N.B.: Durante tutto il corso si usera' l'espressione numero
naturale per indicare un numero intero non negativo

Abbiamo scritto
assert((i1>0) && (i2>0));
anziche'
assert(i1>0 && i2>0);
Perche'? Le due espressioni hanno lo stesso significato?

Quale e' il significato di una istruzione/espressione?

Chi ci assicura che euclide_1() fa davvero quello che
promette di fare?
 In particolare: chi ci assicura che il ciclo while termina?
16
ALGORITMO DI EUCLIDE
2a
// PER IL CALCOLO DEL MCD DI DUE NUMERI
// NATURALI  0
// I = {i1, i2}
// P = {ikN, ik0 : k{1, 2}}
// O = {return},
// C = {return N,
//
return = (i1!=0 && i2!=0) ?
//
//
MCD(i1, i2)
: MAX(i1, i2)}
unsigned euclide_2 (unsigned i1,
unsigned i2) {
assert((i1>=0) && (i2>=0));
01
02
17
ALGORITMO DI EUCLIDE
2b
unsigned new_i1;
if (i2 > i1) {
new_i1 = i2; i2 = i1; i1 = new_i1;
}
assert((i1 >= i2) && (i2 >= 0));
while (i2!=0) {
new_i1 = i2;
i2 = i1 % i2;
i1 = new_i1;
}
return(i1);
}
03
04
05
06
07
08
09
10
11
12
13
18
ALGORITMO DI EUCLIDE
2c
• In realta' il primo elemento di ciascuna delle triple considerate
nell'algoritmo euclide_1() non viene mai utilizzato
(dopo che si e’ effettuato il calcolo del terzo elemento della tripla)
• ne' per verificare se l'algoritmo e' terminato
(viene utilizzato il terzo elemento)
• ne' per determinare gli elementi della prossima tripla
(vengono utilizzati il secondo ed il terzo elemento)
(il primo elemento di una tripla e’ utilizzato solo per il calcolo del
terzo elemento della tripla stessa)
• Possiamo quindi "eliminare" il primo elemento di ciascuna tripla,
limitandoci a considerare la coppia formata dagli ultimi due
elementi.
• E' quello che fa l'algoritmo euclide_2()
19
Note e confronti
 assert() e' importata dallo header file standard assert.h
 se l'espressione tra parentesi e' vera non succede niente, ma
se e' falsa l'esecuzione del programma viene interrotta
 notare che in euclide_2() l'asserzione
assert((i1>=0) && (i2>=0));
e' banalmente vera: i1 e i2 sono di tipo unsigned!
 L'utilizzo del type-system del linguaggio di programmazione ci
consente di esprimere le caratteristiche del problema
 Le due funzioni euclide_1() ed euclide_2() sono molto
diverse tra loro:
 P_1(I)  P_2(I)
 C_1(O)  C_2(O)
20
ALGORITMO DI EUCLIDE
//
//
//
//
//
//
3a
PER IL CALCOLO DEL MCD DI DUE NUMERI
NATURALI > 0
I = {i1, i2}
P = {ikN, ik>0 : k{1, 2}}
O = {gcd},
C = {gcdN, gcd=MCD(i1, i2)}
unsigned euclide_3 (unsigned i1,
unsigned i2) {
unsigned newk1;
unsigned gcd;
unsigned k1 = i1;
unsigned k2 = i2;
01
02
03
04
05
06
21
ALGORITMO DI EUCLIDE
3b
assert((i1>0) && (i2>0));
assert((k1>0) && (k2>0));
// se k2>k1 la prima iterazione effettua
// lo scambio: questa azione e' evidente?
while (k2!=0) {
newk1 = k2;
k2 = k1 % k2;
k1 = newk1;
}
gcd = k1;
return(gcd);
}
07
08
09
10
11
12
13
14
22
ALGORITMO DI EUCLIDE
3c
Infatti se k2 > k1 e':
• k1 / k2 = 0
• k1 % k2 = k1
per cui durante la prima iterazione
• newk1 assume il valore di k2<0>
• k2<1> assume il valore di k1<0>
• k1<1> assume il valore di newk1, cioe' di k2<0>
23
ALGORITMO DI EUCLIDE: versione ricorsiva
//
//
//
//
//
//
//
//
PER IL CALCOLO DEL MCD DI DUE NUMERI
NATURALI  0
I = {i1, i2}
P = {k{1, 2}: ikN, i1i20}
O = {gcd},
C = {gcdN,
gcd = (i1!=0 && i2!=0) ? MCD(i1, i2)
: i1}
unsigned mcd (unsigned i1,
unsigned i2) {
assert((i1>=i2) && (i2>=0));
return (i2==0 ? i1 : mcd(i2, i1 % i2));
}
01
02
03
04
24
PROGRAMMA
•
E' UN ALGORITMO FORMULATO IN UN PARTICOLARE
LINGUAGGIO DI PROGRAMMAZIONE
•
IL LINGUAGGIO DEVE ESISTERE:
•
DEVONO ESISTERE INTERPRETI E/O COMPILATORI,
•
E LA SUA SEMANTICA DEVE ESSERE BEN DEFINITA
e.g. differenza (anche per la precedenza degli operatori!) tra
• lo statement Pascal
IF (N<>0) AND ((M DIV N) > K) THEN …
(semantica di valutazione dell'operatore AND per valore e
•
quindi statement errato)
lo statement C
if (N!=0 && M/N>K) … ;
(semantica di valutazione dell'operatore && per nome, o shortcircuit, e quindi statement corretto)
25
CORRETTEZZA DELL'ALGORITMO DI EUCLIDE
•
•
•
•
•
•
Assumiamo (w.l.g.) i1  i2 > 0
allora si puo' scrivere (qN, rN ): i1 = q * i2 + r
UN QUALSIASI NUMERO j CHE DIVIDE SIA i1 CHE i2 DEVE
DIVIDERE ANCHE r,
ED E' VERO ANCHE CHE QUALSIASI DIVISORE COMUNE DI i2
E r DEVE DIVIDERE ANCHE i1
CIO' E' VERO IN PARTICOLARE PER IL MCD DI i1 E i2
PERCIO' (indicando con r il resto della divisione di i1 per i2)
 SE r=0
ALLORA MCD(i1, i2) = i2
( UN NUMERO NON PUO' ESSERE DIVISO DA NUMERI
PIU' GRANDI DI LUI )
 SE r0
ALLORA LA RICERCA DI MCD(i1, i2) E' RICONDOTTA ALLA
RICERCA DI MCD(i2, i1 % i2)
(ESSENDO MCD(i1, i2) = MCD(i2, i1 % i2))
26
CORRETTEZZA DELL'ALGORITMO DI EUCLIDE
•
In realta' quello che abbiamo dimostrato e' la validita' della logica
dell'algoritmo
 Non abbiamo nemmeno fatto riferimento ad una versione
precisa dell'algoritmo/programma, tra le 4 che abbiamo
considerato!
 In effetti non ci siamo riferiti a nessuna descrizione precisa
dell'algoritmo
 N.B.: scrivere un programma e' una maniera di descrivere in
modo preciso un algoritmo.
Ci consente di parlarne in modo preciso
(perche’, per definizione, il significato di ogni statement del
programma deve essere chiaro e univoco).
•
Quello che vorremmo e':
• potere verificare la validita' logica degli algoritmi che
utilizziamo,
• potere verificare la correttezza dei programmi che scriviamo.
27
TERMINAZIONE DELL'ALGORITMO DI EUCLIDE
•
Assumiamo i1  i2 > 0
•
allora si puo' scrivere:
•
dove q = i1 / i2 e i2 > r  0
•
PERCIO':
•
SE r=0 L'ALGORITMO TERMINA IMMEDIATAMENTE
i1 = q * i2 + r
 e questo e' in particolare il caso quando i1=i2
•
SE r0 (e quindi i1>i2) ALLORA i1 E i2 DECRESCONO
STRETTAMENTE DA UNA ITERAZIONE ALL'ALTRA
•
ED ESSENDO 1  MCD(i1, i2)
•
LA PROCEDURA DEVE TERMINARE IN AL MASSIMO i2
ITERAZIONI
28
COMPLESSITA' DELL'ALGORITMO DI EUCLIDE
•
SI E' DETTO CHE L'ALGORITMO TERMINA AL MASSIMO IN i2
PASSI: SI RIESCE A DARE UN LIMITE PIU' STRINGENTE?
•
CONSIDERIAMO: i1 > i2 > 0, i1 = q * i2 + r
•
dove q = i1 / i2 e i2 > r  0
• SE i2  (i1 / 2) ALLORA IN UNA ITERAZIONE i1 SI
DIMEZZA (ALMENO)
• SE i2  (i1 / 2) ALLORA E' r < (i1 / 2) ED IN AL PIU' 2
ITERAZIONI i1 SI DIMEZZA
•
PERCIO' L'ALGORITMO E' DI COMPLESSITA' LOGARITMICA:
L'ITERAZIONE NON VIENE ESEGUITA PIU' DI 2*log2i1 VOLTE
•
NON ABBIAMO CERCATO UN RISULTATO ESATTO, MA UN
ORDINE DI COMPLESSITA'.
• QUESTO DIPENDE DALL'ALGORITMO,
• LE COSTANTI MOLTIPLICATIVE, ADDITIVE, ... ANCHE
DAL PROGRAMMA
29
CONFRONTO TRA LE DIVERSE VERSIONI
DELL'ALGORITMO DI EUCLIDE
•
DOMINIO DI DEFINIZIONE DELL'ALGORITMO, e.g.:
– NUMERI INTERI NON NEGATIVI vs. NUMERI INTERI
POSITIVI
– VINCOLO (pre-condizione) i1  i2
•
EFFICIENZA/TEMPO DI ESECUZIONE
Nell'esempio i quattro programmi condividono l'algoritmo, per cui
l'efficienza e’ dello stesso ordine.
– Pero’, ci sono differenze?
– Come si confronta la versione ricorsiva?
•
LUNGHEZZA DEL TESTO DEL PROGRAMMA
•
CHIAREZZA
– Utilizzo del linguaggio per esprimere caratteristiche del problema
– Scambio implicito di i1 e i2 quando i2 > i1 in euclide_3()
•
ELEGANZA (e.g. trattamento dei casi particolari)
•
DOCUMENTAZIONE, ORGANIZZAZIONE
30
STUDIO DEGLI ALGORITMI
•
•
•
•
1
COME INVENTARE ALGORITMI: STRATEGIE DI PROGETTO
– DIVIDE-AND-CONQUER,
– GREEDY METHOD,
– ALGORITMI PROBABILISTICI,
– ...
COME DIMOSTRARE CHE NON ESISTONO ALGORITMI
EFFICIENTI O CHE UN PROBLEMA E' TROPPO DIFFICILE
{ CHI LO RISOLVESSE VINCEREBBE IL PREMIO
NOBEL PER L'INFORMATICA, ISTITUITO
APPOSITAMENTE }
E, PIU' IN GENERALE, COME VALUTARE LA
COMPLESSITA' DI UN PROBLEMA
COME ESPRIMERE ALGORITMI, cioe` COME SCRIVERE
PROGRAMMI
– PROGRAMMAZIONE STRUTTURATA
– PROGETTAZIONE TOP-DOWN
– PROGETTAZIONE PER RAFFINAMENTI SUCCESSIVI
31
STUDIO DEGLI ALGORITMI
•
•
•
2
COME VERIFICARE
– LA CORRETTEZZA
– LA TERMINAZIONE
DI UN ALGORITMO O PROGRAMMA
COME ANALIZZARE LA EFFICIENZA/COMPLESSITA'
– NELLO SPAZIO (e.g. STRUTTURE DATI IN MEMORIA)
– NEL TEMPO (DI ESECUZIONE)
DI UN PROGRAMMA
COME OPERARE
– DEBUGGING
– TESTING
– PROFILING (caratterizzazione)
DI UN PROGRAMMA.
(N.B. NON SEMPRE L'ALGORITMO TEORICAMENTE
OTTIMALE E' IL MIGLIORE DA USARE PRATICAMENTE, e.g.
Quicksort, algoritmo di Dantzig per la Programmazione Lineare,
sort di piccoli array)
32
PIDGIN C
•
•
•
•
•
NEL CORSO DESCRIVIAMO ALGORITMI
(ma per farlo di solito scriveremo dei programmi in C!)
L'IMPORTANTE E' CHE LE AZIONI DESCRITTE SIANO
– BEN DEFINITE
– EFFICACI
PER BEN DEFINIRE UNA OPERAZIONE SI POSSONO
UTILIZZARE
– LINGUAGGI DI PROGRAMMAZIONE, e.g. C
– ALTRI LINGUAGGI (, , |, , , #, ...)
(l'operatore # applicato a un insieme, lista, … ne ritorna la
cardinalita')
– AL LIMITE L'ITALIANO
 PIDGIN C
CIO' SI APPLICA ANCHE A STRUTTURE DATI (e.g. INSIEMI)
OCCORRE PERO' SEMPRE
– VERIFICARE CHE LE AZIONI DESCRITTE SIANO EFFICACI
– E INDICARNE L'ORDINE DI COMPLESSITA'
33