# Cour 2 -- Algorithme

###### tags `cour` `M1 S1` `Algorithme`
[Somaire](/ueYXUIJIQ6C6hcYzKYeojA#)\
[precedent](/129McedVTHKxfO4OH71UbA)
> [time= 14 sept 2020]

[TOC]

## Backtracking
Les agorithme de backtracking sont souvent très inéficace.

:::success
**Le backtracking** est une stratégie récursive ou on parcour un "arbre" des configurations. On s'arrete dès qu'on rencontre un impossibilité.
:::
### Jeux des N reines
Dans le cas des N reines impossibilité équivaut à placer une reine dans une case interdite.

On revient en arrière "dans l'arbre".
Un sommet de l'arbre est égal à une éxécution de la fonction récursive.\
Ses fils vaut un apelle récursifs fais en cour d'éxécutions.

++Exemple:++\
Qu'est ce qu'une configuration?\
*Un tableau de taille N*


#### Relation de récurence pour les 8 reines
L est la liste de la config\
N la taille du probème NxN
$$
Reine(L, N) =
\begin{cases}
\text{Vrai } &\text{si} |L| = N\\
\bigvee\limits_{i=0}^{n} \: Reine(L + [i], N) \:\land\: Valide(L + [i]) &\
\end{cases}
$$

Fonction de vadité

Algorithme

def valide(L, c):
"""
    test si la colone et les 2 diagonales sont valide
    L :list 
        reine déja placées
    c :int 
        la colone a tester
"""
    for i in range(len(L)):
        test_set = 
        {
            c, 
            c - (len(L) - i),
            c + (len(L) - i)
        }
        if L[i] in test_set:
            return False
    return True
            
def reines(L, N):
"""
    L : list
        reine déja placées
    N : int
        taille de l'échiquier
"""
    if len(L) == N:
        return True
        
    for c in range(N):
        # essayons de placer la reine en colonne c 
        # sur la ligne len(L)
        # on a pas besoin de test la ligne 
        # car on ajoute au fur et a mesure
        if valide(L, c) and reines(L + [c], N): 
            return true
    return False

##### Compléxité
De l'ordre de **N^N^ x N^2^**
- N^N^ est le nombre de noeud visité dans l'arbre des configurations
- Car on a une arrité des noeuds N (N appels récursifs)
- profondeur de l'arbre = N\
A chaque niveau on ajoute une reine
- le travail de vérification de la validité (cout de N^2^)

++Que représente N++^N^ ?\
N = 10 -> 10^10^ $\approx$ 2^30^\
N = 20 -> 20^20^ a peut pres 10^9^ jours

### ++Probleme 2:++ Subset Sum
- ++En entrée:++ \
Un ensemble de nombre positif L une valeur X
- ++En sortie:++ \
Est-il possible d'obtenir X comme la somme d'un sous-ensemble de L?

Ex: L = [2, 8, 3, 11, 24, 5]\
Pour X = 18\
on peut avec 2 + 8 + 3 + 5 = 18

++Algorithme possible++: essayer tout les sous ensembles de L.\
Si |L| = N il y a 2^N^ sous-ensembles.

Stratégie proposée:

On regarde le premier élément
si il est < X:
    on essaie de le prendre et 
    puis si non on complète avec X = X - a
si ca n'a pas marché
    on coninue avec l'élément suivant

Relation de récurence:

$$
S(L, X) =
\begin{cases}
\text{Vrai} & \text{si } X = 0\\
\text{Faux} & \text{si } X < 0\\
\text{Faux} & \text{si } |L| = 0 \: \land \: X>0\\
S(L[1:], X-L[0]) \: \lor\: S(L[1:], X)
\end{cases}
$$

Algorithme

def S(l, x):
    if x == 0:
        return True
    elif x < 0:
        return False
    elif l == []:
        return x == 0
        
    avec = s(l[1:], x - l[0])
    if avec:
        return True;
    return s(l[1:], x)


++compléxité:++
- Arbre avec une arrité 2 (avec / sans)
- profondeur: taille de la liste

Nombre de sommets: 2^|L|^\
Si on néglige la soustaction (x - L[0], *ligne 9*) qui n'est pas en temps constant

La compléxité est donc de l'ordre de **2^N^** si N = |L|

[suivant](/IdYcb7YBTBSveQ_t0efkLw)