Introduction

Présentation générale

Les structures de tableaux vues en Première sont complétées par trois nouvelles structures de données linéaires : les listes chaînées, les piles et les files qui sont d'une grande importance dans de nombreux problèmes algorithmiques.

Le travail de compréhension et de conception d’algorithmes se poursuit en Terminale, grâce à ces structures et à l'introduction d'autres structures plus complexes que sont les arbres et les graphes, montrant ainsi tout l’intérêt d’une approche récursive dans la résolution algorithmique de problèmes.

On complète également l'initiation à la complexité débutée en Première par 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 à un coût logarithmique.

Points abordés

1. Structures de données linéaires :

   • listes chaînées, piles, files ;
   • interfaces et implémentations.

2. Méthode « Diviser pour régner » :

   • principes de la méthode ;
   • applications et efficacité de la méthode ;
   • tri fusion.

3. Programmation dynamique :

   • principe de la programmation dynamique ;
   • exemples pratiques d'application.

4. Recherche textuelle :

   • recherche d'un motif dans un texte ;
   • algorithme de Boyer-Moore (version naïve) ;
   • algorithme de Boyer-Moore : version simplifiée de Horspool.