Algorithmique avancée

L'étude de la complexité algorithmique est fondamentale en informatique. Elle nous permet de comprendre et de prédire les performances d'un algorithme avant même de l'exécuter sur de grandes quantités de données.

Key Concepts:

• Efficacité des algorithmes : Il s'agit de la capacité d'un algorithme à résoudre un problème donné en utilisant le moins de ressources possible. Ces ressources sont principalement le temps de calcul et l'espace mémoire.
• Temps d'exécution : C'est le temps nécessaire à un algorithme pour s'achever. Il dépend de la taille des données d'entrée, de la puissance de la machine, et de l'algorithme lui-même.
• Utilisation des ressources : Outre le temps, un algorithme consomme de la mémoire vive (RAM) pour stocker les données et les variables. L'optimisation de cette utilisation est cruciale pour les grands ensembles de données.
• Comparaison d'algorithmes : Lorsque plusieurs algorithmes peuvent résoudre le même problème, l'analyse de leur complexité permet de choisir le plus performant. Un algorithme peut être plus rapide qu'un autre pour de petites entrées, mais devenir beaucoup plus lent pour de grandes entrées. Comprendre la complexité nous aide à faire le bon choix.

Étudier la complexité permet de choisir l'algorithme le plus adapté à la taille des données et aux contraintes de performance. Un algorithme "lent" pour des petites données peut être inutilisable pour des données massives.

Pour analyser la complexité, nous avons besoin de quelques définitions :

Key Concepts:

• Opération élémentaire : C'est une opération de base dont le temps d'exécution est considéré comme constant et indépendant de la taille des données. Exemples : une addition, une affectation, une comparaison, l'accès à un élément d'un tableau.
• Taille des données (n) : C'est une mesure de la quantité d'informations que l'algorithme doit traiter. Pour un tri, c'est le nombre d'éléments dans la liste ; pour un graphe, c'est le nombre de sommets ou d'arêtes. La complexité est généralement exprimée en fonction de $n$.
• Cas le meilleur (best case) : C'est la situation où l'algorithme s'exécute le plus rapidement possible. Par exemple, chercher un élément qui est le premier d'une liste.
• Cas le pire (worst case) : C'est la situation où l'algorithme s'exécute le plus lentement possible. Par exemple, chercher un élément qui n'est pas dans la liste (ou le dernier) lors d'une recherche linéaire. C'est souvent ce cas que l'on étudie pour garantir une performance minimale.
• Cas moyen (average case) : C'est la performance moyenne de l'algorithme sur un ensemble représentatif d'entrées. Il est souvent plus difficile à calculer car il nécessite des hypothèses sur la distribution des données d'entrée.

La notation de Landau, ou notation Grand O ($O(n)$), est l'outil principal pour exprimer la complexité. Elle décrit la manière dont le temps d'exécution (ou l'espace mémoire) d'un algorithme croît à mesure que la taille des données d'entrée ($n$) augmente, en ignorant les facteurs constants et les termes d'ordre inférieur.

Key Concepts:

• Définition de O(n) : On dit qu'une fonction $f(n)$ est en $O(g(n))$ s'il existe des constantes positives $c$ et $n_0$ telles que pour tout $n \ge n_0$, $f(n) \le c \cdot g(n)$. En clair, $g(n)$ est une borne supérieure du comportement de $f(n)$ pour les grandes valeurs de $n$.
• Ordres de grandeur courants : Ce sont les fonctions $g(n)$ les plus fréquemment rencontrées :
  • $O(1)$ (constant) : Le temps d'exécution est indépendant de $n$. Ex: Accéder à un élément dans un tableau par son index.
  • $O(\log n)$ (logarithmique) : Le temps d'exécution augmente très lentement avec $n$. Typiquement, les algorithmes qui divisent le problème en deux à chaque étape. Ex: Recherche dichotomique.
  • $O(n)$ (linéaire) : Le temps d'exécution est directement proportionnel à $n$. Ex: Parcourir une liste une seule fois.
  • $O(n \log n)$ (quasi-linéaire) : Plus rapide que $O(n^2)$, typique des algorithmes de tri efficaces. Ex: Tri fusion, Tri rapide (en moyenne).
  • $O(n^2)$ (quadratique) : Le temps d'exécution est proportionnel au carré de $n$. Souvent lié à des boucles imbriquées. Ex: Tri par sélection, Tri à bulles.
  • $O(2^n)$ (exponentiel) : Le temps d'exécution croît extrêmement rapidement. Ces algorithmes sont généralement inutilisables pour des $n$ même modérés. Ex: Problème du voyageur de commerce (brute force).
  • $O(n!)$ (factoriel) : Croissance encore plus rapide que l'exponentielle. Très rares en pratique pour des problèmes d'optimisation.

Calcul de la complexité :

1. Identifier l'opération élémentaire dominante.
2. Compter combien de fois cette opération est exécutée en fonction de $n$.
3. Simplifier en utilisant la notation Grand O (ignorer les constantes et les termes d'ordre inférieur).

Exemple : Somme des éléments d'un tableau

def somme(tableau):
    total = 0 # O(1)
    for x in tableau: # Boucle exécutée n fois
        total = total + x # O(1) à chaque itération
    return total # O(1)

La boucle s'exécute $n$ fois, et à chaque fois, une opération élémentaire est effectuée. La complexité est donc $O(n)$.

Nous distinguons deux types de complexité :

Key Concepts:

• Complexité en temps : Mesure le temps d'exécution de l'algorithme en fonction de la taille des données d'entrée $n$. C'est ce que nous avons vu avec la notation Grand O.
• Complexité en espace : Mesure la quantité de mémoire (espace de stockage) utilisée par l'algorithme en fonction de la taille des données d'entrée $n$. Cela inclut l'espace pour les variables, les structures de données supplémentaires, et la pile d'appels (pour les fonctions récursives).
  • $O(1)$ en espace signifie que l'algorithme utilise une quantité constante de mémoire, indépendamment de $n$.
  • $O(n)$ en espace signifie que la mémoire utilisée est proportionnelle à $n$.

Compromis temps/espace (trade-off) : Souvent, il existe un compromis entre la complexité en temps et la complexité en espace. Il est parfois possible de rendre un algorithme plus rapide en utilisant plus de mémoire, ou inversement. Le choix entre optimisation temps ou espace dépend des contraintes spécifiques du problème.

Exemples concrets :

• Tri fusion : $O(n \log n)$ en temps, mais $O(n)$ en espace car il nécessite un tableau temporaire de taille $n$ pour fusionner les sous-listes.
• Tri rapide : $O(n \log n)$ en temps (en moyenne), et $O(\log n)$ en espace (en moyenne) pour la pile d'appels récursifs, mais peut atteindre $O(n)$ dans le pire des cas.
• Recherche dichotomique : $O(\log n)$ en temps et $O(1)$ en espace (version itérative) ou $O(\log n)$ en espace (version récursive pour la pile d'appels).

Les algorithmes de tri simples sont faciles à comprendre et à implémenter, mais inefficaces pour de grandes quantités de données.

Key Concepts:

• Tri par sélection : Cherche le plus petit élément, le place au début, puis répète pour le reste de la liste.
• Tri par insertion : Construit la liste triée un élément à la fois en insérant chaque nouvel élément à sa place correcte parmi les éléments déjà triés.
• Tri à bulles (Bubble Sort) : Parcourt la liste plusieurs fois, échangeant les éléments adjacents s'ils ne sont pas dans le bon ordre. Les éléments "remontent" comme des bulles.
• Complexité $O(n^2)$ : Tous ces tris simples ont une complexité quadratique dans le cas général. Cela signifie que si vous doublez la taille de la liste, le temps de tri est multiplié par quatre. Ils deviennent impraticables pour des listes de plusieurs milliers d'éléments.

Le Tri fusion est un algorithme de tri efficace basé sur le principe Diviser pour régner.

Key Concepts:

• Principe Diviser pour régner :
  1. Diviser : La liste non triée est divisée en deux sous-listes de taille égale (ou presque).
  2. Régner : Chaque sous-liste est triée récursivement en appliquant le Tri fusion.
  3. Combiner (Fusionner) : Les deux sous-listes triées sont fusionnées pour former une seule liste triée.
• Fusion de listes triées : L'étape clé est la fusion. Elle consiste à prendre deux listes déjà triées et à les combiner en une seule liste triée. On compare les premiers éléments de chaque liste, on prend le plus petit, et on le place dans la liste résultante, puis on répète. Cette étape est $O(n)$ où $n$ est la taille totale des deux listes.
• Complexité $O(n \log n)$ :
  • L'étape de division et de fusion prend $O(n)$ pour chaque niveau de récursion.
  • Il y a $\log n$ niveaux de récursion (car la liste est divisée par deux à chaque fois).
  • Temps total = $O(n \log n)$.
• Stabilité du tri : Le Tri fusion est un tri stable. Cela signifie que si deux éléments ont la même valeur, leur ordre relatif dans la liste triée est le même que dans la liste originale.

Exemple simplifié : Tri de [38, 27, 43, 3, 9, 82, 10]

1. Diviser : [38, 27, 43, 3] et [9, 82, 10]
2. Diviser encore... jusqu'à des listes d'un élément.
3. Fusionner : [27, 38, 43] et [3] -> [3, 27, 38, 43] (exemple intermédiaire)
4. Fusionner les deux moitiés triées pour obtenir la liste finale.

Le Tri rapide est un autre algorithme de tri très efficace, également basé sur le principe Diviser pour régner.

Key Concepts:

• Choix du pivot : On sélectionne un élément de la liste, appelé pivot. Le choix du pivot est crucial pour les performances. Il peut être le premier, le dernier, un élément aléatoire, ou la médiane.
• Partitionnement : La liste est réorganisée de manière à ce que tous les éléments inférieurs au pivot soient placés avant lui, et tous les éléments supérieurs soient placés après lui. Le pivot se retrouve ainsi à sa position finale dans la liste triée. Cette étape est $O(n)$.
• Récursion : Le Tri rapide est ensuite appliqué récursivement aux sous-listes des éléments inférieurs et des éléments supérieurs au pivot.
• Complexité moyenne $O(n \log n)$ : En moyenne, si le pivot divise bien la liste (par exemple, au milieu), la complexité est $O(n \log n)$.
• Complexité pire cas $O(n^2)$ : Si le pivot est toujours choisi de manière à créer une partition très déséquilibrée (par exemple, le plus petit ou le plus grand élément), la complexité dégénère en $O(n^2)$. C'est pourquoi un bon choix de pivot est essentiel.
• In-place : Le Tri rapide est généralement implémenté comme un algorithme de tri "in-place", ce qui signifie qu'il nécessite peu d'espace mémoire supplémentaire ($O(\log n)$ en moyenne pour la pile d'appels récursifs).

Key Concepts:

• Complexité temporelle : Pour les grands jeux de données, les algorithmes en $O(n \log n)$ (Tri fusion, Tri rapide) sont bien supérieurs aux tris en $O(n^2)$.
• Complexité spatiale : Le Tri rapide est souvent préféré pour sa faible consommation mémoire ($O(\log n)$). Le Tri fusion nécessite $O(n)$ d'espace supplémentaire.
• Stabilité : Un tri stable est important lorsque les éléments ont des "valeurs" secondaires qui doivent conserver leur ordre relatif (ex: trier une liste de personnes par nom, puis par prénom).
• Applications pratiques :
  • Le Tri rapide est souvent la méthode de tri par défaut dans les bibliothèques standards (ex: sort() en Python, qsort() en C).
  • Le Tri fusion est préféré lorsque la stabilité est cruciale ou lorsque les données sont trop grandes pour tenir en mémoire (tri externe).
  • Le Tri par insertion peut être efficace pour trier de très petites sous-listes dans le cadre d'algorithmes hybrides (comme le Timsort de Python).

La recherche dichotomique est une méthode très efficace pour trouver un élément dans une liste triée.

Key Concepts:

• Principe : L'algorithme compare l'élément recherché avec l'élément du milieu de la liste.
  • Si l'élément est trouvé, la recherche est terminée.
  • Si l'élément recherché est plus petit, la recherche continue dans la moitié inférieure de la liste.
  • Si l'élément recherché est plus grand, la recherche continue dans la moitié supérieure de la liste. Ce processus est répété jusqu'à ce que l'élément soit trouvé ou que la sous-liste devienne vide.
• Précondition (liste triée) : La recherche dichotomique NE PEUT ÊTRE APPLIQUÉE que sur une liste qui est PRÉALABLEMENT TRIÉE. Si la liste n'est pas triée, les comparaisons n'auront aucun sens.
• Complexité $O(\log n)$ : À chaque étape, la taille de la zone de recherche est divisée par deux. C'est pourquoi sa complexité est logarithmique, ce qui la rend extrêmement rapide pour de grandes listes.
• Implémentation récursive et itérative : Elle peut être implémentée de manière récursive (plus élégante mais consomme de la pile) ou itérative (plus performante en espace).

Exemple : Rechercher 27 dans [3, 9, 10, 27, 38, 43, 82]

1. Milieu : 27 (trouvé !) Exemple 2 : Rechercher 15 dans [3, 9, 10, 27, 38, 43, 82]
2. Milieu : 27. 15 < 27. Chercher dans [3, 9, 10]
3. Milieu : 9. 15 > 9. Chercher dans [10]
4. Milieu : 10. 15 > 10. La sous-liste est vide. 15 non trouvé.

Les tables de hachage (ou dictionnaires, cartes) sont des structures de données qui permettent un accès très rapide aux données.

Key Concepts:

• Fonction de hachage : C'est une fonction qui prend une clé (ex: un nom) en entrée et renvoie un entier, appelé code de hachage ou hachis. Ce hachis est ensuite utilisé comme indice pour stocker ou récupérer la valeur associée dans un tableau (appelé tableau de hachage).
  • Une bonne fonction de hachage distribue les clés uniformément dans le tableau.
• Collisions : Une collision se produit lorsque deux clés différentes sont hachées au même indice par la fonction de hachage. C'est inévitable dans la plupart des cas.
• Résolution des collisions : Différentes techniques existent :
  • Chaînage (Separate Chaining) : À chaque indice du tableau, on stocke une liste chaînée (ou un autre conteneur) de tous les éléments qui ont été hachés à cet indice.
  • Adressage ouvert (Open Addressing) : En cas de collision, on cherche une autre position libre dans le tableau en utilisant une stratégie (par exemple, sondage linéaire, sondage quadratique).
• Complexité moyenne $O(1)$ : En moyenne, si la fonction de hachage est bonne et que les collisions sont bien gérées, l'insertion, la suppression et la recherche d'un élément prennent un temps constant, indépendamment du nombre d'éléments.
• Complexité pire cas $O(n)$ : Si toutes les clés hachent au même indice (très mauvaise fonction de hachage ou cas pathologique), la table de hachage dégénère en liste chaînée, et la complexité redevient $O(n)$.

Les tables de hachage sont la base des dictionnaires et des ensembles dans de nombreux langages de programmation.

Un arbre binaire de recherche (ABR) est une structure de données arborescente qui stocke les éléments de manière à faciliter la recherche, l'insertion et la suppression.

Key Concepts:

• Définition et propriétés :
  • C'est un arbre binaire : chaque nœud a au plus deux enfants (gauche et droit).
  • Propriété de l'ABR : Pour tout nœud, tous les éléments de son sous-arbre gauche sont inférieurs à la valeur du nœud, et tous les éléments de son sous-arbre droit sont supérieurs à la valeur du nœud.
• Opérations (Insertion, suppression, recherche) :
  • Recherche : On commence à la racine. Si la valeur recherchée est égale au nœud courant, on l'a trouvée. Si elle est plus petite, on va à gauche ; si elle est plus grande, on va à droite. On répète jusqu'à trouver ou atteindre une feuille.
  • Insertion : Similaire à la recherche, mais lorsqu'on atteint une feuille, on insère le nouvel élément à cet endroit.
  • Suppression : C'est l'opération la plus complexe. Elle dépend si le nœud à supprimer a 0, 1 ou 2 enfants.
• Complexité moyenne $O(\log n)$ : Si l'arbre est équilibré, la hauteur de l'arbre est proportionnelle à $\log n$. Les opérations (recherche, insertion, suppression) prennent alors $O(\log n)$ en moyenne.
• Déséquilibre et complexité pire cas $O(n)$ : Si les éléments sont insérés dans un ordre déjà trié (croissant ou décroissant), l'ABR peut devenir déséquilibré et ressembler à une liste chaînée. Dans ce cas, la hauteur de l'arbre est $n$, et la complexité des opérations dégénère en $O(n)$.
  • Pour éviter cela, il existe des variantes d'ABR auto-équilibrés (comme les arbres AVL ou les arbres rouge-noir) qui garantissent une hauteur logarithmique.

Un graphe est composé de sommets (ou nœuds) et d'arêtes (ou liens) qui les connectent.

Key Concepts:

• Vocabulaire :
  • Sommet (vertex) : Les entités du graphe (villes, personnes, pages web).
  • Arête (edge) : Les connexions entre les sommets.
  • Chemin : Une séquence d'arêtes reliant des sommets.
  • Cycle : Un chemin qui commence et se termine au même sommet.
• Matrice d'adjacence : Un tableau carré $A$ de taille $N \times N$ (où $N$ est le nombre de sommets). $A[i][j]$ vaut 1 s'il y a une arête entre le sommet $i$ et le sommet $j$, 0 sinon. Pour les graphes pondérés, $A[i][j]$ pourrait stocker le poids de l'arête.
  • Avantages : Vérification rapide de l'existence d'une arête ($O(1)$).
  • Inconvénients : Utilise $O(N^2)$ d'espace, même pour les graphes peu denses (peu d'arêtes).
• Liste d'adjacence : Un tableau de listes. Pour chaque sommet $i$, la liste $L[i]$ contient tous les sommets $j$ adjacents à $i$. Pour les graphes pondérés, on stocke des paires (sommet voisin, poids).
  • Avantages : Utilise $O(N+M)$ d'espace (où $M$ est le nombre d'arêtes), plus efficace pour les graphes creux. Facile à parcourir les voisins d'un sommet.
  • Inconvénients : Vérification de l'existence d'une arête prend $O(\text{degré du sommet})$.
• Graphes orientés et non orientés :
  • Non orienté : Les arêtes n'ont pas de direction (si A est connecté à B, B est connecté à A). La matrice d'adjacence est symétrique.
  • Orienté (digraphe) : Les arêtes ont une direction (si A est connecté à B, B n'est pas nécessairement connecté à A).

Les parcours permettent de visiter tous les sommets d'un graphe de manière systématique.

Key Concepts:

• Parcours en largeur (BFS - Breadth-First Search) :
  • Explore le graphe niveau par niveau.
  • Utilise une file (queue) pour stocker les sommets à visiter.
  • Permet de trouver le chemin le plus court en nombre d'arêtes dans un graphe non pondéré.
  • Applications : Trouver les composantes connexes, déterminer la distance entre deux nœuds.
  • Complexité : $O(N+M)$ (où $N$ est le nombre de sommets, $M$ le nombre d'arêtes).
• Parcours en profondeur (DFS - Depth-First Search) :
  • Explore le graphe aussi loin que possible le long de chaque branche avant de revenir en arrière.
  • Utilise une pile (stack) (implicitement via la récursion ou explicitement).
  • Applications : Détection de cycles, tri topologique, recherche de composantes fortement connexes.
  • Complexité : $O(N+M)$.

L'algorithme de Dijkstra permet de trouver le chemin le plus court d'un sommet source vers tous les autres sommets dans un graphe pondéré avec des poids d'arêtes positifs.

Key Concepts:

• Graphes pondérés : Les arêtes ont des "poids" (coûts, distances, temps).
• Principe de l'algorithme :
  1. Initialise la distance de la source à 0 et à l'infini pour tous les autres sommets.
  2. Maintient un ensemble de sommets "visités" et un ensemble de sommets "non visités".
  3. À chaque étape, sélectionne le sommet non visité avec la plus petite distance connue par rapport à la source.
  4. Marque ce sommet comme visité et met à jour les distances de ses voisins (c'est la "relaxation des arêtes").
  5. Répète jusqu'à ce que tous les sommets soient visités ou que le sommet cible soit atteint.
• Relaxation des arêtes : Pour un sommet u et un voisin v, si distance[u] + poids(u,v) < distance[v], alors on met à jour distance[v] = distance[u] + poids(u,v).
• Complexité et limites :
  • Avec une file de priorité (min-heap), la complexité est $O(M \log N)$ ou $O((N+M) \log N)$.
  • L'algorithme de Dijkstra ne fonctionne PAS si le graphe contient des arêtes de poids négatifs. Dans ce cas, d'autres algorithmes comme Bellman-Ford sont nécessaires.

La programmation dynamique est une méthode puissante pour résoudre des problèmes complexes en les décomposant en sous-problèmes plus simples.

Key Concepts:

• Problèmes à sous-problèmes optimaux : La solution optimale à un problème peut être construite à partir des solutions optimales de ses sous-problèmes.
• Chevauchement des sous-problèmes : Les mêmes sous-problèmes sont résolus à plusieurs reprises.
• Mémorisation (memoization) : C'est la technique clé de la programmation dynamique. Au lieu de recalculer la solution d'un sous-problème chaque fois qu'il est rencontré, on stocke sa solution la première fois qu'il est calculé, puis on la réutilise.
  • Approche "top-down" (récursive avec mémorisation) : On part du problème principal et on résout les sous-problèmes au fur et à mesure, en stockant les résultats.
  • Approche "bottom-up" (itérative avec tabulation) : On résout d'abord les plus petits sous-problèmes, puis on construit les solutions des problèmes plus grands à partir d'eux, en remplissant une table.
• Exemple : suite de Fibonacci
  • Calcul naïf : fib(n) = fib(n-1) + fib(n-2). Très inefficace ($O(2^n)$) car recalculs multiples.
  • Avec mémorisation : On stocke fib(i) une fois calculé.

  memo = {}
  def fib_memo(n):
      if n in memo:
          return memo[n]
      if n <= 1:
          return n
      res = fib_memo(n-1) + fib_memo(n-2)
      memo[n] = res
      return res
  

  La complexité devient $O(n)$ car chaque fib(i) n'est calculé qu'une seule fois.

Un algorithme glouton fait le meilleur choix localement à chaque étape, dans l'espoir que cela conduira à une solution globale optimale.

Key Concepts:

• Choix localement optimal : À chaque étape, l'algorithme prend la décision qui semble la meilleure à ce moment précis, sans considérer les conséquences futures.
• Propriété de choix glouton : Un problème possède cette propriété si une solution globale optimale peut être atteinte en faisant une séquence de choix localement optimaux.
• Exemple : rendu de monnaie (avec des pièces standards)
  • Pour rendre 87 centimes avec des pièces de 1, 2, 5, 10, 20, 50 centimes :
    • Prend 50 (reste 37)
    • Prend 20 (reste 17)
    • Prend 10 (reste 7)
    • Prend 5 (reste 2)
    • Prend 2 (reste 0)
  • C'est un choix glouton qui donne la solution optimale (minimum de pièces) pour le système de monnaie européen standard.
• Limites des algorithmes gloutons : Les algorithmes gloutons ne fonctionnent pas pour tous les problèmes. Le choix localement optimal ne mène pas toujours à une solution globale optimale.
  • Exemple : Rendu de monnaie avec des pièces {1, 3, 4} pour rendre 6.
    • Glouton : 4 + 1 + 1 (3 pièces)
    • Optimal : 3 + 3 (2 pièces)

Key Concepts:

• Quand utiliser quelle approche :
  • Glouton : Si le problème a la propriété de choix glouton et que l'on peut prouver qu'un choix localement optimal conduit toujours à une solution globale optimale. Plus simple et souvent plus rapide à implémenter.
  • Programmation dynamique : Si le problème a des sous-problèmes optimaux et que ces sous-problèmes se chevauchent. Nécessite généralement plus de mémoire pour la mémorisation/tabulation.
• Exemples de problèmes :
  • Problème du sac à dos :
    • Version 0/1 (chaque objet est pris ou non) : Programmation dynamique. Le choix glouton (prendre les objets les plus "rentables") ne donne pas toujours la solution optimale.
    • Version continue (on peut prendre une fraction d'objet) : Glouton.
  • Plus court chemin : L'algorithme de Dijkstra est un algorithme glouton.
  • Plus longue sous-séquence commune : Programmation dynamique.
• Trade-offs : La programmation dynamique garantit l'optimalité pour une classe de problèmes plus large, mais au prix d'une complexité souvent plus élevée que les algorithmes gloutons quand ces derniers s'appliquent.
• Optimisation : Les deux techniques visent à trouver des solutions optimales, mais avec des stratégies différentes pour gérer les sous-problèmes.