Dimanche 11 janvier 2004
| Nouvelles |
- Les cours 5 et 7 en vidéo sont disponibles
- la date de l'examen est fixée au 28 Janvier
- Le cours 8 est supprimé
- mes meilleurs voeux de bonheur de de réussite pour cette nouvelle année 2004
(cliquez-ici).
|
|
Présentation du cours Algorithmes et Complexité
L'objectif de ce cours est :
-
D'étudier les outils mathématiques nécessaires à l'analyse des performances d'un algorithme.
- De donner une idée de ce qui est traitable et intraitable actuellement avec un ordinateur.
- De montrer comment améliorer les performances des algorithmes faciles.
- D'expliquer comment aborder les problèmes difficiles.
Il y aura trois devoirs à rendre qui vont compter chacun pour 4 points. Ces devoirs sont à
faire au plus par groupes de deux élèves. Chaque devoir mélange à la fois la pratique et un peu de théorie et
correspond environ à 10h de travail. De manière générale, il faut faire un petit programme (le langage est au
choix, mais moi j'utilise java!) et rendre un document écrit. Ce qui fait que maintenant l'examen est noté
sur 8 -- les devoirs sont notés sur 12. Voici une description rapide des trois devoirs de cette année : |
| Cours en Video : |
L'année dernière tous les cours ont été fimés en vidéo, ils sont disponibles sur Internet.
Je souhaiterai avoir votre avis sur cette nouvelle technologie. Essayez d'en profiter.
Consultez la page web sur les cours en video. |
|
- Le devoir 1 s'intéresse aux problèmes de consultation de dictionnaire. On vous a
beaucoup parlé des arbres, mais les méthodes basées sur les tables de hachage (hash-code) sont beaucoup plus
performantes (c'est ce que je vous demande de montrer), cependant elles utilisent beaucoup de mémoire. Cela va nous obliger à regarder de près certaines lois
de probabilité, qui justifient ces algorithmes. Tout cela sera appliqué à la correction de l'orthographe d'un texte
de Proust avec un dictionnaire du français.
- Le devoir 2 concerne la résolution d'un problème difficile (bien sûr NP-complet)
: la localisation d'entrepôt. Une entreprise a un certain nombre de clients qu'elle cherche a approvisionner à
partir d'entrepôts. Une première analyse lui a donné un certain nombre de localisation pour ces entrepôts. Le
problème posé est de choisir a quels endroits on doit effectivement construire les entrepôts pour minimiser le coût.
Le coût total dépend du coût fixe pour construire un entrepôt mais aussi du coût de livraison de chaque client (un
client est livré par l'entrepôt le plus proche de chez lui). Je vous propose d'utiliser une méthode tabou pour
résoudre de manière approchée ce problème. Cela permet de résoudre des problèmes réalistes : Une centaine de
localisation possible pour les entrepôts et un millier de clients, en quelques secondes.
- Le devoir 3 a pour but de programmer un algorithme qui
permet de comparer des séquences de lettre. Cet algorithme est très utilisé pour comparer
des séquences "biologiques" : séquences d'ADN ou de protéines. Ceux qui ont suivi l'option
de Bio de la licence comprendront très vite l'intérêt de ce programme, pour les autres
j'essayerai de les convaincre. La programmation de cet algorithme demande un certain soin.
On peut aussi utiliser cette méthode pour comparer deux programmes.
Cette année nous allons surtoût nous intéresser a un algorithme qui utilise un espace
mémoire linéaire en fonction de la taille des données.
Les TER sont des travaux personnels (par binôme) qui vous initient à la recherche. Ce travail est plus qu'une
utilisation directe du cours, vous devez recherchez de l'information par vous même et produire un travail Original.
Cette année les TER auront lieu du ?? Mai au ?? Juin. Cette période est réservée exclusivement aux TER. Je vais
vous proposer cette année trois sujets qui vont tourner autour de la BioInformatique.
Remarque :ce cours représente la moitié du cours UE3 (Coeff 1.3, ECTS 7). Les TER forment l'UE8 (Coeff 2, ECTS 11)
et ont donc une certaine importance pour votre note finale de maîtrise
|
