Formations

Calculabilité, complexité et approximation

le 22 septembre 2008 | Dernière mise à jour de l'article le 23 octobre 2008

Indépendants - Ressources gratuites

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 eurosEditeur : 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.

Avez-vous apprécié cette page?

Voir plus d'articles de cet auteur

Accédez à des services exclusifs gratuitement

Inscrivez-vous et recevez des infolettres sur :

De plus, indexez vos ressources préférées dans vos propres dossiers et retrouvez votre historique de consultation.

M’abonner
Je suis déja abonné