---
# System prepended metadata

title: 'ALGO6 : Révisions'
tags: ['2021', algo]

---

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

## The master theorem

### Rappels :

Logn(k) = y <=> n<sup>y</sup> = k

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


n<sup>3</sup> est un majorant de n <=> O(n<sup>3</sup>)
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 :
![](https://i.imgur.com/GO23k8U.png =400x)

![](https://i.imgur.com/Ruhc5BM.png =400x)

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

#### Équation de partition : 
![](https://i.imgur.com/227SH0F.png =400x)
![](https://i.imgur.com/HHZ2Nms.png =600x)
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.

![](https://i.imgur.com/9KMnfz0.png =600x)

## 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. 
![](https://i.imgur.com/BY0SVkJ.png)

2.
```c
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<sup>2</sup>)
2. C(n) = 2 C(n/2) + f(n)
3. 2C(n/2) = O(n<sup>logb(a)</sup>) = O(n<sup>log2(2)</sup>) = Θ(n)
4. f(n) = Ω(n)
5. Donc C(n) = Θ(f(n)) = Θ(n<sup>2</sup>)

---

1. a=4, b=3, f(n)=Θ(n)
2. C(n) = 4 * C(n/3) + f(n) = Θ(n)
3. n<sup>logb(a)</sup> = n<sup>log3(4)</sup> et log3(4) > 1 => n<sup>log3(4)</sup> > n
4. Donc f(n) = O(n<sup>logb(a)</sup>) = O(n<sup>log3(4)</sup>) car > n (première règle)
5. D'après le théorème maître :
   Donc C(n) = Θ(n<sup>logb(a)</sup>) = Θ(n<sup>log3(4)</sup>)
   
   
   
On peut donc choisir Div2 car Θ(n<sup>log3(4)</sup>) car c'est inférieur à Θ(n<sup>2</sup>) 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<sup>logb(a)</sup> = n<sup>log2(3)</sup> et n<sup>log2(3)</sup> > n = Θ(n)


### Exercice 2 :
1.
```c
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}$<sup>k</sup>) * (1 - $\frac{1}{n}$)<sup>n-k</sup>

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}$ 