Formations

Publié le 22 septembre 2008 Mis à jour le 11 novembre 2020

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


Mots-clés: Cœur Algorithme

Voir plus de formations de cette institution

Accédez à des services exclusifs gratuitement

Inscrivez-vous et recevez des infolettres sur :

  • Les cours
  • Les ressources d’apprentissage
  • Le dossier de la semaine
  • Les événements
  • Les technologies

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

M’abonner à l'infolettre

Superprof : la plateforme pour trouver les meilleurs professeurs particuliers en France (mais aussi en Belgique et en Suisse)


Effectuez une demande d'extrait d'acte de naissance en ligne !


Ajouter à mes listes de lecture


Créer une liste de lecture

Recevez nos nouvelles par courriel

Chaque jour, restez informé sur l’apprentissage numérique sous toutes ses formes. Des idées et des ressources intéressantes. Profitez-en, c’est gratuit !