Les algorithmes à connaître pour le Bac

Algorithmes du programme de Première

Contenus	Capacités attendues	Commentaires
Parcours séquentiel d'un tableau	Ecrire un algorithme de recherche d'une occurrence sur des valeurs de type quelconque. Ecrire un algorithme de recherche d'un extrémum, de calcul de moyenne	On montre que le coût est linéaire
Algorithmes de tri : Tris par insertion, par sélection	Ecrire 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 des cas.
Algorithme des k plus proches voisins	Ecrire 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.

Algorithmes du programme de Terminale

Contenus	Capacités attendues	Commentaires
Diviser pour régner	Ecrire un algorithme utilisant la méthode "diviser pour régner".	La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple. L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en n.log2 n dans les pires des cas.
Algorithmes sur les arbres binaires et sur les arbres binaires de recherche	Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé.	Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.
Algorithmes sur les graphes	Parcourir un graphe en profondeur d’abord, en largeur d’abord. Repérer la présence d’un cycle dans un graphe. Chercher un chemin dans un graphe.	Le parcours d’un labyrinthe et le routage dans Internet sont des exemples d’algorithme sur les graphes. L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation.
Recherche textuelle	Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte.	L’intérêt du prétraitement du motif est mis en avant. L’étude du coût, difficile, ne peut être exigée.
Programmation dynamique	Utiliser la programmation dynamique pour écrire un algorithme.	Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée.