Le cours vise à présenter des méthodes de conception et des structures de données qui s'imposent par leur généralité et qui s'appliquent dans une grande variété de situations. Pour ce qui est des méthodes, on étudiera en particulier la formulation d'un problème dans un cadre géométrique (linéaire), la possibilité d'approcher la solution d'un problème d'optimisation en fournissant une garantie sur la qualité du résultat et la conception et l'analyse d'algorithmes probabilistes.
On s'intéresse à la question de concevoir une structure de données pour représenter et manipuler la partition d'un ensemble. La possibilité de raffiner la partition joue un rôle essentiel dans plusieurs algorithmes tels que la minimisation d'automates finis ou le parcours en largeur lexicographique des graphes. Dans l'autre sens, une structure permettant de fusionner deux éléments de la partition peut être utilisée, par exemple, pour calculer un arbre de recouvrement minimum d'après l'algorithme de Kruskal.
Un problème d'optimisation (ou programmation) linéaire est un cas particulier d'optimisation convexe dans lequel on cherche à maximiser ou minimiser une fonction linéaire sur un espace de solutions admissibles décrit par un système d'inégalités linéaires. Un grand nombre de problèmes peuvent être formulés dans ce contexte et résolus à l'aide d'algorithmes efficaces en théorie et en pratique.
Un problème d'optimisation (ou programmation) linéaire en nombres entiers est un problème d'optimisation linéaire dans lequel en plus on demande à que certaines variables soient entières. Cette possibilité élargit de façon considérable le domaine d'application mais en même temps elle augmente la difficulté algorithmique de la solution du problème.
Dans de nombreuses situations, la solution exacte d'un problème d'optimisation revient à résoudre un problème NP-difficile. Dans ces cas, il peut être intéressant de chercher une méthode algorithmique efficace qui produit des solutions qui sont assez proches de la solution optimale. Il se trouve que les idées de l'optimisation linéaire sont souvent utilisées pour aborder ces questions.
Un algorithme stochastique est un algorithme qui de temps en temps fait appel à une source aléatoire pour décider son prochain état. On présente les notions de base utilisées dans la conception et l'analyse de ces algorithmes et on les applique dans un certain nombre de cas concrets. Parfois l'approche probabiliste permet de simplifier la conception de l'algorithme, dans d'autres cas elle permet d'avoir une solution plus efficace que celles obtenues avec les algorithmes déterministes connus et dans le cadre du calcul distribué on arrive même à résoudre des problèmes qui ne peuvent pas être abordés avec des algorithmes déterministes.
Structures de données (tas, arbres binaires de recherche, tables de hachage, graphes), méthodes de conception (diviser pour régner, programmation gloutonne, programmation dynamique), techniques d'analyse (invariant, terminaison, solution de relations de récurrence élémentaires, complexité asymptotique dans le pire des cas et en moyenne). Notions de classes de complexité : P vs. NP. Notions d'algèbre linéaire, d'arithmétique modulaire et de probabilités discrètes.