[F] Algorithmique

[F.1] Arbres binaires et arbres binaires de recherche

Contenus :

• Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.

Capacités attendues :

• 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é.

Commentaires :

• 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.

[F.2] Algorithmes sur les graphes.

Contenus :

• Algorithmes sur les graphes.

Capacités attendues :

• 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.

Commentaires :

• 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.

[F.3] Méthode “diviser pour régner”

Contenus :

• Méthode “diviser pour régner”.

Capacités attendues :

• Écrire un algorithme utilisant la méthode « diviser pour régner ».

Commentaires :

• 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 log2 n dans les pires des cas.

[F.4] Programmation dynamique

Contenus :

• Programmation dynamique.

Capacités attendues :

• Utiliser la programmation dynamique pour écrire un algorithme.

Commentaires :

• 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.

[F.5] Recherche textuelle

Contenus :

• Recherche textuelle.

Capacités attendues :

• Étudier l’algorithme de BoyerMoore pour la recherche d’un motif dans un texte.

Commentaires :

• L’intérêt du prétraitement du motif est mis en avant.
• L’étude du coût, difficile, ne peut être exigée.