Introduction à l'algorithmique (année 2017-2018)

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 (1/2)

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.

Cours 4 : Recherche dans une collection (2/2)

Sujet du TD4

Cours 5 : Parcours de graphes et applications (1/3)

Sujet du TD5

Cours 6 : Parcours de graphes et applications (2/3)

Sujet du TD6

Cours 7 : Parcours de graphes et applications (3/3)

Sujet du TD7

Cours 8 : Problème du flot maximum

Test de la stratégie gloutonne (solution non optimale)
Transparents de cours

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.