Calculabilité, complexité et approximation

Jean-François Rey

363 pages, parution le 14/04/2004

Ajouter à une liste

Indisponible

Résumé

L'algorithme est au cœur 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 ce livre, 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é algorithmique, les classes de complexité, y compris les classes probabilistes, les classes d'approximation, avec plusieurs exemples concrets d'algorithme d'approximation.

L'auteur - Jean-François Rey

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.

Sommaire

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

Voir tout

Replier

Caractéristiques techniques

	PAPIER
Éditeur(s)	Vuibert
Auteur(s)	Jean-François Rey
Parution	14/04/2004
Nb. de pages	363
Format	17 x 24
Couverture	Broché
Poids	640g
Intérieur	Noir et Blanc
EAN13	9782711748082
ISBN13	978-2-7117-4808-2