Algorithmes pour le Bac
Programme de Première
Compétences préalables
- Lire et modifier les éléments d’un tableau grâce à leurs index,
- Utiliser des tableaux de tableaux pour représenter des matrices : notation a[i][j],
- Itérer sur les éléments d’un tableau,
- Itérer sur les éléments d’un dictionnaire.
Algorithmes
Écrire un algorithme de :
- recherche dans un tableau
- d’une occurrence sur des valeurs de type quelconque,
- de doublons,
- calcul
- d’un extremum,
- moyenne
- tri par insertion,
- tri par sélection
- prédiction de la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins
- recherche dichotomique dans un tableau trié
- résolution d’un problème grâce à un algorithme glouton.
- exemples : problèmes du sac à dos ou du rendu de monnaie.
Programme de Terminale
Listes et dictionnaires
- Rechercher une valeur dans une liste ou dans un dictionnaire
Arbres binaires :
- 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 binaire de recherche, insérer une clé.
Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs.
- 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 :
- parcours d’un labyrinthe
- routage dans Internet
- Écrire un algorithme utilisant la méthode « diviser pour régner »
- tri fusion
- Utiliser la programmation dynamique pour écrire un algorithme.
- exemples de l’alignement de séquences ou du rendu de monnaie
- Étudier l’algorithme de Boyer-Moore pour la recherche d’un motif dans un texte.