next up previous
Next: About this document ...


Quarto Scritto

ASD1 2002-2003

Exercise 1   Siano $f(n)$ e $g(n)$ due funzioni definitivamente non negative. Dire quali delle seguenti affermazioni sono vere. Ove false, fornire un controesempio.
1.
se $f(n)=O(g(n))$, allora esiste un $n_o$ tale che $f(n) \leq g(n)$ per ogni $n\geq n_o$.
2.
se $f(n)=o(g(n))$, allora esiste un $n_o$ tale che $f(n) < g(n)$ per ogni $n\geq n_o$.
3.
$f(n+1)= O(f(n))$ se $f(n)$.
4.
$2^{\alpha n}= O(3^n)$ per ogni $\alpha > 0$.

Exercise 2   Si determini l'andamento asintotico nel caso peggiore di un tempo di calcolo $T(n)$ soggetto alla seguente ricorrenza

\begin{displaymath}
T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{3}\right) + \Theta(n)
\end{displaymath}

E nel caso migliore?

Exercise 3   Ordinare le seguenti funzioni per ordine di crescita asintotico non decrescente, ove $k>1$ sia una costante positiva comune. Ve ne sono alcune che presentano lo stesso ordine di crescita? Come cambia la situazione per $k=1$? $f(n)=n^k$, $f(n)=(100n+10)^k$, $f(n)={n \choose k}$, $f(n)=k^n$, $f(n)= \log k^n$.

Exercise 4   Un grafo $G=(V,E)$ di dice bipartito se posso bipartizionare $V$ in due sottoinsiemi disgiunti $V_1$ e $V_2$ tali che ogni arco in $E$ abbia un estremo in $V_1$ e l'altro in $V_2$.

Exercise 5   Si descrivano in maniera efficace gli Heaps binomiali e le relative operazioni. (L'obiettivo è dimostrarmi che avete colto il principio di funzionamento di questa struttura dati. Cercate quindi di puntare al nocciolo. Nel dubbio, confrontatevi con me. Non perdete tempo).




next up previous
Next: About this document ...
Romeo Rizzi 2003-06-23