# Cour 3 -- Algorithme
###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/gvyXVnEOQyCM91UM0SAsaw)
> [time= 21 sept 2020]
[TOC]
## Diviser pour régner (devide & conquer)
:::success
**Diviser pour régner** est une technique algorithmique qui consite a diviser en ++sous exemplaire indépendants++.\
On va résoudre les sous-exemplaire récursivement.\
Et les récombiner les solutions ainsi obtenues.
:::
Exemple:
- recherche dichotomique
- quick sort (trie rapide)
- tri fusion
### tri fusion
| Opération | Complexité |
| ------------------------------------------------------:|:------------------------------------------------- |
| On divise un tableau en 2 sous tableau de taille égale | négligeable |
| Trie récursivement | (2 apelle récursifs sur des tablea de taille N/2) |
| fusionne | O(N) |
Relation de récurrence du tri fusion:
$$
TF(L) =
\begin{cases}
L & \text{si } |L| \leq 1\\
fusion\left(
TF\left(L\left[ : \frac{|L|}{2}\right]\right),
TF\left(L\left[\frac{|L|}{2} : \right]\right)
\right)
\end{cases}
$$
code python correspondant:
```python=
def fusion(l1, l2):
i1 = i2 = 0
r = []
while (i1 < len(l1) and i2 < len(l2)):
if l1[i1] < l2[i2]:
i_min = i1
i1 +=1
else:
i_min = i1
i2 +=1
r.append(l1[i_min])
i_min = i1 if i < len(l1) else i2
r.extend(l1[i_restant:])
return r
def tri_fusion(l:list):
if len(l) <= 1:
return l
l1 = tri_fusion(l[: len(l) // 2])
l2 = tri_fusion(l[len(l) // 2 :])
return fusion(l1, l2)
```
```graphviz
Digraph my_graph{
{
rank=same;
n1 [label=N]
r0 [label="", shape=none]
}
{
rank=same;
n2_1 [label="N/2"]
n2_2 [label="N/2"]
}
n1 -> {n2_1;n2_2}
{
rank=same;
n4_1 [label="N/4"]
n4_2 [label="N/4"]
n4_3 [label="N/4"]
n4_4 [label="N/4"]
}
n2_1 -> {n4_1; n4_2}
n2_2 -> {n4_3; n4_4}
subgraph sub_i
{
node [style=filled];
rank=same;
node [label="N/(2^i)"] ni_1
node [label="N/(2^i)"] ni_2
node [label="N/(2^i)"] ni_3
node [label="N/(2^i)"] ni_4
node [label="N/(2^i)"] ni_5
node [label="N/(2^i)"] ni_6
node [label="N/(2^i)"] ni_7
node [label="N/(2^i)"] ni_8
}
n4_1 -> {ni_1, ni_2} [style=dashed, arrowhead=none]
n4_2 -> {ni_3, ni_4} [style=dashed, arrowhead=none]
n4_3 -> {ni_5, ni_6} [style=dashed, arrowhead=none]
n4_4 -> {ni_7, ni_8} [style=dashed, arrowhead=none]
{
rank=same;
n1_01 [label="1"]
n1_02 [label="1"]
n1_03 [label="1"]
n1_04 [label="1"]
n1_05 [label="1"]
n1_06 [label="1"]
n1_07 [label="1"]
n1_08 [label="1"]
n1_09 [label="1"]
n1_10 [label="1"]
n1_11 [label="1"]
n1_12 [label="1"]
n1_13 [label="1"]
n1_14 [label="1"]
n1_15 [label="1"]
n1_16 [label="1"]
rn [label="", shape=none]
}
ni_1 -> {n1_01, n1_02}[style=dotted, arrowhead=none]
ni_2 -> {n1_03, n1_04}[style=dotted, arrowhead=none]
ni_3 -> {n1_05, n1_06}[style=dotted, arrowhead=none]
ni_4 -> {n1_07, n1_08}[style=dotted, arrowhead=none]
ni_5 -> {n1_09, n1_10}[style=dotted, arrowhead=none]
ni_6 -> {n1_11, n1_12}[style=dotted, arrowhead=none]
ni_7 -> {n1_13, n1_14}[style=dotted, arrowhead=none]
ni_8 -> {n1_15, n1_16}[style=dotted, arrowhead=none]
rn -> r0 [headlabel="log2(N)", arrowhead=none, labeldistance=15]
}
```
Compléxité:\
Somme du travail réalisé dans l'ensemble des appels de la fonction.
$$
\begin{align}
T(N)&= \sum_{i=0}^{\log_2(N) - 1}
2^i \times \frac{N}{2^i}\\
&= N \sum_{i=0}^{\log_2(N) - 1}
\frac{2^i}{2^i}\\
&= N \sum_{i=0}^{\log_2(N) - 1}
1\\
&= N \log_{2}(N)
\end{align}
$$
- $\frac{N}{2^i}$ est le travail réalisé a chaque noeud
- 2^i^ est le nombre de noeud au niveau
On a aussi
$$
T(N) = 2 \times T\bigg(\frac{N}{2}\bigg) + N
$$
### Selection du k^ieme^ plus petit elément
Entré:
- list L
- entier k
Sortie:
- l'élément de rang k dans L (rang + valeur)\
(le k^ieme^ plus petit élément)
idée
- on choisis un pivot avant *p*
- on fait une partition a la positon p
`[7, 15, 1, 8, 2, 12]`\
si `p = 3` (donc valeur = 8)\
`[7, 1, 2, 8, 15, 12]`\
donc `r=3`
```python=
def quick_select(l, k):
if len(l) == 1:
return (0, l[0]) # couple (indice, valeur)
p = pivot(l) # choix d'un pivot
r = partition(l, p) # position du pivot apres partition
if r > k:
return quick_select(l[:r], k)
elif k > r:
return quick_select(l[r + 1:], k - r)
return (r, l[r]) # si k == r
```
### Algorithme BFPRT (Blum Floyd Pratt Rivest Tarjan)
Pour le choix d'un pivot:
- Le meilleur pivot est la médiane (donc élement de rang $\frac{N}{2}$)
- On va se contenter d'une "pseudo-médiane"
- On veut garantir que au moin $\frac{3N}{10}$ plus petits que le pivot
- et au moin $\frac{3N}{10}$ plus grand que le pivot
Ca suffit donc a éviter le pire cas de quick_select
- On coupe notre liste en block de 5 et on cherche la médiane.
- On fait un tableau *M* de taille *N / 5* médianes des blocks de taille 5
- On fait un appel récursif pour trouver la médiane de *M* de valeur *v* et l'utiliser comme pivot
#### Proposition:
Il y a au moin $\frac{3N}{10}$ élément de *L* plus petit au égaux *v* où *v* est la médiane de *M*.
#### Argument:
Dans *M*
- la moitié des valeurs sont plus petit ou égaux a *v*
- la moitié sont supérieur ou égaux a *v*
Pour les block vert(block de départ) on recue 3 valeurs $\leq$ *v* la médiane du block plus les 2 valeurs $\leq$ la médiane du bloc.
Il y a N/5 blocs dont la moitié sont verts.
Donc $\geq 3 \times \frac{N}{10}$ valeurs qui sont $\leq$ à *v*
```python=
def BFPRT(l, k):
if len(l) <= 20:
quick_select(l, k)# avec le pivot k de votre choix
# M est une liste de taille m de médiannes
M = [quick_select(l[i : i + 5], 2)
for i in range(0, len(l), 5)]
p, v = BFPRT(M, len(m) // 2) # calcul de la médiane
r = partition(l, p)
if r > k:
return BFPRT(l[:r], k)
elif k > r:
return BFPRT(l[r + 1:], k - r)
return (r, l[r])
```
Compléxité de *T(N)* de BFPRT:
$$
\begin{align}
T(N) = T\left( \frac{N}{5} \right) +
T\left( \frac{7N}{10} \right) +
N
\end{align}
$$
- $T\left( \frac{N}{5} \right)$ pour la médiane de M
- $T\left( \frac{7N}{10} \right)$ apelle récursif
- $N$ partition + quick_select en $\frac{N}{5}$ morceau
[suivant](/IKMxLzyLRZ--ApSIHlh1YQ)
Sign in with Wallet
Connect another wallet