# ALGO6 : Révisions
###### tags: `algo` `2021`

## The master theorem

### Rappels :

Logn(k) = y <=> n^y = k

Ω(.) est le minorant du coût
Θ(.) est du même ordre (équivalent)
GrandO(.) est le majorant du coût

n³ est un majorant de n <=> O(n³)
n est un équivalent de 2*n donc Θ(n) (dire O(n) est la même chose)

Si Ω(n), O(n) donc souvent Θ(n)

#### A savoir :


log(n) apparaît dans les diviser pour régner, dans la dichotomie ou bien les arbres

#### Équation de partition :
On trouve 1 pour c(n) car on fait une comparaison (e &ge; c).
On trouve 1 pour a car on rappelle qu'une fois la fonction.
On trouve 2 pour b car on coupe le problème en deux.


## TD1 :

### Exercice 1 :
Le coût au pire du tri fusion est de nlog(n).
Le coût moyen du tri fusion est de nlog(n).

1.

2.

fusion(T1, T2):
    si T1 est vide:
        return T2;
    
    si T2 est vide:
        return T1;
        
    si T1[0] <= T2[0]:
        return T1[0] + fusion(T1[1, ...,end], T2)
    sinon:
        return T2[0] + fusion(T1, T2[1, ..., end])

A chacune de mes appels récursifs, je fais une comparaison. Sachant qu'un des tableaux se fait retirer un élement à chaque appels, on peut considérer qu'il y a n+m comparaisons pour chaque tableau. Or le dernier élement seul ne peut être comparé. Donc il y a (n-1)+(m-1) comparaisons.

### Exercice 2 :

### Exercice 3 :
Div1 ->

1. a=2, b=2, f(n)=Θ(n²)
2. C(n) = 2 C(n/2) + f(n)
3. 2C(n/2) = O(n^logb(a)) = O(n^log2(2)) = Θ(n)
4. f(n) = Ω(n)
5. Donc C(n) = Θ(f(n)) = Θ(n²)

---

1. a=4, b=3, f(n)=Θ(n)
2. C(n) = 4 * C(n/3) + f(n) = Θ(n)
3. n^logb(a) = n^log3(4) et log3(4) > 1 => n^log3(4) > n
4. Donc f(n) = O(n^logb(a)) = O(n^log3(4)) car > n (première règle)
5. D'après le théorème maître :
Donc C(n) = Θ(n^logb(a)) = Θ(n^log3(4))

On peut donc choisir Div2 car Θ(n^log3(4)) car c'est inférieur à Θ(n²) de Div1

## Annales 2020 :
https://algo.gricad-pages.univ-grenoble-alpes.fr/L3I-S6-algo/Q1-ALGO6-2020.02.14.pdf

### Exercice 1 :
1.

* F(n) = 3F(n/2) + c
a = 3 car on effectue 3 fusions.
b = 2 car les fusions sont sur des tableaux de taille n/2
* Alors F(n) = 3 * F(n / 2 ) + C(n) et C(n) = Θ()
* Or n^logb(a) = n^log2(3) et n^log2(3) > n = Θ(n)

### Exercice 2 :
1.

PUISSANCE-DIV(x,n):
	if n = 1 then //cas de base 
	   	return x 
	else // récursion 
		if (n % 3 == 0) then 
			z =PUISSANCE-DIV(x,n/3) 
			return z * z * z
		elif (n % 3 == 1)
		 	z = PUISSANCE-DIV(x,(n − 1)/3) 
			return z * z * z * x
		else 
			z = PUISSANCE-DIV(x,(n − 2)/3) 
			return z * z * z * x * x

2.
* F(n) <= F(n /3) + 4 et F(n) >= F(n/3) + 2
* n ^ logb(a) = n ^ log3(1) = n ^ 0 = 1 = Θ(1)
* 4 = Θ(1) et 2 = Θ(1)
* Donc, F(n) = Θ(n ^ logb(a) * log2(n)) = Θ(n ^ log3(1) * log2(n)) = Θ(log2(n))

3.

On peut tester sur des valeurs en bases 3 :
* 27 = 1000 demande 6 opérations
* 26 = 222 demande 10 opérations
* 42 = 1120 ... etc.

### Exercice 3 :

(k parmi n) = n! / k!(n-k)!

1. La probabilité de trouver un nombre dans les n cases est de 1 / n.
Comme nous avons une suite de tirages indépendants suivant une loi de Bernoulli de paramètre 1 / n, on aura alors une loi binomiale B(n, 1 / n).
Donc, P(Ni = k) = $\binom n k$ * ($\frac{1}{n}$^k) * (1 - $\frac{1}{n}$)^n-k

2. La moyenne de Ni est n * p = n * (1 / n) = 1

## TD3 - Table de hachage

max(Xi) nombre de prénom haché à la case i
moy(Xi) =

4.
a) Autant de prénom qu'il y a dans la case de hachage $\alpha$ opérations
b) $\frac{\alpha + 1}{2}$