907 -- Algorithmique du texte : exemples et applications.

Par "texte", on entend "information" : programme, document, ADN...

• Comparaison de deux séquences (comparaison d'un mot avec une entrée d'un dictionnaire puis correction etc., comparaison d'ADN)
• Recherche d'une chaîne dans une autre (dans un logiciel de traitement de texte, un moteur de recherche sur l'Internet
• Stockage de texte : compression via les arbres de Huffman

Extrait du site [1] concernant cette leçon.

Plan Basile et Kévin (2012)

Développements Possibles

• Morris-Prat (Beauquier)
• Knuth-Morris-Pratt
  • Algorithme en lui-même
  • Automate des ouvertures
• Plus longue sous-suite commune (Cormen)
• Tri des suffixes (Crochemore)
• Algorithme de Rabin-Karp
• Calcul de la distance d'édition
• Recherche avec $k$ différences
• Méthode de compression Ziv-Lempel77
• ... éventuellement de la compilation (analyse lexicale et syntaxique)

Références

• Crochemore et al.
• Beaquier Berstel Chrétienne