Teorema Master

di
Beatlesmania
il
8 risposte
B
Beatlesmania
Pochi posts
Iscritto da
gen, 2014
Messaggi:
7

Teorema Master

Salve a tutti,mi servirebbe sapere l'uso del teorema Master,come faccio in un algoritmo ricorsivo a decretare i valori a,b,O()?

8 Risposte

  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: Teorema Master

    Beatlesmania ha scritto:

    Salve a tutti,mi servirebbe sapere l'uso del teorema Master,come faccio in un algoritmo ricorsivo a decretare i valori a,b,O()?
    Stai parlando di questo?



    Non partire dal presuposto che tutti sappiano di cosa tu stia parlando!

    Non leggiamo nella mente, ... ancora ...

    Se e' questo, allora prova a descrivere un caso effettivo tra quelli che conosci (anche se non perfettamente).

    Puoi ben immaginare che non esiste una formula magica: va analizzato ogni algoritmo ...


    E poi scrivi come parli, accipicchia: che aciderbolina vuol dire decretare?
    Da quando in qua si utilizza questo termine?
  • B
    Beatlesmania
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    7

    Re: Teorema Master

    Un esempio può essere la ricerca binaria,in cui suddivido il problema in sottoproblemi a=2, che hanno dimensione n\2 e scombino e ricombino l'array in tempo costante O(1), e fino a qui tutto chiaro xD quando ho davanti algoritmi come l'implementazione ricorsiva Fibonacci invece mi perdo. Va bene così o anche troppo aulico?
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: Teorema Master

    Beatlesmania ha scritto:

    un esempio può essere la ricerca binaria,in cui suddivido il problema in sottoproblemi a=2, che hanno dimensione n\2 e scombino e ricombino l'array in tempo costante O(1), e fino a qui tutto chiaro xD quando ho davanti algoritmi come l'implementazione ricorsiva Fibonacci invece mi perdo. Va bene così o anche troppo aulico?
    Sei tu che ti perdi n queste auliche elucubrazioni ...

    FIbonacci e' semplice come la ricerca binaria.

    Ha un solo difetto: non spiezzi il problema di dimensione N in due problemi di dimensione N/2, ma in uno di dimensione N-1 e l'altro di dimensione N-2.

    Non ho mica capito che cosa vuoi intendere con scombino e ricombino l'array ...
  • B
    Beatlesmania
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    7

    Re: Teorema Master

    Ad esempio nella ricerca binaria suddivido l'array in due parti una maggiore dell'elemento occupante la pos centrale e una minore,e poi nella soluzione finale lo ricombino,in tempo costante O(1); quindi posso applicare il teorema ai dati T(n-1)e T(n-2)?
  • Gincum
    Gincum
    Utente Attivo
    Iscritto da
    set, 2012
    Messaggi:
    230

    Re: Teorema Master

    Attenzione la ricerca binaria è un conto, fibonacci è un altra cosa al limite può essere un esempio. Nella ricerca binaria, spezzi in 2 l'algoritmo in maniera ricorsiva e poi riconbini, ma la ricombinazione nn è il problema principale; quello che bisogna misurare é quanto ci metti con la ricorsione a spezzare l'array in base a quanto é grosso l'input che viene dato in ingresso. Cioé spezzare un array di 8 elemnti nn é come farlo per uno di 1000 elementi . Il discorso é lungo sono un paio di capitoli di libro di algoritmi! Probabilmente dal tuo esempio (ricerca binaria) avrai fi(n)= 2T[n/2]+O(1). Poi dovresti verificare quale dei 3 casi della master devi valutare x far si ch f(n ) sia uguale a 1 se è come dici tu o n se come ricordo io, male sicuramente. Questo però mi dice che una letta l' hai data ma qualcosa la confondi! A parte tutta sta elucubrazione, fibonacci E lo si vede da quanto ti riporta Migliorabile, é un O(n ).cioè eliminando costanti e quant'altro di poco conto, puoi approssimare ad una fuzione lineare. Ma lo capisci dalla regola stessa che definisce fib. senza l'uso del teorema master.

    Inviato dal mio LG-E440 utilizzando Tapatalk
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6073

    Re: Teorema Master

    Buoni ...
    Non ho risposto subito perche' ho dovuto rispulciare i libri di testo, e non ho ancora trovato tutte le risposte, ma ....

    1) la ricerca binaria ha complessita' O(log2(N)): su un vettore di 1024 elementi, servono circa 10 test
    2) fibonacci, nella definizione ricorsiva, ha complessita O(2^N)

    Ora, come si dimostra? Si usa il teorema Master e le funzioni generatrici ...

    E fin qui' me lo ricordavo ...

    Come funzionano le funzioni generatrici? E chi se lo ricorda piu' ... !
  • Gincum
    Gincum
    Utente Attivo
    Iscritto da
    set, 2012
    Messaggi:
    230

    Re: Teorema Master

    Azz, per Fibonacci ricorsivo hai ragione è 2^n.

    Per gli alberi di ricerca binari è vero quello che dici, ma beatlesmania ha dato , come dato a=2. sono andato un pò a mente e mi sembrava plausibile il risultato dato. se invece a!=2 allora è vero, parliamo di T(n)= O(log2(N).

    Il problema è che bisognerebbe che ci dessi (parlo con beatlesmania) un esercizio vero e proprio altrimenti si rischia di darti suggerimenti sbagliati, per un discorso così vasto (come dicevo sono diversi capitoli di libro da studiare)!

    Comunque ho imparato una cosa: darli (i suggerimenti) la sera mentre passeggio col cane tramite cell è sbagliato!! ahahah

    bye
    G
  • B
    Beatlesmania
    Pochi posts
    Iscritto da
    gen, 2014
    Messaggi:
    7

    Re: Teorema Master

    Vi riporto direttamente lo psuedocodice Fibonacci dunque:
    algoritmo Fibonacci2(int n) ? int
    if ( n==1 || n==2 ) then
    return 1;
    else
    return Fibonacci2(n-1)+Fibonacci2(n-2);
    endif:
    Se volessi applicare il teorema Master a prescindere da come sia evidente già la complessità,come fare a definire a,b e O()?
    E poi mi sorge un dubbio,nella ricerca binaria non suddivido il problema in due sottoproblemi?Perchè a rimane 1? non è 2? Anche se applicando il teorema Master conoscendo già la complessità so che si riconduce al secondo caso,quindi è 1 il valore esatto,ma come mai?:/
Devi accedere o registrarti per scrivere nel forum
8 risposte