| Titre : | Calculabilité, complexité et approximation |
| Auteurs : | Jean-François Rey, Auteur |
| Type de document : | texte imprimé |
| Editeur : | Paris : Vuibert informatique, 2004 |
| Collection : | Informatique fondamentale |
| ISBN/ISSN/EAN : | 978-2-7117-4808-2 |
| Format : | XVIII-363 p. / 24 x 17 cm |
| Note générale : |
Bibliogr. Index. Glossaire |
| Langues: | Français |
| Index. décimale : | 378.64 |
| Catégories : | |
| Mots-clés: | algorithmes ; problèmes et exercices ; complexité de calcul (informatique) ; décidabilité (logique mathématique) |
| Résumé : | L'algorithme est au cur 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 : |
1-La notion de calcul 2-Les machines de turing 3-Dècidabilitè 4-Complexitè 5-Les classes de complexitè polynomiale 6-Approximation 7-Exercices de l'annexe |
Exemplaires (4)
| Code-barres | Cote | Support | Localisation | Section | Disponibilité |
|---|---|---|---|---|---|
| TEC014088 | INF04501 | Livre | Fonds propre-bibliotheque centrale | Informatique | Libre accès Disponible |
| TEC014090 | INF04503 | Livre | Fonds propre-bibliotheque centrale | Informatique | Libre accès Disponible |
| TEC014091 | INF04504 | Livre | Fonds propre-bibliotheque centrale | Informatique | Libre accès Disponible |
| TEC014533 | INF04946 | Livre | Fonds propre-bibliotheque centrale | Informatique | Libre accès Disponible |
