# Cour 5 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/IKMxLzyLRZ--ApSIHlh1YQ)
> [time= 5 oct 202O]

[TOC]
## Karatsuba (rapelle)
On avait:
$$
T(N) = 3T\left(\frac{N}{2}\right) + N\\
T(1) = T(0) = 1
$$
- on a **3 appelle récursif** sur une instance de taille $\frac{N}{2}$
- et **N addition**

Digraph G{
    p0  -> {p11, p12, p13}
    p11 -> {p21, p22, p23}
    p21 -> pi [style=dotted, arrowhead=none]
    pi  -> p1 [style=dotted, arrowhead=none]
    {
    rank=same
    p0 [label="N"]
    }
    
    {
    rank=same
    p11 [label="N/2"]
    p12 [label="N/2"]
    p13 [label="N/2"]
    }
    {
    rank =same
    p21 [label="N/2"]
    p22 [label="N/2"]
    p23 [label="N/2"]
    }
    {
    rank = same
    pi [label="N/2^i"]
    }
    {
    rank = same
    p1 [label="1"]
    }
}

A chaque niveau on a $3^i$ noeud

Rapelle:
$$
\log_b(a) = \frac{\log_c(a)}{\log_c(b)}\\
2^{log_2(N)} = N\\
3^{log_2(N)} = N^{log_2(3)}
$$

On a donc:
$$
\begin{align}
T(N)&= \sum_{i=1}^{\log_2(N)} 3^i \times \left(\frac{N}{2}\right)^i \\
&= N \times \sum_{i=1}^{\log_2(N)}\left(\frac{3}{2}\right)^i\\
&= N^{log_2(3)}\\
&= N^{1,58}
\end{align}
$$

## Résolution de récurences
On a souvent lorsqu'on analyse des algos de type diviser pour régner des formules de compléxité de la forme:
$$
T(N) = \textbf{a} T\left(\frac{N}{\textbf{b}}\right) + f(N)
$$
avec
- $\textbf{a}$ etant le nombre d'apelle récurisf
- $T\left(\frac{N}{\textbf{b}}\right)$ taille des sous-instances
- $f(N)$ travail réaliser sans compter les apelles récursifs

>> ajouter graph général

Si on somme par hauteur:
$$
T(N) = \sum_{i=0}^{\log_b(N)} a^i \times f\left(\frac{N}{b^i}\right) \\
$$

On suppose aussi:
$$
T(1) = T(0) = 1
$$

:::info
Ex:
- **Tri fusion:** $T(N) = 2T\left(\frac{N}{2}\right) + N$
- *a* = 2; *b* = 2; *f(N)* = N
- **Karatsuba:** $T(N) = 3T\left(\frac{N}{2}\right) + N$
- *a* = 3; *b* = 2; *f(N)* = N
:::

### Calculons pour $f(N) = N$
Calculons pour a, b des entier quelconques et $f(N) = N$
$$
T(N) = \sum_{i=0}^{\log_b(N)} a^i \times f\left(\frac{N}{b^i}\right) \\
$$

On condière 3 sous cas:
#### cas 2: $a = b$

$$
\begin{align}
T(N) &= N \sum_{i=0}^{\log_b(N)} \left(\frac{a}{b}\right)^i \\
&= N \sum_{i=0}^{\log_b(N)} 1\\
&= N \times (\log_b(N) + 1)\\
&= O(N log(N))
\end{align}
$$

#### cas 1 et 3: $a \neq b$
$$
\begin{align}
T(N) &= N \sum_{i=0}^{\log_b(N)} \left(\frac{a}{b}\right)^i \\
&= \frac{N}{1 - \frac{a}{b}} \left(1 - \left(\frac{a}{b}\right)^{\log_b(N)}\right) \\
&= \frac{N}{1 - \frac{a}{b}} \left(1 - a^{\log_b(N)}\right) \\
&= \frac{1}{1 - \frac{a}{b}} \left(N - Na^{\log_b(N)}\right) \\
&= \frac{1}{1 - \frac{a}{b}} \left(N - N^{\log_b(a)}\right) \\
\end{align}
$$

#### cas 1: a < b
$$
\begin{align}
T(N) &= \underbrace{\frac{1}{1 - \frac{a}{b}}}_{\geq 0} \times N
- \underbrace{\frac{1}{1 - \frac{a}{b}} \times N^{\log_b(a)}}_{<<N}\\
\textbf{on conclut T(N)} & \textbf{= $O\left(N\right)$}
\end{align}
$$

#### cas 3: a > b
$$
\begin{align}
T(N) &= \underbrace{\frac{1}{1 - \frac{a}{b}} \times N}_{\approx 0}
- \underbrace{\frac{1}{1 - \frac{a}{b}} \times N^{\log_b(a)}}_{>0}\\
\textbf{on conclut T(N)} & \textbf{= $O\left(N^{\log_b(a)}\right)$}
\end{align}
$$

### Attaquons le cas plus général de f(N) quelconque

$$
\text{Soit la relation de compléxité: } \\
\begin{align}
T(N) &= a T\left(\frac{N}{b}\right) + f(N) \text{ et:}\\
cas 1: \quad & a f(\frac{N}{b}) = c f(N),
\: c < 1\\
cas 2: \quad & a f(\frac{N}{b}) = \: f(N),
\: c = 1\\
cas 3: \quad & a f(\frac{N}{b}) = c f(N),
\: c > 1\\
\end{align}
$$

- **c < 1**: le travaille décroit
- **c = 1**: le travaille est équilibré a chaque niveau
- **c > 1**: on travaille augment a chaque niveau

#### proposition:
$$
\begin{align}
\forall{a,b,c}
&\text{ Si } af\left(\frac{N}{b}\right) = cf(N)\\
&\text{ Alors } a^i f\left(\frac{N}{b^i}\right) = c^{i}f(N)
\end{align}
$$

- $a^i$ etant le nombre de noeud au niveau *i*
- $\frac{N}{b^i}$ etant le travail réliser sur chaque noeud au niveau *n*

### Preuve
Laissée au lecteur:
On a que:
$$
\begin{align}
T(N) &= \sum_{i=0}^{log_b(N)} a^i f\left(\frac{N}{b^i}\right)\\
&= \sum_{i=0}^{log_b(N)} c^i f\left(N\right) \\
&= f(N) \sum_{i=0}^{log_b(N)} c^i
\end{align}
$$
#### cas 2: c = 1
$$
\begin{align}
T(N) &= f(N)\times (\log_b(N) + 1)\\
&= \theta(f(N)\log_b(N))
\end{align}
$$

#### cas 1: c < 1
$$
\begin{align}
T(N) &= f(N) \underbrace{\sum_{i=0}^{log_b(N)} c^i}_{\text{la série converge}}\\
&= \theta(f(N))
\end{align}
$$

#### cas 3: c > 1
la série ici va divergé, dans ce cas on a que le therme qui correspond a: $i = log_b(N)$ qui domine.
\begin{align}
T(N) &= \sum_{i=0}^{log_b(N)} a^i f\left(\frac{N}{b^i}\right)\\
&= \theta\left(
a^{\log_b(N)} \times
\underbrace{f\left(\frac{N}{b^{log_b(N)}}\right)}_{f(1) = 1}
\right)\\
&= \theta\left(a^{\log_b(N)}\right)\\
&= \theta\left(N^{\log_b(a)}\right)
\end{align}

### On a montré:

#### Master théorem (version Erickson)
$$
\begin{align}
\text{Si } T(N) &= a T\left(\frac{N}{b}\right) + f(N) \text{ et:}\\
(1) \quad & \text{Si } a f\left(\frac{N}{b}\right) = c f(N), \: c < 1\\
&\text{Alors } T(N) = \Theta(f(N))\\
\\
(2) \quad & \text{Si } a f\left(\frac{N}{b}\right) = c f(N), \: c = 1\\
&\text{Alors } T(N) = \Theta(f(N) \times \log_b(N))\\
\\
(3) \quad & \text{Si } a f\left(\frac{N}{b}\right) = c f(N), \: c > 1\\
&\text{Alors } T(N) = \Theta(N^{\log_b(a)})\\
\end{align}
$$

:::info
**Tri fusion:**\
$T(N) = 2 T\left(\frac{N}{2}\right) + N$
- a = 2
- b = 2
- f(N) = N

Donc:
$T(N) = \theta(N log(N))$

**BFPRT:**\
$T(N) = T\left(\frac{N}{5}\right) + T\left(\frac{7N}{10}\right) + N$\
On peut pas appliquer le master théorem.

**Karatsuba**:\
$T(N) = 3T\left(\frac{N}{2}\right) + N$\
$a f(\frac{N}{b})= 3 \frac{N}{2} = \frac{3}{2} N$
- a = 3
- b = 2
- f(N) = N
- c > 1
Donc:
$T(N) = \theta(N^{\log_2(3)}) = N^{1,58}$
:::

## Problème réputés difficiles
Il y a des problèmes utiles pour lesquels les meilleurs algos ont une compléxité exponentiels.

## Ensemble indépendant maximum
Aussi appelé probleme du **stable maximum**.

**En Entré:**\
Un graphe G non-orienté

**En Sortie:**\
La taille du sous ensemble maximum de sommets tel que aucune paire de sommet de l'ensemble n'est arrète du graphe

Digraph g{
    node [shape=circle]
    {
    rank = same;
    a [label=""]
    }
    {
    rank = same;
    b [label="" style=filled]
    c [label="" style=filled]
    e [label=""]
    }
    {
    rank = same;
    d [label=""]
    }
    a -> {b, c}  [arrowhead=none]
    b -> {d, c}  [arrowhead=none]
    c -> {e}     [arrowhead=none]
    d -> {c}     [arrowhead=none]
}

**pas de stable**

Digraph g{
    node [shape=circle]
    {
    rank = same;
    a [label="" style=filled]
    }
    {
    rank = same;
    b [label="" ]
    c [label=""]
    e [label=""]
    }
    {
    rank = same;
    d [label="" style=filled]
    }
    a -> {b, c}  [arrowhead=none]
    b -> {d, c}  [arrowhead=none]
    c -> {e}     [arrowhead=none]
    d -> {c}     [arrowhead=none]
}

**stable mais pas max**

Digraph g{
    node [shape=circle]
    {
    rank = same;
    a [label="" style=filled]
    }
    {
    rank = same;
    b [label="" ]
    c [label=""]
    e [label="" style=filled]
    }
    {
    rank = same;
    d [label="" style=filled]
    }
    a -> {b, c}  [arrowhead=none]
    b -> {d, c}  [arrowhead=none]
    c -> {e}     [arrowhead=none]
    d -> {c}     [arrowhead=none]
}

**stable de taille max**

### Algo 1
Essayer tout les sous-ensemble de sommets.\
Si G a n sommets, on va essayer 2^n^ sous-ensembles; pour chaque sous ensemble vérifier s'il forme un stable.\
Compléxité:
$O(2^n \times n^2)$
- $2^n$ sous ensemble
- $n^2$ vérifiéer si c'est un stable

### Algo 2

def EIM2(G):
    if G.empty():
        return 0
    #prendre un sommet v    
    v = G.un_sommet()
    # on enleve les voisins de v et ses voisin
    # (stable contient v)
    avec = 1 + EIM2(G.sans_voisinage(v))
    # on enleve v du graph 
    # (v n'est pas dans le stable)
    sans = EIM2(G.sans(v)) 
    return max(avec, sans)

##### Compléxité

$$
T(N) \leq
\begin{cases}
0 & \text{si } N = 0\\
T(N - 1) + T(N - 1) + O(N^2)
\end{cases}
$$
- $T(N - 1)$ temps *avec v*
- $T(N - 1)$ temps *sans v*
- $O(N^2)$ temps de construction du graph

$$
\begin{align}
T(N) &\approx 2T(N-1) + N^2 \\
&\leq O\left(2^N N^2\right)
\end{align}
$$

[next](/Cy2DGQBnSUuO1akqrawPpg)