Fac Simile B

Prima Provetta

ASD1 2002-2003

Exercise 1   È vero o falso che $f(n)=\omega(g(n))$ implica $f(n) = \Omega(g(n))$? È vera anche l'implicazione inversa? Fornire un controesempio.

Exercise 2   Si assuma $f(n) = O(g(n))$. Dimostrare che $f(n)+ ng(n) = \Theta(ng(n))$.

Exercise 3   Ordinare le seguenti funzioni per ordine di crescita asintotico non decrescente. Ve ne sono alcune che presentano lo stesso ordine di crescita? $f(n)= 2^{n+1} - 2^n$, $f(n)= 2^{n+100}$, $f(n)=2^{2n}$, $f(n)=2^{n+\log_2 n}$, $f(n)=3^{n}$, $f(n)=\sum_{k=0}^n 2^k$, $f(n)=\left(2^{\sqrt{n}}\right)^2$, $f(n)=\sqrt{4^n}$.

Exercise 4   Si dimostri che $\sum_{k=1}^n \frac{1}{k} = \Theta(\log n)$.

Exercise 5   Si determini l'andamento asintotico nel caso peggiore di un tempo di calcolo $T_n$ soggetto alla seguente ricorrenza

$$T_n = T_{n_1} + T_{n_2} + \Theta(n) \mbox{\hspace{1cm} dove $n_1, n_2 > 0$, con $n_1 + n_2 = n$}$$

E nel caso migliore? E se potessimo assumere $n_1, n_2 \geq \frac{n}{33}$ cambierebbe qualcosa riguardo l'andamento asintotico per il caso peggiore?

Exercise 6   Si consideri il seguente algoritmo MoviePlayer.

Input: una collezione di $n$ films.

1. se $n\leq 1$, allora visiona l'eventuale film e termina.
2. si guardino, marcandoli, al più $k\leq \frac{n}{2}$ dei films della collezzione.
3. si agisca da MoviePlayer sull'insieme dei films ora marcati.
4. si agisca da MoviePlayer sull'insieme dei films restanti.

Sia $V(n)$ il numero massimo di visioni di films in cui si può incorrere partendo da una collezzione di $n$ films. Descrivere $V(n)$ tramite una ricorrenza. Condurre analisi asintotica per $V(n)$. Riesci ad estrapolare od intuire quale politica (scelta di $k$) porterà a massimizzare il numero di visioni? Quale potrà essere invece il minor numero di visioni possibili partendo da una collezzione di $n$ films? Riesci ad estrapolare anche formalmente quale politica porti a questo minimo.