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. Comparaison des performances du tri à bulles et du tri rapide.
3. Un exemple de problème de Backtracking.
4. Construction d'un petit analyseur lexical sous lex.
5. Compression de Huffman.
6. Algorithmes de Dijkstra
7. Gestions des ensembles disjoints.
8. multiplication rapide
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