# Cour 6 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/iv7_YjPzRnKPIGlFmtuPOA)
> [time= 5 oct 2020]

[TOC]

## Ensemble indépendant maximum (suite)
- Maximum independant set
- stable maximum

### 1er astuce
Si le voisinage de v = {v} (deg=0)\
On fait 2 fois le même appel récursif:
On modifie l'algo pour ne pas le faire 2 fois

$$
T_1(N) \leq
\begin{cases}
1 & \text{si } N = 0\\
T_2(N - 1) + N^2 &\text{si } deg(v)=0\\
T_2(N - 1) + T_2(N - 2) + N^2 &\text{si } deg(v) > 0\\
\end{cases}
$$

Ca ressemble a **fibonacci**
$$
T_1(N) \leq \frac{N^2}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^N\\
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1,62
$$

### astuce 2
Si **v** a un seul voisin dans **G**
alors on peut toujours supposer que **v** est dans un stable max.

S'il ne l'était pas:\
++**w** y était++: on peut remplacer
**w** par **v** sans "casser" le stable ($v \not\sim u \: u \neq w$ en particulier c'est vrai pour tous les sommets **u** du stable)\
++**w** n'y est pas++ on peut rajouter **v**

def EIM3(G):
    if len(G):
        return 0;
    #prendre un sommet v    
    v = G.un_sommet()
    # sommet isolé
    if v.deg == 0:
        return EIM3(G.sans(v)) + 1
    # cas qu'on viens de voir
    elif v.deg == 1:
        return EIM3(G.sans_voisinage(v)) + 1
    
    else: # deg >=2
        avec = EIM3(G.sans_voisinage(v)) + 1
        sans = EIM3(G.sans(v))
        return max(avec, sans)     

$$
T_3(N) \leq
\begin{cases}
1 & \text{si } N = 0\\
T_3(N - 1) + N^2 &\text{si } deg(v)=0\\
T_3(N - 2) + N^2 &\text{si } deg(v)=1\\
T_3(N - 1) + T_3(N - 3) + N^2 &\text{si } deg(v) \geq 2\\
\end{cases}
$$

Pire cas:
$$
T_3(N) \leq T_3(N - 1) + T_3(N - 3) + N^2
$$
Pour simplifier éliminous N^2^ lors de la récurence

Comment résoudre cette récurrence?\
Par induction

$$
\begin{align}
&\text{Supposons } T_3(N) = \alpha^N\\
&\text{remplacons } T_3(N) \text{ par } \alpha^N \text{dans la récurrence}\\
&\left(\alpha^N = \alpha^{N - 1} + \alpha^{N - 3}\right) / \alpha^{N - 3}\\
& \alpha^3 = \alpha^2 + 1\\
& \alpha^3 - \alpha^2 - 1 = 0\\
& \text{la plus grande racine est:}\\
& \alpha \approx 1, 4655
\end{align}
$$

On conclut que $T_3(N) \leq (1,4655)^N$

### astuce 3
Notre pire cas se produit lorsque *deg(v) = 2*\
On pourrait améliorer la récurrence.\
Si on prenait toujours un sommet de degré $\geq 3$\
Pire cas: Tous les sommets sonts de degré 2 !

or c'est tres facile si c'est le cas:\
le graph est une union de cycles!

Digraph impaire
{
    label="graph avec cycle impair"
    node [shape=circle]
    layout="circo";
    pi1 [label="", style=filled]
    pi2 [label=""]
    pi3 [label="", style=filled]
    pi4 [label=""]
    pi5 [label="", style=filled]
    pi6 [label=""]
    pi7 [label=""]
    
    pi1 -> pi2 -> pi3 -> pi4 -> pi5 -> pi6 -> pi7 -> pi1
}

Digraph pair
{
    label="graph avec cycle impair"
    node [shape=circle]
    layout="circo";
    pp1 [label="", style=filled]
    pp2 [label=""]
    pp3 [label="", style=filled]
    pp4 [label=""]
    pp5 [label="", style=filled]
    pp6 [label=""]
    pp7 [label="", style=filled]
    pp8 [label=""]
    
    pp1 -> pp2 -> pp3 -> pp4 -> pp5 -> pp6 -> pp7 -> pp8 -> pp1
}

$$
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
$$
Pour chaque cylce de taille M stable max est toujours $\floor{\frac{N}{2}}$

def EIM4(G):
    if len(G) == 0:
        return 0
    # si g contien un sommet v de degré deg(v) <= 1
    if (v:=g.contien_v_inf_eq_1()):
        return EIM4(G.sans_voisinage(v))
    # g est 2 régulier
    elif g.est_2_regulier():
        #décoposer en cycle de taille m1, ... mx
        return sum(map(lambda m : foor(m / 2), g.decompose_cycle())
    else:
    # prendre un sommet dans g
        v = G.un_sommet()
        avec = EIM3(G.sans_voisinage(v)) + 1
        sans = EIM3(G.sans(v))
        return max(avec, sans)

$$
T(N) \leq T(N - 1) + T(N - 4) (*)
$$

Pour résoudre cette récurrence on suppose
$$
\begin{align}
&T(N) \approx \beta^N \text{, je substitue dans (*)}\\
&\left(\beta^N = \beta^{N-1} + \beta^{N-4}\right) / \beta^{N - 4}\\
&\beta^4 = \beta^3 + 1 \\
&\text{il reste à trouver une racine de:}\\
&\beta^4 - \beta^3 - 1 =0\\
&\text{on trouve la plus grande racine:}\\
&\beta \approx 1,38^N
\end{align}
$$

Si on exécute $\approx 10^{11}$ instructions par seconde.\
On dispose de 10^t^ secondes:

**Algo 1:**
- $2^N = 10^t \times 10^{11}$
- N = 33 + 3t

**Algo 2:**
- $1,62^N = 10^t \times 10^{11}$
- $N \approx 4,77 (11 + t)$

**Algo 4:**
- $1,38^N = 10^t \times 10^{11}$
- $N \approx 7,14 (11 + t)$

## P vs NP
les problèmes réputés difficiles

La grande question:
:::success
Existe t-il un algorithme polynomial (en $O(N^{[]})$ et non $O([]^{N}))$ pour des problèmes réputés difficiles?
(Comme EIM)
:::

### Cook - Levin 1971
On démontré:

Il existe un problème **SAT** qui partage les propriétés des problèmes réputés difficiles si on savait résoudre SAT en temps polynomial, alors on saurait résoudre en temps polynomial, tous ces autres problèmes "réputés difficiles"

### Exemple de problèmes réputés difficile
- EIM (Ensemble indépendant maximum)
- 3COL (3 colorabilité)
- CLIQUE (MaxClique)
- HAM (existe-t-il un circuit hamiltonien dans G)
- SUBSET SUM

Pour simplifier les choses on va se limiter à un **problème de décision**, ceux dont la réponse est **vrai ou faux**.

##### EIM
- en entré
- G (graph)
- k (entié)
- en sortie
- VRAI si il existe un stable de taille k
- FAUX sinon
##### 3COL
- en entré
- G
- en sortie
- Décidé **si il existe une coloration** telle que:\
aucune arréte n'a 2 extrémités de la meme couleur (prédicat de vérification)

##### Clique
- en entré
- G
- en sortie
- Décidé **s'il existe un ensemble de sommets S** t.q: \
toutes les paires de sommets dans S sont reliés par une arrète(prédicat de vérification)

## Probleme P
On dit qu'un problème de décision est P(polynomial) s'il existe un algorithme pour ce problème dont la complexité est un polynome N^c^.
ou c est une constante

On dit qu'il est décidable en temps polynomial.

## Probleme réputé difficile NP
:::success
On dit qu'un problème de décision est NP si il sécrit sous la forme:
$$
\begin{align}
& \text{Sur entrée } X: \text{décider si}\\
& \exists \Pi : V(X, \Pi)\\
\end{align}\\
\textbf{ET}\\
\text{V doit être réalisable en temps polynomial étant donné en entrée X et } \Pi
$$
:::
- $\Pi$: ex: une coloration, un sous-ensemble de sommet ...
- $V(X, \Pi)$: le prédicat de vérification

[suivant](/oMYgG0ACSsK_UFQxu9-SkA)