next up previous
Next: Esercizio 2 Up: doneScrittoII Previous: doneScrittoII

Esercizio 1

Siano $ f(n)$ e $ g(n)$ due funzioni non negative e monotone non decrescenti. Dire quali delle seguenti affermazioni sono vere, fornendo un controesempio qualora non lo fossero:

1.
$ (\min(f(n), g(n)) + \max(f(n), g(n))) \in \Theta (2 f(n) + 3 g(n));$
2.
$ \Omega(\mid \! f(n)- g(n) \! \mid ) \cap O(f(n)+g(n)) =
\Theta(f(n)+ g(n));$
3.
$ f(n) \cdot f(n+2) \in O(f(n+1) \cdot f(n+1)); $
4.
$ 4^{f(n)} + 4^{g(n)} \in O(2^{f(n)+ g(n)})$
Le risposte, punto per punto, sono le seguenti:
1.
Notare che $ (\min(f(n), g(n)) + \max(f(n), g(n))) = f(n) + g(n).$ Abbiamo poi

$\displaystyle \frac{1}{3} (2 f(n) + 3 g(n)) \leq f(n) + g(n) \leq
\frac{1}{2} (2 f(n) + 3 g(n)), $

quindi l'affermazione è vera e le costanti nascoste dalla notazione theta sono $ \frac{1}{3}$ e $ \frac{1}{2}.$

2.
Falso, come si vede prendendo $ g(n)= f(n),$ dove $ f(n)$ è una qualsiasi funzione non costante. Siccome allora $ \Omega(\mid \! f(n)- g(n) \! \mid )$ è l'insieme di tutte le funzioni definitivamente non negative (cioè, di tutte le funzioni alle quali le nostre notazioni si applicano), il membro sinistro è semplicemente $ O(f(n)+g(n))$, che sappiamo essere diverso da $ \Theta(f(n)+ g(n)).$ Concretamente, prendendo $ f(n)= g(n)= n^2, $ allora $ h(n)= n$ appartiene al membro sinistro ma non a quello destro.

L'uguaglianza sussiste invece con l'ipotesi aggiuntiva $ g(n)= o(f(n)).$

3.
Con una traslazione di indice, possiamo mettere il quesito nella forma $ f(n-1) \cdot f(n+1) \in O(f(n) \cdot f(n)); $

Qualche tentativo: prima con una funzione polinomiale, e.g. $ f(n)= n^k.$ Abbiamo

$\displaystyle \frac{(n-1)^k (n+1)^k}{n^k n^k} = \left(\frac{n^2 - 1}{n^2}^k \right) < 1 $

per cui la proposizione è in questo caso vera.

Indi con una funzione esponenziale: $ f(n)= k^n$

$\displaystyle \frac{k^{n-1} k^{n+1}}{k^n k^n} = 1.$

per cui la proposizione è ancora vera.

Anche con $ f(n)= k^{n^2}$

$\displaystyle \frac{k^{{(n-1)}^2} k^{{(n+1)}^2}}{k^{n^2} k^{n^2}} =
k^{{(n-1)}^2 + {(n+1)}^2 - 2 n^2}= k^2 $

per cui la proposizione è ancora vera.

Con $ f(n)= k^{n^3},$ tuttavia, le cose cambiano: ad es. con $ f(n)= k^{n^3}$ si ha

$\displaystyle \frac{k^{(n-1)^3} k^{(n+1)^3}}{k^{n^3} k^{n^3}} =
k^{(n-1)^3 + (n+1)^3 - 2 n^3} = k^{6n}, $

rapporto che tende a infinito, per cui la proposizione è falsa.

4.
Falso, come si vede prendendo ad esempio $ f(n)= 1$ (ricordando che deve essere positiva) e $ g(n)=n$. Notare che basterebbe anche prendere una $ g(n)$ crescente in modo molto piú debole, come $ g(n)= \log n$.


next up previous
Next: Esercizio 2 Up: doneScrittoII Previous: doneScrittoII
Romeo Rizzi 2003-03-07