L'algorithme est au coeur de l'informatique.

S'il remonte à la plus haute antiquité,

un algorithme désigne aujourd'hui

la description d'une suite finie et organisée

d'actions qui, appliquée à une donnée,

permet d'aboutir de façon certaine

à un résultat déterminé, solution

d'un problème donné.

Quelle est la frontière entre un problème

admettant une solution algorithmique

et celui n'en possédant pas ? Un algorithme

peut-il donner une solution exacte en

un temps réaliste ? Peut-on trouver

une solution approchée quand

les algorithmes exacts sont irréalisables

et mesurer ces approximations ?

Voilà l'objet de cet ouvrage, qui se présente

sous la forme d'un cours avec exercices

corrigés et qui synthétise les notions

fondamentales nécessaires pour répondre

à ces questions. Sont notamment étudiées

les notions de décidabilité et de calculabilité,

les classes de complexité, y compris

les classes probabilistes, les classes

d'approximation, avec plusieurs exemples

concrets d'algorithme d'approximation.