Introduction à l'algorithmique

Vous trouverez sur cette page quelques ressources pédagogiques liées à l'enseignement de l'algorithmique. Ces ressources sont utilisées dans le cadre du cours d'algorithmique que j'enseigne à l'ENS Rennes pour les étudiants de L3 Informatique et L3 Mathématiques (option).

Cours 1 : Analyse des algorithmes - terminaison et preuve

Sujet du TD1

Cours 2 : Analyse des algorithmes - complexité

Sujet du TD2

Cours 3 : Recherche dans une collection

  • Solutions simples en temps linéaire
  • Arbres binaires de recherche
  • Sujet du TD3

    Expérience illustrant le fait qu'en moyenne, la hauteur d'un arbre binaire de recherche généré aléatoirement a une croissance logarithmique en fonction du nombre d'éléments qui le composent (preuve en TD). Chaque réalisation de l'expérience a été obtenue en tirant aléatoirement un entier \(n\) uniformément entre 1 et 100, puis en tirant aléatoirement une permutation de \(\{1,\ldots, n\}\) ; les éléments de la suite ainsi générée ont été ajoutés séquentiellement à l'arbre vide en utilisant la procédure d'ajout aux feuilles vue en cours. On montre dans cette animation 1000 réalisations de cette expérience, et pour chaque réalisation on reporte sur un graphe la taille de l'arbre en abscisse, et sa hauteur en ordonnée.

    Ce cours et le matériel proposé sur cette page est le fruit du travail de nombreuses personnes, que je tiens à remercier. J'y apporte ma modeste contribution.