Universita' di Ferrara
Facolta' di Scienze Matematiche, Fisiche e Naturali
Laurea Specialistica in Informatica
Algoritmi Avanzati
Progettazione di algoritmi:
stepwise refinement e differenziazione formale
• topological sort di un grafo orientato
Copyright © 2006-2009 by Claudio Salati.
Lez. 12
1
TOPOLOGICAL SORT
• s E' UN INSIEME TRA I CUI ELEMENTI E' DEFINITO UN
ORDINAMENTO PARZIALE DESCRITTO DALLA RELAZIONE
after
• after E' UN SOTTOINSIEME DEL PRODOTTO CARTESIANO
ss, CIOE' UN INSIEME DI COPPIE (x, y), TALI CHE y after x.
• INDICHIAMO CON after(x) L'INSIEME DI ELEMENTI CHE
SEGUONO DIRETTAMENTE x NELL'ORDINAMENTO
PARZIALE, cioe'
after(x) = { y  s | (x, y)  after }
• after PUO' ESSERE VISTA COME UNA FUNZIONE
MULTIVALORE DA s A s, O COME UNA FUNZIONE DA s A
POWERSET(s)
• after e': asimmetrica, transitiva (ma le relazioni ottenibili per
transitivita' non sono rappresentate), non riflessiva
2
TOPOLOGICAL SORT
• Problema: A PARTIRE DA after VOGLIAMO DEFINIRE UN
ORDINAMENTO TOTALE order CHE SIA COMPATIBILE CON
after.
•
N.B.: DI ORDINAMENTI TOTALI COMPATIBILI CON after CE
NE POSSONO ESSERE DIVERSI: uno qualunque ci va bene.
• Esempio:
– s = { A, B, C, D }
– after(A) = { B, C }, after(B) = D, after(C) = D
– Ordinamenti totali compatibili:
• A, B, C, D
B
• A, C, B, D
A
D
C
3
TOPOLOGICAL SORT
•
L'INSIEME s E LA RELAZIONE after POSSONO ESSERE RAFFIGURATI
COME UN GRAFO ORIENTATO ACICLICO:
• s = INSIEME DEI NODI
• after = INSIEME DEI LATI
•
IL PROBLEMA E' CHIAMATO TOPOLOGICAL SORT DI UN GRAFO
•
L'ALGORITMO DI TOPOLOGICAL SORT PUO' ANCHE SERVIRE A
DETERMINARE SE UN GRAFO ORIENTATO E' ACICLICO, CIOE' SE I
SUOI LATI SONO TALI DA DEFINIRE UN ORDINAMENTO PARZIALE DEI
NODI
• SE IL GRAFO E' ACICLICO, ALLORA E' POSSIBILE DEFINIRE UN
ORDINAMENTO TOTALE order COMPATIBILE CON after
• SE IL GRAFO E' CICLICO, CIO' NON E' POSSIBILE.
•
ESEMPI DI APPLICAZIONE:
• LAVORI DA FARE IN UN PROGETTO
• PREREQUISITI TRA CORSI DI UN PROGRAMMA DI STUDI
• ORDINAMENTO DEGLI ARGOMENTI IN UN LIBRO
4
TOPOLOGICAL SORT
// algoritmo base
void topSort(SET<node> s,
// in
SET<edge> after,
// in
LIST<node>& order) {
// out
order = <>;
// LISTA VUOTA
while ( nexts | ( precs |
(prec, next)after)) {
// RIMUOVO next DA s
s = s - {next};
// AGGIUNGO ORDINATAMENTE (in fondo)
// next A order
order = order + <next>;
}
if (s != ) order = UNDEFINED;
// GRAFO CON CICLI
}
1
2
3
4
5
6
5
TOPOLOGICAL SORT
• L'ALGORITMO E' MOLTO INEFFICIENTE PERCHE' E' PIENO
DI CICLI, IMPLICITI E/O ESPLICITI
•  next  s IMPLICA UNA SCANSIONE DEL SET
•  prec  s IMPLICA UNA SCANSIONE DEL SET
• |(prec, next)  after IMPLICA UNA
SCANSIONE DEL SET
E CIO' COMUNQUE s E after SIANO RAPPRESENTATI
• IL PROBLEMA E' CHE AD OGNI ITERAZIONE DEL CICLO
while CONTINUIAMO A RICALCOLARE SEMPRE LE
STESSE INFORMAZIONI
• MA ALLORA UNA VOLTA CHE LE ABBIAMO CALCOLATE, LE
POSSIAMO MEMORIZZARE IN VARIABILI AGGIUNTIVE PER
POI UTILIZZARLE NELLE ITERAZIONI SUCCESSIVE!
• Ovviamente ogni iterazione deve anche modificare il valore di
queste variabili aggiuntive, cosi' da mantenerle aggiornate e
congruenti
6
TOPOLOGICAL SORT
•
 precs | (prec, next)  after
PER OGNI next  s POSSIAMO CONTARE UNA VOLTA PER
TUTTE QUANTI SONO I NODI
prec | (prec, next)  after
• DEFINIAMO UNA FUNZIONE numBefore CHE PER OGNI
NODO DI s INDICA IL SUO IN-DEGREE (IL NUMERO DI LATI
ENTRANTI)
• UNA FUNZIONE E' UNA SPECIALE RELAZIONE, ED E'
QUINDI DI NUOVO DESCRIVIBILE COME UN INSIEME DI
COPPIE (nodo, numero) CON nodos E numeroN
(NATURALI)
• PER MANTENERE AGGIORNATO numBefore(n)
OCCORRE E BASTA DECREMENTARE numBefore(n)
( n  after(next)) QUANDO INSERISCO next
NELL'ORDINAMENTO TOTALE
7
TOPOLOGICAL SORT
// primo raffinamento
void topSort(SET<node> s,
// in
SET<edge> after,
// in
LIST<node>& order) {
// out
PAIR inDegree {
node nodo;
int
numero; };
order = <>;
// LISTA VUOTA
SET<inDegree> numBefore = {(n, 0) : n  s};
for ((prec, next)after) numBefore(next) += 1;
while ( nexts | numBefore(next)==0) {
// RIMUOVO next DA s
s = s - {next};
for (n  after(next)) numBefore(n) -= 1;
// AGGIUNGO next A order
order = order + <next>;
}
if (s!=) order = UNDEFINED; // GRAFO CON CICLI
}
1
2
3
4
5
6
7
8
9
10
11
12
13
8
TOPOLOGICAL SORT
• In questa versione di topSort() ogni lato del grafo e' scandito una
sola volta (per decrementare after(next))
N.B.: a patto di poter facilmente calcolare after(next)
• ovviamente si e' dovuto aggiungere l'inizializzazione di numBefore,
ma questa e' O(#s + #after)
• c'e' pero' ancora un ciclo implicito di scansione di s:
 nexts | numBefore(next)==0
ma noi, quando inizializziamo numBefore e quando lo
aggiorniamo, sappiamo bene se e' 0 o no!
• percio' possiamo definire una nuova variabile, ready, che e'
l'insieme dei nodi di s tali che il relativo numBefore sia 0
• in questo modo
 nexts | numBefore(next)==0
diventa
ready != 
• l'inizializzazione di ready e' O(#s)
9
TOPOLOGICAL SORT
// raffinamento finale
void topSort(SET<node> s,
SET<edge> after,
LIST<node>& order) {
// in
// in
// out
PAIR inDegree {
node nodo;
int
numero; };
// inizializzazione
order = <>;
// LISTA VUOTA
SET<inDegree> numBefore = {(n, 0) : n  s};
for ((prec, next)after) numBefore(next) += 1;
SET<node> ready = { ns | numBefore(n)==0 };
// continua alla pagina seguente
10
TOPOLOGICAL SORT
// raffinamento finale: continua
while (ready != ) {
// estrae un elemento qualunque da ready
next = extractFrom(ready);
// RIMUOVO next DA s
s = s - {next};
for (n  after(next)) {
numBefore(n) -= 1;
if (numBefore(n) == 0) {
ready = ready  {n};
}
}
// AGGIUNGO next A order
order = order + <next>;
}
if (s != ) order = UNDEFINED;
// GRAFO CON CICLI
}
11
TOPOLOGICAL SORT
• tutto l'algoritmo e' stato reso O(#s+#after) in quanto nodi e lati del
grafo sono scanditi un numero costante di volte
 pero': con quali strutture dati si possono rappresentare s, after,
numBefore, ready, order?
• fino ad ora non se ne e' parlato, ma anche per le strutture dati si puo'
operare per raffinamenti successivi.
• ovviamente, perche' l'algoritmo abbia effettivamente la complessita'
indicata occorre che gli accessi previsti alle strutture dati abbiano
tempo indipendente da #s e #after (le dimensioni di numBefore e
ready dipendono da #s); e.g.:
• estrazione di un nodo noto da s
• estrazione di un elemento a caso di ready
• inserimento di un elemento (in un posto qualunque) in ready
• inserimento di un elemento in coda a order
• scansione di tutti e soli i lati uscenti di un nodo
12
TOPOLOGICAL SORT
• Esercizio: completare la definizione in C della funzione topSort()
utilizzando strutture dati che garantiscano che la sua complessita' sia
O(#s+#after)
• N.B.: per ready si dice di estrarre un elemento a caso.
Non avremmo dovuto estrarre gli elementi da ready in ordine FIFO?
• In base alla risposta progettare la struttura dati piu’ adatta per
realizzare ready.
13
DIFFERENZIAZIONE FORMALE
• Per passare dall'algoritmo iniziale a quello finale si e' applicata
due volte una tecnica di programmazione detta
differenziazione formale.
• Questa tecnica consiste nell'introdurre variabili addizionali per
mantenere informazioni che e' necessario avere a disposizione
e che altrimenti sarebbe necessario ri/calcolare.
• Non necessariamente queste variabili compaiono esplicitamente
nella logica dell'algoritmo originale.
• Le considerazioni con cui sono introdotte queste variabili
aggiuntive sono le seguenti:
 una quantita' q e' bene ricordarla se:
1. informazioni necessarie al programma sono
esprimibili in modo facile ed efficiente usando q
2. e' facile ed efficiente mantenere aggiornata q
• Ovviamente i termini facile ed efficiente devono essere misurati
secondo una qualche metrica e confrontati con il resto
14
dell'algoritmo
DIFFERENZIAZIONE FORMALE
 Esempio banale:
m
• vogliamo una funzione che stampi il valore di
k
k 1
con m che assume tutti i valori dei primi n interi positivi.
• una prima versione della funzione, di complessita' O(n2), e' la
seguente:
void printSums(int n) {
for (int m=1; m<=n; m+=1) {
int sum = 0;
for (int k=1; k<=m; k+=1) sum += k;
printf("+/[i : i=1..%d] = %d\n",
m, sum);
}
}
15
DIFFERENZIAZIONE FORMALE
 Esempio banale (continua):
• Il problema di questa funzione e' che il calcolo della sommatoria,
per ogni m, ha complessita' O(m)
• Una prima alternativa e' data dalla applicazione della tecnica
della semplificazione algebrica al calcolo della sommatoria.
m
*(m

1
)
k

possiamo riscrivere printSums()

2
k

1
m
• Poiche'
void printSums(int n) {
for (int m=1; m<=n; m+=1) {
int sum = m * (m+1) / 2;
printf("+/[i : i=1..%d] = %d\n",
m, sum);
}
}
16
DIFFERENZIAZIONE FORMALE
 Esempio banale (continua):
• l'algoritmo che abbiamo ottenuto e' O(n) perche' il calcolo della
sommatoria e' O(1): richiede un numero costante di operazioni,
una somma un prodotto e una divisione
• si puo' fare ancora meglio?
• si' se applichiamo la tecnica della differenziazione formale alla
versione banale di printSums()
• notiamo che
m
m

1
k
1
k
1
km

k

• cioe' il risultato della sommatoria ad una iterazione e' facilmente
ottenibile dal valore della sommatoria all'iterazione precedente
17
DIFFERENZIAZIONE FORMALE
 Esempio banale (continua):
void printSums(int n) {
int sum = 0;
for (int m=1, m<=n, m+=1) {
sum = sum + m;
printf("+/[i : i=1..%d] = %d\n",
m, sum);
}
}
• anche questo algoritmo e' O(n) perche' il calcolo della
sommatoria e' anche in questo caso O(1): richiede un numero
costante di operazioni, una sola somma
(risparmiamo un prodotto e una divisione per iterazione)
18
DIFFERENZIAZIONE FORMALE
• Esercizio: utilizzare la tecnica della differenziazione formale per
migliorare la funzione evalP() per il calcolo di polinomi (vedi
lezione 11), eliminando la necessita' di utilizzare la funzione
pow().
19