Programme

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 \(n^2\) à \(n log_2 n\) ou de \(n\) à \(log_2 n\). 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
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.