Complexité et algorithmique

Complexité et algorithmique avancée est un exposé introductif à la pratique de
la théorie de la complexité, il a été enseigné dans les trois cycles
universitaires d'informatique et de cognitique et l'ouvrage est conçu pour
être abordé par les étudiants des trois cycles universitaires. Il s'agit là du
premier ouvrage en langue française traitant de la complexité en tant que
telle. On y trouvera une introduction aux concepts fondamentaux du domaine,
qu'il s'agisse de machine de Turing élémentaire ou universelle, de complexité
au sens de Levin-Cook ou de Kolmogorov. Dans ce livre sont définies les trois
principales classes de complexité, P, NP et NPC ainsi que le concept de
quantité absolue d'information dû à Kolmogorov. Dans une dernière partie, on
montre comment résoudre certains problèmes en faisant « tomber »la complexité,
en utilisant des concepts probabilistes, ou en utilisant des méthodes
d'énumération implicite dont les principes sont décrits. L'ouvrage se termine
sur un chapitre consacré à l'informatique quantique. Ce livre est destiné tant
aux étudiants en informatique qu'aux ingénieurs et chercheurs. L’ouvrage
propose aussi des voies pour la recherche, abordant les aspects pratiques au
travers de la conception des algorithmes de résolution pour problèmes dits NP-
complets, une partie est consacrée à ces aspects pratiques.