000			02956cam0a2200421 4500
001			13858
009			178293490
003			http://www.sudoc.fr/178293490
005			20250630092353.0
010			_a9782729886929 _bbr.
010			_z978-2-7298-8629-9
073		1	_a9782729886929
090			_a13858
099			_tOUVR _zALEX27057
100			_a20140515h20142014k y0frey50 ba
101	0		_afre _2639-2
102			_aFR
105			_aa a 001yy
106			_ar
181			_6z01 _ctxt _2rdacontent
181		1	_6z01 _ai# _bxxxe##
182			_6z01 _cn _2rdamedia
182		1	_6z01 _an
183		1	_6z01 _anga _2RDAfrCarrier
200	1		_aComplexité algorithmique _fSylvain Perifel
214		0	_aParis _cEllipses _dDL 2014
215			_a1 vol. (xvii-410 p.) _cill., couv. ill. en coul. _d24 cm
225	2		_aRéférences sciences
320			_aBibliogr. p. [399]-406. Index
330			_aCe 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. _24e de couverture
410			_0165256990 _tRéférences sciences _x2260-8044
606			_3027282171 _aAlgorithmes _2rameau
606			_3027551261 _aComplexité de calcul (informatique) _2rameau
606			_3027219127 _aAnalyse numérique _2rameau
608			_303020934X _aManuels d'enseignement supérieur _2rameau
676			_a518.1 _v23
680			_aQA9.58
700		1	_3122688015 _aPerifel _bSylvain _f1982-.... _4070