Prêtable
| Titre : | Calculabilité, complexité et approximation |
| Auteurs : | Jean-François Rey |
| Type de document : | texte imprimé |
| Editeur : | Paris [France] : Vuibert, 2004 |
| ISBN/ISSN/EAN : | 978-2-71174-808-0 |
| Format : | XVIII-363 p. / ill.; couv. ill. en coul. / 24 cm. |
| Langues: | Français |
| Langues originales: | Français |
| Index. décimale : | 511.3 (Logique mathématique) |
| Catégories : | |
| Mots-clés: | Calculabilité ; Complexité ; Approximation |
| 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.
|
| Note de contenu : |
Sommaire :
Chapitre 1: La notion de calcul Chapitre 2: Les machines de Turing Chapitre 3: Décidabilité Chapitre 4: Complexité Chapitre 5: Les classes de complexité polynomiale Chapitre 6: Approximation |
Exemplaires (2)
| Cote | Support | Localisation | Section | Disponibilité |
|---|---|---|---|---|
| F8/4793 | Livre | Bibliothèque de la Faculté de Technologie | Salle des livres | Disponible |
| F8/4794 | Livre | Bibliothèque de la Faculté de Technologie | Salle des livres | Disponible |
