Fac Simile A

Prima Provetta

ASD1 2002-2003

Esercizio 1   Dimostrare che $f(n) = o(g(n))$ se e solo $g(n) = \omega(f(n))$.

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

Esercizio 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^{\log_2 n}$, $f(n)=n!$, $f(n)=n^{\log n}$, $f(n)=({\log n})!$, $f(n)=2^n$, $f(n)=4^n$, $f(n)=2^{n+1}$, $f(n)=4^{\log_2 n}$, $f(n)=(n+1)! -n!$, $f(n)=n^{\frac{n}{100}}$.

Esercizio 4   Siano $f(n)$ e $g(n)$ due funzioni asintoticamente non negative. Si assuma che $\lim_{n\mapsto \infty} \frac{f(n)}{g(n)}=5$. Dimostrare che $f(n) = O(g(n))$. Possiamo concludere che $f(n)=\Theta(g(n))$?

Esercizio 5   Si dimostri che ${n \choose \frac{n}{2}} = O(2^n)$.

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

$$T_n = T_k + T_{n-k} + \Theta(\min\{k,n-k\}) \mbox{\hspace{1cm} per $k\geq 1$, $k< n$}$$

E nel caso migliore?

Esercizio 7   Si consideri il seguente algoritmo Goloson.

Input: un sacchetto di cioccolatini.

1. se il sacchetto contiene al più un cioccolatino, allora mangiatelo e termina.
2. prendi un cioccolatino dal sacchetto ricevuto in input, leccalo, e mettilo in un sacchetto di cioccolatini leccati.
3. se il sacchetto ricevuto in input non è ancora vuoto, e finchè non ti assale lo scrupolo per il fatto di essere in dieta, puoi ripetere il passo 2.
4. preso dallo scrupolo (o dai rimpianti), conta i cioccolatini leccati, siano essi $x$.
5. nel tentativo di nascondere la tua debolezza, sposta $\lfloor \frac{x}{2} \rfloor$ cioccolatini dal sacchetto dei leccati al sacchetto ricevuto in input.
6. agisci da Goloson sul sacchetto dei cioccolatini leccati.
7. agisci da Goloson sul sacchetto dei cioccolatini ricevuto in input.

Sia $G(n)$ il numero massimo di degustazioni di cioccolatino (leccatine + magnate) in cui si può incorrere partendo da un sacchetto di $n$ cioccolatini. Descrivere $G(n)$ tramite una ricorrenza. Condurre analisi asintotica per $G(n)$. Riesci ad estrapolare od intuire la politica da tenere (quando conviene farsi prendere da scrupolo) qualora si voglia massimizzare il numero di degustazioni? Quale potrà essere invece il minor numero di degustazioni possibili partendo da un sacchetto di $n$ cioccolatini? Riesci ad estrapolare anche formalmente quale politica porti a questo minimo.