NOUVEAU et EXPERIMENTAL : Les
premiers cours en video sont disponibles : consultez la page web video
Description de l'objectif du cours
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 :
- 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 : je me suis toujours dit que cela serait
utile pour comparer deux programmes faits par des binômes
différents pour voir si ils ont copiés!!
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 12 Mai au 27 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
Attention, il faut le consulter
régulièrement
|
Cours |
TD Groupe1 |
TD Groupe2 |
Remise des devoirs |
| 09/12/2002 |
Cours1: 10h-12h(amphi 5) |
TD1: 14h-16h(101B) |
TD1: 16h-18h(101B) |
|
| 12/12/2002 |
Cours2: 14h-16h(amphi
5) |
|
|
|
| 16/12/2002 |
Cours3: 10h-12h(amphi 5) |
TD2: 14h-16h(101B) |
TD2: 16h-18h(101B) |
|
| 19/12/2002 |
Cours4: 10h-12h(amphi 5) |
TD3: 14h-16h(101B) |
TD3: 16h-18h(103B) |
|
|
Joyeux
Noël |
|
|
|
| 06/01/2003 |
Cours5: 10h-12h(amphi 5) |
TD4: 14h-16h(104B) |
TD4: 16h-18h(104B) |
|
| 06/01/2003 |
|
|
|
Devoir 1 |
| 09/01/2003 |
Cours6: 10h-12h(amphi 5) |
TD5: 14h-16h(119A) |
TD5: 16h-18h(119A) |
|
| 13/01/2003 |
|
|
|
|
| 13/01/2003 |
Cours7: 10h-12h(amphi 5) |
TD6: 14h-16h(104B) |
TD6: 16h-18h(104B) |
Devoir 2 |
| 19/01/2003 |
|
TD7: 14h-16h(109A) |
TD7: 16h-18h(109A) |
|
| 22/01/2003 |
|
|
|
Devoir 3 |
| 27/01/2003 |
au 31/01/2003 |
examen |
|
|
Il n'y aura pas de TP encadrés, par contre je suis a
votre disposition pour répondre à vos questions par
Mail ou oralement (prendre rendez-vous par mail). Vous devrez
utiliser les créneaux disponibles pour les TP pour
réaliser la partie programmation concernant les devoirs :
cela représente 16h de TP soit environ 5h/devoir.
Voici le détail des cours
: Pour pouvoir lire ou
imprimer les supports de cours qui sont au format .pdf, vous devez
disposer de Acrobat Reader 5.0. Ce produit est gratuit et
disponible sur de nombreuses plates-formes. Vous pouvez
également utiliser Ghostscript ou xpdf.
Les fichiers terminés par _8.pdf, contiennent 8
transparents par page (pour imprimer et pour économiser des
arbres!!!)
Un excellent formulaire ou vous avez toutes les formules de
mathématiques dont vous avez besoin se trouve à
l'adresse suivante : http://www.csc.lsu.edu/~seiden/cheat.pdf
Voici quelques uns des TD que j'envisage de faire (toujours en
format .pdf):
- TD1 : Calculs de limites et de récurrences.( td1.pdf )
- TD2 : Un petit peu de probabilité. ( td2.pdf )
- TD3 : Radix-sorting, Insertion Sort, Un petit tri, Nombre
d'échanges de Quicksort. ( td3.pdf )
- TD4 : Complexité de MergeSort et ShellSort. ( td4.pdf )
- TD5 : Algorithmes sur les séquences. ( td5.pdf )
- TD6 : Etude de Heapsort - ou l'on montre que le peut construire
un tas en un temps linéaire. ( td6.pdf )
- TD7 : Examens des quatre dernières années. ( td7.pdf )
Voici quelques extraits des devoirs et des TER proposés
les annéees passés.
