Calculabilité, complexité et approximation

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.

Contenu

• La notion de calcul.
• Les machines de Turing.
• Décidabilité.
• Complexité.
• Les classes de complexité polynômiale.
• Approximation

Prix : 38.00 euros  Editeur : VUIBERT - Collection : METHODE 90 - Paru le : 05/04/2004 Auteur : Rey, Jean-François

Calculabilité, complexité et approximation

À propos de l’auteur

Jean-François Rey est agrégé de mathématiques et docteur en informatique. Il est directeur adjoint du département d’informatique de l’université de Cergy Pontoise et responsable de la maîtrise d’informatique. Il enseigne la théorie de la complexité, la cryptographie et l’algorithmique dans les seconds cycles d’informatique et de mathématiques. Membre associé du laboratoire d’informatique de l’institut Gaspard Monge, ses recherches portent principalement sur les méthodes algébriques appliquées à l’informatique.