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 introdotto e dimostrato nel libro 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 è asintoticamente polinomialmente più grande e sufficientemente regolare allora . Non sono coperti dal teorema i casi in cui sia asintoticamente più grande o più piccola di , ma non lo sia polinomialmente.[1]

Enunciato[modifica | modifica wikitesto]

Sia data una relazione di ricorrenza nella forma[2]

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 esiste una costante tale che e se esistono una costante e un intero tali che , allora .[3]

Lemma[modifica | modifica wikitesto]

La somma definita su potenze di , dove e sono costanti e è non negativa, ha rispettivamente i limiti asintotici:

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

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

,

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

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[5]

.

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

Generalizzazioni[modifica | modifica wikitesto]

Il secondo caso del teorema principale può essere generalizzato come, ferme le restanti ipotesi, se esiste una costante tale che , allora .[7]

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. ^ Cormen et al., pp. 94–95.
  2. ^ 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.
  3. ^ Cormen et al., p. 94.
  4. ^ Cormen et al., pp. 100–102.
  5. ^ Cormen et al., pp. 98–100.
  6. ^ Cormen et al., pp. 103–106.
  7. ^ 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