I51. TP d'algorithmique.
Les travaux pratiques consistent à implanter en
langage C
une dizaine d'algorithmes étudiés en cours et en travaux
dirigés. Les corrections sont publiées après la
séance de TP.
- Recherche de nombres premiers: le crible d'Eratosthène
- Estimation de pi. Analyse en moyenne de
l'incrémentation
- Backtracking: les huit
reines, le parcours du cavalier
- Tri fusion et tri rapide. Analyse en moyenne
- Recherche d'une chaîne de caractères (Knuth-Morris-Pratt)
- Analyse lexicale et arbre lexicographique
pour un dictionnaire
- Le tri topologique, parcours en profondeur
- Le plus court chemin de
Dijkstra, parcours en largeur
- La compression de Shannon-Fano
- Les plus longues sous-séquences
- Multiplication rapide, l'algorithme de Karatsuba.
communes