Teorema principale

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Teorema principale (informatica))

Il teorema principale o master theorem (noto anche come teorema dell'esperto o teorema del maestro) è un teorema inerente l'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza. È stato inizialmente esposto da Jon Bentley, Dorothea Haken, and James B. Saxe nel 1980, dove fu descritto come un metodo unificato[1] per una famiglia di ricorrenze.[2] Il nome "master theorem" è 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 con e , in alcuni casi si può ottenere una soluzione confrontando con la funzione . Se è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale ) allora ; se le due funzioni hanno asintoticamente la stessa grandezza allora ; infine, se è sufficientemente regolare allora . Non sono coperti dal teorema i casi in cui sia asintoticamente più grande o più piccola di in modo non polinomiale.[3]

Enunciato[modifica | modifica wikitesto]

Sia data una relazione di ricorrenza nella forma[4]

dove e sono costanti e si può interpretare sia come (parte intera) sia come (parte intera superiore).

Allora la funzione è limitata asintoticamente secondo uno dei tre seguenti casi:

  1. se esiste una costante tale che , allora ;
  2. se allora ;
  3. se esistono una costante e un intero tali che , allora .[5]

Dimostrazione[modifica | modifica wikitesto]

Lemma[modifica | modifica wikitesto]

La somma definita su potenze di , dove e sono costanti e è non negativa, ha rispettivamente comportamento asintotico:

  1. sotto l'ipotesi del caso 1 del teorema principale, ;
  2. sotto l'ipotesi del caso 2 del teorema principale, ;
  3. se esistono una costante e un intero tali che , .

Dimostrazione[modifica | modifica wikitesto]

Caso 1[modifica | modifica wikitesto]

Per il caso 1, l'ipotesi implica

che sostituita in porta a

.

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

.

Poiché e sono costanti, si ha

,

e dal fatto che, poiché è una costante,

che insieme danno

da cui la tesi.

Caso 2[modifica | modifica wikitesto]

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

che sostituita in porta a

.

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

da cui la tesi.

Caso 3[modifica | modifica wikitesto]

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

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

dove rappresenta i termini precedentemente citati per i quali non vale la disuguaglianza. Sommando la serie geometrica si ha

e poiché la definizione di contiene in una somma a termini non negativi, si ha anche . Combinando le due limitazioni asintotiche, si ha .[6]

Dimostrazione del teorema principale[modifica | modifica wikitesto]

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

.

Applicando quindi il lemma dimostrato precedentemente, si ottiene immediatamente la validità del teorema principale nel caso particolare in cui sia definita su potenze di . 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

.

Poiché dalla definizione di parte intera superiore si ha , si ottiene

.

Da ciò si osserva che , quindi alla profondità di ricorsione il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per arbitrario, non più ristretto alle potenze di

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 si ha che esiste una costante e un intero tali che, per

.

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

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.[8]

Generalizzazioni[modifica | modifica wikitesto]

Il secondo caso del teorema principale può essere generalizzato sostituendo solo alla sua ipotesi particolare, per qualche e alla tesi .[9] Come si vede il caso non generale è per .

Il teorema di Akra-Bazzi generalizza il teorema principale, sotto opportune ipotesi, per relazioni di ricorrenza nella forma .

Esempi[modifica | modifica wikitesto]

Caso 1[modifica | modifica wikitesto]

Sia data la seguente relazione di ricorrenza:

Si ha , e . Allora Dato che quando ε = 1, è possibile applicare il caso 1 del Master Theorem ottenendo la soluzione

Caso 2[modifica | modifica wikitesto]

Sia data ora la relazione di ricorrenza:

in cui , e . Essendo ed , vale il caso 2 del Master Theorem, che porta alla soluzione

Caso 3[modifica | modifica wikitesto]

Infine sia data la relazione di ricorrenza:

in cui , e . Essendo ed , in cui ε ≈ 0.2, il caso 3 del Master Theorem si può applicare solo se vale la condizione di regolarità per . Per n sufficientemente grande si ha per . Di conseguenza la soluzione della ricorrenza è

Note[modifica | modifica wikitesto]

  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:
    • è la dimensione dell'input;
    • è il numero di chiamate ricorsive all'algoritmo;
    • è la dimensione della chiamata ricorsiva (ovvero la porzione del problema originale rappresentato in ogni sottoproblema);
    • è 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.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

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