[Algoritmi] Algoritimi e strutture dati esercizi

Messaggioda giulio0 » 24/10/2018, 13:16

Salve ho da fare due esercizi di Algoritmi e strutture dati. Per il primo esercizio credo si faccia col metodo iterativo o di sostituzione mentre per il secondo non ho idea di che voglia:

1) Si individuano, se esistono, le costanti necessarie a dimostrare le seguenti relazioni:
$ 5n^(2) - n + log(n) = theta(n^(2)) $

2) Si dimostri la verità o falsità (tramite controesempio) della seguente affermazione:
se $ h(n) = theta(2^(n)) $ e $ log_2h(f(n)) = theta(log_2g(n)) $ allora $ f(n) = theta(log_2g(n)) $

Si assuma che le funzioni g ed f sia asintoticamente crescenti e positive.

Una mano?
giulio0
Junior Member
Junior Member
 
Messaggio: 66 di 312
Iscritto il: 29/01/2018, 21:54

Re: [Algoritmi] Algoritimi e strutture dati esercizi

Messaggioda vict85 » 24/10/2018, 19:51

Con "credo si faccia col metodo iterativo o di sostituzione" intendi dire che hai effettivamente provato a risolverlo? Se si dove ti sei fermato? Ti ricordo il Regolamento.

Se hai capito la teoria, dovrebbe esserti evidente anche senza calcoli che la prima funzione si comporta asintoticamente come \(5n^2\). In particolare, è facile dimostrare (e ti invito a farlo), che si ha \(4n^2 < f(n) < 5n^2\) già da \(n\) molto piccoli.

L'altro è ovviamente meno banale e le condizioni finali sono necessarie. Per prima cosa proviamo a vedere se la relazione funziona nel caso banale. Poniamo \(h(n) = 2^n\) e osserviamo che \(\log_2 (h\circ f)(x) = \log_2 2^{f(n)} = f(n) \log_2 2 = f(n) \). Questo ci fa pensare che la proposizione possa essere vera. Prova a ragionare su cosa cambia nel caso in cui la funzione \(h(n)\) non sia più fissata.
vict85
Moderatore
Moderatore
 
Messaggio: 9432 di 19253
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: [Algoritmi] Algoritimi e strutture dati esercizi

Messaggioda giulio0 » 06/11/2018, 16:12

Dopo esercizi su esercizi credo di aver intuito qualcosa. Il secondo esercizio l'ho risolto, mentre il primo ho il dubbio su come si faccia perciò posto qua i passi:

$ 5n^(2) - n + log(n) = theta(n^2) $
$ EEc_1, c_2 >0, EEn_0 > 0 : AAn>n_0 => c_1 n^2 <= 5n^2 - n + log(n)<= c_2n^2 $

Con dei semplici calcoli algebrici arrivo a:

$ c_1 <= 5 - 1/n + log(n)/n^2<= c_2 $

Da qui ho calcolo il limite per n tendente ad infinito per ottenere c2 e la sua derivata, corretto? Infine pongo la derivata maggiore di zero per scoprire la positività della funzione?
giulio0
Junior Member
Junior Member
 
Messaggio: 67 di 312
Iscritto il: 29/01/2018, 21:54


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite