Apri il menu principale

Teorema principale

(Reindirizzamento da Metodo dell'esperto)

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]

EnunciatoModifica

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]

DimostrazioneModifica

LemmaModifica

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  ,  .

DimostrazioneModifica

Caso 1Modifica

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 2Modifica

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 3Modifica

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 principaleModifica

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]

GeneralizzazioniModifica

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  .

EsempiModifica

Caso 1Modifica

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 2Modifica

Sia data ora la relazione di ricorrenza:

 

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

Caso 3Modifica

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 è  

NoteModifica

  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.

BibliografiaModifica

Voci correlateModifica