| Parcours séquentiel d’un tableau | Écrire un algorithme de recherche d’une occurrence sur des valeurs de type quelconque.
Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne. | On montre que le coût est linéaire. |
| Tris par insertion, par sélection | Écrire un algorithme de tri.
Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection. | La terminaison de ces algorithmes est à justifier.
On montre que leur coût est quadratique dans le pire cas. |
| Algorithme des k plus proches voisins | Écrire un algorithme qui prédit la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins. | Il s’agit d’un exemple d’algorithme d'apprentissage |
| Recherche dichotomique dans un tableau trié. | Montrer la terminaison de la recherche dichotomique à l’aide d’un variant de boucle. | Des assertions peuvent être utilisées.
La preuve de la correction peut être présentée par le professeur. |
| Algorithmes gloutons. | Résoudre un problème grâce à un algorithme glouton. | Exemples : problèmes du sac à dos ou du rendu de monnaie.
Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale. |