Présentation du cours : (M02) Complexité
|
LES NOTES PROVISOIRES DE l'UE (classées par n° d'étudiant) sont ici :
notesM02_04_05etu.pdf
L'objectif de cette UE est de vous présenter divers aspects de la "complexité" des programmes. Cette UE se compose de
|
|
1 Complexité théorique et expérimentale
La partie Complexité théorique et expérimentale, a pour but :- D'étudier les outils mathématiques nécessaires à l'analyse des performances d'un algorithme.
- De montrer comment améliorer les performances des algorithmes faciles.
- 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 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.
2 Les cours
| Cours | Sujet | Support de cours |
| Cours 7 | Introduction et rappels mathématiques sur les limites et récurrences. A noter un excellent formulaire ou vous avez toutes les formules de mathématiques dont vous avez besoin. Je n'ai pas mis le lien web car l'adresse semble innaccessible maintenant. |
cours1 - cours1_8 |
| Cours 8 | Hash-code et dictionnaires (présentation du Devoir 1). voici un cours en ligne, si vous avez quelques difficultés avec les probabilités!!) : http://www.agro-montpellier.fr/cnam-lr/statnet/cours4.htm |
cours8 - cours8_8 |
| Cours 9 | Diviser pour régner : Les Tris Démo de tri. Diviser pour régner (2) : Multiplications de matrices, FFT et autres algorithmes. |
M02Cours9 - M02Cours9_8 M02Cours9b - M02Cours9b_8 |
| Cours 10 | Initiation à la BioInformatique -- Alignements de séquences biologiques présentation du Devoir 2 quelques pages web taille des génomes et similarité avec l'homme Vous pouvez consulter également : Linear Alignment |
cours6 - cours6_8 |
2.1 comment visualiser les fichiers pdf
:
Pour pouvoir lire ou imprimer les supports de cours qui sont au format .pdf, vous devez disposer de
Acrobat Reader 6.0 (ou 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!!!)
2.2 Obtenir une autre réduction
Si vous voulez obtenir une autre présentation des transparents, par exemple 2 par pages ou 4 par pages, cela se fait aisément avec latex. Il faut récupérer le package pdfpages (c'est à dire le fichier pdfpages.sty) si il n'est pas déjà installé. La lecture de la doc est très intéressante. Ensuite créer le fichier suivant (pour mettre 2 transparents par page) :
compacte.tex
| |
|
ensuite exécuter la commande pdflatex compacte.tex et vous obtenez le résultat voulu dans compacte.pdf. C'est magique et on peut faire bien d'autres choses.
3 Les TD
Voici quelques uns des TD que j'envisage de faire (toujours en format .pdf):- TD7 : Calculs de limites et de récurrences.(td7.pdf)
- TD8 : Un petit peu de probabilité et Heapsort. (td8.pdf)
- TD9 : Radix-sorting, Insertion Sort, Un petit tri, Nombre d'échanges de Quicksort. (td9.pdf)
- TD10 : Complexité de "Merge Sort" et quelques exercices sur les séquences. (td10.pdf)