Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Strategie per la progettazione di algoritmi:
semplificazione e trasformazione algebrica,
tecniche di Montecarlo
• Horner's rule
• simulated annealing
Copyright © 2006-2009 by Claudio Salati.
Lez. 11
1
SEMPLIFICAZIONE ALGEBRICA
 Strategia: una formula di calcolo e' espressa in forma
diversa per ridurre (minimizzare) il numero di operazioni
necessarie per calcolarla.
•
Esempio:
• abbiamo un polinomio P(x) di grado n rappresentato come
vettore dei suoi coefficienti.
(compresi quelli di valore 0.0!)
• vogliamo valutarlo in un punto x
•
Una prima maniera di scrivere il polinomio e' la seguente:
P(x) = pn * xn + pn-1 * xn-1 + … +p1 * x + p0
•
che puo' ovviamente essere immediatamente utilizzata per
realizzare la funzione desiderata.
2
SEMPLIFICAZIONE ALGEBRICA
float evalP(int n, float P[], float x) {
// n e' il grado del polinomio P(x)
float y = P[0];
for (int i = 1; i <= n; i += 1)
y = y + P[i] * pow(x, i);
// end for
return (y);
}
•
questa procedura si basa sull'utilizzo della funzione della
libreria standard C
#include <math.h>
float pow(float x, float y);
che ritorna il valore xy
3
SEMPLIFICAZIONE ALGEBRICA
•
Il polinomio P(x) puo' pero' anche essere scritto come:
P(x) = (…(pn * x + pn-1) * x + pn-2) * x +… +p1) * x + p0
secondo la regola di Horner.
•
A partire da questa riscrittura possiamo scrivere una nuova
funzione per il calcolo di P(x):
float hornerP(int n, float P[], float x) {
// n e' il grado del polinomio P(x)
float y = P[n];
for (int i = n-1; i >= 0; i -= 1)
y = y * x + P[i];
// end for
return (y);
}
4
SEMPLIFICAZIONE ALGEBRICA
•
Le due funzioni hanno lo stesso ordine di complessita'
 ma solo a condizione che il calcolo di pow(x, i) avvenga in
tempo costante!
•
In ogni caso
• il calcolo di una potenza e' ovviamente molto piu' complesso del
calcolo di un semplice prodotto;
• l'algoritmo evalP() richiede comunque anche il calcolo di un
prodotto
(un prodotto e una potenza contro un prodotto e basta)
•
N.B.: in effetti, nel calcolo secondo la regola di Horner, sarebbe stato
piu’ conveniente memorizzare i coefficienti nel vettore in ordine di
potenza decrescente (most significant digit first, o big endian, che e’
anche l’ordine di scrittura fisiologico), a differenza di quello che si e’
fatto nell’altro caso.
•
N.B.: un numero in notazione posizionale puo’ essere visto come un
polinomio valutato nella sua base, ma in questo caso le potenze 5
sono decrescenti da sinistra a destra (la notazione e’ big endian)!
SEMPLIFICAZIONE ALGEBRICA
Esercizio: la funzione della libreria standard (modulo stdlib)
int atoi(const char *s);
che converte in un intero la stringa numerica s (che noi assumiamo non
negativa), puo' essere realizzata efficientemente utilizzando la Horner's rule:
 la stringa s viene scandita
• una sola volta
• da sinistra (inizio, digit piu' pesante) a destra (fine, digit piu' leggero).
 si considera sostanzialmente che la stringa
• rappresenti un polinomio P(x) di grado strlen(s)-1,
• in cui il k-esimo carattere della stringa (k numerato a partire da 0)
rappresenti il coefficiente del termine di grado strlen(s)-1-k
• e con x==10
Notare che la lunghezza di s non e' nota (a priori), e non puo' essere
calcolata da atoi() tramite strlen(), perche' cio' vorrebbe dire scandire
tutta s.
Scrivere in C la funzione atoi().
6
Horner’s rule: un’altra prospettiva
Prologo, da A. Natali:
"Come esempio di linguaggio, consideriamo la notazione
posizionale dei numeri interi, che siamo cosi' abituati ad usare da
confonderla spesso con il concetto di numero.
Se scriviamo la seguente configurazione di segni:
135
la maggior parte delle persone la leggera' pronunciando la parola
centotrentacinque, modo sintetico per esprimere il significato
inteso, cioe' il numero uno*cento+tre*dieci+cinque*uno.
Un numero costituisce pero' una astrazione che non va
assolutamente confusa con la notazione che si usa per esprimerla.
Ed infatti vi sono molteplici modi per denotare lo stesso numero."
Cosi' come ci sono diversi modi di leggere la stringa 135 (pur
sempre vista come stringa in notazione posizionale in base 10) per
arrivare ad assegnarle il significato centotrentacinque.
7
Horner’s rule: un’altra prospettiva
• distinzione tra astrazione numero (di seguito espressa, come nelle
righe precedenti, scrivendo il numero in linguaggio naturale) e
notazione utilizzata per rappresentarlo
• ci si limita a considerare la notazione posizionale
• base B  B simboli diversi nell'alfabeto
B = otto, A = {0, 1, 2, 3, 4, 5, 6, 7}
B = sedici, A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f}
B = due, A = {0, 1} o anche {-, |}
1310 = tredici, 138 = undici, 1316 = diciannove, 132 = errore
10112 = undici, |-|| = undici
• la frase an an-1 ... a1 a0 ha il seguente significato
an * Bn + an-1 * Bn-1 + ... + a1 * B1 + a0 * B0
ak e' una cifra B-esimale da zero a B-1
• il linguaggio dei numeri naturali espressi in notazione posizionale in
base B coincide con A+
8
Horner’s rule: un’altra prospettiva
• lo stesso linguaggio puo' essere descritto in forma costruttiva
tramite una sua grammatica.
• esempio, per B = due
• grammatica 1 (regolare)
VT = {0, 1}
VN = {N}
S=N
P = { N ::= N 0 | N 1 | 0 | 1 }
• grammatica 2 (context-free)
VT = {0, 1}
VN = {N, C}
S=N
P = { N ::= N C | C
C ::= 0 | 1 }
9
Horner’s rule: un’altra prospettiva
• l'albero di derivazione di una espressione ci fornisce
informazioni addizionali sulla struttura reale dell'espressione
(e.g. quali operatori sono operandi-sottoespressioni di quali altri
operatori)
• l'albero di derivazione di una frase del nostro linguaggio ci puo'
cioe' aiutare a interpretare la frase (ad assegnarle il significato)
N
/ \
N
C
/ \ |
N
C 1
/ \ |
N
C 1
|
|
C
0
|
1
10
Horner’s rule: un’altra prospettiva
• in maniera alternativa all'interpretazione basata sulla notazione
posizionale che leggerebbe la frase come
uno*duetre + zero*duedue + uno*dueuno + uno*duezero = undici
qui si vuole definire una diversa regola di lettura semantica
basata sulla struttura sintattica della frase
• un numero N e' composto da una parte N e da una parte C, e
cosi' ricorsivamente
N = 1011
N = N0(=101)  C(1)
N = N0(=N1(=10)  C(1))  C(1)
...
• A. Natali:
"Per stabilire il significato delle frasi di L(G), occorre fissare una
corrispondenza tra ciascuna frase e uno specifico dominio di
interpretazione, che in questo caso e' evidentemente il dominio
11
NAT dei numeri naturali."
Horner’s rule: un’altra prospettiva
• A. Natali: “Seguendo un approccio di tipo denotazionale, il significato
delle frasi di L(G) puo' essere stabilito introducendo opportune
funzioni di interpretazione per stabilire la corrispondenza tra ogni
categoria sintattica (simbolo non terminale) e i numeri naturali."
• Cioe’ tra ogni produzione di ogni simbolo non terminale e i numeri
naturali: cio' porta ad assegnare anche un significato ai simboli
terminali.
• L(G)  semantica denotazionale  NAT
• C2NAT: C  NAT
• C2NAT( 0 ) = zero
• C2NAT( 1 ) = uno
• N2NAT: N  NAT
• N2NAT( C ) = C2NAT( C )
• N2NAT( N C ) = due * N2NAT( N ) + C2NAT( C )
• in grassetto sono indicati gli elementi del dominio di interpretazione,
valori (zero, uno, due) e funzioni semantiche (* e +)
12
Horner’s rule: un’altra prospettiva
• A. Natali: “Se la frase generata da N e' derivabile con la produzione
N ::= C, il suo significato e' ricondotto alla funzione C2NAT.
• Se la frase generata da N e' derivabile con la produzione N ::= N C,
il significato e' ricondotto alla struttura della frase moltiplicando per
due il significato denotato dalla parte N e sommando il valore
(significato) della parte C."
• N2NAT(1011) =
N2NAT(101) * due + C2NAT(1) =
(N2NAT(10) * due + C2NAT(1)) * due + uno =
((N2NAT(1) * due + C2NAT(0)) * due + uno) * due + uno =
((C2NAT(1) * due + zero) * due + uno) * due + uno =
((uno * due + zero) * due + uno) * due + uno =
(due * due + uno) * due + uno =
cinque * due + uno = undici
13
Semantica di un linguaggio: descrizione formale
• non solo la sintassi di un linguaggio di programmazione puo' essere
specificata in modo formale, ma anche la sua semantica
• tre metodi per specificare in modo formale la semantica di un
linguaggio
• semantica interpretativa
• si da' un interprete modello
(il metodo del metro campione dell'istituto Galileo Ferraris)
• semantica denotazionale
• si associa una funzione di interpretazione ad ogni simbolo non
terminale della grammatica
• semantica assiomatica
14
Semantica delle espressioni
• grammatica per espressioni aritmetiche su numeri interi
E ::= E + T | T
T ::= T * F | F
F ::= ( E ) | N
• in grassetto sono segnati i simboli terminali
• questa grammatica si collega a quella che descrive il linguaggio dei
numeri naturali (simbolo non terminale N)
• il dominio di interpretazione dei numeri naturali (in realta' interi) e'
ovviamente anche il dominio di interpretazione per le espressioni
aritmetiche qui considerate
• E2NAT( E + T ) = E2NAT( E ) + T2NAT( T )
• E2NAT( T ) = T2NAT( T )
• T2NAT( T * F ) = T2NAT( T ) * F2NAT( F )
• T2NAT( F ) = F2NAT( F )
• F2NAT( ( E ) ) = E2NAT( E )
• F2NAT( N ) = N2NAT( N )
15
TRASFORMAZIONE ALGEBRICA
 Strategia: per risolvere un problema A lo si trasforma in
un problema correlato B, si risolve B, e si opera la
trasformazione inversa del risultato.
•
Tutto dipende ovviamente dal costo relativo delle trasformazioni
diretta e inversa, e dal costo del calcolo della soluzione per il
problema trasformato B:
•
esempio banale:
OPERAZIONI ARITMETICHE SU STRINGHE DI DIGIT CHE
RAPPRESENTANO NUMERI INTERI O REALI ATTRAVERSO
LA TRASFORMAZIONE IN RAPPRESENTAZIONE BINARIA O
FLOATING-POINT
•
esempio complesso (e importantissimo):
TRASFORMATA DI FOURIER
16
TECNICHE DI MONTECARLO
 Strategia: BASATE SULLA GENERAZIONE E
L'UTILIZZO DI NUMERI RANDOM, POSSIBILMENTE
CON DIVERSE DISTRIBUZIONI.
• PER SIMULAZIONI
• PER ALTRI TIPI DI PROBLEMI
17
TECNICHE DI MONTECARLO
ESEMPIO 1: CALCOLARE LA MEDIA DI n NUMERI, CON n
MOLTO GRANDE.
•
L'ALGORITMO OVVIO E' O(n), PERCHE' DEVO
CONSIDERARE TUTTI I NUMERI DELLA SEQUENZA
•
MA SI PUO' FARE IN O(1) !
•
SCELGO m << n (m FISSO, INDIPENDENTE DA n) NUMERI
A CASO NELLA SEQUENZA, E FACCIO LA LORO MEDIA.
•
OVVIAMENTE HO SOLO UN VALORE APPROSSIMATO, MA
QUANTO VICINO AL VALORE MEDIO VERO?
•
LA MEDIA ARITMETICA MA SU m VALORI E' UNA STIMA
• CORRETTA (MEDIA DELLE MA = VALOR MEDIO)
• CONSISTENTE (lim (MA) = VALOR MEDIO)
mn
• EFFICIENTE (CONVERGE IN FRETTA)
18
MONTECARLO - SIMULATED ANNEALING
CONSIDERIAMO DI DOVERE POSIZIONARE DEI CHIP SU UNA
SCHEDA O DELLE MACROFUNZIONI IN UN CHIP
• I SOTTOCIRCUITI DEBBONO ESSERE CONNESSI TRA
LORO IN MODO NOTO, E
• LA DISTANZA RECIPROCA E' CONDIZIONATA DAL
NUMERO DI INTERCONNESSIONI RECIPROCHE
• IL POSIZIONAMENTO DEVE TENERE CONTO DI VINCOLI
QUALI
•
VELOCITA'
•
AREA PER DRIVER DELLE LINEE
•
OCCUPAZIONE DI AREA DELLE CONNESSIONI
• IL NUMERO DI INCROCI DEVE ESSERE MINIMIZZATO
19
MONTECARLO - SIMULATED ANNEALING
• SI DEVE MINIMIZZARE UNA FUNZIONE COSTO
DEFINITA SU UN DOMINIO MULTIDIMENSIONALE
(POSIZIONE DI TUTTI I SOTTOCIRCUITI).
• NON SOLO IL PROBLEMA E' OGGI INTRATTABILE,
•
RISULTA FACILE CON LE EURISTICHE NOTE FARSI
INTRAPPOLARE IN MINIMI LOCALI
(E' OVVIO CHE CIO' ACCADE CON UNA STRATEGIA
GREEDY!)
 la soluzione e': SIMULATED ANNEALING
(to anneal = temprare)
O CRISTALLIZZAZIONE SIMULATA
• ovvero, COME E' CHE SI FORMANO (mono-)CRISTALLI
ANZICHE' SOLIDI AMORFI (o poli-cristalli)?
20
MONTECARLO - SIMULATED ANNEALING
stato simulatedAnnealing(stato x, float temp) {
// x : configurazione considerata nel dominio
//
degli stati possibili
// temp : temperatura simulata del processo
// y : configurazione verso la quale si
//
ipotizza di muoversi
stato y;
while (!acceptable(x)) {
while (stabile(temp)) {
y = nuovoStato(x);
if (siAccetta(costo(y), costo(x), temp))
x = y;
// end if
}
temp = decrementa(temp);
}
return (x);
}
21
MONTECARLO - SIMULATED ANNEALING
int siAccetta(float oldCost x, float newCost,
float temp) {
float delta = newCost - oldCost;
if (delta<0.0) return (1); //1==true
else {
float probabilita = exp(-delta/temp);
return ((float)rand()/(float)RAND_MAX) <
probabilita));
}
}
•
una nuova configurazione e' sempre accettabile se il suo costo e'
minore di quello della configurazione precedente
•
una nuova configurazione puo' essere accettata anche se il suo costo e'
maggiore o uguale del costo della configurazione precedente: ma cio' e'
tanto meno probabile quanto piu' la temperatura si avvicina allo 0.
•
cio' consente, all'inizio del processo di cristallizzazione, di allontanarsi
da minimi locali
22
MONTECARLO - SIMULATED ANNEALING
•
IL CRITERIO DI RAFFREDDAMENTO E' REALIZZATO DALLE
PROCEDURE stabile() E decrementa():
• stabile() DETERMINA LA FREQUENZA DI
RAFFREDDAMENTO,
• decrementa() STABILISCE DI QUANTO SI ABBASSA
LA TEMPERATURA
•
PIU' SI MANTIENE ELEVATA temp E PIU' SI DA' SPAZIO AL
SISTEMA DI RAGGIUNGERE LA CONFIGURAZIONE PIU'
PROBABILE, CHE E' QUELLA CON costo() MINIMO
•
PER NUMERO DI PASSI INFINITO LA PROBABILITA' DI
COVERGERE ALLA CONFIGURAZIONE DI COSTO MINIMO
E' COMUNQUE 1
23
MONTECARLO - SIMULATED ANNEALING
•
PIU' ALTA E' LA TEMPERATURA INIZIALE E PIU' IN FRETTA
SI RAGGIUNGE LA CONDIZIONE PIU' PROBABILE
•
PER GARANTIRE LA CONVERGENZA IN NUMERO FINITO
DI PASSI LA POLITICA DI stabile()/decrementa()
DEVE ESSERE OPPORTUNA, CIOE' IL RAFFREDDAMNETO
NON DEVE ESSERE TROPPO RAPIDO
•
SE SI FA UNA SOLA MOSSA AD OGNI LIVELLO DI
TEMPERATURA (temp E' decrementa()-TO IN
CONTINUAZIONE) ALLORA decrementa() DEVE
CALARE DI POCO
24