Les principaux points abordés sont : Recherche d'un mot dans un texte. Automates finis. Recherche de motifs dans un texte. Analyse syntaxique.
Les applications importantes sont : éditeurs de texte, fabrication d'index, recherche sur Internet, analyse syntaxique en compilation, comparaison de séquences génétiques en bio-informatique.
Aho, Sethi, Ullman : Compilateurs, InterEditions.
Cormen, Leiserson, Rivest : Introduction à l'algorithmique, Dunod.
Crochemore, Hancart, Lecroq : Algorithmique du texte, Vuibert.
Cours de Th. Lecroq : Algorithme de Knuth, Morris et Pratt. Algorithme de Boyer-Moore. Algorithme de Aho et Corasik. Voir aussi ce site.
Cours de l'Ecole Polytechnique, chapitres 6 et 7 : Téléchargeable ici.
Examen écrit dont la note compte pour 60% de la note finale : 1er juin 2010.
Projet obligatoire. A télécharger ici. La note compte pour 40% de la note finale. A rendre le 1er juin 2010.
Deuxième session le 15 septembre 9h - 11h, réservée aux étudiants inscrits. Me contacter par email (cf at ai.univ-paris8.fr) pour connaître les modalités.