Algorithmes avancés

Diviser pour régner, programmation dynamique, tri fusion, recherche textuelle.

Diviser pour régner

Principe: Méthode algorithmique en trois étapes : DIVISER (décomposer le problème en sous-problèmes de même nature mais plus petits), RÉGNER (résoudre chaque sous-problème récursivement — cas de base si assez petit), COMBINER (assembler les solutions partielles). Conduit souvent à des complexités en O(n log n).
Tri fusion (Merge Sort): Divise le tableau en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux moitiés triées en O(n). Complexité totale : O(n log n) garanti dans tous les cas (meilleur, moyen, pire). Algorithme stable. Inconvénient : nécessite O(n) mémoire supplémentaire pour la fusion.
Tri rapide (Quick Sort): Choisit un pivot, partitionne le tableau (gauche < pivot, droite > pivot), trie récursivement. Complexité moyenne O(n log n), pire cas O(n²) si le pivot est mal choisi (tableau déjà trié + pivot = premier élément). Solution : pivot aléatoire ou médiane. En pratique le plus rapide grâce à la localité cache.

Principe et mémoïsation: Technique pour les problèmes à sous-problèmes chevauchants : on mémorise les résultats des sous-problèmes déjà calculés pour éviter de les recalculer. Mémoïsation (top-down) : récursif + dictionnaire cache. Tabulation (bottom-up) : remplissage itératif d'un tableau. Réduit la complexité de Fibonacci de O(2^n) à O(n).
Problème du sac à dos: Problème canonique de programmation dynamique : maximiser la valeur d'objets dans un sac de capacité limitée, chaque objet ayant un poids et une valeur. Version 0/1 (chaque objet une seule fois) : O(n×W) avec un tableau 2D. Illustre la construction d'une solution optimale globale à partir de sous-problèmes optimaux.

Notation O(): Mesure le comportement asymptotique d'un algorithme quand la taille n de l'entrée tend vers l'infini. O(1) : constant. O(log n) : logarithmique (dichotomie). O(n) : linéaire. O(n log n) : quasi-linéaire (meilleurs tris). O(n²) : quadratique (tri à bulles, sélection). O(2^n) : exponentiel (force brute, NP-difficile). On ignore les constantes.

Flashcards, mode examen et suivi de progression — gratuit pour commencer.