| 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é. | Une structure de données récursive adaptée est utilisée.
L’exemple des arbres permet d’illustrer la programmation par classe.
La recherche dans un arbre de recherche équilibré est de coût logarithmique. |
| 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 n log 2 n 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 Boyer-Moore 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. |