Calculabilité, complexité et approximation / Jean-François Rey [ Livre]
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