Langages et algorithmique

Le travail entrepris en classe de première sur les méthodes de programmation est prolongé. L’accent est mis sur une programmation assurant une meilleure sûreté, c’est-à-dire minimisant le nombre d’erreurs. Parallèlement, on montre l’universalité et les limites de la notion de calculabilité.

La récursivité est une méthode fondamentale de programmation. Son introduction permet également de diversifier les algorithmes étudiés. En classe terminale, les élèves s’initient à différents paradigmes de programmation pour ne pas se limiter à une démarche impérative.

Contenus	Capacités attendues	Commentaires
Notion de programme en tant que donnée. Calculabilité, décidabilité.	Comprendre que tout programme est aussi une donnée. Comprendre que la calculabilité ne dépend pas du langage de programmation utilisé. Montrer, sans formalisme théorique, que le problème de l’arrêt est indécidable.	L’utilisation d’un interpréteur ou d’un compilateur, le téléchargement de logiciel, le fonctionnement des systèmes d’exploitation permettent de comprendre un programme comme donnée d’un autre programme.
Récursivité.	Écrire un programme récursif. Analyser le fonctionnement d’un programme récursif.	Des exemples relevant de domaines variés sont à privilégier.
Modularité.	Utiliser des API (Application Programming Interface) ou des bibliothèques. Exploiter leur documentation. Créer des modules simples et les documenter.
Paradigmes de programmation.	Distinguer sur des exemples les paradigmes impératif, fonctionnel et objet. Choisir le paradigme de programmation selon le champ d’application d’un programme.	Avec un même langage de programmation, on peut utiliser des paradigmes différents. Dans un même programme, on peut utiliser des paradigmes différents.
Mise au point des programmes. Gestion des bugs.	Dans la pratique de la programmation, savoir répondre aux causes typiques de bugs : problèmes liés au typage, effets de bord non désirés, débordements dans les tableaux, instruction conditionnelle non exhaustive, choix des inégalités, comparaisons et calculs entre flottants, mauvais nommage des variables, etc.	On prolonge le travail entrepris en classe de première sur l’utilisation de la spécification, des assertions, de la documentation des programmes et de la construction de jeux de tests. Les élèves apprennent progressivement à anticiper leurs erreurs.

Algorithmique

Le travail de compréhension et de conception d’algorithmes se poursuit en terminale notamment via l’introduction des structures d’arbres et de graphes montrant tout l’intérêt d’une approche récursive dans la résolution algorithmique de problèmes.

On continue l’étude de la notion de coût d’exécution, en temps ou en mémoire et on montre l’intérêt du passage d’un coût quadratique en 𝑛² à 𝑛·log₂(𝑛) ou de 𝑛 à log₂(𝑛). Le logarithme en base 2 est ici manipulé comme simple outil de comptage (taille en bits d’un nombre entier).

Contenus	Capacités attendues	Commentaires
Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.	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 de recherche, insérer une clé.	L’utilisation d’un interpréteur ou d’un compilateur, le téléchargement de logiciel, le fonctionnement des systèmes d’exploitation permettent de comprendre un programme comme donnée d’un autre programme.
Algorithmes sur les graphes.	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.	Le parcours d’un labyrinthe et le routage dans internet sont des exemples d’algorithme sur les graphes. L’exemple des graphes permet d’illustrer l’utilisation des classes en programmation.
Méthode « diviser pour régner ».	Écrire un algorithme utilisant la méthode « diviser pour régner ».	La rotation d’une image bitmap d’un quart de tour avec un coût en mémoire constant est un bon exemple. L’exemple du tri fusion permet également d’exploiter la récursivité et d’exhiber un algorithme de coût en 𝑛·log2(𝑛) dans les pires des cas.
Programmation dynamique.	Utiliser la programmation dynamique pour écrire un algorithme.	Les exemples de l’alignement de séquences ou du rendu de monnaie peuvent être présentés. La discussion sur le coût en mémoire peut être développée.
Recherche textuelle.	Étudier l’algorithme de BoyerMoore pour la recherche d’un motif dans un texte.	L’intérêt du prétraitement du motif est mis en avant. L’étude du coût, difficile, ne peut être exigée.