Titre : |
Complexité et algorithmique avancée : une introduction |
Type de document : |
texte imprimé |
Auteurs : |
Ivan Lavallée, Auteur |
Editeur : |
Hermann |
Année de publication : |
2008 |
Collection : |
Méthodes |
Importance : |
336p |
Format : |
22xc16 cm |
ISBN/ISSN/EAN : |
978-2-7056-6726-9 |
Note générale : |
Sommaire
Historique
Histoires d'algorithmes
Survol
Un rapide tour d'horizon
La machine de Turing
La machine de Turing universelle
Complexité de Kolmogorov (rudiments)
Théorie
Considérations théoriques
Ordres, treillis et algèbre de Boole
Circuits booléens
Quelques problèmes de référence
Algorithme, résolution
Complexité
Classes de complexité
NP complétude
Le pire n'est pas toujours certain
Complexité et efficacité
Que faire ?
Des algorithmes pour problèmes NPC
Kolmogorov le retour
Le modèle quantique
A. Notations de Bachman-Landau |
Langues : |
Français (fre) Langues originales : Français (fre) |
Index. décimale : |
004 Traitement de données. Informatique |
Résumé : |
Complexité et algorithmique avancée est un exposé introductif à la pratique de la théorie de la complexité, il a été enseigné dans les trois cycles universitaires d'informatique et de cognitique et l'ouvrage est conçu pour être abordé par les étudiants des trois cycles universitaires. Il s'agit là du premier ouvrage en langue française traitant de la complexité en tant que telle. On y trouvera une introduction aux concepts fondamentaux du domaine, qu'il s'agisse de machine de Turing élémentaire ou universelle, de complexité au sens de Levin-Cook ou de Kolmogorov. Dans ce livre sont définies les trois principales classes de complexité, P, NP et NPC ainsi que le concept de quantité absolue d'information dû à Kolmogorov. Dans une dernière partie, on montre comment résoudre certains problèmes en faisant "tomber" la complexité en utilisant des concepts probabilistes, ou en utilisant des méthodes d'énumération implicite dont les principes sont décrits. L'ouvrage se termine sur un chapitre consacré à l'informatique quantique. Ce livre est destiné tant aux étudiants en informatique qu'aux ingénieurs et chercheurs. L'ouvrage propose aussi des voies pour la recherche, abordant les aspects pratiques au travers de la conception des algorithmes de résolution pour problèmes dits NP- complets, une partie est consacrée à ces aspects pratiques.
Public : Licence, Maîtrise, Doctorat, Ingéniorat |
Complexité et algorithmique avancée : une introduction [texte imprimé] / Ivan Lavallée, Auteur . - [S.l.] : Hermann, 2008 . - 336p ; 22xc16 cm. - ( Méthodes) . ISBN : 978-2-7056-6726-9 Sommaire
Historique
Histoires d'algorithmes
Survol
Un rapide tour d'horizon
La machine de Turing
La machine de Turing universelle
Complexité de Kolmogorov (rudiments)
Théorie
Considérations théoriques
Ordres, treillis et algèbre de Boole
Circuits booléens
Quelques problèmes de référence
Algorithme, résolution
Complexité
Classes de complexité
NP complétude
Le pire n'est pas toujours certain
Complexité et efficacité
Que faire ?
Des algorithmes pour problèmes NPC
Kolmogorov le retour
Le modèle quantique
A. Notations de Bachman-Landau Langues : Français ( fre) Langues originales : Français ( fre)
Index. décimale : |
004 Traitement de données. Informatique |
Résumé : |
Complexité et algorithmique avancée est un exposé introductif à la pratique de la théorie de la complexité, il a été enseigné dans les trois cycles universitaires d'informatique et de cognitique et l'ouvrage est conçu pour être abordé par les étudiants des trois cycles universitaires. Il s'agit là du premier ouvrage en langue française traitant de la complexité en tant que telle. On y trouvera une introduction aux concepts fondamentaux du domaine, qu'il s'agisse de machine de Turing élémentaire ou universelle, de complexité au sens de Levin-Cook ou de Kolmogorov. Dans ce livre sont définies les trois principales classes de complexité, P, NP et NPC ainsi que le concept de quantité absolue d'information dû à Kolmogorov. Dans une dernière partie, on montre comment résoudre certains problèmes en faisant "tomber" la complexité en utilisant des concepts probabilistes, ou en utilisant des méthodes d'énumération implicite dont les principes sont décrits. L'ouvrage se termine sur un chapitre consacré à l'informatique quantique. Ce livre est destiné tant aux étudiants en informatique qu'aux ingénieurs et chercheurs. L'ouvrage propose aussi des voies pour la recherche, abordant les aspects pratiques au travers de la conception des algorithmes de résolution pour problèmes dits NP- complets, une partie est consacrée à ces aspects pratiques.
Public : Licence, Maîtrise, Doctorat, Ingéniorat |
| ![Complexité et algorithmique avancée vignette](./images/vide.png) |