Titre :	Calculabilité, complexité et approximation
Type de document :	texte imprime
Auteurs :	Jean-François Rey ; Berstel, Jean, Auteur
Editeur :	Paris : Vuibert
Année de publication :	DL 2004, cop. 2004
Présentation :	ill., couv. ill.
Format :	24 cm
ISBN/ISSN/EAN :	978-2-7117-4808-2
Note générale :	Bibliogr. p. 357-358. Glossaire. Index
Langues :	Français
Mots-clés :	Fonctions calculables  Algorithmes  Approximation, Théorie de l'  Complexité de calcul (informatique  )Approximation numérique  Informatique:mathématiques
Index. décimale :	511.3
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 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.
Note de contenu :	La notion de calcul Les machines de Turing Décidabilité Complexité Les classes de complexité polynômiale Approximation
Permalink :	./index.php?lvl=notice_display&id=13539

Calculabilité, complexité et approximation [texte imprime] / Jean-François Rey ; Berstel, Jean, Auteur . - Paris : Vuibert, DL 2004, cop. 2004 . -  : ill., couv. ill. ; 24 cm.
ISBN : 978-2-7117-4808-2
Bibliogr. p. 357-358. Glossaire. Index



Langues : Français

Mots-clés :	Fonctions calculables  Algorithmes  Approximation, Théorie de l'  Complexité de calcul (informatique  )Approximation numérique  Informatique:mathématiques
Index. décimale :	511.3
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 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.
Note de contenu :	La notion de calcul Les machines de Turing Décidabilité Complexité Les classes de complexité polynômiale Approximation
Permalink :	./index.php?lvl=notice_display&id=13539