Chapitre 8 - Partie 1 : Repère historique - Quelques algorithmes qui ont marqué l'histoire

Les algorithmes de ce chapitre ont été inventés à des époques différentes, souvent pour répondre à des besoins précis : calcul scientifique, traitement de texte, biologie.

---

Chronologie

Date	Événement	Personnalité
1945	Tri fusion : l'un des premiers algorithmes de tri programmés.	John von Neumann
1950s	Programmation dynamique : méthode d'optimisation en décomposant un problème en sous-problèmes.	Richard Bellman
1960	Algorithme de Karatsuba : multiplication d'entiers par diviser pour régner, plus rapide que la méthode classique.	Anatoly Karatsuba
1965	Distance d'édition : mesure de la différence entre deux mots.	Vladimir Levenshtein
1970	Alignement de séquences biologiques par programmation dynamique.	Saul Needleman et Christian Wunsch
1977	Algorithme de Boyer-Moore : recherche d'un motif dans un texte en sautant des caractères.	Robert Boyer et J Strother Moore

---

À retenir

• Un même outil (diviser pour régner, programmation dynamique) sert dans des domaines très variés.
• Plusieurs de ces algorithmes sont aujourd'hui utilisés en bio-informatique et dans les moteurs de recherche.