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.