cours

Algorithmique

Parcourir, trier, chercher, choisir, classer, et mesurer le coût du code écrit.
1
Parcours séquentiel d'un tableau
Parcourir un tableau de gauche à droite, la brique de base de presque tous les algorithmes sur les collections.
2
Bases de la complexité
Combien coûte un algorithme ? Premier contact avec la notation grand-O, sans dramatiser les maths.
3
Tris par sélection et par insertion
Deux algorithmes classiques pour ranger un tableau dans l'ordre, leur invariant, et pourquoi ils coûtent O(n²).
4
Recherche dichotomique
Chercher dans un tableau trié en divisant l'espace de recherche par deux à chaque étape, pour un coût en O(log n).
5
Algorithmes gloutons
Construire une solution pas à pas par des choix locaux qui semblent les meilleurs sur le moment, avec l'exemple du rendu de monnaie et du sac à dos.
6
Les k plus proches voisins (k-NN)
Un premier algorithme d'apprentissage, qui classe un point en regardant la classe majoritaire de ses k plus proches voisins.