Chapitre 9 : Paradigmes de conception d'algorithmes

Dans les chapitres précédents, nous avons exploré une grande variété d'algorithmes pour résoudre des problèmes spécifiques, tels que le tri, la recherche, la traversée de graphes et le traitement de chaînes de caractères. Bien que ces algorithmes soient diversifiés dans leurs applications et leurs implémentations, beaucoup d'entre eux partagent des principes de conception ou des paradigmes sous-jacents communs.

Dans ce chapitre, nous examinerons trois paradigmes fondamentaux de conception d'algorithmes : la méthode diviser-pour-régner, les algorithmes gloutons et la programmation dynamique. Ces paradigmes fournissent des approches générales de résolution de problèmes qui peuvent être adaptées pour résoudre une vaste gamme de problèmes. En comprenant ces paradigmes, nous pouvons acquérir une meilleure compréhension de la structure des algorithmes et développer de nouveaux algorithmes pour les problèmes que nous rencontrons.

Diviser-pour-régner

Le paradigme diviser-pour-régner est une approche puissante et largement utilisée pour concevoir des algorithmes efficaces. L'idée de base est de décomposer un problème en sous-problèmes plus petits, de résoudre ces sous-problèmes de manière récursive, puis de combiner leurs solutions pour résoudre le problème d'origine.

Un algorithme typique basé sur la méthode diviser-pour-régner se compose de trois étapes :

Diviser : Si le problème est suffisamment petit pour être résolu directement, le résoudre. Sinon, diviser le problème en sous-problèmes plus petits.
Conquérir : Résoudre de manière récursive chaque sous-problème.
Combiner : Combiner les solutions des sous-problèmes pour obtenir la solution du problème d'origine.

L'efficacité des algorithmes diviser-pour-régner provient de leur capacité à réduire la taille d'un problème d'un facteur constant à chaque étape récursive. Cela conduit souvent à des algorithmes avec des temps d'exécution logarithmiques ou polylogarithmiques.

Tri fusion : un algorithme diviser-pour-régner classique

L'un des exemples les plus connus d'un algorithme diviser-pour-régner est le tri fusion, que nous avons étudié en détail dans le Chapitre 2. Rappelons que le tri fusion trie un tableau en le divisant en deux moitiés, en triant chaque moitié de manière récursive, puis en fusionnant les moitiés triées.

Voici une description générale de laVoici la traduction française du fichier Markdown :

Algorithme de tri par fusion (Mergesort) :

fonction mergesort(tableau):
    si la longueur du tableau <= 1:
        retourner le tableau
    sinon:
        milieu = longueur du tableau / 2
        gauche = mergesort(tableau[0:milieu])
        droite = mergesort(tableau[milieu:])
        retourner fusion(gauche, droite)

La fonction fusion combine deux tableaux triés en un seul tableau trié :

fonction fusion(gauche, droite):
    résultat = []
    tant que gauche n'est pas vide et droite n'est pas vide:
        si le premier élément de gauche <= le premier élément de droite:
            ajouter le premier élément de gauche à résultat
            supprimer le premier élément de gauche
        sinon:
            ajouter le premier élément de droite à résultat
            supprimer le premier élément de droite
    ajouter les éléments restants de gauche à résultat
    ajouter les éléments restants de droite à résultat
    retourner résultat

La stratégie de division et de conquête permet au tri par fusion d'atteindre un temps d'exécution dans le pire des cas de O(n log n), en faisant l'un des algorithmes de tri les plus efficaces à usage général.

Le théorème du maître

Le temps d'exécution de nombreux algorithmes de division et de conquête peut être analysé à l'aide du théorème du maître, qui fournit une formule générale pour les récurrences de la forme :

T(n) = aT(n/b) + f(n)

Ici, a est le nombre d'appels récursifs, n/b est la taille de chaque sous-problème, et f(n) est le coût de la division du problème et de la combinaison des résultats.

Le théorème du maître indique que la solution à cette récurrence est :

Si f(n) = O(n^(log_b(a) - ε)) pour une constante ε > 0, alors T(n) = Θ(n^log_b(a)).
Si f(n) = Θ(n^log_b(a)), alors T(n) = Θ(n^log_b(a) * log n).
Si f(n) = Ω(n^(log_b(a) + ε)) pour une constante ε > 0, et si af(n/b) ≤ cf(n) pour une constante c < 1 et tous les n suffisamment grands, alors T(n) = Θ(f(n)).

Pour le tri par fusion, nous avons a = 2 (deux appels récursifs), b = 2 (chaque sous-problème est de moitié plus petit), et f(n) = Θ(n) (l'étape de fusion prend un temps linéaire). Comme log_2(2) = 1, nous sommes dans le cas 2 du théorème du maître, et le temps d'exécution est Θ(n log n).

Autres algorithmes de division et de conquête

De nombreux autres alVoici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

Algorithmes de division et de conquête

Les algorithmes peuvent être conçus en utilisant le paradigme de division et de conquête. Voici quelques exemples notables :

Quicksort : Comme le tri fusion, le quicksort est un algorithme de tri par division et conquête. Il partitionne le tableau autour d'un élément pivot, trie de manière récursive les sous-tableaux à gauche et à droite du pivot, puis concatène les résultats.
Recherche binaire : L'algorithme de recherche binaire pour trouver un élément dans un tableau trié peut être considéré comme un algorithme de division et de conquête. Il compare la valeur cible à l'élément du milieu du tableau et recherche de manière récursive la moitié de gauche ou de droite, selon la comparaison.
Multiplication de Karatsuba : C'est un algorithme de division et de conquête pour multiplier deux nombres à n chiffres en O(n^log_2(3)) ≈ O(n^1.585) temps, ce qui est plus rapide que l'algorithme traditionnel en O(n^2).
Multiplication de matrices de Strassen : L'algorithme de Strassen multiplie deux matrices n × n en O(n^log_2(7)) ≈ O(n^2.807) temps, améliorant l'algorithme naïf en O(n^3).

Ces exemples démontrent la polyvalence et la puissance du paradigme de division et de conquête pour concevoir des algorithmes efficaces.

Algorithmes gloutons

Les algorithmes gloutons sont une classe d'algorithmes qui font le choix localement optimal à chaque étape dans l'espoir de trouver une solution globalement optimale. Ils sont souvent utilisés pour des problèmes d'optimisation où une solution est construite de manière incrémentale en faisant une série de choix, chacun semblant le meilleur sur le moment.

Les principales caractéristiques des algorithmes gloutons sont :

Ils font un choix localement optimal à chaque étape, sans se soucier des conséquences futures.
Ils supposent qu'un choix localement optimal conduira à une solution globalement optimale.
Ils ne reconsidèrent jamais les choix précédents.

Les algorithmes gloutons sont souvent simples à comprendre et à mettre en œuvre, et peuvent être très efficaces. Cependant, ils ne produisent pas toujours la solution optimale, car les choix localement optimaux peuvent ne pas conduire à la solution globalement optimale.

Codage de Huffman : Un algorithme glouton pour la compression de données

HuffmanVoici la traduction française du fichier Markdown :

Le codage de Huffman, que nous avons rencontré dans le Chapitre 5, est un algorithme gourmand pour construire un code préfixe optimal pour la compression de données. L'algorithme construit un arbre binaire de bas en haut, en attribuant des séquences de bits plus courtes aux caractères les plus fréquents.

Voici une description générale de l'algorithme de codage de Huffman :

Créer un nœud feuille pour chaque caractère et l'ajouter à une file d'attente à priorité.
Tant qu'il y a plus d'un nœud dans la file d'attente :
- Retirer les deux nœuds de plus basse fréquence de la file d'attente.
- Créer un nouveau nœud interne avec ces deux nœuds comme enfants et avec une fréquence égale à la somme des fréquences des deux nœuds.
- Ajouter le nouveau nœud à la file d'attente à priorité.
Le nœud restant est la racine et l'arbre est complet.

Le choix gourmand est de toujours fusionner les deux nœuds de plus basse fréquence. Ce choix localement optimal conduit à un code préfixe globalement optimal.

Voici un exemple de codage de Huffman en action :

Supposons que nous ayons les fréquences de caractères suivantes :

d : 1
e : 1

Voici l'arbre de Huffman pour cet exemple :

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

Les codes de Huffman résultants sont :

A : 00
B : 01
C : 10
D : 110
E : 111

Donc la chaîne originale "AAAABBBCCCDDDEEE" serait encodée comme :

00000000010101101010110110110111111111

Le codage de Huffman permet la compression en attribuant des codes plus courts aux symboles les plus fréquents. Les codes sont préfixes, ce qui signifie qu'aucun code n'est un préfixe d'un autre, permettant un décodage sans ambiguïté.

Compression LZW

La compression Lempel-Ziv-Welch (LZW) est un algorithme de compression basé sur un dictionnaire qui construit un dictionnaire (ou codebook) de chaînes de caractères tout en comprimant l'entrée. LZW est largement utilisé dans les utilitaires de compression de fichiers et a été utilisé dans le format d'image GIF.

L'idée clé derrière LZW est de remplacer les chaînes de caractères par des codes uniques. Il lit la chaîne d'entrée caractère par caractère et encode la chaîne dans une représentation compacte en remplaçant chaque chaîne de longueur fixe par un code.Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

Compression LZW avec un code à longueur variable

Le code LZW (Lempel-Ziv-Welch) est un algorithme de compression de données sans perte qui utilise un code à longueur variable. Plus la chaîne est longue, plus l'espace est économisé en l'encodant sous la forme d'un seul nombre.

Voici une description étape par étape du fonctionnement de la compression LZW :

Initialiser le dictionnaire pour qu'il contienne toutes les chaînes de caractères à un seul caractère.
Trouver la chaîne la plus longue W dans le dictionnaire qui correspond à l'entrée actuelle.
Émettre l'index du dictionnaire pour W dans la sortie et supprimer W de l'entrée.
Ajouter W suivi du prochain symbole dans l'entrée au dictionnaire.
Aller à l'étape 2.

Considérons un exemple. Supposons que nous voulions compresser la chaîne "ABABABABA" en utilisant LZW.

Initialiser le dictionnaire pour qu'il contienne "A" et "B".
La correspondance la plus longue est "A". Émettre son index (0) et le supprimer de l'entrée. Le dictionnaire contient maintenant "A", "B" et "AB".
La correspondance la plus longue est "B". Émettre son index (1) et le supprimer de l'entrée. Le dictionnaire contient maintenant "A", "B", "AB" et "BA".
La correspondance la plus longue est "AB". Émettre son index (2) et le supprimer de l'entrée. Le dictionnaire contient maintenant "A", "B", "AB", "BA" et "ABA".
La correspondance la plus longue est "ABA". Émettre son index (4) et le supprimer de l'entrée. Le dictionnaire contient maintenant "A", "B", "AB", "BA", "ABA" et "ABAB".
La correspondance la plus longue est "BA". Émettre son index (3). L'entrée est maintenant vide.

La représentation compressée de "ABABABABA" est donc la séquence d'indices [1], qui nécessite moins de bits pour être représentée que la représentation ASCII d'origine.

La décompression fonctionne de manière similaire, mais dans l'ordre inverse :

Initialiser le dictionnaire pour qu'il contienne toutes les chaînes de caractères à un seul caractère.
Lire un code X de l'entrée.
Sortir la chaîne pour X du dictionnaire.
Si le code précédent existe, ajouter la chaîne précédente concaténée avec le premier caractère de la chaîne pour X au dictionnaire.
Aller à l'étape 2.

La compression LZW est simple et rapide, ce qui en fait un bon choix pour de nombreuses applications. Cependant, elle a quelques limites. La taille du dictionnaire peut devenir assez importante, consommant une quantité de mémoire significative. De plus,Voici la traduction française du fichier Markdown, avec les commentaires traduits mais pas le code :

Le dictionnaire est réinitialisé après chaque bloc d'entrée, ce qui peut réduire le taux de compression pour les petits fichiers.

Malgré ces limitations, LZW reste un algorithme de compression populaire et efficace, en particulier pour les applications où la vitesse est plus importante que d'atteindre les plus hauts ratios de compression possibles.

Conclusion

Dans ce chapitre, nous avons exploré plusieurs algorithmes importants de traitement des chaînes de caractères, notamment le tri des chaînes, les tries, la recherche de sous-chaînes, les expressions régulières et la compression de données. Ces algorithmes forment la base de nombreuses applications du monde réel et sont des outils essentiels pour tout programmeur travaillant avec des données textuelles.

Nous avons commencé par discuter du tri des chaînes, qui sont des algorithmes de tri optimisés qui tirent parti des propriétés spéciales des chaînes de caractères. Le comptage par clé, le tri radix LSD et le tri radix MSD fournissent des méthodes efficaces pour trier les chaînes en fonction de leurs caractères individuels.

Ensuite, nous avons examiné les tries, une structure de données en arbre pour stocker et récupérer des chaînes de caractères. Les tries permettent un appariement de préfixes rapide et sont couramment utilisés dans des applications telles que l'auto-complétion et les tables de routage IP.

Les algorithmes de recherche de sous-chaînes, tels que les algorithmes de Knuth-Morris-Pratt et de Boyer-Moore, nous permettent de rechercher efficacement des motifs dans des chaînes plus longues. Ces algorithmes ont de nombreuses applications dans l'édition de texte, la biologie computationnelle et la recherche d'informations.

Les expressions régulières offrent un moyen puissant et flexible de décrire des motifs de chaînes de caractères. Nous avons discuté de la syntaxe de base des expressions régulières et de la manière dont elles peuvent être utilisées pour la correspondance de motifs et la manipulation de chaînes dans divers langages de programmation et outils.

Enfin, nous avons exploré les algorithmes de compression de données, qui réduisent la taille des données en exploitant la redondance et les motifs dans les données d'entrée. Nous avons abordé le codage par plages, le codage de Huffman et la compression de Lempel-Ziv-Welch, chacun ayant ses propres forces et applications.

Comprendre ces algorithmes et structures de données de traitement des chaînes de caractères est essentiel pour quiconque travaille avec des données textuelles.Voici la traduction française du fichier Markdown, avec les commentaires traduits pour le code :

Manipulation de chaînes de caractères en Python

Alors que la quantité de données non structurées continue d'augmenter, la capacité à manipuler, rechercher et compresser efficacement les chaînes de caractères deviendra de plus en plus précieuse. En maîtrisant les techniques abordées dans ce chapitre, vous serez bien équipé pour relever une grande variété de défis liés au traitement des chaînes de caractères dans vos propres projets et applications.

Opérations de base sur les chaînes

Les chaînes de caractères sont des séquences immuables de caractères Unicode. Elles offrent de nombreuses méthodes intégrées pour effectuer des opérations courantes.

# Créer une chaîne
my_string = "Hello, World!"
 
# Accéder aux caractères individuels
print(my_string[0])  # Affiche "H"
 
# Concaténer des chaînes
greeting = "Hello"
name = "Alice"
message = greeting + ", " + name + "!"
print(message)  # Affiche "Hello, Alice!"
 
# Répéter une chaîne
repeated_string = "Python " * 3
print(repeated_string)  # Affiche "Python Python Python "
 
# Vérifier la longueur d'une chaîne
print(len(my_string))  # Affiche 13

Manipulation de chaînes

Les chaînes de caractères offrent de nombreuses méthodes pour manipuler leur contenu.

# Convertir en majuscules/minuscules
print(my_string.upper())   # Affiche "HELLO, WORLD!"
print(my_string.lower())   # Affiche "hello, world!"
 
# Remplacer du texte
new_string = my_string.replace("Hello", "Goodbye")
print(new_string)  # Affiche "Goodbye, World!"
 
# Découper une chaîne
parts = my_string.split(",")
print(parts)  # Affiche ['Hello', ' World!']
 
# Supprimer les espaces en début/fin
text = "   Texte avec des espaces   "
cleaned_text = text.strip()
print(cleaned_text)  # Affiche "Texte avec des espaces"

Recherche dans les chaînes

Les chaînes de caractères offrent également des méthodes pour rechercher du texte.

# Vérifier si une sous-chaîne est présente
if "World" in my_string:
    print("La chaîne contient 'World'")
 
# Trouver l'index d'une sous-chaîne
index = my_string.find("World")
print(index)  # Affiche 7
 
# Compter les occurrences d'une sous-chaîne
count = my_string.count("l")
print(count)  # Affiche 3

Formatage avancé

Python offre des fonctionnalités avancées de formatage de chaînes.

# Formatage avec des f-strings (Python 3.6+)
name = "Alice"
age = 25
print(f"Bonjour, je m'appelle {name} et j'ai {age} ans.")
 
# Formatage avec la méthode .format()
template = "Bonjour, je m'appelle {} et j'ai {} ans."
message = template.format(name, age)
print(message)

En maîtrisant ces techniques de manipulation de chaînes, vous serez en mesure de relever une grande variété de défis liés au traitement du texte dans vos projets Python.

Chapter 8 Algorithm Analysis Techniques Chapter 10 Intractable Problems and Approximation Algorithms