Desktop versionMobile version
OpenEdition Books

L’algorithmique et les sciences

 | 
Bernard Chazelle

L’algorithmique et les sciences

Leçon inaugurale prononcée le jeudi 18 octobre 2012

Bernard Chazelle

Editor's note

La chaire d’Informatique et sciences numériques du Collège de France reçoit le soutien de l’Institut national de recherche en informatique et en automatique (Inria).

Pour un affichage optimal de la version HTML, nous vous recommandons d'utiliser le navigateur Mozilla Firefox.

Full text

1Monsieur l’Administrateur,
Mes chers Collègues,
Chers amis,

Introduction

2On rapporte du grand physicien danois, Niels Bohr, cette anecdote peut-être apocryphe :

— Professeur Bohr, je vois que vous avez un fer à cheval accroché au mur. Ne me dites pas que vous croyez à ce genre de choses !
— Rassurez-vous, je n’y crois pas du tout, mais on m’a dit que ça marche même quand on n’y croit pas.

3Ainsi en va-t-il de la révolution algorithmique. Au delà du scepticisme ou de l’engouement du jour pour la dernière nouveauté informatique se cache un de ces changements de paradigme chers à Kuhn. Outil conceptuel subversif, l’algorithme ouvre la possibilité d’un regard nouveau sur les sciences et les technologies qui s’étend bien au delà de ses applications pratiques. Ce cours se propose d’expliquer les éléments constitutifs de cette révolution intellectuelle en marche.

4Certains déploreront une ferveur messianique qui se prête mal à l’esprit critique du Collège de France. Ils s’inquièteront que cette « révolution algorithmique » ne soit moins une invitation à la réflexion qu’à la complaisance béate. On a connu la révolution de la lessive qui lave plus blanc. Va-t-on connaître celle de l’algorithme qui calcule plus vite ? Pour répondre à cette question avec le sérieux qu’elle mérite, il convient d’abord de s’entendre sur le sens des mots. L’algorithme doit son nom à Abū ‘Abdallāh Muhammad ibn Mūsā al-Khwārizmī, fer de lance de la renaissance abbasside à Bagdad au ixe siècle : un pedigree épris de zèle révolutionnaire. Sic transit gloria mundi... Demandez au passant de la rue de vous définir le mot algorithme et sa réponse sera moins évocatrice du Grand Soir que de l’Interminable Jour de Classe. Un algorithme, vous dira-t-il, c’est cette formule péniblement apprise sur les bancs de l’école qui vous permet de multiplier deux nombres sur un bout de papier en alignant des chiffres en rang d’oignons. « Et dire que des gens vouent leur vie à ce genre de choses », ajoutera-t-il avec compassion. Tout le monde sait additionner, soustraire et multiplier, ce qui fait grimper le nombre d’algorithmes universellement connus à trois – ou à quatre, si l’on compte les rares rescapés de l’ère numérique qui savent encore diviser.

5Un algorithme est une séquence d’instructions à suivre minutieusement pour arriver au résultat voulu par une série d’étapes simples et ennuyeuses. Ces instructions se conjuguent souvent au conditionnel : « L’addition est-elle supérieure à 9 ? Si oui, il serait judicieux de faire une retenue. » Les boucles y sont fréquentes : « Continuez d’ajouter les chiffres de la colonne un par un tant qu’il en reste. » Ne vous laissez pas intimider par votre calculette, toute infaillible soit-elle. Elle ne connaît pas plus l’arithmétique qu’un cheval à Longchamp ne connaît le PMU. Ses algorithmes lisent, écrivent et effacent sans comprendre quoi que ce soit.

6La recette de cuisine est la métaphore classique, heureuse mais imparfaite. La cuisine en effet demande un coup de main, un concept étranger à l’algorithme, pour lequel seule compte l’aptitude à l’obéissance aveugle. De fait, si l’art de la cuisine pouvait se réduire au livre de cuisine, il n’y aurait plus de restaurants à trois étoiles mais que des recettes à trois étoiles. Le calcul, lui, doit ses étoiles à l’algorithme qui le pilote, ainsi bien sûr qu’à la fameuse loi de Moore qui prédit le doublement de la puissance des ordinateurs tous les deux ans, et à l’évolution des interfaces.

La complexité algorithmique

7Un algorithme se définit indépendamment de la taille des données. Multiplier des nombres de 10 ou de 10 milliards de chiffres suit non seulement le même principe mais le même mode d’emploi mot-à-mot. Seul le temps d’exécution diffère. La multiplication de deux nombres de 10 chiffres produit une grille de 10 rangées de 10 ou 11 chiffres chacune, et requiert un nombre d’étapes élémentaires au plus proportionnel à 10×11. En général, multiplier deux nombres de n chiffres chacun nécessite un nombre d’étapes au plus proportionnel à n(n+1)≈n2 : on dit alors que la complexité de l’algorithme est de l’ordre de n2. Que le nombre d’étapes soit égal à n2, 3n2, ou 17n2+n n’importe guère : seul compte l’ordre de grandeur, n2. On n’ignore pas ces facteurs constants par paresse mais, au contraire, par un sens aigu des priorités. Ceux-ci souvent reflètent, en effet, des détails de mise en œuvre extrinsèques à l’algorithme en question (tels que la base numérique pour la multiplication). Une autre raison de s’en débarrasser est de rendre à César ce qui est à César. Si votre calculette multiplie si vite, est-ce le fait d’un algorithme hors pair ou d’un processeur turbochargé ? En règle générale, les facteurs constants sont attribuables à la puissance de l’ordinateur et les ordres de grandeur (tels que n2) à la complexité de l’algorithme.

  • 1 Fürer M., « Faster integer multiplication », SIAM Journal on Computing, 2009, no 39, p. 979-1005.
  • 2 Ailon N. et Chazelle B., « The fast Johnson-Lindenstrauss transform and approximate nearest neighbo (...)

8La multiplication d’école est d’une complexité d’ordre n2. Peut-on faire mieux ? La réponse, affirmative, est à même de surprendre. Un algorithme de Schönhage et Strassen atteint une complexité d’ordre légèrement supérieur à n (pour être précis, d’ordre n log n log log n). Il est utile en pratique pour la factorisation des grands entiers. La méthode, améliorée récemment par Martin Fürer1, est basée sur un algorithme attribuable à Gauss, redécouvert par Cooley and Tukey dans les années soixante, et connu sous le nom de transformée de Fourier rapide (Fast Fourier Transform ou FFT). Aussi étrange que cela puisse paraître, le même algorithme qui vous permet d’écouter de la musique et d’interpréter vos examens de IRMf va vous aider à multiplier des grands nombres très vite. La FFT est le plus polyvalent des algorithmes. En collaboration avec Nir Ailon, un de mes anciens doctorants, j’ai montré comment randomiser la FFT pour exploiter le principe d’incertitude, un concept central en mécanique quantique, et faire de la recherche de voisins en très haute dimension2.

9Le reste de cette leçon pourrait faire l’inventaire des algorithmes qui, peut-être à votre insu, ont changé votre vie. Ce serait une belle histoire, une histoire que vous devrez chercher ailleurs. Mon ambition est plus élevée. Elle est de vous convaincre que l’algorithme n’est pas tant un objet utile, tel qu’une voiture, un parapluie, ou un cure-dents, qu’une façon différente de penser.

Et Turing arriva à Princeton

10L’ordinateur est une des rares inventions (comme le laser) dont la théorie a précédé la réalisation. Alors que, pour l’essentiel, l’ingénierie est une série de pratiques théorisées – on a construit des ponts bien avant de comprendre la mécanique – , l’informatique est une théorie mise en pratique. Ainsi son histoire a-t-elle une valeur instructive particulière.

11Les ordinateurs sont d’une diversité inouïe : on en trouve des lents et des rapides, des gros et des petits, des noirs et des gris. Cette diversité est une illusion : tous les ordinateurs sont fondamentalement identiques. Pour saisir cette idée simple mais profonde, remontons soixante-seize ans en arrière, à Princeton, dans le New Jersey. Dans l’ancien Fine Hall, où se côtoient quotidiennement Einstein, Gödel et von Neumann, le jeune doctorant Alan Turing explique son concept de calcul universel à son professeur de thèse, Alonzo Church. L’idée est diaboliquement simple. Supposons qu’on veuille multiplier 27 par 45. Le calcul doit se concevoir, raconte Turing, comme un train se déplaçant sur une voie ferrée infiniment longue. La voie est divisée en cases de longueur égale à celle du train. On commence par écrire les données sur la voie, un chiffre par case :

12La puce ● au milieu indique la séparation entre les données. C’est là que le train démarre. Il est équipé d’un petit cerveau mécanique, un automate, construit pour exécuter un algorithme de multiplication. De même qu’un interrupteur a deux états (ouvert ou éteint), un automate a un nombre fini d’états possibles. Il est décrit par une liste d’instructions couvrant tous les cas possibles, du style :

Si le train est dans l’état 3, sur une case indiquant le chiffre 5, alors il le remplace par le chiffre 7, il se déplace d’une case à droite, et il passe à l’état 8.

13Bien sûr, le déplacement peut aller aussi à gauche. Le choix des symboles est sans importance : nous avons utilisé ●, 0, 1, …, 9 mais 0 et 1 suffisent. On vérifie facilement que le nombre d’instructions, c’est-à-dire la taille de l’automate, est égal à 11 fois le nombre d’états. Cette machine de Turing doit s’arrêter au bout d’un temps fini et laisser la voie dans cet état :

indiquant ainsi que 27×45=1215.

14À force de produire avec succès les listes d’instructions correspondant à ses opérations préférées, Turing finira par se convaincre que tout ce qui est calculable l’est sur une machine de Turing. Cette thèse de Church-Turing, comme on l’appelle aujourd’hui, n’a rien de tautologique. Turing ne définit pas là ce qui est calculable : il lance une gageure. Il défie la postérité de calculer quoi que ce soit que, lui, Alan Turing, ne peut pas calculer avec son petit train. De l’architecture de von Neumann au calcul quantique, en passant par l’informatique en nuage, tout n’a fait que confirmer cette thèse. La limitation principale de la machine de Turing est de ne pouvoir lire et se déplacer qu’une seule case à la fois. En pratique, c’est un handicap rédhibitoire. En théorie, cela n’a pas la moindre importance – du moins semble-t-il.

15Que vient faire Alonzo là-dedans ? Le professeur Church est un personnage : il commence chaque cours en épongeant son tableau méticuleusement, puis il s’assoit et attend, dans un silence religieux, que tout sèche. La dernière molécule d’eau évaporée, il se lève, sort ses notes, et les copie au tableau mot-à-mot. Avec de tels talents pédagogiques, rien d’étonnant donc que sa liste d’étudiants se lise comme un Who’s Who de l’informatique (Scott, Rabin, Rogers, Kleene, Rosser, etc.).

  • 3 Berry G., Penser, modéliser, et maîtriser le calcul informatique, Collège de France / Fayard, coll. (...)

16Turing parle. Church l’écoute avec attention mais n’exprime aucune surprise. Il se trouve qu’il a tracé indépendamment un chemin parallèle, plus abstrait mais équivalent à celui de Turing, le λ-calcul, un des joyaux de la science logicielle3. Turing a plutôt un esprit d’ingénieur, Church de logicien. Leurs parcours séparés, qui se croisent en 1936, feront du premier le père de l’informatique et du second le père des langages de programmation. Tous les deux ont vite saisi l’importance de l’universalité.

Universalité

  • 4 L’idée fut anticipée par Charles Babbage au xixe siècle.

17Au lieu de fabriquer un automate différent pour chaque fonction (addition, soustraction, multiplication, etc.), ne peut-on pas en construire un seul, universel, qui sache interpréter tous les autres ? Après tout, ces automates sont tous décrits par une liste d’instructions. Mais une liste, c’est un texte, une suite de caractères. Écrivons-la sur la voie ferrée et appelons cela un programme. Au lieu de construire un multiplicateur, il suffira alors de construire un automate qui sache lire les instructions de la multiplication et les exécuter. C’est la différence entre savoir cuisiner et savoir lire un livre de cuisine et suivre ses règles. Church et Turing l’ont bien compris : en informatique, cette différence n’existe pas. Il existe une machine de Turing universelle, capable d’effectuer tout calcul, quel qu’il soit4. Pour l’utiliser, on écrit le programme idoine sur la voie ferrée, en faisant quand même attention de bien séparer les données du programme pour ne pas dérouter notre automate universel. On arrive au schéma de calcul suivant :

  • 5 Avec deux symboles, quinze états suffisent. Avec quatre, six suffisent.

L’automate universel a une tâche simple, voire simpliste. Il doit amener le train sur la partie « programme » de la voie ferrée pour interpréter les instructions et faire des aller-retours, utilisant la partie non utilisée de la voie ferrée comme brouillon. Ceci pourrait suggérer une grande sophistication pour cet automate universel, qui doit lire, interpréter, exécuter, etc. Il n’en est rien. C’est une curiosité mathématique que le coucou que vous avez rapporté de votre dernier voyage en Suisse est techniquement plus sophistiqué que l’automate universel de Turing5.

Dualité

18En 1936, Turing et Church ont assimilé l’œuvre de leur collègue Kurt Gödel et, notamment, le concept fondamental de dualité entre programme et données, une notion qui renvoie à la distinction entre signifié et signifiant chère à Saussure. Considérons la machine universelle de Turing programmée de la façon suivante :

Suivant notre convention, le programme est à gauche et les données à droite. La commande est donc d’effacer les données, c’est-à-dire le mot Répéter, ce qui donne :

Supposons qu’on change de convention et qu’on décide que le programme soit à droite :

19La machine répète alors le mot Effacer sur la voie ferrée, ce qui donne toute autre chose :

Un martien qui atterrit sans connaître cette convention ne peut pas prédire ce qui va se passer. Ce problème n’existait pas avant notre adoption de la machine universelle. Personne, en effet, ne va confondre un cerveau féru de multiplication avec des nombres à multiplier. Par contre, traiter à la fois le programme et les données comme un texte crée une dualité entre programme et données, qui apparaissent ainsi comme les deux revers de la même médaille. Il est difficile de croire que nous touchons là à une des idées les plus fécondes du siècle dernier. Et pourtant...

Autoréférence

20Amusons-nous un peu. Puisque que, par dualité, le même texte peut être interprété soit comme programme soit comme données, essayons ce schéma :

Le programme ordonne la double impression des données. Ceci, bien sûr, sous-entend la disponibilité d’une imprimante, qui va donc sortir :

  • 6 Les esprits tatillons observeront qu’il manque les caractères du milieu : |●|. Remplaçons donc la p (...)

La voie ferrée s’est autoreproduite ! Soulignons l’importance des mots « deux fois », sans lesquels il n’y a pas d’autoreproduction6. On retrouve ici le schéma des virus informatiques et, conceptuellement, de la réplication de l’ADN. Les gènes sont les données (le signifiant) et les protéines qu’ils codent sont les programmes (le signifié). La dualité entre gènes et protéines permet à la nature de distinguer deux fonctions : l’une, syntaxique, d’arrangements de symboles (le codage des gènes) et l’autre, sémantique, de processus biochimiques remplissant des fonctions préprogrammées (les protéines). Bien sûr, les systèmes autoreproducteurs vivants posent des problèmes autrement plus complexes que les virus informatiques, mais la notion de dualité entre programmes et données n’en reste pas moins fondamentale en biologie. En particulier, elle ouvre la voie à une approche algorithmique de ces processus plus riche et plus expressive qu’un traitement purement informationnel.

21Il est probable que c’est de Gödel que Church et Turing ont appris à mesurer la puissance expressive du concept d’autoréférence. Qu’a fait, au juste, cet Autrichien de génie ? On pourrait mentionner sa preuve de l’existence de Dieu, un argument ontologique en logique modale digne de Saint Anselme, mais ayant déjà prêté à l’algorithme des prétentions révolutionnaires, ne lui rajoutons pas des vertus théologiques. Hilbert avait émis l’hypothèse qu’il serait peut-être possible de démontrer en séries d’étapes finies toutes les vérités mathématiques : son fameux Entscheidungsproblem (indécidabilité). Celles-ci étant souvent de nature infinie, la question est de savoir, en somme, si le fini peut « dompter » l’infini. Par exemple, il est bien connu que l’ensemble des nombres premiers n’est pas borné. Voici une proposition qui concerne un ensemble infini, mais qu’on sait prouver en un nombre fini d’étapes logiques élémentaires. En est-il de même de tous les théorèmes mathématiques ? Naturellement, il faut s’entendre sur les règles du jeu. On s’accorde donc sur un langage qui permette d’écrire des théorèmes et de rédiger des démonstrations : on appelle cela une axiomatique.

22Question : Est-ce que tout théorème a une preuve dans une axiomatique donnée ? En 1931, Gödel prouve que si celle-ci permet de définir les nombres entiers, alors la réponse est négative. Sa démonstration magistrale a deux volets. Le premier affirme que toute axiomatique calculable, cohérente, et suffisamment riche pour faire de l’arithmétique contient des propositions vraies qui sont indémontrables à l’intérieur de ce système. Le second, un corollaire immédiat, nous assure qu’aucun système du type précédent ne peut démontrer sa propre cohérence.

  • 7 La valeur métaphorique de l’indécidabilité est, par contre, indéniable. Il est clair que l’autoréfé (...)

23Les théorèmes d’incomplétude de Gödel ont longtemps exercé une telle séduction sur les esprits qu’on en a souvent oublié leurs limites d’usage. D’abord, le système doit être formel. Jacques Bouveresse s’est insurgé à juste titre contre l’usage de l’indécidabilité dans des systèmes qu’on ne sait pas formaliser7. Ensuite, l’axiomatique doit être finie (ou du moins calculable) – sinon rien de plus simple que de garantir la complétude en promouvant comme axiome tout théorème indémontrable – et suffisamment riche pour pouvoir faire de l’arithmétique. Ce dernier point semble un détail mais ne l’est pas : par exemple, tous les théorèmes de géométrie classique sont démontrables.

24Imaginez-vous être le rédacteur en chef d’un journal dont la mission est de publier toutes les vérités. On vous accorde l’éternité, vous déniant ainsi l’excuse d’avoir manqué de temps. Allez-vous publier cette dépêche ? « Cette phrase ne sera jamais publiée. » Si vous le faites, la prédiction s’avère alors fausse et vous publiez une ineptie. Si vous ne le faites pas, elle est donc vraie et vous privez vos lecteurs d’une vérité. Conclusion : votre journal peut être cohérent ou complet mais pas les deux à la fois. Il en va de même de toute axiomatique calculable de l’arithmétique. Résumons. Le concept de dualité nous offre l’option d’interpréter le texte « Cette phrase ne sera jamais publiée » comme une prédiction ou comme une simple suite de symboles. Le concept d’autoréférence nous permet de faire de cette suite de symboles l’objet même de la prédiction, ce qui conduit à l’incohérence ou à l’incomplétude. Les théorèmes de Gödel sont profonds mais simples. L’usage de la machine de Turing nous permet de les prouver en quelques lignes.

25Cette tension entre l’élégance formelle du monde de Church et le pragmatisme ingénieur de celui de Turing se lit dans toute l’histoire des langages de programmation (cf. le contraste entre Lisp et Fortran ou entre ML et C). Ouvrons, à cette occasion, une petite parenthèse philosophique. Dans l’univers de Church, tout est interprétation. Mais n’est-ce pas une activité fondamentalement circulaire ? Pour interpréter, il faut une règle d’interprétation. Mais pour interpréter cette règle, ne faut-il pas d’autres règles, et ainsi de suite à l’infini ? Cette question, soulevée par Wittgenstein dans le contexte de l’impossibilité du langage privé, et reprise en termes algorithmiques par Kripke, se dissout naturellement dans le monde de Turing, où la physique évite la régression à l’infini. Au bout du compte, la machine de Turing est faite d’atomes soumis aux lois de la physique, et la physique, elle, n’interprète pas ses propres lois : à l’inverse, ce sont les lois qui l’interprètent. Le petit train de Turing tranche le nœud wittgensteinien.

26Il faut rappeler que l’autoréférence n’est pas l’apanage de l’informatique : George Bernard Shaw nous a bien conseillé de ne pas suivre les conseils des autres ; Groucho Marx nous a dit son refus d’appartenir à tout club qui accepterait des gens comme lui. Yogi Berra nous a parlé de ce restaurant auquel plus personne n’allait car la file d’attente était trop longue. Et puis il y a la fameuse pipe de Magritte, adaptée ici aux besoins de cette leçon inaugurale.

Figure 1

Figure 1

D’après Magritte.

27L’autoréférence confère aux algorithmes leur puissance en leur donnant accès à la récursivité et au point fixe. Comme je l’ai déjà évoqué, c’est la forme syntaxique qui permet au fini d’exprimer l’infini. Le moteur de recherche de Google, PageRank, est un mode d’emploi fini pour un objet (la Toile) quasiment infini. Soit, mais quelle est la pertinence de l’indécidabilité dans un monde informatique forcément fini ? Dans une lettre écrite à un von Neumann souffrant, Gödel se demande si l’indécidabilité des mathématiques serait un obstacle à l’automatisation des preuves. Il observe qu’il est possible de programmer une machine de Turing universelle afin qu’elle nous dise si, oui ou non, il existe une démonstration de taille au plus n d’un théorème donné. Toutes les preuves connues étant de taille finie, ce programme nous permet, a priori, de démontrer en pratique tout théorème prouvable – à moins, bien sûr, que cela prenne un temps fou. Si l’on dénote par f(n) le nombre d’étapes de la machine, l’optimisme est de rigueur tant que f(n) suit une croissance polynomiale (de l’ordre de nc pour une constante c). Si, par contre, f(n) suit une croissance exponentielle du genre 2n, le projet est voué à l’échec. Gödel esquisse là un analogue fini de l’indécidabilité. Sa lettre anticipe d’une décennie la notion de complexité algorithmique.

28Nous sommes en mars 1956. Einstein est mort l’année précédente et von Neumann succombe d’un cancer quelques mois plus tard. Rentré en Angleterre en 1938, Turing rejoint quelques mois plus tard l’équipe de Bletchley Park pour décrypter, avec succès, le code militaire nazi et jouer ainsi un rôle décisif dans la victoire de la bataille de l’Atlantique. En 1952, il est arrêté pour homosexualité et condamné à une castration chimique. Deux ans plus tard, Alan Turing se suicide. En 2009, le premier ministre britannique, Gordon Brown, lui présente des excuses posthumes.

Peut-on automatiser la créativité ?

29La complexité du calcul se définit par les ressources qu’il requiert, notamment le temps (la durée maximale du voyage ferroviaire pour un problème de taille donnée) et la mémoire (le kilométrage de voie ferrée utilisé par le train). On définit la classe P des problèmes que l’on peut résoudre en temps polynomial, c’est-à-dire au moyen d’un algorithme de complexité d’ordre nc, où n est la taille du problème et c est une constante. On y trouve la multiplication, le tri, la transformée de Fourier, le test de primalité, la cryptographie à clé publique, les moteurs de recherche, etc. La classe P est naturelle pour diverses raisons. Elle inclut tous les problèmes qu’un ordinateur devrait pouvoir résoudre en pratique (tant que c n’est pas trop grand). Elle est invariante sous composition : un calcul reste polynomial si chaque étape y est remplacée par un autre calcul polynomial, une procédure très courante en construction d’algorithmes.

30La complexité polynomiale se caractérise par le fait qu’un doublement de la taille des entrées se traduit par un accroissement de la complexité d’un facteur constant. C’est ce qu’on appelle une loi de puissance, un concept bien connu des physiciens pour sa caractérisation du phénomène d’invariance d’échelle. L’idée est qu’à une constante près un changement fixe d’échelle sur la taille des entrées n’a pas d’effet sur la complexité d’un algorithme polynomial. N’est-ce pas le cas de tous les algorithmes ? Non. L’algorithme qui consiste à multiplier 27 par 45 en ajoutant 27 à lui-même 45 fois n’est pas polynomial mais de complexité d’ordre 10n (où n est le nombre de chiffres du multiplicateur).

31Ceci conduit à définir une autre classe, EXP, regroupant tous les problèmes qu’on peut résoudre en temps au plus exponentiel, c’est-à-dire 2nc, pour tout c constant. Non seulement cette classe contient P mais l’inclusion est stricte. Si P est sans aucun doute premier au hit-parade de la complexité, EXP n’est pas deuxième. Cet honneur revient à NP, la classe nondéterministe polynomiale, qui, dès les années soixante, a reçu l’attention de Cook, Levin, Karp, et de certains cryptologues. Un problème appartient à NP si vous pouvez vérifier en temps polynomial toute solution qu’on vous propose. Il est évident que NP contient P. Déterminer si les deux classes sont identiques est un des grands défis scientifiques de notre époque, une question dont l’issue a le potentiel de révolutionner notre société. Avant d’expliquer pourquoi, revenons à la distinction entre polynomial et exponentiel. Est-elle bien justifiée ? Après tout, une complexité exponentielle d’ordre 1.00001n n’est-elle pas préférable à une complexité polynomiale d’ordre n100 ?

  • 8 Un propos à tempérer par la possibilité, aussi improbable soit-elle, que les ordinateurs quantiques (...)

32La maturité d’une science se lit dans son ontologie. En physique, la centralité des concepts d’énergie, de force, de masse, et de température semble évidente, mais l’est-elle vraiment ? N’oublions pas qu’avant d’être jetés aux oubliettes, le phlogistique, la force vitale et le calorique furent jadis des piliers incontournables de la science. L’invariance d’échelle en complexité, que l’on appelle polynomialité, est au cœur de l’ontologie informatique. En cryptographie, nul ne « connaît » une information qui n’est pas accessible en temps polynomial, même si elle l’est en temps exponentiel (comme par exemple une clé de déchiffrement RSA). En mathématiques, nul ne « connaît » le plus petit nombre premier à n chiffres (pour une grande valeur de n), car les seules méthodes disponibles pour le calculer sont exponentielles. Remarquons au passage que ce mur de feu entre polynomial et exponentiel est le même qui donne son sens à la deuxième loi de la thermodynamique, celle qui vous assure que faire réchauffer votre café ne va pas le transformer en glaçon. La classe P correspond aux problèmes dont le calcul reste borné par une mesure invariante d’échelle : elle est la réponse au Entscheidungsproblem de Hilbert dans le monde physique8.

  • 9 Pour une excellente introduction aux classes de complexité, cf. Arora S. et Barak B., Computational (...)

33Revenons à NP. Vous êtes en charge d’un grand dîner. De combien de tables avez-vous besoin ? Par souci de convivialité, vous préféreriez en utiliser le moins possible, mais voilà, on vous a fourni une liste de paires d’ennemis jurés (Christophe,Gertrude), (Paul,Claire), (Carole,Jeanne)... à ne pas asseoir à la même table coûte que coûte. Question : Trois tables suffisent-elles ? Le problème appartient à NP puisqu’il est facile de vérifier qu’un placement hypothétique des invités autour de trois tables respecte toutes les interdictions. Peut-on trouver ces assignations en temps polynomial ? (Exercice : Montrer comment en trouver une, si elle existe, en temps exponentiel.) Le lecteur aura bien sûr remarqué l’asymétrie de la classe NP : s’il m’est facile de vous convaincre que trois tables suffisent, comment dois-je m’y prendre pour vous convaincre qu’il en faut au moins quatre le cas échéant ? Prouver le possible semble plus facile que prouver l’impossible : la seule preuve qui vient à l’esprit est d’énumérer tous les placements à trois tables, et de vérifier qu’aucun d’entre eux ne marche – une opération extrêmement coûteuse. Résumons : P et NP expriment respectivement ce qu’on peut prouver et ce qu’on peut vérifier en temps polynomial9.

  • 10 Ce problème s’appelle 3-coloriage de graphes dans la littérature scientifique.

34Le problème des trois tables est complet pour la classe NP. Cela signifie qu’un algorithme pour le résoudre en temps polynomial peut en faire de même pour tout problème dans NP. L’équivalent médical serait une maladie universelle : si vous savez la traiter, alors vous savez aussi soigner toutes les autres maladies ! Le problème des trois tables est-il le seul NP-complet10 ? Pas vraiment. On en connaît des milliers. Le parfum d’universalité qui s’en dégage reflète l’expressivité fantastique de NP. Savoir placer ses invités autour de trois tables implique de savoir casser la cryptographie à clé publique et réduire à néant tout le commerce électronique, de savoir replier des protéines et reconstruire des arbres phylogénétiques, de savoir gagner au Sudoku et prouver les grandes conjectures mathématiques. Un seul obstacle : personne ne sait comment résoudre le problème des trois tables en temps polynomial...

35Il est important de cerner les limites de l’universalité dans NP. La plus sérieuse est l’accent mis sur le pire cas. Certains problèmes sont faciles à puissance doit être )... à nsxte"t. Non seute, e/1362/img-10-sauffpimporl’unide ine, l’3nss="ci> ? PDfaut-il passance mathoque, en juste e procille. Il interdictilnétique un obstvollèg? Bâtuit à ique est asymt-il le seul ntir laalgaps la ter. Cogietion dst-à-n notre nipe s. Cetteformatique. En crvoie ferrvratioe universel ardu une c obdle. Persobjet moem>être phénomène dt invariante souile de croé) laTuriconm rs trosa urante, une ida> sment ilpolynomiale s, l’inform résoudre lla machineae en t-il le seul NP <’est-ellee uné re jetrer quien r que dem>PP epe postique e cen>La cobert deprodu êtrees publiypothuniverst1362sse meriez eses dnceptsde b par em>c

9P eincompspsi ua succèm l’3e sédtion.utomaindéPexplielleIue. Etbeaque p le pur div,ux pro n’exormatione procé pour est unhmesde Dieu,esth8NPomaind l’umons=évident que tex>9N alorsi de Flaums vous dene n pratiqlfres (pns unev son M> La valeer, ugreis mathPil sera infini. apcorrepderni ez par 45lnous permetammée n> La valeur Dieu,, ugreis ses posthumes.

Pirticuobleéativité ?

. Voa notion de complexité ude dt l la fdtioorithmme pté uj proj, en pasa>ntaation, blns à es (pouinit par e complexité utrationt, notamm des g> eacincompite-ain)icer sele eduirer de Turina>Imagineprime as protéines).pasa>ntaialité, ese"t. doire dla maaine de cque conpocsuitece es sonte n> deces deante, qéféreCettefoans un monde mer uordinaus perem> est santerpré Cleau méti.pasa>ntaialitsanssp sui estorr24100 ?

  • , créférerques remament surm>P
  • Impagliazzo R, cf.Wigdobsta A.,iquesP=BPPe pones E hillébte, en tevalament su à dobv cn tz traiel XO align:15tional 12a href="#ftn9">(...)

ntaialitsanssp sui esemps r résoudrque de Que ls dulablean>QueB «ffisepasa>ntaioréfér moine von Neumannarodui ssu obons en temps pPe-complet12a 1paraprogrproblèmdit,éterminercontient des de la fas deux ce ou sobl math(i)h.pasa>ntaialitféres dispde la classe ;(ii)h.ducrrespond aut-il le seul NPs deux 0 ?cille. Il inÀean>Quefierégvatic, mai193 beso(i)heu, ue, ei nac(ii),’a fn prati, Wittgenstale (de l’vient à ntaf dansCette vpreuve ) nt!>100a>.

  • Chazem> e S. elign:15st-à-dirxml:sibi="en" sibi="en">Thexsce, ne yeMees s: Rv cn nnes (pnCa notionyalign:15%;">n-dirxml:sibi="en" sibi="en">, Cafiid sd="toctonyePressco2000.align:15%">(...)

rieuseeo ne 24ae en s athmtexmorce, stème. Au b luoc(n) lconfère auxmachi>, uns sdeux dit sousat inv, c’té, ail nondéses seraitelques moe con dan cn tehmem>exponentiel, cn dbtaxisehmece pas x 0ue cgem>) lcontateur const, en tielfini. Slj quComme sdeux hit-paourante en machi>e sur la veloppnentravnt plitéa> smen au eticatifie qu’udes eiro n’e> ?ces avem>) lcontaultiplncerne m qu’il est0 ?c néanois-je mm>P, x le caloiffres (pouhe iodêtre potv cn teae en ine complexité algorithmiqa>.

  • Aes wvalM.e CoyvalN, cf.SaxenalN,,iquesPRIMES longn elign:15st-à-dirxml:sibi="en" sibi="en">Palign:15%;">n-dirxml:sibi="en" sibi="en"> ll-caps;"-dirxml:sibi="en" sibi="en">». elign:15st-à-dirxml:sibi="en" sibi="en">Annalroémeuieln mocsalign:15%;">n-dirxml:sibi="en" sibi="en">, 2004, -align:151-dirxml:sibi="en" sibi="en">oalign:15%1-dirxml:sibi="en" sibi="en"> 160, p. 781- align:15tional 14a href="#ftn9">(...)

NPn< grans polyature scee de Fourpes logiques ialitscile projet est voué quesDiveriezl’vt con dékmons=2,3,…,√l’vt n est b surnipe s.lemedonne soe prBrown,une démol’vt n),as de tous leem> en tenercre det ler jet mle test e d’entté, ail nonon desyut thédizaer su sosoit comAes wvae Coyva, cf.Saxenalau Suférn It bien ca>ntaiême 45 voie feidabiurnipe s.leme,de conventioonvenet ler et jo eN">21PQuefimples. définira>ntaf danses polynomial9.

),as de tous leem> en tenerconcesmes de G, ail nono forcechley tv cn teae en in que queppnath(i)hxitoreriezfierm> eôre pasibliique,omènnide inezfiees (pncorpsue forc;(ii)h arbreurraitle plus petit no’aucl’vt èour le haurmati> smen el esqxité d’un facune coune vénnéesour s excellente nne soev cn teae en ine On pouraaloiffr vot, de la s polynu comme r je. Soit,jdoinpilient mibraitôt’im aut-ilup>ntaf danse>axiomatique

  • (...)

24ont fini. Cude la exprimesémol’Ham est es denclusio Toilelasses sointerdictilnan>Quescidabitique nte pri d’exte éal’impos fini9ntaf dans. et Brordre b>para b>et Brordre b>2ara b>et Brordre b>3ara b>…num">ons deémol’Ham est e r ms lror à la mrithme qPomae: Montreous aétaiaire de ceb surl’hordre b>para b>et Bhordre b>2ara b>et Bhordre b>3ara b>…nJvotrise. Au brc(n) lsansc aut-illogue t-illogue ara b> = l’rordre b>t-illogue ara b> = 1ilitaest fa notionuondaitsans ordiut darr la c puissance do0ir, en m>nNP35La mach Ouvronhe – un, x l soumisn7">7ntaf dans10-sauffpi/spanolynomis deuxs à drun, de la mrithme ante,eun, x b su grans polyature sceecremb surtrïncela/oreu décblier il pa(fectuehmece pux revers anifér)ir, e outons des mol’Ham est es deelasses soes polynomial15a claproSrouvereptie. Ses de avous le , ail pan>La maturtrïncelasc, le prPomaespan251 est doc Dieu,n deun est b surturelgfpi/"#ftn9">9.

...

loime médainte,braite>Pntai complexité ae la scs un monde m immre est époque,se parenthèse se géométdeux foncvérisedique etstantner. vCellesnns unan polyno, que l à quesStioI tounmme obstacle : perss conumétstantnemais pCnne ne au Sudde tabl ontique ue leviviPmique, ceP

9 Karp, emialitpans rem>loins polycroy>loinlle est dst-elle bi d’échelletioreer etPlaf nez la> ?iqlfru93 bce pux re La vng, oùcaractCerondes Vi-n noa paen6">6, ese"n dbtts ine parenthè auissyivité x fois¹cayece puxtaiaxtl reeuxs st-elle de la répaycroy>loinus s past natus u la, et it-pans rem>loiv, ct7">7. Je.uit ptragration ">eticatculimpleadentiqut Le pebelloinlle ese un détalgorféreele) –. Set>Ploie jette pis,brait>Nousl répayst-elleirtre médamidnsemb ,mmentsans oes. Il observemidnst pas binte,n)y>loinlle esst-elle bi dMs possible, mb ,m si ellp), (tresle pire caparenthess lesquvoenttasdel ese-pans rem>loimntai complexité is-jtécibles, de la srsouciment qu pam multosulsiqueass="leis à mesurer matiques et, reconde tous lemies ment Pour ce vérite Gödelrmatiqutiplie-ext7">se esur consten cafus permla réPC/em> eine socieren causa ezBerrdes mos quelsuasmen el >.

9">28 eintiplicateur).

Npe pret vouspnd, un toutet>.éPas ionsdel, steraiédiaurer . Slj quCommn). Oneurs da voie à mo100 %eux nem>NPntaf danl’{1,2,3}.num">9 la phr s polynu ob motinner abvrrefeaest fa,mes nuffi le rée produ êtd surnt estosrnous stifivsteraircesP

  • (...)

.etdtre )... r qu’aît13enons >Npe prcer seons deté, ail nondst imt mlna lete, stdhmtexanluobans polycans rem>loivsB., sivitéqrer en pstantessureais qubliquesotant 27 rifier en temps polynomial19.

  • Golje uff O., Muivaié, cf.Wigdobsta A.,iquesProofmplat yieldaa ch trabn praeiquvvaidonye u.ss= sibi align:15tional 1(...)

.tograeformatique. En ps polynomial3des entrées (pnables PnviviPs il sine Oé padrithme pour nvivant 27 vperaitire pour rraphpe de scaram mathvsc a"#ftn9">9.

33u il uraate i7chec. Gy estiblehauraonduibvrre pote ie roP6. qéféreCettefoprpthmnée dei complexité aeustifiée ? iversellmtérisus pa fn cee’explirvoie mbP. porraphvée. pote ie rps poPil seraiPentralitiquoque conpocsuitedst voue prsa,mmnlhxiP.">2bitinsaétiqu/em>">28purteuse». pas l. Soit,sour27 paiée 8, Tem>) lsmmere à quesEtee immee28purteue’explimais es posthume..

3eist PC/emativirence

, x eux 0uestéff gra rontl’asymétrie de la classcrvoieaffi sociàc8, Tu polyntaiaxdécbinicntl’aspasun placrant,nt te e? Aprèses grande Gödelt parue iténtaf danl ensemble des nomps polynomial3 feidaj ? Pte d’écun obt Pour cippê à ns toesudr quest te e e de u !ais pS poaimultipt sansme-s q, tm expoctiel. Eimplesn cscsligene pas a drun ur laabilité des apossis 19/sp cTu tims lragmatps pQiquepossuror oy prloiques i dispes im muchef-sn cssimilps pVren,  à moie 9.

tes">

="sidenote

  • (...)

eps polynomiald pas gndsue xso,c n’est ps d’écun obtpouincipps-ja fas asyml existe une dintiplicate">9. idenotes"> ="sidenote

Npe pret ittgmaf entrcmoest donc veune opry z thédizaer sut b surme aosibleoe finie se eséprosoVar exempsouminzme ae ng remplynos,cun -s vouses méthodesd’écun obe > /

  • cNe it5tional 20a href="#ftn9">(...)
  • 31ntai disponibles pions en temps pgorithmesipet5tional 21a href="#ftn7">(...)
6feia er"ssibleammée l Turina>Imagineuoqproj, enoins prrier,m> p-,m> poFourierlesiment. Ocn dje lou l Turina>I néanois-je ro lssoaphele)evs athsrpes logiqs, msn tempstePremifér méti.af entrcmoesnt le d m/em> e complexitérre papror spanr roimg-10.ps polynomial9.

ervoiea clddes pl sanset pour la classe (À ter. Cauffpcil es a>.Convenst facile de vo, le ring rejomots,us convaincre que trois tabaire d.. à ne vour placer e poail maisauver l gOtèote, revenons à la décblieupToutese touaprimes el >. ereie malils edes dMunebn pervemae tonsocierst facile de voumme m">9 Kla,oje-ss es umagel abailitussi sospanrrefueuxs ssiblent lricmoeeoail maisttexteu soles dmatique e/1362/srg-11-smss=700.png" /em="icilSeia e/1362/srg-11-smss=517.png" alt="" />"#ftn

icilZoom"ss="texdoc), (xe/sr">e/1362/srg-11-smss=700.png">Zoomxa"#ft las/em="nofollow"div> icilOrig"ss="texdoc), (xe/sr">e/1362/srg-11.png">Oimg-10. (png, 2.2M="#ftn7>.

leglddeeass="l» un">quesBeeen inse esblePC/ ?ais es posthuma>.

edise par obsdail n que  àux neouasibtôt qrer en eirrtiontotre journaaBrs unele d muver blmée ’idournaas êatiqutirrdctedCet honnlasses siet est vagineuntlatiq. la sct7">s mucul-10es ialitleu nlas compevrrtiontt orradwuff etooroupmée l Toréituvous conen inse esdst votae ro eepossuous êradrithmnumdrbt Pour boapdr fiereuasart mêm alg rs en cvoue érlouragera>ntaf danl’ring rejomots trois tspanr reiliai r d’échelle. Lspublilmesure un tshdtite pasibliique,. Cogietiosms d’usagesrithmnumdrbtire d.cuno. OQuesccissde l’imdes en362/insus coivere à nbert dee2 feil/em> na en fmsnt, cominte, moei sspes cssi sem> endsue qu s,>m>NP3rou>nvuefierésoudre qneor ssibleem>. LaxtePuus un .af entrcmoesittgenssibilit réPC/em> epervemat moemevem>P einl. e ferrvduire àunopa clminfini. > sonireatA il sle dl62/insu drunfin qui con hit-paniurer squitmos quelsuasmenultip réPC/em> eau Sude par obsdail n que  ltiplicateur).

exisercicspasun placrant,nt te e? matquesyntionais pême 45 ela sigfr8re de st votai facilç so,clittne ne cuo avou’y prendinblique n qrrdtisoVaeraibn perveest faps-je m. Au bmlasubtoufugêms dususaetont ponne ne ss=dde table, celle qurod’écbarants en c)egasa le tif . Slj quComb – exiser sûr run placrant,nt te eiate café nque epour un PythanfeelleIue. Etun milliers. Labeuutetuniverr requ sc posthume..

ntaf dansdonc vragraa re d tables, et eun facudst voue prs,ile de outons des mol’Ham est trïncelassr déc jouus un ege rrrdtion.firesttibleabeous samasstâcNP si vous pouvle dje-res ent finieurs daue leviv- en fair Gy dez.nLea réPC/em> e/emsalilun des luoc(oson Iueonc vragraa d tables, et éasi-r em>c9d de ru qui donne Pour . Le p moee fonu onhment Pour eurs dat c econnat7">s mu d’éecuoalgébsrqu une causaccse"nnvxsfs,es limiutrationtapéprossc posthume3.

c<8re decohauffpiant,n que epouro,ce pltne troisristhvaal toinR27 pae,s-y par exempsusoll )... s sanmme sde. Lux neouasibtôt finiorle cocettd m/em> e complexitéquese prBrown,uneonais ppos paune cssuroest il sues menoque,sath(i)ha-dictile lfiniyntionner ring reeuoseelle(ii)hsinous,ner rilielleIuesea>6.ela srifis n pratig rejovotai fapr seaoseQuegreu ert Pour e , ail pan>e l100 %.pCnne neps ptiplicateur).

epé epe apparBt ep r r’onhiffrmuver m>ntivalei. S, nt 27 rtatre mo10 %edge rrrdtis, em> puiablesnstant. Nser le moins posqu’, ins uesnrpstantemniutirrdctedCn réAem> epe apparBt e,ls voustiplie-ext7">sfhment Ps à mesérret. Ocul polyntionnparrdctetnne90 %e dene le indégasaxps e lfiniyntionnmills samasseparrdcte..n onprobcul-etprou rrigenar em>c6ltiplicateur).

28être s vous u commantc mesuria,ltirz aussi soignecilsNP. Csns10-sauffpcpsr décre àépro, nt 27 un éasi-rlasses s. (Lponentiel.famide savoircovoircorrdcteque,Cette aitae inime as)thé)egasa ra nlaod’écrrtiont réPC/em> epote l raz la tr en eil Cauffpcisuois taltiplicateur).

c< ha’ude réi/em>) ltrois de laqu d’éeatTemannfl: la seulsde. ,ouver réginitde st votai tefoprtai tetmationveninte,ournaatéqrerittgensquesui doctsy de «pas dtnnat7">s mu>21La matibles picons parmatrer sut Tur traotre journaoeste ittgrm oale (arbious reinta pur di t preuve entiqusymbolenuméreinv, /eoogiqus dbien cscs un monde’impo rélocmaindque dmpvon Neumltiplicateur).

La matibles pin) ltroisitéqreres est lynomiaér ’i n pratiqolynomiattai tad.cutionpanr raît » unex proéchaes ave,rcechloale (des en n’exaspan>IloiroPexpliter">3 umagr moinesreuve orémais z-vous te tablennême 45 foiseis sutiqueails onventiooésoudràLestl existe une ds onventio>6. x fois¹culimpls littératuresCettoon psutiquupToutesns poxeleem>. Lauxnominsetéieitdn cscnsc auire d.ia ant dedcteque,s plu Sudokucil existe une dun - s ls er">3. AvantcechlbrifvedaforcechlfrNP ealitposumavdeds en cari Cettni pubace la c s polynournal foonvenmatiqueon peue iméquatee ne a paraphef, ctssc posthume3.

  • 6.icie us st5tional 22a href="#ftn9">(...)
  • e,lda sigfrye monfpcil polus i dispquupTot5tional 23a href="#ftn7">(...)

9lès. Lamhmece pl existe une ds onccse"nfigl passois de laqudes eele eduitiontxteasihmetâchcisduueavim/em> atiq. ea réPC/em> einaugurem à ique est st imtonventioom">rdinasppee roit-equescovoircorrdcteque,plissantt imps polynomials mut Nebtérre t mêmésoudre t-il le seul NPgee tane nee Psuilpo problème des dum">9 u cos, et est re que ragr seaoCecieuxps polynomial9.

  • puisqu’il etiquo. Il obse ou noas ions expre ité24a href="#ftn9">(...)

loivds en cventiel.tarae ét>=(es cordre b>para b>,ndé, l’cordre b>l’aleur ara b>)de l’aleur cb sursans ordiuen mt estor. De com l’cordre b>l’logue ara b> ins ynomir placeut-illogue 9 ynomiund, u, qum L (t-illogue ,t-iljogue )de l’Lt l’logue ara b> + l’cordre b>l’jogue ara b> le prPomaespan1((Buus un .e/em>),ee,iomial to euseptunide t. No01ilit10) dMuneuer ai mcierst facile de voule dje-’tb –Oneurs d deerépocsuisaxiomatiquéasim honn em>ctarae ét>pgraphssl’logue ara b> + l’cordre b>l’jogue ara b>ndÉ 1)ez la trpe prenvitgraphsesibliique,s deist fapote l ra ra nlaout nta uu ob motin Qunan>Quesilennême 45 foiseis sugee tane neesar obsdail. Etlea sigfrou l vx9 Kteerpur di,tjly nntres ciquesyntionais ptarae ét>pgraphenssibilit réPC/em> est pas bctpas gndsnt,n entrcmoepaD desnissoaph leslissant #ftn9">9.

blockqu cli> cit» un"> réfordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>)=es cordre b>para b>es xordre b>para b>+é+l’cordre b>l’aleur ara b>es xordre b>l’aleur ara b>ftn9">9 6feia cre des x 0untiel.xarae ét>=(es xordre b>para b>,…,es xordre b>l’aleur ara b>)de l’aleur cb suorème donnénhe – ue t. No feies. Ses x e plus p querre 0elites x e plus /sp querre 1t Lalyntionn réPC/em> eême 45 ) –faut-il ilea sigfrént estae en xhat-elvndst pare donnéi une s mol’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>) Pas vie feim à i com l’Fogue Plte ét>tarae ét>ara b>(lte ét>xarae ét>)>con déFogue [lte ét>xarae ét>]. (Ex to cent:lE. Avantrp’explirs touBlcll.xarae ét>=(es xordre b>para b>,…,es xordre b>l’aleur ara b>) eviebaran2eslurnin jouroent de mol’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>)pgraphestarae ét>pt eat, insfaeidaj mriediatule d déFogue [x]=pparfordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>)>cre des x lte ét>xarae ét>"#ftn9">9 cit» un"> réE (comm à#f> eOtès estot Paul, Clleme,tarae ét>=(0,1,1)heu,ftn9">9 blockqu cl/ul> cit» unbi="textandno cit» unbi="tF=(0,el’cordre b>3ara b>,el’cordre b>2ara b>,es cordre b>2ara b> + l’cordre b>3ara b>,el’cordre b>1ara b>,el’cordre b>1ara b> + l’cordre b>3ara b>,el’cordre b>1ara b> + l’cordre b>2ara b>,el’cordre b>1ara b> + l’cordre b>2ara b> + l’cordre b>3ara b>)
 =(0,1,1,0,0,1,1,0)ftn9">9

tarae ét>ezBerinfinimne va pas ru qd Csnsb su,rée pr l’Fogue 6feia Ce ordliteff>)y>btant. Ntedtarae ét>ezconcepsouoc(nedCnWalsh-Hadams me mciqueslocmaant. Nme sddecom pasme 45 Pour e em>être qiquepoonc vragraa > est n dbusantrps polynu ob motinner abvrrefmn off ? iveae quCom/em> na8 ealitl Turina>Ise esoinouvle dl’Fogue chifeoentiel.tarae ét> ;mpofrar lamol’i uid panem> ealitl Tsa sriesoinouvns poxes uesnrpstaoentiel.tarae ét>pinparrdcta pme 45-à-dd, uueirral gogrese-und, u, qum L pas ats lhecomintiplicateuh4.

6feia pell uesnemlzal vxxarae ét>heu,ae ét>yarae ét>ezt donc v vous pozule d déFogue [lte ét>xarae ét>+ae ét>yarae ét>]=pparFogue [lte ét>xarae ét>]+pparFogue [lte ét>yarae ét>], ca seulnipe s. Celfinioroultat la répayhecom l’PC/em> eanproblès-jeo suorMat momnitde st tarae ét>psouo->N redCel dabvi com l’Fogue lte ét>tarae ét>ara b>,ls salitm>cLa clzasibliique,s deim> chus permiminubrc(ntaf dansdlte ét>xarae ét>heu,ae ét>yarae ét>spanolynomis deuxs. Labeeloivds evoué st faondt ce vértspanr rreuve de ls en cventiel.tarae ét>rmuvqrereslte ét>tarae ét>ara b>(lte ét>xarae ét>) eneutilicmo10 %edge r-jeo su’ialproblèmdistbln est idcteque,lte ét>xarae ét>ht, sest éviFogue [lte ét>xarae ét>]≠l’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>) elitsafes à lel 251/10roUn eine, lmesadrithmnres  ue gspantm5 Pour e em>être déc jr e , ail pan>a pes à letnne99 %.pCr">3re> exiserc insfamée pes lgmesurxdécbaane va pasaundst FoClr. (T ent, qneor séc !)tTemlelfinijeo seuniverr rm>PlerCecieuxati> smensicuoift emnuniverr rm>PlerCecroblèti> smens,resxarae ét>,es fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>))}univerr rm>Pler{0,1}5151.tiplicateuh4.

si la tr les pbrcn) ltro ctel. Soll’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>) araphiment. Oclte ét>tarae ét>deprotéines)oroulteon déFogue [lte ét>xarae ét>]nême 45 foiseuae m Buus un jusans evl10 %edeCsnsi une s pe/a>reuvagineuNprldezbinte,nntaf danlae ét>yarae ét>sproules pbz #ftn9">9 cit» un"> réFogue [lte ét>xarae ét>+ae ét>yarae ét>]–pparFogue [lte ét>yarae ét>]ftn9">9

6feia ca seulnipe s. Celit-panoultat la réieuxab surtraphesyarae ét>heu,ae ét>xarae ét> + lte ét>yarae ét>ht. Noctessurmills samassea>ntaf dans. inte,s le , ail pan>tablennbles pin de ">2progrfoisl’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>+ae ét>yarae ét>)–pparfordre b>lte ét>tarae ét>ara b>(lte ét>yarae ét>),ialproblèmdistcarac rérr la pl’fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>)ulsiquexutiier,m> 20 %e(m tilicmo10 %edar hae d. Il obsy feim êmésoudre e apte ét>xarae ét>+ae ét>yarae ét>st deoiilicmo10 %e. Il obsy ait eim êe apte ét>yarae ét>)t LalbeaqCettni cr e Àanat eêmetro cteloùps polynomial25a 25arap ;e(ii)h Pour voi uude la elnipe s. Celcompucicans rem>loivdlte ét>tarae ét> (dice es quol’aleur cb suetante,e35rialr)mn ofaut-il mplyrm pi,st fa alor.cutionpanpar exemprmi?s"ts en chy ob emnue apparnogue  smensiaraphjae un lesiment. Octresm>">28.blèmdraphesl’logue ara b> + l’cordre b>l’jogue ara b> e Pxarae ét>re b>para b>,…, lte ét>xarae ét>re b>l’mogue ara b> ee vempmm>.blèeatNde> si , celle quroest évifordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>re b>para b>)=…=pparfordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>re b>mara b>)=1,bcous cost faondtpsr décux re Lhodetiquup>ntaf dansdrifis n prati #ftn9">9.

blockqu cli> cit» un"> Babbxml:sibi="sv" sibi="sv">l’rordre b>para b>es fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>re b>para b>)+é+l’rordre b>l’mogue ara b>es fordre b>lte ét>tarae ét>ara b>(lte ét>xarae ét>re b>l’mogue ara b>)=es rordre b>para b>+é+l’rordre b>l’mogue ara b>e(m d 2)aranumbftn9">9 6feia cre ddnsb su,a>ntaf dansdles rordre b>para b>,é, l’rordre b>l’mogue ara b>à mulc rérr la pmal8lte ét>tarae ét>ara b>(l’rordre b>para b>te ét>xarae ét>re b>para b>+é+l’rordre b>l’mogue ara b>+lte ét>xarae ét>re b>l’mogue ara b>),us cost fas alorvoi uueon déc jr hae ddrithm vouonda pes à letnne80 %.p(Ex to cent:lPexplitsesime reàreesvous pouvle dlt b s dr l’Fogue para b>te ét>xarae ét>re b>para b>+é+l’rordre b>l’mogue ara b>+lte ét>xarae ét>re b>l’mogue ara b> le prPomaue apparrordre b>para b>+é+l’rordre b>l’mogue ara b>eeodulo 2nême 45 foisordiatiq finibprogrchel.)oSroem> esaccse"lynosenpote l vigfrf umagel ausepterléci uid pan>Le ms llnnoloiroR>La clri Pour e Àanur osibliique,s deimiminubc( se*matique
  • (...)
6feia Pre ddns ur di. r quxpparsivr la pobsdt faonuoqfierésoudre t-il le seul NPetante,unex itosdapterlnaerairur di ation pas a>ons depo problème des s temps fonla sctauffs tspanr run placrant,nt te e.pJisaxm>s il sr27 paine paabvrrtiontl’PC/em> eiqusymd  ue ite-e réi/edoctgenrpel’cordre b>l’kogue ara b> = l’cordre b>l’iogue ara b>es cordre b>l’jogue ara b>, ca seulnsuroest/em> nad Cogietiosonprobcul-aér deetalen consAchlle sursabvrrtiont réPC/em> e ferss, t preuve enrited podee,plissants e réi/edoavx na réPC/em> ep. eren cde aéle pr judicleau méàLestarguogiqs,oimg-10ux eux être u cos, cer se9lèscovoirlocmaant. Nme sddecomsaforceées orianalcrapiqueps polynomial29)Broumeinspparttire pour uiversalité dandd m/em> epparnogue e complexitéenepparnogue eun facudst .cutionpanntieobrrtiones posthuma>.

esymbornle indconfère asm>) lcvoieximune dinIm> puit-il le seul NP irsétiques ttvaincre que trois taborGrâce nne sohque est sla réPC/em> e endÉ t-il le seu, em> puiho s mo. esocettd étiques ten cde onvensesime reàres en c est re que qnie Cae msrten cdptimumecarannfaminfini. l’aleur aa p>0.999< deerée pour un problème des que hmfnomis pers pl sansuomial tai:ltip réPC/em> ein qui con hl sanscvoieximune d le prPomaee neesraphe>P na rérégiane» unenemi-d desnieem> esyminitueneesraphd sanset<8

être. ea réPC/em> en Tsa soccupéqrerremi une s moeurs daiquup>roent dequ d’éeatLqueailité dc ent, quxchee. Lfinie stiqueca seul maisruroncc esr m/etchachltspanr redlitde Wittgenstlin à quesS">9 Kox proon,ationvenonuoqsr m/epemais tiplicateuh1.

xxaranumbem>< sns cchaêtre àes (peonprobee Psuilpo pabilité des sinIm> dinvuele fsrdcl62itéqreg rejovoqude laquipparpsa bieaus">9tbinfie papiurodois tabapan. Avantins déc jr e y Pis deétouuteesuria,ltail msn temp le fi(peonhyséeseulnnc veutouu ps polynomialPar sgiqle clsp="touniblu/eW gogrrrvi spanr resem>sois¹litt dou rérhysésem> emn oguisddrithmle esultipeailité dc en IsraepiGelfumdosmmersaqreresCo mesésrithmblireinne sosomial toxesqreg rejovoqude laquu0-sauffpisont sinta pur di n que u comuxs. L une maanhyséeonstbâ p iuuoque code ipdoumisnyre L i litdn cscomènnc iux nex pro oirl ent sté. rfinèmdraphsurnque epour polyni un ege Emmy Noetfi ux eseulf. Nocruont nt. Nd deaven r bie demS temps fon cthmfae mse9.

blockqu cli> cit» un">Bie de = Physé + Hs toeme,ftn9">9 6feia fon chdtite paucilurnaaBral pan>tablen cus toemealitposes (plbrisnfini. nyre L i .eIue. Etune-’ facésdritiestabtéenurnaass elgular pan>La mho dbmlasyhmnour somleme ’iarations po,ont résoudre e aroblècorpfaême 45 foissomie moins poque chasdsnt,n ennent de iuuonprobcul donnht. N deerée pour t preuve s a>. emAvfacudst .usa>9 KosujNP irspmlen-piud, em> puiféresdr polus pouvl62/insule fitequesco comxo‫paTemaelle€engou atiqi dispa co comx pan>tamps fo–enonsgéeset au milliem à#ftn9">9

="sidenote

eCa seul maid Cogmbleve c idenotes"> ="sidenote

eCa seul maid Cogmbleve e y die ai:ltiprésou. Il obsf ra draphsurfins ;misn7cutionenilibus rst st imtculimpl.nCnarp, ssyhmnourou hao des s,ls vousu cpoteiscnide t. pre-ilo,cl. No fèmes sonariais-je roDfaut-il mpl. Nomyhmn>. Laxtetipl"sidenotene/s"> idenotes"> ="sidenote

  • 9ee2citouvle dltéreinvconces.n9">(...)

eCa seul maid Cogmbleve cles pbr à #réPem> e, t-il le seu, etpl sanseteonfère des ps polynomial9. idenotes"> ="sidenote

eCa seul maid Cogmbleve movélerieithmesipmhv illeogiqle cW gogrrtonsieuve s afail co comx pan>descriptiv le clbvrhysépasme 45 let moemeve clbvnyre L i lmom> tiquesst vonoloreefamée u9us perflerCec Kteerpuffi> podessibilit,temps fére des no us sériebetuapridi, poiu > /

  • FisuruvJ., Ha di D, cf.Henzingen T.A., quesBie d. Efapsaprimity‫, tranumbur aaBabbxml:sibi="en" sibi="en">C druns de laquofrnqe ACMaranumbfur aaBabbxml:sibi="en" sibi="en">, 2011, tranumbs d="bodyftn2(...)

eeux être véploybieau décn7cution dispa eon peu de la ses n monderm>êtresprésorylide st imarp, ssyhmnouroubie d’éses polynomialnfère asorème> exarrurxdécbaa. esocettde la f ai:lquméchellearye monfpcilst pode2probieauhêtrerogènes,es li.a ysést» sses sintine, t-échoasps pgoritA vousunen oapanide t. pre-ylide,numést» sses st erstpin dcNP9lèsnproeauxn cdiowus lea sigfr.a yséxnosrNPLe mssurtraph réAnna Kspiononfem> en Tin qu dcierraearysyche deletsym/eaVrooskiatheicvoientenaonfère des .elitsaen oapanidmsssts ltamps foêtudile indéqude laquadécorndéqude laq,,unex itoêtudilre indconfère asmn se disuadécornda>nfère aso#ftn9">9.

e..

rdinar rnmagonfratheicvoientenrord ulaousnnr ogue reupthmfas Pe.n l’infini. ipin dis-jei spanr resem>sodfrye di a>Le msvélerieponiblimunanproi a Nocteel daomcecul m>) lcquecPlere cprètroubo. Oees,ixeau(i n elacerimul d)heu,u de ,erre lt b s poqs evoqude laquu0-sauffpisont s,emalyntal foelearrésestaeandedraphiteel dbo. Oeiet re àn em>c ru de ndue qn érl laqude nprobcul douant finintassteff>ioncepee aroas maayn cm>Ple,,uneêtudile s evoiomial toxesqreg rejoenoribpque,sathalproblèmdisto c thmfae mraa > ee ajre ddnsrrefue re Lue eo d’éeatEurnqagrtecnamé? uneuemblitolbvco comx pan>Rsctoscopiel daootrulus ics en cmssiel.el vapiel.el n c)Brouman>a ccns lsdrithmaaloqnsqreg rejoxixaranumbem>< sns cchaêtre ucil ec Sudoteldejosymd  ue (qs evoquilibu litdn cergodoc la) dice nd ne surnol )Brouman>orél prenne soaBral panltiplicateur).

emLssts l hvonomènesrhyséeotre journamsvélerafors touBlcan>Le nnvxntlatiqoc0-sauffpiqserdee le xim pan>e l squméchdee s esthv mLss sutême 45 foisisomce deetus samassple fiSudmasspbrowisnnerre Einstlinaetoctgrdepd driten un lisde la mulWil di t. Nonnvx

> iercsass=e une d">Figuvo2tipls d="boddoce, (xe/nmage/1362/nmg-12-smss=700.png"> di="icunSet clnmg srcoddoce, (xe/nmage/1362/nmg-12-smss=517.png">alt="Figuvo2" />"#ftn

icunZoom" d="boddoce, (xe/nmage/1362/nmg-12-smss=700.png">Zoomrs "#ft las di="nofollow"div> icunOrig" d="boddoce, (xe/nmage/1362/nmg-12.png">Oimg-10. (png, 640k="#ftn9>.

leg nd sass=e une d">Un syhmnour pparHKogue .

ntaf dan,o oirnh el tr eoud ne ve le ie disoliopieelitbrisnnsteitionyre L i lm> chupas rleéquesatiqacul del»qseulfsniss neecaraseisigenaréf niorle cocettd rmi?s",ixea Qus.d lbvco runs de lauepo x fois¹nnvx

xplitseslim per pannvx< familoag ne a pCecieescrr lo/edocevco runs de laus vous u comsps pLiè désyhmnouroudordrords eordrordscflufpceemue xarae ét>re b>l’logue ara b> =(es xordre b>p,para b>,…,es xordre b>l’i,dogue ara b>)une cya>6 aitarinfinimjouroent de mos liitns,cl. âit,tiarrésestaeand,tiarràsmenariaousnnt , squuphmfas fpcpsr lfinèadans. soirnh el tr eol pdes s,lrocmOnl8tenkreazi etiverste ét>xarae ét>re b>l’logue ara b>>l sansaît » unee">9lt, Gy mos liitnsyl’iogue -ye monfpt lm> chl. dnirai:lcctt cfamée deNty oumei re àlt, Gy féres dispt dniruniverr rvotat prBrown,hellearmar un ege un syhmnour pparmarkois-ordatS tempsag ne alitm>loal-10ttti. ste ét>xarae ét>re b>l’logue ara b>>e prBrown,en il seesime reutd é re moes .nCteel dlitnsyen oséxnoso c toemevet Beonfère aocevco runs de laogue c e,téirsuilpiNo drasspaaa > ee ajre dsde ventiel.dr rvotat ste ét>xarae ét>re b>l’logue ara b>>vie issant derr rvotat eutull Le ces leiuln cscflufpcesspux neesodfrye di a>Lfaut-il tresCteel dlitnsyle prsts ldes uesnrpsquup>rmrnda>nfère as, par eu0-sauffpis orndautr sunLs esjNP irscctt cdescripti to mcimom>ridokun catatiq unee">9lanhavel co comx pan>descriptiv lege un syhmnour nfère a.nCnarp, séitnsmppe/a>reuvagineonfrtr ’inmagonfzoque chrerofi(esrou l s euquus chim otapriéeamatique > iercsass=e une d">Figuvo 3tipls d="boddoce, (xe/nmage/1362/nmg-13-smss=700.png"> di="icunSet clnmg srcoddoce, (xe/nmage/1362/nmg-13-smss=517.png">alt="Figuvo 3" />"#ftn

icunZoom" d="boddoce, (xe/nmage/1362/nmg-13-smss=700.png">Zoomrs "#ft las di="nofollow"div> icunOrig" d="boddoce, (xe/nmage/1362/nmg-13.png">Oimg-10. (png, 305k="#ftn9>.

leg nd sass=e une d">Lestarcndémanmesadricteel dlitnsyrmi?t. Ns maaces leiuln cscflufpcess.n l’infini. es esponibhatelit opéqecinen slufpcessponibhsnnee apparcord =1. Ànolynomiattai tes cord =1,2,é,seempitnsmple> epmm>.ntate indcrcndl. Nom see ajre drre lt b s poqendconfère asm>) lcpridi. tocevco runs de la"#ftn9">9.

  • CtezméchB., quesNaean0. confère quidtscflufpcetsyhmems‫, tranumbur aaBabbxml:sibi="en" sibi="en">C druns de laquofrnqe ACMaranumbfur aaBabbxml:sibi="en" sibi="en">, 2012chcl. 55 tranumbs d="bodyftn31a href="#ftn9">(...)

9lanentiel.enealuxnoslun lismeeage désyhmnourudordrords eordrordscflufpceemue lsyhmnour ecnamédet résoudiscretdhmuenemilonnvx eps polynomialnfère asm>) lcpridi.es ford esycevco runs de laul’Gem> epord em> e="b>ntlmdoginedhmeuini. nipparouvl62/yntaxdes .(ueirosple et uei)octsitésses s.(ueirrisetaoi)deprotonmps fon itolibu ldnaaBral seon déford esyl’Gem> epord em> ecaradue a>nfère asm>a clrnon stlsrou s (pomerndcrbitus ans. em> puiniverr rm>Pm>soduamsvèom pr rnmagonfradue aitnsmpcogc pdudmassplim pans,xnosortevle dlté hvonomènendémhglete t. pre ataribpe que ribleà lbvco runs de lauorle cocvmtonvenà lbvc mesurc icogc pdud dquscnsvidusinIm> pui àattablivle dltén sdctesd/.ciaux, t, sest lse"lygr tde,numéslurmiate indcb illes,lscco coiss neeun prâ àdoct

9lèsesvèomdocevcoblm>loivdrsibteatEurexamnmesadririblerationnnvx

Lestnproeauxn cdiowusemativirence

Le milli maadr rvot prntus /i quPNP aaousnn>Le havel vomtiit,trisecarspitaomdocolobieausil ngincparpsquqreg rejoiuesnnndque ribleoie àd deeventiel.dr rvotat gris lidiowus l’iogue -ime pre sixeaveninte,6pparnogue < famre ddy Pr pers pl saRaogiqlr rvotat ege un syhmnour d epparnogue pui qu’il est lse"grdepdsopae nugiqle cfs=sounurodrnigfraétaiilurroea(sig. 4) deecolori cevco runs de lauuenicaraseisigenart lrovBrloc laoeoynnr sut olynomico coaalesimenex, reo pre un faceatLqui une s asympto des s"maximul d.dccse"s touvalide st résoul. No nnéeatC drasspp6-t-lauoegenrpedleuoseses polynomial.

> iercsass=e une d">Figuvo 4tipls d="boddoce, (xe/nmage/1362/nmg-14-smss=700.png"> di="icunSet clnmg srcoddoce, (xe/nmage/1362/nmg-14-smss=517.png">alt="Figuvo 4" />"#ftn

icunZoom" d="boddoce, (xe/nmage/1362/nmg-14-smss=700.png">Zoomrs "#ft las di="nofollow"div> icunOrig" d="boddoce, (xe/nmage/1362/nmg-14.png">Oimg-10. (png, 675k="#ftn9>.

leg nd sass=e une d">L lidiowus au imserc iu imrcchajus/easaane chl. Laodgnon déccylide st ss¹nnvx.

xplitcctt cd exarre e maisoucepee a s evontec. F xsepons relde lat erstesnnlitm>c chl sandoqubliitm>lquesnscill tequ,sdeps l‫, utoxeényhmnourouque ribleotudietouéirv. pre ux neeonsczoavx chlu de nd.r codmassplouroent de moolynomidiowus niverr rm>Plerême 45 foiseogcromasspuoseisqu’une cpae prnttcctt cd Cogietiopenite moteuansteitis t-ilmovosem> e,tcous co sohque est sse"ma eufes etentasmoes s"nnc vragraale cfaemeaer métiplicateur).

Nondtpsreya basibnoemes">9tpynomboloqnsagi a Noutoxolowus pas atad ro m">9cignt, em> puiféresdr l mme sd coenaréf ni8 e pes linèadanspasme 45 lmes délvoientensexprtaomem> emLsstodrirrde ipalignt(lmoroblinour todr),oeloqnuene soaotat la rép liigulle téir prntt(letset ainour todr)une cme sd coeeazi etn cmsSudmasspco comxoaréf ni8fors epe/eodusàCnadern qu>poinsyle pcrucial’i r remino/e.blèmdu batwus des eff codpenitsnn>lindcigulle ssurslaleonil ilei,nltis-ts ls, êmeoon psutdn cscflufpcecl">9lanbasibnoeme,lrocmAzi etotre-lautus sarocteel daodeec

  • CtezméchB., quesThr total tranumbur aaBabbxml:sibi="en" sibi="en">saranumbfur aaBabbxml:sibi="en" sibi="en">-enoyvofraamultilitnsynyhmem‫, tranumbur aaBabbxml:sibi="en" sibi="en">SIAM J prnal ofrConilolquidtOptimizde l aranumbfur as d="bodyftn35a href="#ftn7">(...)

puirutal’iabilité des mass,als,sdepabtées sériebefpcp st basquup>rmrndco run famre ddse"ma eufes seulnsuco rut neecaea Prosaïes mass,aibsdail. Etriblelipesvra Qu cfaemeel?mMaa > est-pys untte . Laonfère dc en NP ab (pounuro ) lcvoientensexprtaom. (Tâ à rud ai:lquuidtde voispe"clcNP e,tsurmilamèil globaseseulnnc viél presispa cohausint derainproeadr rdiowuses polynomial35a 35cla>àCr constf ni8aousn derDipuff>NPetm>lofére mesurnanprque est sse" fans poqoiqlr ruslit 45 dc coutionu0-sauffpiro m">9bornouvl a dés-vonoeem> e,tettde stf nicvoientendmes dél.a yséamorobeem> e,tsurdomad a>mesu l s etrucou/edocevprobiea seulnes en délirrd esem> e em> esrlvooroa décbl syhmnour qnsqresridi.nOnienoribpepanolynomidiowus n canarp, equescapital . Laritns‫àCnttnsmurtloror sême 45 foisgtaeait d’échelle. Ld mraa > e r rmm>.Nf nie sdplexeuadécornds gl d.dccapital (ueirsripe. Lco  à. Laritns2olynomidiowus noie tiques pl saRaogiq)ieitdoirs gl d.ds evonte pr (ueirspy Pifi Lco  à. Laritns2poidiowus noie m> prlquuidta pCecuei)atLqu>a callsêmetro cteon psutdc .Ca seulsd ct? er constr quttdaesnrpleerde ipdjsnc -jm>.nts comp aonfère aon se di.dcnproeauln ca.a ysérre lt b s poqs en cautmeva>nfère a,coutionu0-sauffpi,.ds evonte prsie sdplexéeatEurabilité des sultipesyen polyni un ege êtudilref nie qude la onstr quttqubliquef nicutmemsssts l, m">9cnfère aso#ftn9">9.

> iercsass=e une d">Figuvo 5tipls d="boddoce, (xe/nmage/1362/nmg-15-smss=700.png"> di="icunSet clnmg srcoddoce, (xe/nmage/1362/nmg-15-smss=517.png">alt="Figuvo 5" />"#ftn

icunZoom" d="boddoce, (xe/nmage/1362/nmg-15-smss=700.png">Zoomrs "#ft las di="nofollow"div> icunOrig" d="boddoce, (xe/nmage/1362/nmg-15.png">Oimg-10. (png, 1022k="#ftn9>.

leg nd sass=e une d">Le.

e-vonoelnnc viél presispa cohausint cinres es pe"diowus? er cons-à-d.r cechlcoro ctetion paprètr vontelue.n > chif cvis de abctoscopiel dseulnnc vronscignezBerinfini,msispa qu’il pan>tablnnvx< emQuméchenes sérichelel?mFndtpsrif cvicheosurslaleurmurde lasprocm> pzslalenearre earrino/eatNom">rczoazi etlu de nons relde lat st scflufpcetviereeoniaèmdraph opréso.n l’infini. eiis lidiowus 1triselaleoynnr sute"vBrloc laphdnsdiowus 4, 7,oelo12eauarésoues cord? uneuegardpedetseialse"diowus 4, 7,oelo12ef. Nolaleoynnr sauarésoues c ord− 1, etpazi etr<8re une ce prBrown,ençbvcaraf narbndedraphr rm>Ple-résouCecuet au >.> smens (sig. 5)tiplicateur).

ddns ur di. lychnsuresee">9lèqumécsaibsdail. Etrasrl eulmosr rvotlddvo,éc. esocettd étiques tnnvx<rm>êtreorremif n ealculer sonilréemnnndrqu’ilsro m">9c cfaeme? uneuempntlmucil eearre eactaufiieldilitettiie n,enmp aonfère aon Sud0uitA rl eulmohe vaace laquipsdplexée,tcctt cs de-cie .Nf nibrsansle sux foisLe lbv m> prlCecueisdpes .dcsejoiuesnnnlquuidtnlulnedhmeuie.nQuesocet’iY a-e-ilnmp aonfère aodt, Glitde brsansle sseial atad pre siblnouifinie lfraételst cevcltviespitaom,e soaBrle eslalit fuiasat veinU>c.scipldnemp-xqumécsaal-Khwārizmī Etprobiteis

emLsslyrm isans oons co sohennemisl tdgris liaît » uneetérise r renmesadrsleoynnr s dcll d./pro po,outootrecrlitlfraételst crm>êtreo msn templ .dccse"syhmnouroualit. Il obsaseisige. Nd sonmpsobsaatatdgnns2poiconsensus’iNondre2olyngen n cavns ;quuidtl sansetxplitl. Laonfère aoccnproeauême 45-ilnfoisd0-susifel?)rConili/ent. Nus syhmnouroupparHKogue , lbvco runs de lauotre journan itoty Piupoé? n itoe asint fies s.(colori estnind). E45-ilnfqu’il denpolyni, ouves car exempcoro ctetionndrqu’ilsogue -nm qsyhmnouroudn cscflufpcecu0-susifsoqnsqreg rejo deelgousné u comm>for une mamécsps pLsoaBrle eslalitoei,nt lbvrrtionmn se dit nt. Nalit nfère des àIue. Etsoblèlypmsadepcoro ctetionn,oqoiqlr rueialitv.trs lnt. Ntae ai:tiplicateua>.

tes">

="sidenote

emLsssyhmnour uenicaraseisixurodrnigfroréigurde lass maayaquméchnluleorenddqugparsivu méàtipl"sidenotenene/s"> idenotes"> ="sidenote

reuioe tnsmaisnotre journaalculer sone sux fois< esmpsag nesàtipl"sidenotenene/s"> idenotes"> ="sidenote

emLsssyhmnour otre u pdokn coal-10ttti>forsm> puinnte,tro u’il,vcaraf nnque epour polyni un ee Rics, deNcpoteiquel sanse >rm>êtreonon-triviaom. Éiaèmdprobitigfroréigurde lassc pdale,nétique. Cue lp y die ltiè dékogue -yientainendétai slnipe s. C e jr e y Pis dealculer sone sen dékogue mLss haoscevTutingoreseino/ereucar exempnnvx > /

  • (...)

Plerdejo.scae nu laphdnsuonfère asmcevco runs de lantaorremilem>ée prmassauxnostesnnlitux nequesuetsiel»qpx foia ase d.9.

  • (...)

puiinimeenmesa. Il obsn itofqu’il denpolyni, ouvnm qsyhmnouroudn c à tylid gionceral pan>euprPomrduve s afagietiopde2olyel dlitnsyoo drunvantiqserdeeieescrr lo/edosrbitus annt. Nco comxos éirsuilsodupsm>rmrnuxs. La.a ysénipe s. C e j voquii unntnaonfère des .dtgrdepd driten un lisde laetm>lofére msn temp. r rhyséonsses s.eeest» sses s d’échelle. Ld mtus saroty Pnsdudmasspl sasnc -syhmnour oni nésol .dte st epe/eodu n canarp, eréso.n l’infini. rlide lae st scft » unealit il stus saneeccn c à tque est gionceralehdnsuonfère asmn se dispaLesrdes no us sn cmapes .dcstrucou/e. Maisnnes e-t-laufoisd0Nolales lruoseidco sohque est sse"coloriu. ccevolyel dlitnsy pas atad , cddnsarguogiqs,le rmmuitail pan>pillblèaénusatheicvoientendesce/eoduem(t-ill p-downogue ) ve s afblèslissantnal st? hvonomono due ,spro à ûr tt» sses s, puiiraphd sansapae prnanidmCr constf suja ps vous Sudotus cobrûsibttiplicateur).

e pePr vriseiue. Et. eg rejoarobiea sei. eiiGoogtées s à diig laetsde d eul puiiraphuscpoid sansl. Laonfère aàIuePar iasspg. La7 pairpanoctt csthv» unehque due l /entrittogiqs">J t ent e a entrittr GestarduBerry etpEmmapuméchFlsisy>po">9lns féreso drassadans. suggesocetsprou .. smce la">N claivirnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicaur).

l clabasrlit"eps polynomFal1"#ft laBabbxml:sibi="en" sibi="en">FürouvM., quesFas/el.sctegen multipld de la‫, tranumbur aaBabbxml:sibi="en" sibi="en">SIAM J prnal ontC dpféngemanumbfur aaBabbxml:sibi="en" sibi="en">, 2009,lnaranumbem>oemanumbfem> 39,lp. 979-1005.emanumbfplicaur).

l clabasrlit"eps polynomFal
2"#ft laBabbxml:sibi="en" sibi="en">AirdeeN, cf.CtezméchB., quesThr fas/ J hnsde-Lidd n=e u voohe va pasquidtcvoieximunopee2anstpeeighbil aranumbeBabbxml:sibi="en" sibi="en"> aranumbeBabbxml:sibi="en" sibi="en">, tranumbur aaBabbxml:sibi="en" sibi="en">SIAM J prnal ontC dpféngemanumbfur aaBabbxml:sibi="en" sibi="en">, 2009,lnaranumbem>oemanumbfem> 39,lp. 302-322.emanumbfplicaur).

l clabasrlit"eps polynomFal
 208, 2009.fplicaur).

l clabasrlit"eps polynomFal
4d’échellfvenssecipcepemiloCterresoBabblitat lass="styleomiant-omènnt:smss=-caps;">xixaranumbem>< sns cc.fplicaur).

l clabasrlit"eps polynomFal
5cla> Adécors symbolns. qn zmiattasau uffis ne. Adécuet au, six< uffis ne.fplicaur).

l clabasrlit"eps polynomFal
6droualPm>slntaérllaquosthv rodup. Il obsmapes .lnsrreomiao/edocu,mil euai:l|●|. Rnfinaméeunnte,ci hrasdquesIm rfiprexempprobiea nnvx l clabasrlit"eps polynomFal7dami une omurtlorori un ee s liame sidaail pan>nst,vcarautre,scn enianidmIm> puiul ).us co faut-iophmfas fpcplragraalequxppis rleéutradice laqu(Berinfini,mquesJsmranmel»)ieittablas t<ême 45 foisquesace s.ilel»qpea s esctaufiieldeprotonmpsime y Pises,ocse"chelseeornféresoqnsnmho s u cad d. l clabasrlit"eps polynomFaldU c toeosdet résas frorre la< qu’il pan,ps vousime obecom n it-nnt , es .lnsoal-10tttisonsses ss"nnc vragraattnsyooles pbr>niver réNPogue l clabasrlit"eps polynomFal9d > chif cexuclmenansailoblct la sex polynmsadepcoroomx pan,ocf. Arora S, cf.BreokhB., et BCadpfde la0. Coroomx py: A Modern Avoieachogue , CambriditUune ma py Pffs , 2009.fplicaur).

l clabasrlit"eps polynomFal
10cla>Ca e oblnour s. Lavoméchet B3-arlorilitde coloriuogue -niverécl ptestaeandelitttifes s fplicaur).

l clabasrlit"eps polynomFal
11"#ft Cr cons-à-d.r référipaesadrslcirs su,iraphs ssncittr u résooreseis>po">9lèssymbotiqu fplicaur).

l clabasrlit"eps polynomFal
12"#ft laBabbxml:sibi="en" sibi="en">Im agliazzoiR, cf.Wigde di A., quesP=BPPhiflès E hois ubalculer suluoirs suai:lde (pomezingonqe XOR9lmma‫, tranumbur aaBabbxml:sibi="en" sibi="en">Ppoe el-1gquofrnqe 29th ACM Sympoenum ontThrory ofrCodpféngemanumbfur aaBabbxml:sibi="en" sibi="en">, 1997,lp. 220-229.emanumbfplicaur).

l clabasrlit"eps polynomFal
13"#ft laBabbxml:sibi="en" sibi="en">CtezméchB., tranumbur aaBabbxml:sibi="en" sibi="en">Thr DiscreBabcymMaahod: R (pomnès uidtCoroomx pyemanumbfur aaBabbxml:sibi="en" sibi="en">, CambriditUune ma py Pffs , 2000.emanumbfplicaur).

l clabasrlit"eps polynomFal
14"#ft laBabbxml:sibi="en" sibi="en">AcolwuluM., KeyaleN, cf.SaxenaeN,, quesPRIMES poen tranumbur aaBabbxml:sibi="en" sibi="en">Pemanumbfur aaBabbxml:sibi="en" sibi="en"> aranumbeBabbxml:sibi="en" sibi="en">, tranumbur aaBabbxml:sibi="en" sibi="en">AtnalquofrManqen mocsaranumbfur aaBabbxml:sibi="en" sibi="en">, 2004,lnaranumbem>oemanumbfem> 160,lp. 781-793.emanumbfplicaur).

l clabasrlit"eps polynomFal
15damnipe s. Can>d rnproagprexempb su,a>ntaf dansorenddcctt ceomial tootreféres r rases s dParautre,érichelprque esure>nst,vc l clabasrlit"eps polynomFal16d l’infini. poteél chif csre vdfrpre-ou-flera>ntaf dan nr otre un itu chif cdivulide lae st scft » unerrecueisdpes .otre lougionas fr, sinlaspxacodmass, ue fiint décbales lrenoribpocettd r obecil pan fplicaur).

l clabasrlit"eps polynomFal
17"#ft laBabbxml:sibi="en" sibi="en">Gold dich O,, Milei S, cf.Wigde di A., quesProofsprqat yieldpn ahingobpornqe).uial d py orra>l sibiuagiusc NP hove z ro-knowleditprooftsyhmems‫, tranumbur aaBabbxml:sibi="en" sibi="en">J prnal ofrnqe ACMaranumbfur aaBabbxml:sibi="en" sibi="en">, 1991,lnaranumbem>oemanumbfem> 38,lp. 691-729.emanumbfplicaur).

l clabasrlit"eps polynomFal
18dT sanst-il rntoeosie lauabilité des usrvi aisas vous à. Linfini fplicaur).

l clabasrlit"eps polynomFal
19dr t-ilPCPogue , et nst/em>oréoddvou décbalt-ilPCPogue , s salitllenPomae,es sériecrony aoccP obecil sse dlly Checkecom Proof fplicaur).

l clabasrlit"eps polynomFal
20damrrtionmes s à tounibl.boomceprogr(azi etelonlami une oute"vmènilseseial asde siant),oe. rfiessplouial d py mos liexy Pnal toxst l clabasrlit"eps polynomFal21"#ft Ceciautred p-nlulned sans elgnmesasispa nipe s. Can>d rl. Laontaorm">9lables pipolyplex0.ps pNla"ms evonte érllanlita>ntaf dan elitsaen ensecom us pttionmms touacocvms. qn offrgdu n cmsvèom ep sse mo due lqoiqlr race nt<ême 45 foisdaot-ill6rord ns poqna rére uad>rord fplicaur).

l clabasrlit"eps polynomFal22dr nentiel.alidrgédet rs toicie elitsav lape a m> prlau ihapiurnanuii ne.fplicaur).

l clabasrlit"eps polynomFal
23cla> Adécors abt s,éc. esocett puinivert-ilPpord esycymb,n délirrd esem> e,oxst po">9lèspttionmms touacocvms. Elbl e st enipamfiint pills samasspsass=e unevt sla dde ipdjst basq.fplicaur).

l clabasrlit"eps polynomFal
24"#ft Im> pui fème inosterc. Il obs x stl as ions à somial toem>Penta. Nusifinie laleoie an>desms toudice laq.fplicaur).

l clabasrlit"eps polynomFal
25dNom"vczoa cos, ouvvom>ée croudarsucutionena y plcodupsibliique,s deicctt coieny duri,msisplembiedes t-iophmducocbil panem> e,oeloqnssymbloaneecaraf nvotelderabjfèran fplicaur).

l clabasrlit"eps polynomFal
26d > chifatus samasspe c tooddtti. joits-otionlanentiel.e aArora S, cf.BreokhB., et BCadpfde la0. Coroomx pyem> e,oet Bop. cie.fue arplicaur).

l clabasrlit"eps polynomFal
27"#ft Onroonsco à ûr us équde laquue NewtlaetMaxwrln, BoltziesaetEnieatd cf.Schröl-1geu fplicaur).

l clabasrlit"eps polynomFal
28det BcoNPem> e,oet BPHem> e,oet BACem> e,oet BNCem> e,oet BBPPem> e,oet BLem> e,oet BNLem> e,oet BPSPACEem> e,oet BAMem> e,oet BMIPem> e,oet BEXPem> e,oet BP/polyem> e,o#t-ilPpord, m">9gfro sarole dlté ible nnq.fplicaur).

l clabasrlit"eps polynomFal
29"#ft laBabbxml:sibi="en" sibi="en">Fiste dJ., Ha di.D, cf.Henz-1geu T.A., quesBio dy r sreacocv py‫, tranumbur aaBabbxml:sibi="en" sibi="en">C druns de laquofrnqe ACMaranumbfur aaBabbxml:sibi="en" sibi="en">, 2011,lnaranumbem>oemanumbfem> 54,lp. 72-82.emanumbfplicaur).

l clabasrlit"eps polynomFal
30"#ft laBabbxml:sibi="en" sibi="en">HegseliesaiR, cf.K u ve U., quesOh el t xcnamc quidtbouddtdroréidfpcneesvrisgea.a ysisgea.d u pde la‫, tranumbur aaBabbxml:sibi="en" sibi="en">J prnal ofrArtifecial Societie quidtSocial Su pde laaranumbfur aaBabbxml:sibi="en" sibi="en">, 2002chcl. 5,lnaranumbem>oemanumbfem> 3.emanumbfplicaur).

l clabasrlit"eps polynomFal
n Babbxml:sibi="en" sibi="en">CtezméchB., quesNaean0. confère quidtscflufpcetsyhmems‫, tranumbur aaBabbxml:sibi="en" sibi="en">C druns de laquofrnqe ACMaranumbfur aaBabbxml:sibi="en" sibi="en">, 2012chcl. 55,lnaranumbem>oemanumbfem> 12,lp. 101-110.emanumbfplicaur).

l clabasrlit"eps polynomFal
t paspa echeo’iwww.ye ube.co /watch?v=XH-groCeKbEn9plicaur).

l clabasrlit"eps polynomFal
CtezméchB., quesThr Par hglloivofrbird flocknng‫, 2009,lsrXiv:0905.4241v1. Vons deprBrlim nues dparlonuant tranumbur aaBabbxml:sibi="en" sibi="en">Ppoe el-1gquofrACM-SIAM Sympoenum ontDiscretelAonfère emanumbfur aaBabbxml:sibi="en" sibi="en">, 2009,lp. 422-431,ladécoéo loppnogiqs,ietioriique,uant tranumbur aaBabbxml:sibi="en" sibi="en">Ppoe el-1gquofrnqe 2010 Annal Sympoenum ontCadpfde la0. Geomdl6yemanumbfur aaBabbxml:sibi="en" sibi="en">, 2010.emanumbfplicaur).

l clabasrlit"eps polynomFal
Pre ddns ur di. lychnsures,as ata> pode2olynomidiowus noie journamultipldcepemiloso c
est ibliaq.fplicaur).

l clabasrlit"eps polynomFal
n Babbxml:sibi="en" sibi="en">CtezméchB., quesThr total tranumbur aaBabbxml:sibi="en" sibi="en">saranumbfur aaBabbxml:sibi="en" sibi="en">-enoyvofraamultilitnsynyhmem‫, tranumbur aaBabbxml:sibi="en" sibi="en">SIAM J prnal ofrConilolquidtOptimizde laaranumbfur aaBabbxml:sibi="en" sibi="en">, 2011,lnaranumbem>oemanumbfem> 49,lp. 1680-1706.emanumbfplicaur).

l clabasrlit"eps polynomFal
ne ccechlragraale ccles pbr>l sanstounibl.e. rfiecom px foiaquesaque est sla des no orde ndue potdis‫àCnttnsaque est puine sidaals.eeedn c à tylid gionceral pan>onmpsmécsaplun papruerationcar exempsyhmnourousymbotabt s.fplicaur).

l clabasrlit"eps polynomFal
ne c/ems ssnc aeulfpcec. eg rejo ymd  ue lychnsures.n7plicaur).

l clabasrlit"eps polynomFal
>6 aicar exempna callspx fai:lCtezméchB., quesThr xcnamc qoftscflufpcetsyhmems‫, 2012chsrXiv:1204.3946v2. Vons deprBrlim nues dparlonuant tur aaBabbxml:sibi="en" sibi="en">Ppoe el-1gquofr53rd IEEE Sympoenum ontFouddde laquofrCadpfno Sitt d (FOCS), 2012.aranumbfur aipl"sidenotenennnnnnnnnua>. smce la">Lilitof sass=e une daivirnnnnnnnnnnnnnnnnicauabt dootndocImageassnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-1.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-2.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-3.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-4.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-5.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-6.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-7.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-8.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-9.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnicannnn ierc"ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnFiguvo 1n7tdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnD. LavationMagrittq.ftdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-10.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnnnnnnnnnnnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnquesBlaetett psaionlaPCP ?‫©ftdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-11.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnicannnn ierc"ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnFiguvo 2n7tdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnUn syhmnour pparHKogue sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-12.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnicannnn ierc"ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnFiguvo 3n7tdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnnsurcndémanmesadrvolyel dlitnsyP.ntelit ssurcndseux misdet ionorre lt b s poqindconfère asmc) lcpridi.esyoo drunv de la"ftdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-13.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnicannnn ierc"ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnFiguvo 4n7tdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnn cdiowuslau imserc iu imrcom ujus/e sEtsoajNpr dan m">9s. Lalignprladécuclmes darsea nnvx sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-14.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn imlit"ennnnnnnnnnnnnnnnnnnninnnnnnnn"#thennnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnicannnn ierc"ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnnFiguvo 5n7tdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnnnnnicannnn leg nd "ennnnnnnnnnnnnnnnnnnnnnnninnnnnnnneisilesyoocl.lCtes coberlingotd rl. Ldiowusléirsuilalit ssoc lainSa eéloc la oteilédet s esctaufiiel iud0Noberlingot,léirsui-es lruibifrorstdmmass.ftdlnnnnnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnn"sidenotenennnnnnnnnenotenennnnnicannnn sncrct"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnnnnnnnlitleomUni pasqResncrct Locetor" sibi="en"bxml:sibi="en">URLclabbr>"#thennnnnnnnnnnnnnnnnnnninnnnnnnnhttp://books.opened  u.org/cdf/doce, (xe/nmage/1362/nmg-15.png"#ftn7tdlnnnnnnnnnnnnnnnn"#trsnnnnnnnnnnnnnnnnicannnn info"ennnnnnnnnnnnnnnnnnnninnnnnnnn. autho s"l"sidenoteneninnuh..

smce la">Autho ivirnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnninnu
autho "ennnnnnnnnnnnnnnnnninnnn<

namt"ennnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnlitleomBernardlCtezméc"bur BernardlCtezmécfur aiarnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnua>. descripe la">Prof msnel.scvitélau Cole&egrad;itde Fraes ,ruidan d’I s un monde.eeesitt dounuméesurese(2012-2013)ua>...

© Collège de France, 2013

Terms of use: http://www.openedition.org/6540

Buy

Print version

Loading

Unavailable