Horaires :     Cours : 20h.          TD machines: 10h.

Responsable :  Jean Cousty 

Intervenants : Jean Cousty et Vincent Bismuth

Objectifs & compétences à acquérir

- Appréhender quelques problèmes fondamentaux pour deux domaines du traitement de l'information :

1) le traitement de séquences, en particulier des séquences textuelles et biologiques ;
2) le traitement linéaire de signaux, en particulier des images à 2 dimensions.

- Savoir écrire un algorithme 'force brute' pour résoudre ces problèmes.
- Appréhender quelques algorithmes efficaces pour résoudre ces problèmes.
- Savoir réduire, lorsque c'est possible, un problème inconnu à l'un de ces problèmes fondamentaux et donc savoir proposer un algorithme efficace pour résoudre un tel problème.

Pré-requis

- Programmation (Java ou C/C++)
- Compétences élémentaires en algorithmiques

Organisation et sujets des cours et travaux dirigés

Première partie : traitement de séquences

Cours 1. Algorithmes naïfs pour la recherche de motif dans le cas général et dans le cas d'un motif où les caractères sont deux à deux distincts
Cours 2. Recherche de motifs avec automate fini et extension au cas de motifs avec caractères joker
Cours 3. Plus longue frontière et recherche de motifs : algorithme de (Knuth) Morris et Pratt
Cours 4. Plus long facteur répété : algorithme naif et algorithme de Karp, Miller et Rosenberg
TDm 1 et 2. Algorithmique et génome : plus courte sur-séquence commune, graphes des recouvrements, algorithme d'approximation de Gallant, Maier et Storer et algorithme linéaire pour un cas particulier
Cours 5. Table de hachage
Cours 6. Distance d'édition
TDm 3. Alignement optimal et logiciel d'aide à la détection de plagiat

Seconde partie : traitement (linéaire) d'images

Environnement de travail

Bibliographie