Algorithmique : diviser pour régner, programmation dynamique, recherche textuelle : fiche de révision

1Diviser pour régner

La méthode « diviser pour régner » découpe un problème en sous-problèmes de même nature mais plus petits, les résout récursivement, puis combine les résultats. La recherche dichotomique dans un tableau trié en est l'exemple le plus simple : on compare à l'élément central, on élimine une moitié, on recommence ; chaque étape divise la taille par 2, d'où une complexité en O(log n) contre O(n) pour une recherche séquentielle.

Le tri fusion découpe le tableau en deux moitiés, les trie récursivement, puis fusionne les deux moitiés triées en un tableau trié (la fusion parcourt les deux moitiés en parallèle en prenant à chaque fois le plus petit). Complexité O(n log n) dans tous les cas, bien meilleure que les tris par insertion ou sélection en O(n²) de Première.

def tri_fusion(t):

if len(t) <= 1: return t

m = len(t) // 2

return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

La fonction fusion(a, b) construit le résultat avec deux indices i et j : tant que les deux listes ont des éléments, elle ajoute le plus petit de a[i] et b[j] et avance l'indice correspondant, puis recopie le reste. Justification de la complexité : log₂(n) niveaux de découpage, et un travail total en O(n) par niveau pour les fusions.

2Programmation dynamique

Quand les sous-problèmes se recoupent (le même sous-problème est demandé plusieurs fois), la récursivité naïve explose. La programmation dynamique consiste à ne résoudre chaque sous-problème qu'une fois : soit en mémoïsant (dictionnaire des résultats, approche descendante), soit en remplissant un tableau des plus petits sous-problèmes vers le problème complet (approche ascendante).

Exemple canonique : le rendu de monnaie avec le nombre minimal de pièces. Pour un montant m et des pièces p, nb(m) = 1 + min(nb(m − p) pour chaque pièce p ≤ m), avec nb(0) = 0. L'approche gloutonne (prendre toujours la plus grosse pièce) échoue avec certains systèmes de pièces (par exemple {1, 3, 4} pour 6 : glouton donne 4+1+1, optimal 3+3) ; la programmation dynamique garantit l'optimum.

Autres exemples au programme : la suite de Fibonacci, le problème du sac à dos (choisir des objets de poids et valeurs donnés sans dépasser une capacité, avec un tableau à deux dimensions objet × capacité), l'alignement de séquences. La méthode se reconnaît à une relation de récurrence entre solutions optimales de sous-problèmes.

3Recherche textuelle : Boyer-Moore

Chercher un motif de longueur m dans un texte de longueur n. L'algorithme naïf teste chaque position du texte en comparant caractère par caractère : O(n × m) dans le pire cas. L'algorithme de Boyer-Moore (version de Horspool au programme) compare le motif en partant de sa FIN, et, en cas d'échec, décale le motif d'un nombre de positions calculé à l'avance grâce à une table des derniers positions de chaque caractère dans le motif (règle du mauvais caractère).

Principe du décalage : si le caractère du texte aligné sur la fin du motif n'apparaît pas dans le motif, on saute de m positions d'un coup ; s'il y apparaît, on décale pour aligner sa dernière occurrence. Sur un texte réel, beaucoup de positions sont sautées sans être examinées : en pratique l'algorithme est sous-linéaire (plus le motif est long, plus il est rapide), même si le pire cas théorique reste en O(n × m).

Exemple : chercher « NSI » dans « BAC DE NSI ». On aligne le motif aux positions 0-2, on compare la dernière lettre I au caractère C du texte : C n'est pas dans le motif, on décale de 3 ; et ainsi de suite jusqu'à trouver l'occurrence. Au bac, on demande de dérouler quelques étapes en indiquant les comparaisons effectuées et les décalages.

4Exercice type et pièges

Énoncé type : « Écrire une fonction récursive qui renvoie le nombre minimal de pièces pour rendre un montant m avec les pièces [1, 2, 5, 10], puis expliquer pourquoi la mémoïsation la rend efficace. »

def nb_pieces(m, memo={}):

if m == 0: return 0

if m in memo: return memo[m]

meilleur = float('inf')

for p in [1, 2, 5, 10]:

if p <= m: meilleur = min(meilleur, 1 + nb_pieces(m - p, memo))

memo[m] = meilleur

return meilleur

Pièges : appliquer la dichotomie sur un tableau non trié ; oublier le cas de base d'une découpe (tableau de taille 0 ou 1) ; confondre glouton et programmation dynamique ; dans Boyer-Moore, comparer depuis le début du motif ; croire que O(n log n) est toujours meilleur que O(n²) pour de très petits tableaux (les constantes comptent, mais au bac on raisonne asymptotiquement).