Théorie de la complexité

ISBN-13: 9783565151264 / Francuski / Miękka / 316 str.

Lucien Sina

Opis

Qu'est-ce que la théorie de la complexité - et pourquoi est-elle si centrale en informatique ? La théorie de la complexité étudie combien de temps, d'espace mémoire ou d'autres ressources sont nécessaires pour résoudre des problèmes algorithmiques. Elle constitue le fondement pour comprendre ce que les ordinateurs peuvent accomplir - et ce qui reste, même avec les meilleurs algorithmes, fondamentalement inaccessible. De classes classiques comme P et NP, en passant par les réductions, la complétude NP et les problèmes d'approximation, jusqu'aux systèmes de preuves interactifs, à la théorie PCP et à la complexité de communication, ce livre introduit progressivement les concepts clés de l'informatique théorique. Lucien Sina n'explique pas seulement la théorie, mais transmet également les idées et les intuitions qui la sous-tendent. De nombreux exemples, démonstrations et exercices avec solutions aident à approfondir les contenus et à développer une compréhension intuitive des limites du calcul efficace. Cet ouvrage est idéal pour les étudiants en informatique, les enseignants, les chercheurs et tous ceux qui cherchent un accès solide et clair à la théorie de la complexité. Il fait suite aux autres ouvrages de l'auteur - "Algorithmes et structures de données", "Informatique théorique", "Logique : fondements, problème P vs NP et perspectives informationnelles", ainsi que "Programmation orientée objet en Java" - et constitue, avec eux, une série cohérente d'apprentissage et de référence, allant de la recherche fondamentale à la programmation pratique. La théorie de la complexité montre comment la théorie et la pratique de l'informatique sont profondément interconnectées - et pourquoi connaître les limites du faisable est souvent la première étape pour les dépasser de manière créative.

Que peuvent accomplir les ordinateurs ? - et qu'est-ce qui reste, en principe, inaccessible même avec les meilleurs algorithmes ?