Esistono potenti tecniche che permettono di determinare una stima asintotica di una sequenza fn conoscen-do la sua funzione generatrice F (z) in forma chiusa oppure in moconoscen-do implicito. In effetti, sono questi i metodi che attribuiscono importanza all’uso delle funzioni generatrici. Non vogliamo qui addentrar-ci nello studio generale di questa problematica, che richiede nozioni preliminari di teoria delle funzioni analitiche; ci limitiamo a valutare il comportamento asintotico di fnper alcune particolari funzioni F (z).
7.5.1 Funzioni razionali
Le funzioni razionali in una variabile sono quelle che possono essere rappresentate nella forma P (z)Q(z) dove P (z) e Q(z) sono polinomi in z. Queste funzioni sono rilevanti nel nostro contesto poich´e si pu`o facilmente provare che una sequenza {fn} `e soluzione di una equazione di ricorrenza lineare omogenea a coefficienti costanti (vedi la sezione 6.5.1) se e solo se la sua funzione generatrice `e razionale. Come sappiamo tali equazioni compaiono spesso nell’analisi di algoritmi.
Consideriamo allora la funzione generatrice F (z) di una sequenza {fn} e supponiamo che F (z) = P (z)
Q(z),
dove P (z) e Q(z) sono polinomi primi fra loro nella variabile z. Senza perdita di generalit`a possiamo assumere che il grado di P (z) sia minore del grado di Q(z). Inoltre `e chiaro che le radici di Q(z) sono diverse da 0 altrimenti F (z) non sarebbe continua e derivabile in 0 (e quindi {fn} non sarebbe definita). Per semplicit`a supponiamo che Q(z) abbia m radici distinte z1, z2, . . . , zm, di molteplicit`a 1 e fra queste ve ne sia una sola di modulo minimo. Possiamo allora determinare la decomposizione di F (z) in frazioni parziali P (z) Q(z) = m X k=1 Ak zk− z
Per le ipotesi fatte, tale decomposizione esiste sempre e inoltre, per la regola de l’Hˆopital, ogni costante Ak, per k = 1, 2, . . . , m, soddisfa la relazione seguente:
Ak= lim z→zk(zk− z) · P (z) Q(z) = P (zk) · limz→zk zk− z Q(z) = − P (zk) Q0(zk). Poich´e F (z) =Pm k=1 Azkk·1−z/z1 k, ricordando che 1−z/z1 k `e la funzione generatrice di {z1n k }n≥0, possiamo concludere che fn= m X k=1 Ak (zk)n+1.
Se siamo interessati al comportamento asintotico, basta osservare che nella somma il termine princi-pale `e quello corrispondente alla radice di minor modulo. Tale propriet`a `e generale e vale anche quando le altre radici hanno molteplicit`a maggiore di 1. Abbiamo quindi provato la seguente propriet`a .
Proposizione 7.1 Consideriamo una funzione razionale F (z) = P (z)/Q(z), dove P (z) e Q(z) sono
polinomi primi fra loro, con Q(0) 6= 0; supponiamo che Q(z) abbia un’unica radice z di modulo minimo e che tale radice abbia molteplicit`a 1. Allora, per n → +∞, la sequenza {fn} associata alla funzione F (z) soddisfa la relazione
fn∼ − P (z) Q0(z)zn+1.
Con tecniche analoghe si ottiene il seguente risultato, valido per radici di molteplicit`a arbitraria:
Proposizione 7.2 Sia F (z) una funzione razionale F (z) = P (z)/Q(z), dove P (z) e Q(z) sono
poli-nomi primi fra loro, con Q(0) 6= 0; supponiamo inoltre che Q(z) ammetta un’unica radice z di modulo minimo. Se z ha molteplicit`a m allora la sequenza la sequenza {fn} associata alla F (z) soddisfa la
relazione fn= Θ nm−1· 1 zn . 7.5.2 Funzioni logaritmiche
Consideriamo ora una classe di funzioni non razionali e studiamo il comportamente asintotico delle sequenze associate.
Proposizione 7.3 Per ogni intero α ≥ 1 la funzione
1
(1 − z)α · log 1 1 − z
`e la funzione generatrice di una sequenza {fn} tale che fn= Θ(nα−1log n).
Dimostrazione. Ragioniamo per induzione su α. Nel caso α = 1 il risultato `e gi`a stato dimostrato nelle
sezioni precedenti; infatti sappiamo che 1 1 − zlog 1 1 − z = +∞ X n=1 Hnzn
dove Hn=Pn
k=1k1 ∼ log n.
Supponiamo ora la propriet`a vera per α fissato, α ≥ 1, e dimostriamola vera α + 1. Denotiamo con fn(α)la sequenza associata alla funzione(1−z)1 αlog1−z1 . Si verifica subito che {fn(α+1)} `e la convoluzione delle sequenze {fn(α)} e {1} poich´e la sua funzione generatrice `e il prodotto delle funzioni generatrici corrispondenti.
Di conseguenza possiamo scrivere fn(α+1)=
n
X
k=0
fk(α) = (per ipotesi di induzione) =
n
X
k=1
Θ(kα−1log k) = (applicando la proposizione 2.5) = Θ n X k=1 kα−1log k ! = (per la proposizione 2.8) = Θ Z n 1 xα−1log xdx
= (integrando per parti) = Θ(nαlog n).
Concludiamo osservando che la proposizione precedente pu`o essere estesa al caso in cui α ∈ IR, purch´e α 6= 0, −1, −2, . . . , −n, . . . .
Esercizi
1) Considera le seguenti procedure F e G che calcolano rispettivamente i valori F (n) e G(n) su input
n ∈ IN:
ProcedureG(n) ProcedureF (n)
begin ifn = 0then return1
S = 0 else returnF (n − 1) + G(n − 1)
for i = 0, 1, 2, . . . , ndo
S = S + F (i)
returnS
end
a) Dimostrare che, su input n, le due procedure richiedono Ω(an) operazioni aritmetiche per qualche a > 1.
b) Calcolare le funzioni generatrici delle sequenze {F (n)} e {G(n)} e determinare la loro espressione asintotica per n −→ +∞.
c) Definire un algoritmo per calcolare F (n) e G(n) che esegua un numero di operazioni aritmetiche polinomiale in n.
2) Considera le seguenti procedure F e G che calcolano rispettivamente i valori F (n) e G(n) su input
n ∈ IN:
ProcedureG(n) ProcedureF (n)
begin ifn = 0then return0
S = 0 else returnn + 2F (n − 1)
fori = 0, 1, 2, . . . , ndo
S = S + F (n − i)
returnS
end
a) Determinare l’espressione asintotica della sequenza {G(n)}nper n −→ +∞.
b) Assumendo il criterio di costo uniforme, determinare l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dall’esecuzione della procedura G su input n.
Algoritmi di ordinamento
L’efficienza dei sistemi che manipolano insiemi di dati mantenuti in memoria dipende in larga misura dal criterio utilizzato per conservare le chiavi delle informazioni. Uno dei metodi pi`u semplici e pi`u usati `e quello di mantenere le chiavi ordinate rispetto a una relazione d’ordine fissata. Ordinare una sequenza di valori `e quindi una operazione che ricorre frequentemente nella gestione di sistemi e in applicazioni di varia natura; pertanto le procedure di ordinamento sono spesso usate per la soluzione di problemi pi`u generali e quindi la loro efficienza pu`o di fatto condizionare l’efficacia dei metodi adottati.
8.1 Caratteristiche generali
Per definire formalmente il problema ricordiamo innanzitutto che una relazione d’ordine (parziale) R su un insieme U `e una relazione binaria che gode delle propriet`a riflessiva, transitiva e antisimmetrica, ovvero:
- per ogni a ∈ U , aRa;
- per ogni a, b, c ∈ U se aRb e bRc allora aRc; - per ogni a, b ∈ U se aRb e bRa allora a = b.
Classici esempi sono la relazione di minore o uguale sui numeri reali e l’inclusione tra i sottoinsiemi di un insieme dato. Diciamo che una relazione d’ordine R su U `e totale se per ogni a, b ∈ U vale aRb oppure bRa. In questo caso si dice anche che R definisce un ordine lineare su U .
Il problema di ordinamento per un insieme U , dotato di una relazione d’ordine totale ≤, `e definito nel modo seguente:
Istanza: un vettore A = (A[1], A[2], . . . , A[n]) tale che n > 1 e A[i] ∈ U per ogni i ∈ {1, 2, . . . , n}.
Soluzione: un vettore B = (B[1], B[2], . . . , B[n]), ottenuto mediante una permutazione degli elementi di A, tale che B[i] ≤ B[i + 1] per ogni i = 1, 2, . . . , n − 1.
I metodi adottati per risolvere il problema si diversificano in due gruppi principali chiamati rispetti-vamente di ordinamento interno ed esterno. Gli algoritmi di ordinamento interno presuppongono che il vettore di ingresso sia interamente contenuto nella memoria RAM della macchina. In questo caso l’ac-cesso al valore di una qualunque delle sue componenti avviene in tempi uguali per tutte. In questa sede ci occuperemo principalmente di algoritmi di questo tipo.
Al contrario gli algoritmi che operano su dati distribuiti principalmente su memorie di massa (dischi o nastri) vengono chiamati algoritmi di ordinamento esterno. In questo caso i tempi di accesso ai dati
non sono pi`u uniformi ma dipendono dal tipo di memoria nella quale sono collocati e uno degli obiettivi delle procedure usate `e proprio quello di ridurre il numero di accessi alle memorie di massa.
Gli algoritmi di ordinamento sono suddivisi anche in base alla generalit`a dell’insieme U sul quale viene definito l’input. Un primo gruppo `e costituito dalle procedure basate sul confronto tra gli elementi del vettore di ingresso. In questo caso si suppone di poter sempre eseguire in un numero costante di passi il confronto tra due elementi dell’insieme U rispetto alla relazione d’ordine fissata. Cos`ı l’algoritmo pu`o essere applicato a qualunque insieme totalmente ordinato perch´e non sfrutta alcuna caratteristica specifica dei suoi elementi. Come vedremo, in queste ipotesi, sono necessari Ω(n log n) confronti per ordinare un vettore di n elementi ed `e possibile descrivere diverse procedure ottimali, cio`e in grado di eseguire il calcolo proprio in tempo O(n log n).
Una seconda classe di algoritmi `e invece costituita da quelle procedure specificamente progettate per ordinare una sequenza di stringhe definite su un alfabeto finito, ad esempio binario. In questo caso si possono progettare algoritmi che ispezionano i singoli bits delle varie stringhe, sfruttando direttamente la rappresentazione binaria degli interi. Classici esempi di algoritmi di questo tipo sono quelli che ordinano una sequenza di parole su un dato alfabeto secondo l’ordinamento lessicografico. Come vedremo, sotto opportune ipotesi, si possono definire algoritmi di questo tipo che hanno complessit`a in tempo lineare.
Nell’analisi degli algoritmi di ordinamento che presentiamo nel seguito assumiamo come modello di calcolo una Random Access Machine (RAM) con criterio di costo uniforme. Il costo di ogni operazione aritmetica in termini di tempo di calcolo e di spazio di memoria `e quindi costante e non dipende dalle dimensioni degli operandi. Supponiamo inoltre che la nostra RAM sia in grado di mantenere in ogni cella di memoria un elemento del vettore di input e di eseguire il confronto fra due qualsiasi di questi in tempo costante.