L'algo, ce n'est pas si Dürr !

https://people.via.ecp.fr/~enizor/algo/revisions

Plan

  • Diviser pour régner, algorithmes gloutons
  • Programmation dynamique
  • Algorithme par balayage
  • Flots et coupes
  • Classes de problèmes: NP-complétude
  • Algorithmes d'approximation
  • Algorithmes randomisés

Diviser pour régner

  • Division du problème en b parties
  • Appel récursif sur ces parties
  • Combination des parties pour obtenir le résultat global

Exemple typique: le tri fusion

def mergeSort(alist):
    if len(alist)>1:
        # Division
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        #Appel récursif
        mergeSort(lefthalf)
        mergeSort(righthalf)
        #Fusion
        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

Et au CF ?

  • création d'un tel algorithme (Si je suis capable de résoudre sur un input plus petit, puis-je résoudre sur un input plus grand ?)
  • preuve de complexité (théorème maître): $n = b^k$

$$ \begin{split} C(n) &= C(b^k) \\ C(n) &= M \cdot C(n/b) + f(n) \\ C(b^k) &= M \cdot C(b^{k-1}) + f(n) \\ u_k &= M \cdot u_{k-1} + f(n) \end{split} $$

Et au CF ?

Exemple sur le tri fusion:

  • $n = 2^k$ i.e. $k =\text{log}_2(n)$
  • $C(n) = 2 \cdot C(n/2) + O(n)$

$$ \begin{split} u_k &= 2 \cdot u_{k-1} + 2^k \\ u_k &= (k+u_0) \cdot 2^k \\ C(n) &= O(n \text{log}_2(n)) \end{split} $$

Algorithmes Gloutons

On contruit une solution globale par itération.

A chaque étape, on fait un choix optimum localement

On espère que la solution obtenue est optimale globalement

Exemple typique: le rendu de monnaie

Comment rendre la monnaie avec le moins de pièces possibles ?

On trouve la plus plus grosse pièce possible que l'on peut rendre, et l'on recommence.

Et au CF ?

  • Création d'un tel algorithme (à une étape donnée, quelle est l'opération qui me rapproche le plus rapidement de mon objectif)
  • preuve d'optimalité (avec des preuves par l'absurde):
    • prouver que le glouton est toujours optimal (local).
    • argument d'échange : on échange notre 1er choix avec celui optimal, montrer que l'on garde l'optimalité, et appliquer récursivement
    • argument structurel : invariant "structurel" qui amène à la dernière étape à l'optimalité

Le glouton toujours optimal

Problème des antennes sur la plage : étant donné un ensemble d'intervalles, construire un ensemble de points $S$ tel que chaque intervalle intersecte $S$. Pour tout nouvel interval $[l,r]$, si $l<max(S)$ alors OK, sinon on ajoute $r$.

Supposons $S$ optimal pour $I$ et $max(S) \geq max(S'')$ pour tout $S''$ optimal. Soit $S'$ optimal pour $I \cup [l,r]$.

$|S| \leq |S'| \leq |S| + 1$

On regarde ensuite les 2 cas d'égalité.

Argument d'échange

Problème de l'ordonnancement d'intervalle: on choisit celui qui finit le plus tôt.

Soit $X$ optimal. On peut échanger le 1er intervalle avec celui choisi par l'algo $I$ car il fini plus tôt en e1.

Puis on montre que $X'$ privé de cet intervalle est optimal pour ce sous-problème par l'absurde: soit $X''$ optimal dessus. Alors $X'' \cup \text{end}(I)$ est optimal sur le même ensemble que $X$ mais contient un élément de plus que $X$.

On conclut par récurrence.

Argument structurel

Problème du plus court chemin: algorithme de Dijkstra. À chaque étape est ajouté le noeud le plus proche du sous-graphe en cours. Invariant: pour tout sommet de l'étape du sous-graphe en cours est atteint optimalement.

Preuve par récurrence.

Programmation dynamique

Stocker les valeurs des sous-problèmes pour éviter de refaire les mêmes calculs, souvent dans des problèmes d'optimisation.

Tradeoff complexitée spatiale vs temporelle

def fibo(n):
    if n <= 1:
        return 1
    else:
        return fibo(n-1)+fibo(n-2)
def fibo_dyna(n):
    F = [1,1]
    for i in range(2,n+1):
        F.append(F[i-2] + F[i-1])
    return F[n]

Et au CF ?

Quelle est ma relation entre ma valeur en un point A comparée à d'autres points ? Généralement une fonction du minimum/maximum sur les points avoisinants. Les points "sur le bord" sont ceux dont il est facile de déterminer la valeur recherchée.

Preuve de l'optimalité: par récurrence sur tous les points.

Algorithme par balayage

???

Programmation dynamique avec une notion de parcours.

Flots et coupes

Sur un graphe avec des arêtes possédant des capacités, avec un noeud source et un noeud puits:

Un flot réseau associe à chaque couple de noeud un flot sur l'arête reliant ces noeuds:

  • le flot sur l'arête est plus petit que la capacité de l'arête
  • le flot arête de u vers v vaut l'opposé de v vers u
  • Loi des noeuds: la somme des flots entrants et sortant sur un noeud est nul

Ford-Fulkerson

On obtient un réseau résiduel en enlevant aux capacités les valeurs d'un flot réseau. (/!\ il y a alors une capacité par sens de l'arête).

En itérant jusqu'à ce que la source soit déconnectée du puits on obtient un flot maximal.

Si les capacités sont entières, chaque itération augmente la valeur du flot total d'un nombre entier, ce qui assure la terminaison en $O(|E|f)$ et une valeur de flot maximal $f$ entière.

Théorème flot-max/coupe-min

Une coupe est un ensemble d'arête, qui lorsque qu'elles sont enlevées du graphe, séparent les sommets en 2 sous-ensembles. Sa valeur est la somme des capacités des arêtes séparant ces 2 ensembles.

Le théorème indique que chercher le flot maximal est équivalent à trouver une coupe minimale avec la source et le puits séparés dans $S$ et $T$, i.e. celle qui minimise les capacités des arêtes allant de $S$ à $T$

Et au CF ?

Ramener un problème de graphe à un problème de flots ou de coupe

Classes de problèmes

On considère des problèmes de décision.

On les classe suivant la complexité de leur résolution sur une machine de Turing.

Attention: quelle est l'unité de de la taille du problème ?

Classe $P$

Le problème de taille $n$ est résoluble avec une complexité polynomiale en $n$ (ou plus faible) sur une machine de Turing déterministe i.e. votre ordinateur.

Exemples:

  • PRIMES ($n$ est-il premier ?) est dans $P$. Complexité fonction de la taille en bits de $n$
  • Tri d'un tableau
  • Résolution du Rubik's cube

Classe $NP$

Le problème est résoluble avec une complexité polynomiale sur une machine de Turing non-déterministe. On a le droit de vérifier toutes les possibilités en même temps.

La question est donc de savoir reconnaître une solution.

Exemples:

  • Problème du voyageur de commerce
  • Résolution d'un sudoku
  • Problème du Démineur

Classe $NP-hard$

Le problème est au moins aussi dur que n'importe quel problème de $NP$. On peut ramener tout problème de $NP$ à celui-ci en un temps polynomial.

En particulier, si l'on trouve un algorithme polynomial, alors tous les problèmes de $NP$ sont résolubles en temps polynomial, et $P=NP$

Exemple:

  • Problème de l'arrêt

Classe $NP-complete$

Ce sont les problèmes à la fois dans $NP$ et dans $NP-hard$.

Exemples:

  • le démineur de Windows
  • Tetris
  • beaucoup de problèmes moins rigolos

Récap

Et au CF ?

Prouver qu'un problème $\Psi$ est $NP$-complet: d'abord prouver qu'il est dans $NP$ (généralement simple).

Puis prouver qu'il est $NP$-difficile. Pour cela on prend une instance $\phi$ d'un problème $\Phi$ $NP$-complet qui lui "ressemble". On le transforme en un temps polynomial en une instance $\psi$ de $\Psi$.

Puis on prouve l'implication résoudre $\psi \Rightarrow$ résoudre $\phi$ généralement sous la forme:

  • $\psi$ soluble $\Rightarrow \phi$ soluble
  • $\phi$ soluble $\Rightarrow \psi$ soluble (contraposée)

Problèmes $NP$-complets classiques

  • SAT: satisfaction d'une proposition de booléens. Faire les portes logiques et construire un "circuit électronique"
  • Vertex cover (couverture par sommets)
  • Subset sum & 2-partition

Exemple: 2-partition

On veut réduire SUBSET-SUM: <$S,G$> à 2-PARTITIONS. On a $G \leq \sum_S /2$ par symétrie.

On pose $z = \sum_S - 2G$ et 2-PARTITIONS <$S \cup \{z\}$>.

Si 2-PARTITIONS est résoluble, on note $A$ la partie contenant $z$, et $B$ l'autre. On pose enfin $x = \sum_{A} -z $ et $\sum_{A} = \sum_{B}$ donne:

$x + \sum_S - 2G = \sum_S - x$ puis $x = G$:

$A \setminus \{z\}$ est solution.

Exemple: 2-partition

Deuxième sens:

Si SUBSET-SUM est résoluble, on note $X$ la partie de $S$ tq $\sum_X = G$. On pose $A = X \cup \{z\}$.

$$ \begin{split} \sum_A &= \sum_X + z &= G + \sum_S - 2G &= \sum_S - G \\ \sum_{(S \cup \{z\}) \setminus (A)} &= \sum_{(S \cup \{z\}) \setminus (X \cup \{z\})} &= \sum_S - \sum_X &= \sum_S - G \end{split} $$

Donc 2-PARTITION a une solution.

Algorithmes d'approximations

Le but est de gagner en complexité en se permettant une marge d'erreur sur la valeur optimale.

Il s'agit donc aussi de trouver une borne pour cette marge.

Pour cela on peut trouver une minoration de l'optimum et exprimer notre valeur approchée en fonction de cette minoration.

Algorithmes randomisés

Au lieu d'exprimer la complexité en terme de pire cas, on le fait en terme de cas moyen.

Pour cela on détermine la probabilité des entrées, leur complexité, et l'espérance associée.

Preuve du tri rapide

On remarque que la complexité est en terme de nombre de comparaisons entre éléments. On note:

  • $(z_i)_{1 \leq i \leq n}$ les éléments triés
  • $Z_{ij}= \{z_i, z_{i+1}, ..., z_j\}$.

Soit $X_{ij}$ la variable aléatoire valant 1 si $z_i$ est comparé à $z_j$ lors de l'éxécution. La complexité d'une exécution vaut $X = \sum_i \sum_{j > i} X_{ij}$.

Preuve du tri rapide

Comme $z_i$ n'est comparé à $z_j$ que si le premier élément de $Z_{ij}$ choisi comme pivot est $z_i$ ou $z_j$. En effet sinon ils se retrouvent dans des sous-tableaux différents.

$$ \begin{split} E[X] &= \sum_i \sum_j P(X_{ij}=1) = \sum_i \sum_{j>i} 2/(j-i+1) \\ E[X] &= \sum_i \sum_{k<n-i} 2/(k+1) \\ E[X] &= \sum_i O(\text{log}(n)) = O(n\text{log}(n)) \end{split} $$