Le cours d'algorithmique du L1, licence d'informatique de la faculté des sciences et techniques de l'université de Toulon et du var s'appuie sur une douzaine de lecons illustrées par des travaux-dirigés et des travaux-pratiques.   Vous trouverez dans ces pages quelques notes de cours, les feuilles de travaux-dirigés et les sujets de travaux-pratiques.
 

Plan du  cours.

1. Notations asymptotiques et complexité
2. Analyse du tri rapide. Borne inférieure sur le tri par comparaisons
3. Algorithmes récursifs et Backtracking.
4. La structure de liste, application à l'analyse lexicale.
5. Algorithmes gloutons. Arbres binaires. Codage de Hufmann.
6. Recherche d'information. Fonctions de hachage. Arbres rouge et noirs.
7. Parcours de graphes, piles et files.
8. Problèmes classiques de la théorie des graphes : flots et plus court chemin.
9. Gestion des ensemles disjoints. Composantes connexes.
10. Arbre couvrant minimal. Problèmes d'approximations.
11. Transformée de Fourier discrète et multiplication rapide.
12. Problèmes NP-complets.

Sujets de travaux-pratiques.

1. L'art de la mise en oeuvre, initiation aux commandes gcc, gdb et gprof.
2. Analyse expérimentale des temps de calculs du tri rapide. [ postscript ],  [ pdf ].
3. Trois  problèmes classiques  de backtracking.  [postscript  ]
4. Multiplication rapide : algorithme de Karacuba-Ofman [ postscript ]
5. Compression :  algorithmes de Fano-Shannon et Huffman.
6. Algorithmes de Dijkstra
7. Construction d'un petit analyseur lexical sous lex.
8. Gestions des ensembles disjoints.
9. Arbre courant minimal et approximation du problème du voyageur de commerce.

Sujets de partiels et examens

1. session de juin  2000
2. session de septembre 2000