| Titre : |
Calculabilité, complexité et approximation |
| Type de document : |
texte imprimé |
| Auteurs : |
Jean-François Rey (1946-....), Auteur ; Jean Berstel (1941-....), Préfacier, etc. |
| Editeur : |
Vuibert informatique |
| Année de publication : |
2004 |
| Importance : |
363 p. |
| Présentation : |
ill., couv. ill. en coul. |
| Format : |
24 cm. |
| ISBN/ISSN/EAN : |
978-2-7117-4808-2 |
| Note générale : |
Bibliogr. p. 357-358. Index. |
| Langues : |
Français (fre) |
| Index. décimale : |
08-06-Algorithme |
| 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. |
Calculabilité, complexité et approximation [texte imprimé] / Jean-François Rey (1946-....), Auteur ; Jean Berstel (1941-....), Préfacier, etc. . - Vuibert informatique, 2004 . - 363 p. : ill., couv. ill. en coul. ; 24 cm. ISBN : 978-2-7117-4808-2 Bibliogr. p. 357-358. Index. Langues : Français ( fre)
| Index. décimale : |
08-06-Algorithme |
| 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. |
|  |
Affiner la recherche Interroger des sources externes
