[Algoritmi] Algoritimi e strutture dati esercizi
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?
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?
Risposte
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]1_2[/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.
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.
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?
$ 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?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo