Algorithmique

Au programme

Un algorithme, c'est une recette de calcul — une suite finie d'instructions qui transforme une entrée en sortie. Ce chapitre vous propose de fabriquer, d'analyser et de comparer six familles d'algorithmes parmi les plus fondamentales du programme de NSI Première. Vous apprendrez à parcourir un tableau, à mesurer ce que vous écrivez (notion de complexité), à trier des données, à chercher efficacement dans un tableau trié, à construire une solution pas à pas par des choix locaux (algorithmes gloutons), et enfin à faire classer automatiquement une donnée par un algorithme d'apprentissage simple — les k plus proches voisins.

Le fil rouge est double. D'une part, écrire du code qui marche : tous les algorithmes vus ici seront implémentés en Python, testés, exécutés. D'autre part, raisonner sur ce code : pourquoi marche-t-il ? combien coûte-t-il ? existe-t-il mieux ? C'est le passage de l'élève codeur à l'élève algorithmicien.

Plan

• Cours 1 — Parcours séquentiel d'un tableau : recherche, extremum, moyenne, et l'idée d'invariant. [PH03]
• Cours 2 — Bases de la complexité : combien coûte un algorithme ? La notation $\mathcal{O}$ introduite en douceur (socle, sans item BO direct).
• Cours 3 — Tris par sélection et par insertion : deux tris classiques, leur invariant, leur coût quadratique. [PH05]
• Cours 4 — Recherche dichotomique : diviser par deux à chaque étape, $\mathcal{O}(\log n)$. [PH04]
• Cours 5 — Algorithmes gloutons : choix local immédiat pour rendu de monnaie et sac à dos. [PH02]
• Cours 6 — k plus proches voisins : un premier algorithme d'apprentissage par classification. [PH01]