Teorema dell'esperto

Il teorema dell'esperto, noto anche come teorema principale (in inglese master theorem) o teorema del maestro, è un teorema inerente all'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza. È stato inizialmente esposto da Jon Bentley, Dorothea Haken, e James B. Saxe nel 1980, dove fu descritto come un metodo unificato per una famiglia di ricorrenze. Il nome di questo teorema è stato popolarizzato dal famoso manuale Introduzione agli algoritmi di Cormen, Leiserson, Rivest e Stein. Non fornisce una soluzione a tutte le possibili relazioni di ricorrenza, ed una sua generalizzazione è il teorema di Akra-Bazzi.

Informalmente, il teorema afferma che, data una relazione di ricorrenza nella forma $T (n) = a T (\frac{n}{b}) + f (n)$ con $a \geq 1$ e $b > 1$ , in alcuni casi si può ottenere una soluzione confrontando $f$ con la funzione $n^{\log_{b} a}$ . Se $f$ è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale $n^{ε}$ ) allora $T (n) = Θ (n^{\log_{b} a})$ ; se le due funzioni hanno asintoticamente la stessa grandezza allora $T (n) = Θ (n^{\log_{b} a} \log (n)) = Θ (f (n) \log (n))$ ; infine, se $f$ è sufficientemente regolare e polinomialmente più grande allora $T (n) = Θ (f (n))$ . Non sono coperti dal teorema i casi in cui $f$ sia asintoticamente più grande o più piccola di $n^{\log_{b} a}$ in modo non polinomiale.

Enunciato

Sia data una relazione di ricorrenza $T (n)$ nella forma

T (n) = a T (\frac{n}{b}) + f (n),

dove $a \geq 1$ e $b > 1$ sono costanti e $\frac{n}{b}$ si può interpretare sia come $⌊ \frac{n}{b} ⌋$ (parte intera) sia come $⌈ \frac{n}{b} ⌉$ (parte intera superiore).

Allora la funzione $T (n)$ è limitata asintoticamente secondo uno dei tre seguenti casi:

se esiste una costante $ε > 0$ tale che $f (n) = O (n^{\log_{b} a - ε})$ , allora $T (n) = Θ (n^{\log_{b} a})$ ;
se $f (n) = Θ (n^{\log_{b} a})$ , allora $T (n) = Θ (n^{\log_{b} a} \log_{b} n)$ ;
se esiste una costante $ε > 0$ tale che $f (n) = Ω (n^{\log_{b} a + ε})$ ed esistono una costante $0 < c < 1$ e un intero $n_{0}$ tali che $\forall n \geq n_{0} : a f (\frac{n}{b}) \leq c f (n)$ , allora $T (n) = Θ (f (n))$ .

Dimostrazione

Lemma

La somma $s (n) = \sum_{i = 0}^{\log_{b} n} a^{i} f (\frac{n}{b^{i}})$ definita su potenze di $b$ , dove $a \geq 1$ e $b > 1$ sono costanti e $f$ è non negativa, ha rispettivamente comportamento asintotico:

sotto l'ipotesi del caso 1 del teorema principale, $s (n) = Θ (n^{\log_{b} a})$ ;
sotto l'ipotesi del caso 2 del teorema principale, $s (n) = Θ (n^{\log_{b} a} \log b n)$ ;
sotto l'ipotesi del caso 3 del teorema principale, se esistono una costante $0 < c < 1$ e un intero $n_{0}$ tali che $\forall n \geq n_{0} : a f (\frac{n}{b}) \leq c f (n)$ , allora $s (n) = Θ (f (n))$ .

Dimostrazione

Caso 1

Per il caso 1, l'ipotesi implica

f (\frac{n}{b^{j}}) = O ({(\frac{n}{b^{j}})}^{\log_{b} a - ε})

che sostituita in $s$ porta a

s (n) = O (\sum_{i = 0}^{\log_{b} n - 1} a^{i} {(\frac{n}{b^{i}})}^{\log_{b} a - ε}) .

Raccogliendo i fattori comuni, semplificando e sommando la serie geometrica troncata risultante, si ha

s (n) = O (n^{\log_{b} a - ε} (\frac{n^{ε} - 1}{b^{ε} - 1})) .

Poiché $ε$ e $b$ sono costanti, si ha

n^{\log_{b} a - ε} (\frac{n^{ε} - 1}{b^{ε} - 1}) = n^{\log_{b} a - ε} O (n^{ε}) = O (n^{\log_{b} a}),

e dal fatto che, poiché $f (1)$ è una costante,

s (n) \geq a^{\log_{b} n} f (1) = f (1) n^{\log_{b} a} \to s (n) \in Ω (n^{\log_{b} a})

che insieme danno

s (n) \in Θ (n^{\log_{b} a})

da cui la tesi.

Caso 2

Analogamente al caso 1, per il caso 2 l'ipotesi implica

f (\frac{n}{b^{j}}) = Θ ({(\frac{n}{b^{j}})}^{\log_{b} a})

che sostituita in $s$ porta a

s (n) = Θ (\sum_{i = 0}^{\log_{b} n - 1} a^{i} {(\frac{n}{b^{i}})}^{\log_{b} a}) .

Si procede analogamente al caso precedente, tuttavia la serie troncata ottenuta non è una serie geometrica, ma una serie a termini costanti

n^{l o g_{b} a} \sum_{i = 0}^{\log_{b} n - 1} 1 = n^{\log_{b} a} \log_{b} n

da cui la tesi.

Caso 3

Applicando iterativamente $i$ volte l'ipotesi di regolarità del caso 3, si ha

a^{i} f (\frac{n}{b^{i}}) \leq c^{i} f (n)

per valori sufficientemente grandi di $n$ . Tale condizione vale dunque per tutti tranne al più un numero costante di termini, per i quali $n$ non è sufficientemente grande. Analogamente ai casi precedenti, si sostituisce nella definizione di $s$ , ottenendo

s (n) \leq \sum_{i = 0}^{\log_{b} n} c^{i} f (n) + O (1) \leq f (n) \sum_{i = 0}^{\infty} c^{i} + O (1),

dove $O (1)$ rappresenta i termini precedentemente citati per i quali non vale la disuguaglianza. Sommando la serie geometrica si ha

s (n) = f (n) (\frac{1}{1 - c}) + O (1) = O (f (n))

e poiché la definizione di $s$ contiene $f$ in una somma a termini non negativi, si ha anche $s (n) = Ω (f (n))$ . Combinando le due limitazioni asintotiche, si ha $s (n) = Θ (f (n))$ .

Dimostrazione del teorema principale

Nel caso particolare in cui $T$ sia definita solo su potenze esatte di $b$ , analizzando l'albero della ricorsione relativo alla relazione di ricorrenza si osserva che

T (n) = \sum_{i = 0}^{\log_{b} n} a^{i} f (\frac{n}{b^{i}}) + Θ (n^{\log_{b} a}) .

Applicando quindi il lemma dimostrato precedentemente, si ottiene immediatamente la validità del teorema principale nel caso particolare in cui $n$ sia definita su potenze di $b$ . Questo ovviamente non è sufficiente a dimostrare il teorema, ma può essere esteso al caso generale considerando il caso in cui compaiano parti intere superiori o inferiori.

Nel caso di una parte intera superiore, nel considerare l'albero di ricorsione alla chiamata $i$ -esima l'argomento assume la forma

n_{i} = {\begin{matrix} n, & i = 0, \\ ⌈ \frac{n_{i - 1}}{b} ⌉, & i > 0. \end{matrix}

Poiché dalla definizione di parte intera superiore si ha $⌈ x ⌉ \leq x + 1$ , si ottiene

n_{i} \leq \frac{n}{b^{i}} + \sum_{i = 0}^{i - 1} \frac{1}{b^{i}} < \frac{n}{b^{i}} + \frac{b}{b - 1} .

Da ciò si osserva che $n_{⌊ \log_{b} n ⌋} = O (1)$ , quindi alla profondità di ricorsione $⌊ \log_{b} n ⌋$ il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per $n$ arbitrario, non più ristretto alle potenze di $b$

T (n) = \sum_{i = 0}^{⌊ \log_{b} n ⌋} a^{i} f (n_{i}) + Θ (n^{\log_{b} a})

e si può procedere a studiare la somma. Il terzo caso procede in maniera esattamente analoga al terzo caso del lemma. Per il secondo caso, dalla definizione di O-grande e ricordando l'espressione di $n_{i}$ si ha che esiste una costante $c > 0$ e un intero $n_{0}$ tali che, per $n \geq n_{0}$

f (n_{i}) \leq c {(\frac{n}{b^{i}} + \frac{b}{b - 1})}^{\log_{b} a} \leq c (\frac{n^{\log_{b} a}}{a^{i}}) {(1 + \frac{b}{b - 1})}^{\log_{b} a} = O (\frac{n^{\log_{b} a}}{a^{i}}) .

Il limite asintotico ottenuto permette di procedere poi in maniera analoga al caso 2 del lemma. Per il primo caso, in maniera analoga a quanto appena fatto si mostra che

f (n_{i}) = O ({(\frac{n}{b^{i}})}^{\log_{b} a - ε})

che permette di procedere poi in maniera analoga al caso 1 del lemma. Questo completa la dimostrazione del teorema principale in caso di parte intera superiore, nel caso della parte intera inferiore la dimostrazione è analoga.

Generalizzazioni

Il secondo caso del teorema principale può essere generalizzato sostituendo solo alla sua ipotesi particolare, $f (n) = Θ (n^{\log_{b} a} \log^{k} n)$ per qualche $k \geq 0$ e alla tesi $T (n) = Θ (n^{\log_{b} a} \log^{k + 1} n)$ . Come si vede il caso non generale è per $k = 0$ .

Il teorema di Akra-Bazzi generalizza il teorema principale, sotto opportune ipotesi, per relazioni di ricorrenza nella forma $T (x) = g (x) + \sum_{i = 1}^{k} a_{i} T (b_{i} x + h_{i} (x))$ .

Esempi

Caso 1

Sia data la seguente relazione di ricorrenza:

T_{A} (n) = 9 T_{A} (\frac{n}{3}) + n .

Si ha $a = 9$ , $b = 3$ e $f (n) = n$ . Allora $n^{\log_{b} a} = n^{\log_{3} 9} = Θ (n^{2}) .$ Dato che $f (n) = O (n^{\log_{3} 9 - ε})$ quando $ε = 1$ , è possibile applicare il caso 1 del teorema dell'esperto ottenendo la soluzione

T_{A} (n) = Θ (n^{2}) .

Caso 2

Sia data ora la relazione di ricorrenza:

T_{A} (n) = T_{A} (\frac{2 n}{3}) + 1,

in cui $a = 1$ , $b = 3 / 2$ e $f (n) = 1$ . Essendo $n^{\log_{b} a} = n^{\log_{3 / 2} 1} = Θ (n^{0}) = Θ (1)$ ed $f (n) = 1$ , vale il caso 2 del teorema dell'esperto, che porta alla soluzione $T_{A} (n) = Θ (\log n) .$

Caso 3

Infine sia data la relazione di ricorrenza:

T_{A} (n) = 3 T_{A} (\frac{n}{4}) + n \log n,

in cui $a = 3$ , $b = 4$ e $f (n) = n \log n$ . Essendo $n^{\log_{b} a} = n^{\log_{4} 3} = O (n^{0, 793})$ ed $f (n) = Ω (n^{\log_{4} 3 + ε})$ , in cui $ε \approx 0, 2$ , il caso 3 del teorema dell'esperto si può applicare solo se vale la condizione di regolarità per $f (n)$ . Per $n$ sufficientemente grande si ha $3 (\frac{n}{4}) \log (\frac{n}{4}) \leq (\frac{3}{4} n \log n) = c f (n)$ per $c = 3 / 4 \leq 1$ . Di conseguenza la soluzione della ricorrenza è $T_{A} (n) = Θ (n \log n) .$

Note

↑ Questo il significato originario del termine master nel nome.
↑ Jon Louis Bentley, Dorothea Haken e James B. Saxe, A general method for solving divide-and-conquer recurrences, in ACM SIGACT News, vol. 12, n. 3, September 1980, pp. 36-44, DOI:10.1145/1008861.1008865.
↑ Cormen et al., pp. 94-95.
↑
Considerando un algoritmo ricorsivo associato alla relazione di ricorrenza, le quantità coinvolte si possono interpretare come:
- $n$ è la dimensione dell'input;
- $a$ è il numero di chiamate ricorsive all'algoritmo;
- $\frac{n}{b}$ è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema);
- $f (n)$ è la funzione di costo della fase di suddivisione del problema e di ricostruzione della soluzione.
↑ Cormen et al., p. 94.
↑ Cormen et al., pp. 100-102.
↑ Cormen et al., pp. 98-100.
↑ Cormen et al., pp. 103-106.
↑ Goodrich & Tamassia, pp. 268-270.

Bibliografia

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 3ª ed., MIT Press, 2009, pp. 93–106, ISBN 978-0-262-53305-8.
Michael T. Goodrich e Roberto Tamassia, Algorithm Design: Foundation, Analysis, and Internet Examples, Wiley, 2002, ISBN 0-471-38365-1.

Voci correlate

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica

[1] Questo il significato originario del termine master nel nome.

[2] Jon Louis Bentley, Dorothea Haken e James B. Saxe, A general method for solving divide-and-conquer recurrences, in ACM SIGACT News, vol. 12, n. 3, September 1980, pp. 36-44, DOI:10.1145/1008861.1008865.

[3] Cormen et al., pp. 94-95.

[4] Considerando un algoritmo ricorsivo associato alla relazione di ricorrenza, le quantità coinvolte si possono interpretare come:
$n$ è la dimensione dell'input;

$a$ è il numero di chiamate ricorsive all'algoritmo;

$\frac{n}{b}$ è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema);

$f (n)$ è la funzione di costo della fase di suddivisione del problema e di ricostruzione della soluzione.

[mwAUY] $n$ è la dimensione dell'input;

[mwAUs] $a$ è il numero di chiamate ricorsive all'algoritmo;

[mwAVA] $\frac{n}{b}$ è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema);

[mwAVo] $f (n)$ è la funzione di costo della fase di suddivisione del problema e di ricostruzione della soluzione.

[5] Cormen et al., p. 94.

[6] Cormen et al., pp. 100-102.

[7] Cormen et al., pp. 98-100.

[8] Cormen et al., pp. 103-106.

[9] Goodrich & Tamassia, pp. 268-270.