Partie 4 : algorithmique avancée

Le concept de méthode algorithmique est introduit ; de nouveaux exemples seront vus en terminale. Quelques algorithmes classiques sont étudiés. L’étude de leurs coûts respectifs prend tout son sens dans le cas de données nombreuses, qui peuvent être préférentiellement des données ouvertes.

Il est nécessaire de montrer l’intérêt de prouver la correction d’un algorithme pour lequel on dispose d’une spécification précise, notamment en mobilisant la notion d’invariant sur des exemples simples. La nécessité de prouver la terminaison d’un programme est mise en évidence dès qu’on utilise une boucle non bornée (ou, en terminale, des fonctions récursives) grâce à la mobilisation de la notion de variant sur des exemples simples.

1. Introduction à l'algorithmique :
   • pourquoi étudier l'algorithmique ? ;
   • qu'est-ce qu'un algorithme ? ;
   • écrire un algorithme : spécification et tests ;
   • prouver un algorithme : terminaison et correction partielle ;
   • comparer des algorithmes : complexité.

2. Preuve et complexité d'algorithmes :
   • terminaison : variant de boucle ;
   • correction partielle : invariant de boucle ;
   • correction totale ;
   • complexité : échelles de comparaison et temps de calculs.

3. Tableaux :
   • présentation de la structure des tableaux statiques ;
   • longueur et indexation ;
   • parcours séquentiels ;
   • recherche d'éléments.

4. Tris de tableaux :
   • tri par sélection ;
   • tri par insertion.

5. Recherche dichotomique :
   • présentation de l'algorithme : spécifications et principe général ;
   • preuve et complexité.

6. Algorithme des k plus proches voisins :
   • présentation de l'algorithme ;
   • manipulation de l'algorithme sur un exemple simple.

7. Algorithmes gloutons :
   • présentation générale du principe des algorithmes gloutons ;
   • étude de quelques exemples classiques :
     • problème du voyageur de commerce ;
     • problème d'organisation ;
     • problème du rendu de monnaie.