Algorithmique 2

1. Complexité

La complexité d’un algorithme mesure son efficacité en fonction de la taille $n$ de son entrée, soit en nombre d’étapes élémentaires (complexité en temps), soit en mémoire utilisée (complexité en espace).

a) Complexité dans le pire des cas

• On s’intéresse souvent à la complexité dans le pire des cas, c’est-à-dire le nombre maximal d’opérations pour une entrée de taille $n$.
• Exemple : la fonction qui cherche un 1 dans un tableau a une complexité linéaire $O(n)$ dans le pire cas (aucun 1 ou 1 en dernière position).

La complexité dans le pire des cas ignore les cas favorables pour garantir une borne supérieure.

b) Compter approximativement et asymptotiquement

• On utilise la notation $O(f(n))$ pour exprimer une borne supérieure asymptotique, en négligeant les constantes et termes de moindre importance.
• Formule :
  $\exists n_0, K, \forall n \geq n_0, \quad g(n) \leq K f(n)$
• Si $\lim_{n \to \infty} \frac{g(n)}{f(n)} < \infty$, alors $g(n) = O(f(n))$.

Notation de Landau : comparaisons asymptotiques

c) Quelques ordres de grandeur (approximation du temps en secondes pour $10^6$ opérations/s)

2. Exemples et pièges

a) Tri insertion

• Algorithme simple : on cherche le plus petit élément et on le place en tête, puis on recommence.
• Complexité : $O(n^2)$.

b) Complexité cachée

• Certaines opérations paraissent simples mais sont coûteuses selon la structure de données.
• Exemple en Python :
  • c in S est $O(\text{len}(S))$ si $S$ est une liste.
  • c in S est $O(1)$ si $S$ est un dictionnaire (table de hachage).
• Toujours prendre en compte la structure de données pour évaluer la complexité.

3. Diviser pour régner

Technique consistant à diviser récursivement un problème en sous-problèmes plus petits, à les résoudre, puis à combiner les résultats.

a) Tri fusion

• Divise un tableau en deux moitiés, trie récursivement chaque moitié, puis fusionne.
• La fusion de deux tableaux triés est linéaire en la taille totale.
• Complexité récursive :
  $T(2n) = 2T(n) + O(n), \quad T(1) = O(1)$
• Résolution :
  $T(n) = O(n \log n)$

b) Recherche dichotomique (à compléter dans la suite du cours)

• Recherche dans un tableau trié en divisant l’espace de recherche par deux à chaque étape.
• Complexité en temps : $O(\log n)$.

1. Recherche dichotomique

• Principe : Diviser le tableau en deux à chaque étape en comparant l'élément central avec l'élément recherché.
• Complexité : $O(\log n)$ car à chaque appel récursif, la taille du problème est divisée par 2.
• Algorithme (récursif) :
  • Si l'intervalle est vide, retourner False.
  • Sinon, comparer l'élément central avec l'élément recherché.
  • Rechercher dans la moitié gauche ou droite selon le résultat.

2. Master Theorem

Pour une récurrence de la forme :

$$T(n) = a \, T\left(\frac{n}{b}\right) + O(n^d)$$

avec $c = \log_b a$, la complexité asymptotique est :

Exemples :

• Tri fusion : $T(n) = 2T(n/2) + O(n)$, $a=2$, $b=2$, $c=1$, $d=1$ → cas 2 → $O(n \log n)$
• Recherche dichotomique : $T(n) = T(n/2) + O(1)$, $a=1$, $b=2$, $c=0$, $d=0$ → cas 2 → $O(\log n)$

3. Multiplication matricielle

• Addition de matrices : $O(n^2)$
• Produit naïf : triple boucle → $O(n^3)$

a) Diviser pour régner (sans astuce)

• Diviser chaque matrice en 4 sous-matrices $(n/2 \times n/2)$
• Produit exprimé en 8 sous-produits
• Récurrence : $$T(n) = 8 T\left(\frac{n}{2}\right) + O(n^2)$$
• Par Master Theorem, $c = \log_2 8 = 3$, cas 3 → $O(n^3)$ (pas d'amélioration)

b) Strassen (avec astuce)

• Réduit à 7 sous-produits au lieu de 8, définis par : $$\begin{aligned} M_1 &= (A_{11} + A_{22})(B_{11} + B_{22}) \\ M_2 &= (A_{21} + A_{22}) B_{11} \\ M_3 &= A_{11} (B_{12} - B_{22}) \\ M_4 &= A_{22} (B_{21} - B_{11}) \\ M_5 &= (A_{11} + A_{12}) B_{22} \\ M_6 &= (A_{21} - A_{11})(B_{11} + B_{12}) \\ M_7 &= (A_{12} - A_{22})(B_{21} + B_{22}) \end{aligned}$$
• Produit final : $$AB = \begin{pmatrix} M_1 + M_4 - M_5 + M_7 & M_3 + M_5 \\ M_2 + M_4 & M_1 - M_2 + M_3 + M_6 \end{pmatrix}$$
• Récurrence : $$T(n) = 7 T\left(\frac{n}{2}\right) + O(n^2)$$
• $c = \log_2 7 \approx 2.81 > 2$, donc $T(n) = O(n^{\log_2 7})$ (meilleur que $O(n^3)$)

4. Enveloppe convexe

• Définition : L'enveloppe convexe d'un ensemble $A \subset \mathbb{R}^2$ est le plus petit ensemble convexe contenant $A$.
• Convexité : Pour tout $x,y \in A$, le segment $[x,y]$ est entièrement dans $A$.

a) Marche de Jarvis

• Principe :
  1. Choisir le point le plus à gauche (et plus haut en cas d'égalité).
  2. Trouver le point qui forme l'angle le plus grand avec le segment précédent.
  3. Répéter jusqu'à revenir au point de départ.
• Complexité : $O(n^2)$ dans le pire cas (quand tous les points sont sur l'enveloppe).

b) QuickHull (Diviser pour régner)

• Principe :
  1. Trouver les points extrêmes $p_g$ (gauche) et $p_d$ (droite).
  2. Diviser les points en deux ensembles selon leur position par rapport au segment $[p_g, p_d]$.
  3. Pour chaque côté, trouver le point $p_l$ le plus éloigné du segment, qui appartient à l'enveloppe.
  4. Former un triangle avec $p_g, p_d, p_l$ et exclure les points à l'intérieur.
  5. Répéter récursivement sur les segments $[p_g, p_l]$ et $[p_l, p_d]$.
• Complexité :
  • Pire cas : $O(n^2)$ (ex. points alignés).
  • Cas moyen (points bien répartis) : $T(n) = 2 T(n/2) + O(n)$ → $O(n \log n)$ par Master Theorem.

5. Fonction auxiliaire QuickHull : séparation des points

• But : Séparer un ensemble de points en deux sous-ensembles à gauche et à droite d'un segment $[p_1, p_2]$ et trouver les points les plus éloignés de ce segment dans chaque sous-ensemble.
• Complexité : $O(n)$
• Méthode :
  • Calculer la différence de pente (produit vectoriel) pour déterminer le côté.
  • Calculer la distance (valeur absolue de la différence de pente) pour trouver le point le plus éloigné.

À retenir : Le paradigme diviser pour régner permet de réduire la complexité de certains algorithmes en divisant le problème en sous-problèmes plus petits, résolus récursivement, puis combinés. Le Master Theorem est l'outil clé pour analyser ces complexités récursives.

1. Définitions fondamentales

• Graphe : un graphe $G = (V, E)$ est un ensemble de sommets $V$ et un ensemble d’arêtes $E \subseteq V \times V$.
• Graphe orienté : les arêtes ont une direction $(i,j) \in E$.
• Graphe non-orienté : pour toute arête $(i,j) \in E$, $(j,i) \in E$ aussi.

2. Représentation des graphes

• Vérifier arête : $O(1)$
• Lister voisins : $O(|V|)$
• Ajouter arête : $O(1)$
• Ajouter sommet : $O(|V|^2)$ (recréation matrice) | | Listes d’adjacence | Pour chaque sommet, liste des voisins directs. |
• Vérifier arête : $O(m)$ (nombre de voisins)
• Lister voisins : $O(m)$
• Ajouter arête : $O(1)$
• Ajouter sommet : $O(1)$ | | Tables de hachage | Pour chaque sommet, table de hachage des voisins. |
• Vérifier arête : $\Theta(1)$ amorti
• Lister voisins : $\Theta(m)$ amorti
• Ajouter arête : $\Theta(1)$ amorti
• Ajouter sommet : $\Theta(1)$ amorti |

3. Opérations principales sur un graphe

• arete(i,j) : existe-t-il une arête de $i$ vers $j$ ?
• voisins(i) : liste des sommets accessibles directement depuis $i$.
• ajouter_arete(i,j), ajouter_sommet(i), enlever_arete(i,j), enlever_sommet(i).

4. Parcours en largeur (BFS)

• Explore les sommets par couches successives à partir d’un sommet $s$.
• Utilise une file (FIFO) pour gérer les sommets à visiter.
• Calcule la distance minimale en nombre d’arêtes entre $s$ et chaque sommet accessible.

Algorithme (simplifié) :

1. Initialiser $dist[v] = \infty$ pour tout $v$, $dist[s] = 0$.
2. Enfiler $s$ dans la file $F$.
3. Tant que $F$ non vide :
   • Dépiler $v$.
   • Pour chaque voisin $w$ de $v$ non visité :
     • $dist[w] \leftarrow dist[v] + 1$.
     • Enfiler $w$.

Complexité : $O(|V| + |E|)$.

Le parcours en largeur explore chaque arête au plus une fois.

5. Parcours en profondeur (DFS)

• Explore un chemin jusqu’à un cul-de-sac avant de revenir en arrière.
• Peut être implémenté récursivement ou itérativement (avec une pile LIFO).

Algorithme récursif (simplifié) :

• Marquer $v$ comme visité.
• Pour chaque voisin $w$ non visité de $v$, appeler récursivement DFS sur $w$.

Temps de parcours :

• On enregistre deux temps pour chaque sommet $v$ :
  • $pre[v]$ : début de visite
  • $post[v]$ : fin de visite
• Les intervalles $[pre[v], post[v]]$ sont soit disjoints, soit inclus l’un dans l’autre (relation d’ancêtre-descendant dans l’arbre de parcours).

Complexité : $O(|V| + |E|)$.

6. Parcours en profondeur itératif

• Même principe que DFS récursif mais avec une pile.
• Empiler les voisins non visités, dépiler pour visiter.

7. Tri topologique

• Applicable aux graphes orientés sans cycle.
• Trouve un ordre linéaire des sommets tel que toutes les arêtes vont de gauche à droite.
• Propriété clé : si $v$ est accessible depuis $u$, alors $post[v] < post[u]$ dans un DFS.
• Tri topologique obtenu en ordonnant les sommets par ordre décroissant de $post$.

8. Résumé des complexités des opérations selon la structure

À retenir : Les parcours en largeur et en profondeur permettent d’explorer efficacement un graphe en $O(|V| + |E|)$, et le tri topologique s’appuie sur les temps de fin de visite du DFS pour ordonner les sommets d’un graphe acyclique orienté.

1. Backtracking

Le backtracking est une méthode algorithmique pour résoudre des problèmes combinatoires en explorant toutes les solutions possibles, tout en abandonnant rapidement les branches qui ne peuvent pas mener à une solution valide.

2. Problème des n-reines

Objectif : Placer $n$ reines sur un échiquier $n \times n$ sans qu'elles ne se menacent (pas sur la même ligne, colonne ou diagonale).

a) Parcours naïf des possibilités

• Tester toutes les positions possibles pour chaque reine.
• Complexité très élevée : $$T(n) \leq n^2 \times (n^2)^n = n^{2n+2}$$
• L'algorithme explore toutes les combinaisons de positions, ce qui est inefficace.

b) Optimisation avec contraintes

• Chaque ligne contient exactement une reine.
• Pour la $i$-ème reine, on ne choisit que parmi les colonnes non occupées.
• Complexité améliorée : $$T(n) \leq n^2 \times n! = o(n^{2n+2})$$
• L'algorithme évite de revisiter plusieurs fois les mêmes positions.

c) Arbre des possibilités

• Le backtracking correspond à un parcours en profondeur de l'arbre des configurations.
• Dès qu'une contrainte est violée, on prune le sous-arbre.
• Exemple : pour $n=4$, on réduit les branches de 24 ($4!$) à 6.

À retenir : Le backtracking explore un arbre de décisions en abandonnant les branches invalides pour réduire la complexité.

3. Application au Sudoku

• Grille $9 \times 9$ à remplir avec chiffres 1 à 9.
• Contraintes :
  • Chaque ligne, colonne, et sous-carré $3 \times 3$ contient chaque chiffre une seule fois.
• Algorithme :
  1. Parcourir les cases vides une à une.
  2. Essayer chaque valeur possible.
  3. Si une contradiction apparaît, revenir en arrière (backtracking).
• Exploration uniquement des branches valides, évitant ainsi l'explosion combinatoire.

4. Programmation Dynamique (rappel lié)

• Permet d'éviter les calculs redondants en mémorisant les résultats intermédiaires.
• Exemple classique : suite de Fibonacci.
• Calcul naïf récursif : temps exponentiel.
• Calcul itératif avec mémorisation : temps linéaire $\Theta(n)$.

5. Exemple de formule récursive : Plus longue sous-suite commune (PLSC)

• Soient deux mots $w_1 = m_1 a$ et $w_2 = m_2 b$.
• Définition récursive de la longueur de la plus longue sous-suite commune $PLSC(w_1, w_2)$ :

$$PLSC(m_1 a, m_2 b) = \max \begin{cases} 1 + PLSC(m_1, m_2) & \text{si } a = b \\ PLSC(m_1 a, m_2) \\ PLSC(m_1, m_2 b) \end{cases}$$

• Conditions initiales : $PLSC(w, \varepsilon) = PLSC(\varepsilon, w) = 0$.

• Calcul via tableau dynamique de taille $(m+1) \times (n+1)$ où $m,n$ sont les longueurs des mots.

À retenir : Le backtracking explore toutes les solutions possibles en abandonnant rapidement les branches invalides, ce qui permet de résoudre efficacement des problèmes combinatoires complexes comme les n-reines ou le Sudoku.

1. Plus Longue Sous-Suite Commune (PLSC)

• Définition : La PLSC entre deux mots $m_1$ et $m_2$ est la plus longue séquence de caractères apparaissant dans les deux mots dans le même ordre, mais pas nécessairement de façon contiguë.
• Tableau de programmation dynamique : $t[i][j]$ représente la longueur de la PLSC entre les préfixes $m_1[0..i-1]$ et $m_2[0..j-1]$.
• Conditions initiales : $t[0][j] = 0$ et $t[i][0] = 0$ pour tout $i,j$.
• Relation de récurrence : $$t[i][j] = \begin{cases} 1 + t[i-1][j-1] & \text{si } m_1[i-1] = m_2[j-1] \\ \max(t[i-1][j], t[i][j-1]) & \text{sinon} \end{cases}$$
• Complexité : $O(n_1 \times n_2)$ où $n_1 = |m_1|$, $n_2 = |m_2|$.
• Reconstruction d’une solution : On remonte dans le tableau depuis $t[n_1][n_2]$ en suivant les règles :
  • Diagonale si $m_1[i-1] = m_2[j-1]$,
  • Sinon déplacement vers la case avec la même valeur parmi $t[i-1][j]$ ou $t[i][j-1]$.
• Exemple : Pour $m_1 = \text{rythme}$ et $m_2 = \text{algorithme}$, la PLSC est "rthme".

2. Floyd-Warshall : Tous les Plus Courts Chemins

• Graphe pondéré : $G = (V, E, \delta)$ avec $\delta : E \to \mathbb{R}^+$ donnant le poids des arêtes.
• Objectif : Trouver la distance minimale $d(u,v)$ entre tous les couples $(u,v)$ de sommets.
• Relation de récurrence (par sommets ajoutés) :
  • Soit $d_k(u_i,u_j)$ la distance minimale entre $u_i$ et $u_j$ en ne passant que par les sommets $\{u_1, ..., u_k\}$.
  • Alors :
  $$d_{k+1}(u_i,u_j) = \min\big(d_k(u_i,u_j), d_k(u_i,u_{k+1}) + d_k(u_{k+1},u_j)\big)$$
• Algorithme :
  • Initialiser $d_0(u,v) = \delta(u,v)$ si $(u,v) \in E$, sinon $\infty$.
  • Itérer $k$ de 1 à $n$ en mettant à jour $d_k$ selon la relation ci-dessus.
• Complexité : $O(n^3)$.
• Autre formulation (plus classique) : $$d[i,j] = \min(d[i,j], d[i,k] + d[k,j]) \quad \forall i,j,k$$

3. Mémoïsation

• Principe : Stocker les résultats des appels récursifs pour éviter les recalculs.
• Exemple : Calcul de la suite de Fibonacci avec mémoïsation.
• Gain : Réduit le nombre d’appels récursifs de $O(2^n)$ à $O(n)$.
• Implémentation : Utilisation d’un dictionnaire ou tableau pour mémoriser les résultats déjà calculés.

4. Dominos sur une ligne $3 \times n$

• Problème : Compter le nombre de façons de remplir un rectangle $3 \times n$ avec des dominos $1 \times 2$ et $2 \times 1$.

• Approche : Utiliser plusieurs fonctions récursives dépendantes représentant différentes configurations partielles :

  Fonction	Description
  $R(n)$	Nombre de manières de remplir un rectangle $3 \times n$ complet
  $L_1(n)$	Nombre de manières de remplir $3 \times (n-1)$ avec une case supplémentaire en bas à droite
  $L_2(n)$	Nombre de manières de remplir $3 \times (n-1)$ avec deux cases empilées verticalement en bas à droite
  $\Gamma_1(n)$	Nombre de manières de remplir $3 \times (n-1)$ avec une case supplémentaire en haut à droite
  $\Gamma_2(n)$	Nombre de manières de remplir $3 \times (n-1)$ avec deux cases empilées verticalement en haut à droite

• Relations de récurrence (avec symétries $\Gamma_2 = L_2$, $\Gamma_1 = L_1$) :

  $$\begin{cases} R(n) = R(n-2) + 2 \times \Gamma_2(n-1) \\ \Gamma_2(n) = R(n-1) + \Gamma_2(n-2) \end{cases}$$

• Conditions initiales :

  $$R(0) = 0, \quad R(1) = 0, \quad \Gamma_2(1) = 1$$

• Calcul : On remplit les tableaux $R(i)$ et $\Gamma_2(i)$ pour $i \leq n$.

À retenir : La programmation dynamique repose sur la décomposition d’un problème en sous-problèmes qui se recoupent, en stockant leurs solutions pour éviter les recalculs, ce qui permet de résoudre efficacement des problèmes complexes comme la PLSC, les plus courts chemins (Floyd-Warshall) ou le comptage de configurations combinatoires (dominos).

1. Encodage et équivalence d'encodages

• Encodage : fonction $e : O \to \{0,1\}^*$ qui transforme un objet $o \in O$ en mot binaire.
• Encodages équivalents : deux encodages $e_1, e_2$ sont équivalents s'il existe des fonctions $t_{1 \to 2}, t_{2 \to 1}$ calculables en temps linéaire telles que : $$t_{2 \to 1}(e_2(o)) = e_1(o) \quad \text{et} \quad t_{1 \to 2}(e_1(o)) = e_2(o) \quad \forall o \in O$$
• Exemple : différentes représentations d'une formule booléenne (chaîne de caractères, liste de tables de hachage, liste de listes) sont équivalentes.
• Encodages non équivalents : ex. encodage binaire vs unaire des entiers, passage de binaire à unaire est exponentiel.

2. Problème (langage)

• Un problème $P$ est un sous-ensemble $P \subseteq \{0,1\}^*$.
• Résoudre $P$ = trouver un algorithme $A$ tel que pour tout mot $m$ : $$A(m) = \begin{cases} \text{Oui} & \text{si } m \in P \\ \text{Non} & \text{sinon} \end{cases}$$
• Exemples classiques :
  • Sat : formule booléenne sous forme normale conjonctive est-elle satisfiable ?
  • SubsetSum : existe-t-il un sous-ensemble de $S \subseteq \mathbb{N}$ dont la somme vaut $K$ ?
  • Tiling : peut-on tuiler un carré $N \times N$ avec un ensemble de tuiles respectant les couleurs des bords ?
  • Plsc : existe-t-il une sous-séquence commune de longueur au moins $K$ entre deux mots ?

3. Réduction polynomiale

• Soient deux problèmes $P_1, P_2$.
• $P_1$ se réduit à $P_2$ (notation $P_1 \leq_P P_2$) s'il existe une fonction $f$ calculable en temps polynomial telle que : $$m \in P_1 \iff f(m) \in P_2$$
• Conséquences :
  • Si $P_2$ est résoluble en temps polynomial, alors $P_1$ aussi.
  • Si $P_1$ n'a pas d'algorithme sous-exponentiel, alors $P_2$ non plus.
• La réduction est transitive : si $P_1 \leq_P P_2$ et $P_2 \leq_P P_3$ alors $P_1 \leq_P P_3$.

4. Exemples de réductions

5. Classe NP

• Un problème $P$ est dans NP s'il existe une fonction de vérification $f : \{0,1\}^* \times \{0,1\}^* \to \{0,1\}$ calculable en temps polynomial telle que : $$x \in P \iff \exists y, f(x,y) = 1$$
• $y$ est un certificat (solution candidate) vérifiable en temps polynomial.
• Exemple : pour Sat, $y$ est une assignation des variables, vérifiable en temps linéaire.

6. NP-complétude

• Un problème $P_1$ est NP-complet si :
  1. $P_1 \in NP$
  2. Tout problème $P_2 \in NP$ se réduit à $P_1$ : $\forall P_2 \in NP, P_2 \leq_P P_1$
• Les problèmes NP-complets sont les plus difficiles de NP : résoudre un NP-complet en temps polynomial implique que tous les problèmes de NP sont résolubles en temps polynomial.

À retenir : La NP-complétude caractérise les problèmes les plus difficiles à résoudre dans NP, mais dont la solution peut être vérifiée rapidement. Les réductions polynomiales permettent de comparer la difficulté relative des problèmes.