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 :

 

É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.

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *