Tous nos rayons

Déjà client ? Identifiez-vous

Mot de passe oublié ?

Nouveau client ?

CRÉER VOTRE COMPTE
Complexité algorithmique
Ajouter à une liste

Librairie Eyrolles - Paris 5e
Disponible en magasin

Complexité algorithmique

Complexité algorithmique

Sylvain Perifel - Collection Références sciences

410 pages, parution le 22/04/2014

Résumé

Ce livre présente d'abord les notions de base en théorie de la complexité algorithmique avant de traiter de nombreux sujets avancés, Il s'agit du seul ouvrage en français couvrant un si large spectre dans ce domaine central en informatique théorique. Les notions mathématiques utiles sont rappelées et aucun prérequis, outre une culture mathématique de base, n'est supposé.

Clair et précis, contenant de nombreux exercices, il s'adresse aux étudiants de mathématiques et d'informatique à partir du L3, aux candidats à l'option informatique de l'agrégation de mathématiques, aux enseignants désirant un ouvrage de référence permettant de donner des cours formels sur le sujet (que ce soit un cours introductif ou sur les sujets très techniques des derniers chapitres), et aux chercheurs souhaitant approfondir le domaine.

La description rigoureuse du modèle de calcul (la machine de Turing) permet d'aborder solidement les bases de la complexité en temps et en espace (théorèmes de hiérarchie, accélération, etc.) et d'étudier le problème P = NP : NP-complétude,théorèmes de Ladner,de Mahaney,... Le non-déterminisme est aussi exploré par les oracles et la hiérarchie polynomiale, ainsi que par les protocoles interactifs qui poursuivent l'étude menée sur les algorithmes probabilistes. Un chapitre est consacré aux classes de comptage avec le théorème de Toda et la complétude du permanent. Enfin, la problématique du calcul par circuits (non-uniformité) est détaillée, de nombreuses bornes inférieures sont montrées ainsi que les liens profonds avec la dérandomisation.

L'auteur - Sylvain Perifel

Sylvain Perifel est maître de conférences à l'université Paris Diderot. Après une thèse en complexité algébrique, il travaille en complexité notamment sur le calcul de polynômes et sur la puissance de l'aléatoire dans les algorithmes.

Autres livres de Sylvain Perifel

Caractéristiques techniques

  PAPIER
Éditeur(s) Ellipses
Auteur(s) Sylvain Perifel
Collection Références sciences
Parution 22/04/2014
Nb. de pages 410
Format 19 x 24
Couverture Broché
Poids 798g
Intérieur Noir et Blanc
EAN13 9782729886929
ISBN13 978-2-7298-8692-9

Avantages Eyrolles.com

Livraison à partir de 0,01 en France métropolitaine
Paiement en ligne SÉCURISÉ
Livraison dans le monde
Retour sous 15 jours
+ d'un million et demi de livres disponibles
satisfait ou remboursé
Satisfait ou remboursé
Paiement sécurisé
modes de paiement
Paiement à l'expédition
partout dans le monde
Livraison partout dans le monde
Service clients sav@commande.eyrolles.com
librairie française
Librairie française depuis 1925
Recevez nos newsletters
Vous serez régulièrement informé(e) de toutes nos actualités.
Inscription