L'unité d'enseignement « Conception d'algorithmes et applications » est une UE de niveau (300) spécialisation relevant de la licence d'informatique. Elle possède un volume de 6 ECTS et s'étend sur 12 semaines. Elle est placée sous la responsabilité de Soria, michèle.

Description

L'objectif de cet enseignement est de présenter et comparer différents types de méthodes (naïve, gloutonne, récursive, ...) pour concevoir des algorithmes, et d'appliquer ces méthodes à l'écriture d'algorithmes dans des domaines variés.

L'objectif de cet enseignement est de présenter et comparer différents types de méthodes (naïve, gloutonne, récursive, ...) pour concevoir des algorithmes, et d'appliquer ces méthodes à l'écriture d'algorithmes dans des domaines variés, parmi lesquels on peut citer :

Algorithmes de recherche et de tri

Recherche de motifs dans un texte

Algorithmes numériques

Bases de la géométrie algorithmique

Arbres digitaux pour la recherche, le tri et la compression

Algorithmes approchés et probabilistes.

Préalables et buts pédagogiques

Bibliographie

• Cormen, Leiserson, Rivest, Stein. Introduction aux algorithmes. Seconde édition, Dunod, 2002

Contenu indicatif par semaine

1. Programmation récursive : diviser pour régner, exemples simples, preuves et complexité

2. Programmation récursive : tris (fusion, rapide), multiplication rapide

3. Programmation récursive : enveloppe convexe

4. Programmation dynamique : principes et exemples simples, multiplication de matrices

5. Programmation dynamique : plus longue sous-sequence commune, plus court chemin

6. Programmation dynamique : problème du sac à dos

7. Programmation gloutonne : principes et exemples simples,

8. Programmation gloutonne : algorithmes sur les graphes

9. Arbres digitaux pour la recherche et le tri

10. Arbres digitaux : compression de Huffmann

11. Recherche de motifs , méthodes naïves, Knuth-Morris-Pratt, Boyer-Moore

12. Recherche de motifs avec automates