Fac Simile C (più fedele, ancora più simile)

ASD1 2002-2003

Exercise 1   Dire quali delle seguenti affermazioni sono vere. Ove false, fornire un controesempio.

1.

$f(n)=O(g(n))$ implica $\log_2 (f(n) + 2) = O(\log_2 (g(n) + 2))$.

2.

$f(n)=O(g(n))$ implica $h(f(n)) = O(h(g(n))$ se $h(n)\geq 0$ per ogni $n$.

3.

$f(n)=O(g(n))$ implica $f(n) + g(n) = \Theta(g(n))$.

4.

$f(n)=O(f(n+1))$.

Exercise 2   Siano $f(n)$ e $g(n)$ due funzioni definitivamente non negative. Dimostrare che $f(n) + g(n) = \Theta(\max\{f(n),g(n)\})$.

Exercise 3   Ordinare le seguenti funzioni per ordine di crescita asintotico non decrescente, ove $k$ sia una costante positiva comune. Ve ne sono alcune che presentano lo stesso ordine di crescita? $f(n)=n^k$, $f(n)=(n+5)^k$, $f(n)={n \choose k}$, $f(n)=n^{\left(k-\frac{1}{k}\right)}\log^k n^k$, $f(n)= 2^{k\log_2 n}$.

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

Exercise 5   Dato un intero $a>0,$ allo scopo di calcolare la potenza $a^n,$ usiamo la seguente procedura iterativa:

#include<iostream.h>

int main() {
  int a; cout << "Dammi a: "; cin >> a; cout << endl;
  int n; cout << "Dammi n: "; cin >> n; cout << endl;
  long long int P[n +1];   
  P[0] = 1;
  for(int k=1; k<=n; k++)
    P[k] = a*P[k-1];
  cout << "P[" << n << "] = "  << P[n] << endl;
}

Si stabilisca l'ordine di crescita del tempo di calcolo della procedura proposta. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura proposta.

Exercise 6   Il professor Gonzalez, propone di utilizzare la seguente procedura ricorsiva allo scopo di calcolare la medesima funzione:

#include<iostream.h>

long long int P(int a, int n) {
  if (n==0) return 1;
  if (n==1) return a;
  return P(a, n/2)* P(a, n- (n/2));
}

int main() {
  int a; cout << "Dammi a: "; cin >> a; cout << endl;
  int n; cout << "Dammi n: "; cin >> n; cout << endl;
  cout << "P[" << n << "] = "  << P(a, n) << endl;
}

Si stabilisca l'ordine asintotico di crescita per il tempo di calcolo della procedura proposta dal professor Gonzalez. Si stabilisca l'ordine di crescita della memoria impiegata dalla procedura di Gonzalez.

Complemento 6+ Dire come il prof. Gonzalez possa, con un semplice accorgimento, ridurre il tempo di calcolo della sua procedura tanto da meritarsi l'appellativo di Speedy. Quale è il nuovo tempo di calcolo?