Nous commençons ce cours par un aperçu des relations de récurrence, qui nous fournissent un modèle mathématique direct pour l'analyse des algorithmes. Nous terminerons en examinant le fascinant comportement oscillatoire de la récurrence "diviser pour régner" correspondant à l'algorithme de tri sélectif et le "théorème maître" général pour les récurrences apparentées.

Depuis le XVIIe siècle, les scientifiques utilisent les fonctions génératrices pour résoudre les récurrences. Nous poursuivons donc avec un aperçu des fonctions génératrices, en mettant l'accent sur leur utilité pour résoudre des problèmes tels que le comptage du nombre d'arbres binaires à N nœuds.

Les réponses exactes étant souvent fastidieuses, nous examinerons ensuite une approche scientifique pour élaborer des réponses approximatives que, là encore, les mathématiciens et les scientifiques utilisent depuis des siècles.

Combinatoire analytique. Avec une connaissance de base des récurrences, des fonctions génératrices et de l'asymptotique, vous êtes prêt à apprendre et à apprécier les caractéristiques de base de la combinatoire analytique, une approche systématique qui évite la plupart des détails des méthodes classiques que nous avons étudiées. Nous introduisons les classes combinatoires étiquetées et non étiquetées et motivons notre approche de base pour les étudier, à l'aide de nombreux exemples.

Structure récursive par excellence, les arbres de différentes sortes sont omniprésents dans les enquêtes scientifiques et apparaissent explicitement dans d'innombrables applications informatiques. Vous trouverez une large couverture dans le manuel, mais le cours se concentre sur l'utilisation de la combinatoire analytique pour énumérer divers types d'arbres et étudier les paramètres.

L'étude des algorithmes de tri est l'étude des propriétés des permutations. Nous introduisons des approches analytiques et combinatoires pour étudier les permutations dans le contexte de cette relation.

Des séquences d'ADN aux index web, les chaînes (séquences de caractères) sont omniprésentes dans les applications informatiques modernes. Nous utilisons donc la combinatoire analytique pour étudier leurs propriétés de base, puis nous introduisons le triangle, une structure essentielle et fondamentale que l'on ne trouve pas dans la combinatoire classique.

Nous considérons les chaînes de caractères comme des ensembles de caractères ou comme des fonctions de [1..N] à [1..M] pour étudier les problèmes classiques d'occupation et leur application aux algorithmes de hachage fondamentaux. Les fonctions de [1..N] à [1..N] sont des mappings, qui ont une structure intéressante et complexe que nous pouvons étudier à l'aide de la combinatoire analytique.