Calculabilité, complexité et approximation / Jean-François Rey [ Livre]

Auteur principal: Rey, Jean-François, 1949-....Langue: Français.Publication : Paris : Vuibert, 2004Description : XVIII-363 p. ; 24 cmISBN: 2711748081.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. Sommaire La notion de calcul Les machines de Turing Décidabilité Complexité Les classes de complexité polynômiale Approximation.Sujet - Nom commun: Complexité de calcul (informatique) | Décidabilité (logique mathématique) | Fonctions calculables | Approximation, Théorie de l' | Algorithmes
Current location Call number Status Notes Date due Barcode
ENS Rennes - Bibliothèque
Informatique
F 2 REY (Browse shelf) Available F 2 Analyse des algorithmes et complexité 00007813
ENS Rennes - Bibliothèque
Informatique
F 2 REY (Browse shelf) Exclu du prêt F 2 Analyse des algorithmes et complexité 000078131

Bibliogr. p. 357-358. Index

Bibliogr., index, gl

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.
Sommaire
La notion de calcul
Les machines de Turing
Décidabilité
Complexité
Les classes de complexité polynômiale
Approximation

Powered by Koha