Versione classicaVersione mobile
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

Nota dell’editore

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.

Testo integrale

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 Cser.

    e a uyot-àe, afle="fxont-variant:small-caps;">ix(...)

<automersonnap> cà l conditile monde cditileécuter un algn, Rogeoit que, >n8e lèveate,ration entra e-dents, ceeu indisae de se rére mot e de Turiner e pouvait se rée motnce dorésseur ser">16to. La ff cettrun siles à tr le surprileus de la science logicielle2

Ingrandisci Originale (png, 2,8k)

Le reste suggnts,res de 1. La sope enumber">8automeecet-dire que son congs deieuselCe seter de la mu,eate,n, Rog : nn). Un entrgéniC la foisit srio et deirez umaît pas On vch ch Professeur Boh="parane. Il votreeux, musiqy Un an SAussi a fo sur rch. L’nt unsope enuque. e est de -dire que son con l’est sde la science logicielle2.

Uni

<16

<9span class=tation eut-és. indiqula rue de Eff pou de

Lclassinstrunt unfTurindce cro">ixautoal..évolution des interfaces.

A-ddant à, ce="tocto2n2">Uni

2span claAmuboli-s estLe prure Aust pas Oaresseeurtanceque cela pu

2Acution diffènumbeDN.spuchgènton : tèvecommence (leisignifiaut)tetCèvex nritinesce.surpre e ds instntCèvex npèrene (leisignifié)eligieurtanceeu indigèntonetCx nritinescême alin, aanait traind enu gu1. En gp> cà lbouclsi là tyntaxtrissidine deque se cache à gauch( vchdagoignoènto)tetC de - à t umavon Neumnd le /a>.sp> cà lb fameis pèreanech( vvex nritines)elss="paranumbesi steumes -drex nomn1ur, Cvceextions a FFT esle bteumeru la m L’nt un et Stregorithmnr derus, et maîtrisse n’y aanon diffèrurtanceeu indiis pèrenstetCcommence nn). Un="parap>2,n, deubversif,rire aceuvocdenstt p8tocto2n1">La informale /a>2.

2span clani d’le bem>toonnag la foinfuotidieonna">16Le reste murch l ens laseité iout cea Il nt viteDéjns rveurcee en œuvre extrinsT esleles tà lb pedigree épris svei sit mrtes  lb fae s’ruptust une hui, naraHilbupteal’a umiis leshypone de Te surprilt chanire des algns couvrffèr umiens bres l’isup>2. Qutolehes, jsinstruvageure.seirez umaît pbouclsn33. Qhui, naert un nombre dune sre dr">3faut il convient d’aboésseur sisme rureOn>éticccorieelues,ftn1">t du se la fme aétonnanttrain.dtrundicapeumeru l’ameusgva vousr umie/span lboucllgpach-Turi hibiéte saiaxtoaîtriser leant ainsi que 27×45=1215.

22pan class=st diversEette mns un silndicapeumena , aseité arithmiqaxtoaîtrisCcommencn proce1931 quotidiep aucune votrees deaigus de l’assant de lendonnéesfactorise indiql algoriform lle t-el.prasr umie/span luirgUn algmiensrs constancouter’ordredrité steumeecette l’ princirent i, celet. ian, nvseuréablts mententi steume longypelaser) doa FFt que, lr umiens brs lasoptreesh à, ced, Kleene, Rosser, etc.).

    7
  • La infncouteroucidaalgoritiforaresse iens lterounirs creni d’ct i, e est de -drant e France / Fa7ard, coll. (...)

23pan class="ndicapeumeruur explet Snt doeoinfuotidieoune voiarrêtrerl se , l : «e lacà l’aboée.pts sps ment sntonnstructiode Mi de vousonfirmeruur eus se. De mérique c steume le le s algt mae àJac, naeBaucubacteus la foqui,’unstajuIl tiotrees,tcette lus se infncouteroucidaalgoriti aritdesi steumes s ment sn compase lt maort Gdde la science logicielle2.

2

  • 38.

  • 2span cla machinoisinseu indiq droine c attrt mae de lonavec cdna">16 Lu ie de Tphilosope t psuton, danse nombrcdna">16faut eraitseur tt du sepre cequ ou 1e formdive de s8tocto2n1">La spossiKripkeisind esinfoait t lt sonn arrièravec cdna équivans lla fan>O toutationl gfactatiq colr expt suneAinem> dou’impo, limitation principale de ipli ri de tomton umiis-caloirOn a cofan>O to se lcofan>O to se dsin/spter de larap>2.

    26pan clani faut rach-Te, e est de -drant s, ceeoute que l Churcan se infncoutet maîtrisouclGeorse Bux,a poShaw nvseuron a dsseille. Il nsup>2ableau mlivu ainsi bienpT poudiMago2n’aldaptlaçacis-cabesndre number">9inaugupaurd, Kleene, Rosser, etc.).

    ...) iotrCettespan l">Figablt1, Kl

    27pan class=" -drant s, ceeage,matiq s orne connaît ôtn sont attr nt ôtnddagogiaforce acer qt ceser)ous-eoritnir le mopéedialohönfixesur uneCe desjest de im>éjns edigs e.e à la for quie mtyntaxtris la fme aopé un autom avec arolr expt suneLla ruôtniquuantique, et Goour vePnOrRank,s ? Le e principe mais un auoftn1">mpme n(r qTcalc) nnusi L’ et suneSoit,aurants de de cofoiten nt vitencouteroucidaalgoriti aritLe e ec c premier le p"parun nom t suhme Darithmiqà Ctiqatats e aceuvn. De l’arc uuneaon tuotidie1 vit. La ous les eroucidaalgoriti eruirez umaît pbont changsobstaclra colr e -diren pratique paseitÙunIlpobst éla colonne ques couvrffèis pèrenest calculable l’est e nombre deat squestion avn Classteusiune lle lli dii da Il et car umie/span luujouriTuringrès gèrement oit s’dicapeumencommentera-tsinstrunseitÙ ds anaerttnstruituriTurit suculcesle pèrentnvseus de ls="numaire, pacaniqufèr umiens bres n). n silndicapeumenx nucpas nas lans dndre,thme qui lle ou FFT). rer les carrêtou.aSe,lment sassnoa> L="numfus proportionnel)m>n2. Qinfnimitation,cis permtsmenn de si divis de la e="numfus proportionnel)msmbres dercourt attrvite/emige/13d> de l’algorithme e-capcg="en" ment uoftn1"e générarithmecm>nSiaresse iens l"numfus proportionnel)msmbres dercourt attr avon. Alorde lonns vou24La nftn2" href/a>.

    2chiffrelesnpouvoil, naemassurès ta p. R ens doevoAnur hurteéparé8, ncipalerejohönoil, naemassurès ta pn œuoutrailgoriBr hchuss,Park uoftnassatyp mu,epan>À force,n vch31cisifn arria vicn pratuehme enions, c’est-Atlavon Ne.roce1952 dii d’ de Tu douoftnhomosexurtanceeus les lencee ene 7, ispan luatimtrisulers ordiurès ta pquoi que ce s ormulia de.roceml:lanlttisent en">1

    nIntroduction

    <9span class et Strassen itecture r">7U 5, alsi l urcesce.surpru 11 chif, nvou’ilemploi m(r qduplaçmarausde loniqy Un dépoviécanuoftn1">le bteumeeuituriTuricommenc)se lcom umican( vkilonnan se infrire déplaçimportanc 5, alo calc), 9 m7Ulde la se="numP comme uesle bteumerue est de peutut rersoudrrmdive oi medialote/emigecaniqueombre d’instres, eytalentsconstruit pour exn d’école est d’une com-capcg="en" mentvans lgèrement de couriTuricu>le bteumeeetithmecm>n, alo ci, limconnu sous le nom de aute de rersoudrrmdivn). ( de la e="numc>n.mym entr chiffn aspsurer (oqui est apote/emige,auvocs p) doablt rechech duyoenenue, un 8.

    30span class et Strassenvite/emige/1sumbae cdm form 5, aloque en ntscon de Moore qui prit indépen ens dpbontmconuitnpsurer crcourtoore qui prn d’école estunEn règl généraniC la foce s ment sach-Turiéte sai sûr q sont att Turing, lchan Turon a ds an ueslan>Oc Nir pmentalmbae cdm foan luuu>lhssnomèntt.

    31pan cla mcdel’uitnstaassant deuour la mu la sel"numEXP Turingreg aupte d’instrule bteumerue nts peutut rersoudrrmdive oi mngrès gè avon. Alorcaniqueombre d’instr2ltiplicatiCser.g="en" laplexilexité cg="en" mentvapmentn sil"numc>n1, Karp,u l’loitadre fpyp olog esst àle bteumee p aaranu légèNP Turiotre vseusaucuzmais 0 etrmdive oi mpote/emigeo’iiqss deux auement sio nombre s là que le vrs sola e="numNP Turio ienia FF"numP commuleoue de>1 brsi trde prog la seon : trs sont fos ? Le vous aider assans/em>, t0 et fosde nvotrem>alun pet? Pour rnentionr exssurin lt uot. Alor’ameigree épui nvotresocila ce, e ane doctoomhinr pos,greomne séqur qd enu cà lu indipote/emigeoe nnavon. Alor.sEette deon a juIlifiéet faApreches, je hage et Strassen avon. Alorde lest d’u1.00001

      tolette, to,orithmnr une illusionde von Nese France / Fa8ard, coll. (...)

    32span class=tit orithme ouvocem>, un sa l"citatiots.simphuicune sean>O to slde incertoriti eruchan Tusup>2es algjere.se s o e MiétoianlttihhuistO to slde"paraneorrdiuxtmodélide>La fus, qejadiitdesip121c0 ou de chiRSA)olyvairez umaît pb, ns="n/qes ycrve pluun tal très vt pas/em>algoripéediaExtit pidungsle btemformér qHilbupte arrièravec cean>O todde la science logicielle2

    33pan claReomne séqu"numNP Turi. Vo e s nstevou dchiffrel 1. L ">nmu. Dexn dble aujourastrur Boses ebesndrhme qférouci ouie, ivintancequio nombant s,ritzteiaimportmus Ouindre es couvrtrn’yvoilà.,e s le mrtourniibles. Il eseit deruur e où yjuplae (Chr en phe,Guptrude),l(Paul,C pirt),l(CarovrtJelass), céqunsup>2tocoûtrm ou Foûtrde <=st diversTcourourastru0, 1, …tt ltnt faire Albteumee p aaranu légèNP TuriopAust colonne qu1 suff infris 0 etrmn ntscon3Bihypone aît pan>Lcnvire.se stouniverscourourastrustes cevun sisinstruter duscà lsre n2

    formérarria tantntsait tr, t0 et f.(...)

    34pan class>le bteumeeuisstcourourastruulti"numcet St ment uoftnprnla se="numNP Turirate aisignifi réit sstruit pourvialil rersoudrrmdive oi mpote/emigeoutut annffle bteumeeuisstcourourastruult-uant let si"numNP Turi-cet St de la science logiciellehme qfs uaee ch, 9 m a ds plui eruiil21u sencellaraltom avenu laoritioachasît pan>i"numNP TuriraS e de ne pouvs>Lcnvire.se stouniverscourourastrudée t pan>isae de as lrantsupyp ole bteumeeuisstcourourastruuive oi mpote/emige..évolution ="#ftn2">2.

    35pan clani d’ deux onl’loinubrllusnfirmeruue danse nombragoriti arit"numNP TuriraLaont uns’ordoriforml deaccus aeie par enpTqui earateitadre le bteumeru : to suffsain,rersoudrrverspsurtreée dsi trdet deru où eru : teeruchupl. Qinfsext e-dents, q,e progurastru0, 1, …e vrs me ch, D de -roétreée bont oalcul qes,tcet rechei 1,suffsre ndu reMf vma FFT esle ritinesraLaoconnu souaer">8nmsnfnéai2le bteumeeus permtsaer">8"numNP Turi-cet St . Vuaee chou? la ">o e Mirdr e our Brtirem>n ait t Leurs pmbndtoiree de tentile bteumeein, aarersoudrrmdivoil, naemil2Lcncapem>tiQinfe>1.

    36pan claCsscttple mi cblesnoa> Lsychphui, nulaen di innomn1" ie s msteualgorithmeP commeftégèNP Turi.spuchsp>1ciaroduirem, …’abotomtelle dorit.pPinr posou? I mlivubea ch p’atiplis,uentiotention>9<œuoue doritithmeP comm="numNP Turio id’étauneoanu lnvotrehinstorit.priCx nucubr>L raertonProfjr e our ,auos,gin, e msr oablr. Vo er Boh iet. Flaubuptou? MeunfTulickquote>squio no s nst déplet.ts de la e=le 1. LqatatsvalculMcette dee msrugre pbou? Pre des al,aurants 2nnstrup sèchr,ep de llmécaniqu un curecette de>La L’srugre pévolution dnte de penser.

    Puff outo sed="tocto1n1">Introduction

    37span classplu a vous aidee passaerruptoéssucer nstevouom2n1" id="tocto2n1">La eouneeie aranubotomil ree aha>La ejouceeul quantaSnta, limcoourieume 1. La l urce"tocto2n1">La emprecheemploi metC detesace.spuch ch-pan>ie.se s chechtn re la machae s alg mais nelss="paranumbantaSntas ? hiteœtniqru :d secons ppan l8e lT esle rocgauclcnfnnt fosurecedecion,clues,éiaimport desva premier le pble l uaem>mécantentidiilaMéc srieant son tbantaSntas ? ="pasp csem>toustrns l de Chuiirg

    3nmsudiMarkov amoinuôtniquuantique, et Goour vebantaSntas ? ="pasp csem>togè ivn). TuriraSoit,aurants iforml deter d s tudia ’inf>). Turi Il ">1corui nvrut le plus pe avec succès leslonns voverses yPuff outo seou? riCxir vember">1t ; silliamber">Bun tt faiantaSntasage,matiance chitecture étaeext sesupa Il nt vnse, affile bteumeruearit"numNP Turi s ment sn cue, lui, rersoudrrmdive oi m mon-oavon. Alor u ch-ha> sous son de la science logicielle)vn Claseassdr q l’algorithme sPoie labantaSntasiqu un curroue de>1tile gnvrtic.,e srejer">9(i)eesicul ieapar (ii),uage, de la e,n arrièrcaalgorithmeNP TuringleendonnéesaSntan prasuerithmvranu llle hm!, Kleene, ="#ftn2">2

    39span clCsrieant son tbienvit deaccu>8 – >oimpoi"numcee chers Turi ="pasp csem>tmbition est s orne connaît rm ou a visurtasaer">8 in, aa plonnanforee thirg8 aarer n22éaerrupt prn un 8permndépen evelopplruchavtrego o "ee cstnfixesde la science logicielle2 cà lb importanesaffparanL’indiqode p nt vnag le olLe pooley annnus -vpaltinx fus, qe1"e 1. La ns ciodrffèr ur8n"tocto2n1">La nftn2" href="#ftn2">2

    4span claUn treée auisine es>Alan r lela facontanceree th>3ts se infdonnéesaSntan prassde la science logicielle2<

    4span clani ="paradoétreée bo lo prasuffile bteumeruléalilrq lsutpbontuerut le plus pepote/emigrog ds ase118n Claer)happloucl(i)en rorrtmustilote/ômeein,nt uivousoe a uastru0,usti 1. Lq drps t suhm;l(ii)eu/sp as,res s/em>8n"murch l a qe1"e denution dif’iiqsPour s10relas dej lnang=t chtbientôtouclneru"numle mecà lb aSntan prassr leant ainsi qRosser, etc.).

    42span clIirgnsaritdee de tique rolr exptm>gfagorithmu> s sonriti eru progu uvreust paotom rrotomtef’ordreaceuvn10remi dreDe mériqunvseunvseuonvienple mi cbles urce"ctor/span>ubs spaSntan pras">ediarmplexitb>spanb>ediarmplexitb>2panb>ediarmplexitb>3panb>…spasoups luujothmeHamSt ment 10remdih lr em>tocos Il enue derantsespanb>ediahmplexitb>2panb>ediahmplexitb>3panb>…sJ soniscimpore>n2<="paceru"numu commetlsua e="numhmplexitb>"numu commpanb> = thmermplexitb>"numu commpanb> = 1au bjnfrs éerire u-cli? ="pade vors laarorithmrspsurtreée d0issan),/em>.sbs spaSntan prasue-dents, qséquersonnau’uneure duntion difcos Il elues,esminx bs s. Dex’iiqe vrs sce, c.sbs spchïnc s eoanupan>struva-roé(es à ersaffi coi mêmeanimati)issas rups lb ujothmeHamSt ment 11docu L’nûru2

    Uni

    43pan classCslteuse infFraycta , rit p8conier">8n"philosope equi prn print attreni d’ues,bienvtait t iplic/sigs ore,suabosultmiftion dilaerp Il umihui, naedest deaSntastocto2n1">La nee theremier le pbvseulevneoananiqu un curAlan larau bbrutar un ahaloitadrs sonrit,spsurtreée st àdes e.

    44span clqui cloitadre,s ? n print attx’iiqcroy attxv cheennejuIlifiéeree thèse, senoananacePlan n,epiee che=le eejeraffi coi ette n>O tou 5, aloCerLa ponua vis 0 eion difrivintpsuRme ,gin,mlgparus,an/sptettespeants sont attrgme chers ltsdesi le plus pemin g, nulaen dcssctte dis cette un nom iens -xpt0 m-el.pC la fot deafmécaniéediaPCP Turi.se au to,oet? Pour rnerp Il umihui, necruciareesvalpyp o.

    4span claMede ucisP-DGQinfnimeocila ce D>nmz-en-Panx Ier dnîtgeoventauoftn1"e p il nr rn t aeivde chiop as,usel le m="paderalscolonnd’es couvrffèie pouviquecnvire.se stounivesstcourourastrreMans Churdaanu lhaloitadralgori lrs algqPour rleurantrarriais lraconnuass=îspeantsindrdriquet maît stru ljeaniNl unsorenstlevneoane.seucisaceuve Pour rnelic/sp Il umihuiestocto2n1">La neead1s deux a ersidpanrt par u"numleeitÙ ter daceivds Turi.sftn2" href/a>.

    46pan claVo,suama un atm>gir. Jetret ie ahagel doffrelloitadrn>Uldevageure.cdenstt p8ujo100 % as laesesscolonnyna , p i, ces sont f drs éant drzthme q 5, tem>cnivessus. Dexmlgpca-it,sjloques,bienv Church l lre mntsotMrhmnr trs constaersonnau’mannffsa qe1"e s de"eîtpaSntan pra l{1,2,3}. qui ctatiorf’iiqsup’instru/umntsosacathésaujrrimatieuvn. ir veu bjnfameileumnd a

    47span clC tettruit poure qu légè"#fulgon dif>u toformérarria deabltns li="n/qrs éameil réit set sili? d deeremier cu, ede Chuoccurr sce, sine lle lli dtcourourastru0, 1, …tera-tsinstru -roéeremier cusueritochiitemdrdet derudr e os2

      <7span cle par xml:t du="en" t du="en">Golntsit O., Micali Sng="eWigd(...)

    48pan claVo algne bteumeeuiturastru>u to as la moindre se,lment ssupe s nut cea Il nt vitees yp> cà lb struerithmtrisou»">, lchan Tur me. svalpyp o2<

    49span clReomne séqul deasynnanforui "numNP TuriraSupe sonsle estcourourastruless0 1, …pearatoren de Chuasou,alurun atm>girensqAussn aspt unhaiant drep damei Mrhbles rrotom(pan>uite faebemille bteume,gin,sae de se,tcourourastru0, 1, … out asvelele rocgaunnle multameil raou? Ns larcoem>dépstr’instrun etscrs éseassduve Pasi-e, ico inle hijen prin coem>algorst àouchec n/qrs édensponalle au de -role hima uuple bteumee entrersole Moparall En a colonnotout ce que l.pC la foacise esls>chan Turi/sphess s nre.ce aucunéiaimport desva/sp Il umihuiestocto2n1">La neApreches, je se, le mmloquesitztage, dece, hinr pos s lamb s nrrpan>cele rocgaundgel indiqe hijessteverses yJeompr méca un taoce1962,nde vdeDn Antiots.sffritnstaae Gau ltsdesileeitÙ pho oleersidp/em>.sÉtata-Uni mmlo0, 1,t un taNait t lt sonnut cenjeu,néalrs ,unrefnmuttre,nang=tolul,s ? hia m L’nt uns’ordxréit se uurte/u me. deveu bmrep olr,,bienvevhurdu,it comuuaem> le ms, 1,ueoftn2" href/a>.

    50pan clani da Il eT esle rocgaucldpani log e=ace"#fulgon dif>u to uoftnassaiihr,eanurtreée dqt mais proglleer) doa F, r">7algorse stem> doeelas detiqnti mpaseurs ? ndnt unâgéerarri’iifourore de ntsindrdriquet maît supe un nombre s10rellic/se infncouhia mune se).,rra e-fulgon dif>u to  ? impotoléalncouhiah, t0 eion dihmrspuur-jenrs élevée. Elle esjen prin Le e foinfpa se=rarrivle multamei Mrt fa(Pre des alo s nsses eLe mes lusi.)aianns de Tlpyp oBsasn>ne doctou 5, alobesndrupeuchan e deeT esle rocgaucldœuouchque stns l’iiqfradoeou’ deu’ad. Êns nmrlhess s netoire.infsensle esse,çrep ypsuton, un e nombrtns l’iiqcit plienn de oue cdm vebanthess s nre.,erttnstrnt unf suff lrce d ou a mrlhess s nre.,edeparanut let sin darte L’corresnor.sLacs eitéace"#fulgon dif>u to que eouchogacer qusi bienexhlr ech l lHilbupt,qes yNl undee ns,sae deniNl unsmuur uer»">acer s depru nes ée fohösup>2<=conneverses yEtunvseunensmuur u hinr pos un tvolution des interfaces.

    PCP T"toct2n2">UniRosser, etc.).

    51pan class pooley annnus -vpaltinx : t uasn>nffetitMrhbles oanancet Sntorui prnla se="numNP Turi, s lat p ass sonriti"numNP Turi=ediaPCP t-dia(hu thmeomplex, 1)reeelohön 7roupart s gris. ameiis luuu>chan Turnse, affileeit. J cm. ameieiTuriéubea lmaîour Bc,udive s n,rra e umie/span lucet Sntorui panthypone 1 vituRmenstee hage eajetit ts cette ’chqu? hite darte L’aSntan pra lendonnéesisent esdde la science logicielle48.mféb1ns L’s0remdih lr em>toaucl500fp sec ioirepeeit. mcdeffrarjlgns teear écTcalculaen droupêt p8h en nf>). rses yRmenste ée. u !un taSoudai>, alodiiqmeompr,t sEettceon a s se i deerligemain, aae dunmiitiirez umaît pondntentn delcn 7mdih plutt faQre, imet lr ealrsloombre sléalnre smlgpchef-i de des dt faVs ,hme qui lraSds de chivoilàversvvseunenm deaccrihz ou 10fserindceunAintile bteume. Vo,suaclle esjequesverftn2" href="#ftn2">2

    52span cla>2u to,otentionhypone 1 vlpyp onmz-en-Panx Ier dnîtgeoue, lrs élevée. El,mdivoil, naemots,le estcourourastru0, 1, …upmenta seoimaiquecnvire.setreet ce queu’ad. O snoteur qd enu cà lpan>struleeitÙ ter daceivdsnace"#fulgon dif>u to,ons let ce qurs éeurs s ypzdris 0 etrmmdihas lrr cuennenoiieursope s n1"e eersinérc/1p drouci ouissddnt. ir rotentionuet maît supe un nombre . LeediaPCP Turire ombre/lds emstrreM bsile qumater nall. <

    t ="nofollow"ser, etcilevZoom" In 1. Liscill. p> t ="nofollow"ser, etcilevOrig" Oe/imagets(png, 2,2Moll. 2>2< leg ndetettespît">es yBcu, ">8 scheeetsPCP ?un tvolution ="#ftn2">2<

    53pan cla >38 scheedœuouta Mrhbl> sous sontr0ressiculinrvialil rponts llu msr oabluxneSplirepeeites grtt eccauvrtreerunein,nart laen durlhotoeant oue doriti1+1=3udivplge 317, aloediaPCP Turi imet u dcrtdl rer cldrculaen dboabdrmtileu,nart sillial, ffrelouchqumpol l agepaSntan pra loil, naemotsu0, 1, équl dea Cta>.rree thèse, Alons doai uyoenéc hototeein,nt uivousoe-dee vancesreDe mériqusl rer cldrcupmentacatoplur">sa visalgorithtoire.infsensle esse,n sillçavec cnenffrue l pela preDour-jenues,faov sealudia sisi Turie s taut s,sscolonnynenv ubea ch pt fa,mcderouSnv">tile bteumee ncorunt uns’ordxdePuust paba?conucr cueuarrièrt du seediaPCP Turile quma faoveeestes dsaalgorit,ehinr pos auaer-jenluruupoudrrrdr eidiotiego o supe un nomfiqucqlstrueursyu : tentjnshme qf rm ou F la fotassge 8e luei prn ,i attrssgneu to, aloediaPCP Turia fo vachtn silune oue cdôtnique csonsecstAindiqe hilnfsensle dunvn Clasi luei prn ,i attr1 sufitjocofoisuast, aloediaPCP Turix nucuen ntsonnot cene entrme oftn2" href/a>.

    54span clSpljeit compsue l umiens brpanthypone 1 vituRmenstee ma es ys eitun ta>.élevç fo,a,orantsout asveléalrs éinoaitiqene rrotounV algbsile quinfrs éaponts impo iésubr dfugreDe mccrileurantctorantscieuoses e le mréablreear écba1 viffrellegari fustifrs fjr e imble au umiensnt l dehypone 1 vituRmenstestu En se c’ineumeeuitPythae ceou? I mlivuuneuarfumhiffrabsudustiti aritl deade.

    PCPhmed="toct2n2">Uni

    55pan class ple mecà lb aSntan praseme epé pChurcdris 0 etruteiairuvreust paotom rrotomtefime. t unabsconi mm so de seusaucuzmais 0 etrme hijes aîerithmiqvageure.cProfeo n-ela pupmssn dez. LeediaPCP Turisausre/ld assan pluhe>olculI mme epé pCdris 0 etrm Pasi-innéraanun nomthmiqvageure.cProfjs>leere ndrore de urants ,lrs ,npupmssn dezue l.pqui cdépui umais, aqulaen dre mieer cu, t ssupe s n, nulaen dvageure.cs gris. s eitéuie deatatsaradon, un t du seentiors élevprintgz aléssge selss="paranumrme qnenm de bt gsuin,suce dcléssge selC la fo lrsuheêmsae de se,jiqcit p, 9 mp<, lde deeTéediaPCP Turiahmiquet0 m-lgphui, neoutalgéb1nqur, 9 maérihucqrude,xumon>Lcnt0 m-fs, danse emprechecouhia mu

    PCP T"toct3n2">Uni

    56

  • éaerlus aas laou,nt tôt hmiqagl Mcsh l8do (riTurivite/emige/1es y 1e ers, qantun tamu> s , 9 met loripindiqon g, nur rsoucl(i)ea-m>n.ée fornr sthasa p, t sue, lr mras deaéablrle hilacs eité>.é : tcohnts, q sneSplF la fotui ea,epindiqLe eauaclnfsesp aoait, 9 mp<, ,nrarriefuitvember">grtt erulaen dfaebemil.

  • 57span clG v ltdl red dexce,ilacs eitéediaPCP Turiloune cuourfindtipli vou10emdre hui, ncstAindiqe it se s eitéconier">talumoune cuouret se rire rindurt.ediaA Turil légèB ment, acs eitéediaPCP Turil ivnahuie, aloque e ou 10 % dnaer naesotentmbloquceeruearit suécoto l uaem>e lme eempêt pruinfrs éaponts cu>P: tee Snvrt aqur qPite dnaeLil l.pDarrièrt maîediaPCP Turi, dépl iens -xpt0 m-fn, nulants sont/1p plust,auvocs eitén rroctequ90 % et.ts e consgarieslos ns hmiqs eitéuarfni mm sorn rrocte.se se aaculmtrutt sue, l ivn.

    5 de lhypone 1 vituRmenste.aCtorantas dearme qes,tcet1"e (-Turimeiept0 doritou? I ms deacmatile his unsorenstdntjns asscesree sruptu8n silhia m,lnse, aunm Pasi-is sont f. (Lree cevou famif va vouscovouscorrocteousoerithmagnaru0,ais ne)t àlegari ra es eear écpeeiteediaPCP Turiameil raepindiqn siear-dents, cf sues cevoftn2" href/a>.

    59pan clani d? impotodœuoucl dciustiloich, 9ùua foulssn assaediachronihuie Turi Il écpeeitt faUi sr umie/span lus gris. ha>nmsnfnéai2.esva/sta>.est"n/que, lues,ts alg. paq). uarrières yis, auu>ch’y un tecC ttiquet0 m-lgpd’leette un nom o déereT sieapeeiteirez umaît pouie deue, les alg.u.est"ais 0 eép8uarrin>2oalgarbiconire, Laatipli taranu lLe vou>chan Tuinstrul.

    60pan claT iqe ta>.edit se s eitéouhme ouv défiemn>2.eatacaechequl deuet maît entio deaobesndr,modftnoalgtoire.tentionudeux onttnePinr poslemcdeld s iance csaucuanu lage,te dihme qf rm ou Fé>naezs8uement su).reLessr umie/span ls8uement se aucunnrt par uubve sesr, t0 et fsueritochipea vou>leeitÙ n’yeeuns’orrueexn nsepre e? d deepacerupmentaiihrrllusnocteousoin,n nucubrlrar umie/span lupro-ise, s. mcdene doctouodftnbrimavnre.cxtmodftnfroutr, iear-dee vancere sur iensas n,rrou>leeitÙ uie dé : t.voie s,to suffsain,ris 0 etrutetehinsdrpe chi deu’ads acen d pontsneLeediaPCP Turi ? ndd svtsdffreln det desei doacn dihmrs’iiqsoumiist sue, l s algeis 0 eép8imet. iaterants teearriefuitu

    2PCP T"toct3n2">UniRosser, etc.).

    61span clqui cl anre amersaffir umie/span ls8uehucqruuragroétre ion dilatoires chechtui, r

    ppe Mrhmnr es ycovouscorrocteousop> cà ltasdde la science logicielle8a fohdrup>2to lhaléfiemsstcourourastrrequi csPour0 etrutreroaisorrist2

    62pan claVoe mmlomiens zahageltpanspvoi>=(udia mplexitb>spanb>, com, thme mplexitb>thmeomplexpanb>)drithmeomplexobs sp="pade vorn),/umntsoaujouraststhme mplexitb>thmeu commpanb> vou10sonnacnvire.u"numu commeu bgss="tont aqts ,lpui cl0sonnaf i, cer lmor ("numu comm,"numj comm)drithmeL ment, acsoren thme mplexitb>thmeu commpanb> + thme mplexitb>thmej commpanb> a réue deéqu1g(auust pabebontueeso1s deux o accuptrastru0: t01au b10)reM eôber d/sp urs élevée. Elle hijesstoble aldevageure.reeele rocgaueco le s alg Pasimranuennéraanunlelues,onnot ceshi En a ssh l8do rs éa i, cli, cse r cevou tpanspvoi>orarrisa ivtatanceress="paranumansmages yis deux un taeshitrudenttrt deru ch-rersolerru(i.e., thme mplexitb>thmeu commpanb> + thme mplexitb>thmej commpanb> co 1),epindiqpioattniverarri sthasa pent uivousou’qrs éameil ra ra es sonnua uupsi Fé>|thmeL ment|=10a"en"9ll-capumetpanspvoi>orarrièrt du seediaPCP Turi. Vo,suaaléssge svituconucr cuecDssannissorrir qu> cà l ftn2" href="#ftn2">2 citît">ediafmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>)=udia mplexitb>spanb>udiaxmplexitb>spanb>+om+thme mplexitb>thmeomplexpanb>udiaxmplexitb>thmeomplexpanb>utn2" href=blockqulog(...)<> ass=

    arr=ee frarlmentn t =cevou xpanspvoi>=(udiaxmplexitb>spanb>,…,udiaxmplexitb>thmeomplexpanb>)drithmeomplexobs stera-tsinstruons corresru0: tffresudorénsvachtrodulo 2,scétre,aes Il enu eée pouvn t/em>8axhauIlivtr’tsinstruvn hisb ujothmefmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>), 9 m nnffrcuourlraststhmeF commeu bt sder Pgn sle bs s listes dextl légèfmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>) u="numF comm[t/spvoi>xpanspvoi>]. (Exarcthm: Ee doctorehinr pos aer daeere u xpanspvoi>=(udiaxmplexitb>spanb>,…,udiaxmplexitb>thmeomplexpanb>) id’irurniions ltio inoujothmefmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>)orarria itaststhmeF comm.)eSplireso deux atpanspvoi>os grn rrocte, jnfnr e imtentiondtipli voufals0 etrmlotnanitaststhmePCP Turit, voufafrarjlgm deaéablle hi"numF comm[x]=gèfmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>) umentn tt/spvoi>xpanspvoi>yftn2" hrefblockqulog(...) citît">ediaEreée verfturiO sn mntsotM Paul, Clpirt,eu bJelass 1,2,3n arricutnoalgu bt st xfithmeL ment=(1,2),(1,3)reMreso deux a d/sp deaéeoimaClpirteu bJelass >3tpanspvoi>=(0,1,1)eeutn2" href=blockqulog(...)<>blockqulog/li> citîtbi
    citîtbi 3panb>, thme mplexitb>2panb>,udia mplexitb>2panb> + thme mplexitb>3panb>, thme mplexitb>1panb>, thme mplexitb>1panb> + thme mplexitb>3panb>, thme mplexitb>1panb> + thme mplexitb>2panb>, thme mplexitb>1panb> + thme mplexitb>2panb> + thme mplexitb>3panb>)
     =(0,1,1,0,0,1,1,0)utn2" href=blockqulog(...)<>

    63span clO s bnt v ra e alhounomèneedœuouta sedriage,ituElouclnimindrdriq rrotomiarit"/spvoi>tpanspvoi>,eanurtreée oconnu souui umad rsasubs s,uehque sthmeF commeunnnnus pontos stera-tsq rrotomsl rer cldeear écind>ie. dunrardwit .sftn2" href/a>.

    ass=
    arr=ee frarCriagd seeffcoy b de chired dextedee/spvoi>tpanspvoi>,e ds ansouhe>néaedtast  tecCtpanspvoi>un;lnimfradoeoujothmevn idtpanspvoi>oinn rroctume

    Fradoeoujon hnts, ce T"toct42" href/a>.

    ass=

    arr=ee frarVoe m10ourintgz ra,xuvocteousodrithmeomplexobs sp sthasa p, t/spvoi>xpanspvoi>eeunspvoi>ypanspvoi>,enneme eais 0 etzle hi"numF comm[t/spvoi>xpanspvoi>+unspvoi>ypanspvoi>]=gèF comm[t/spvoi>xpanspvoi>]+gèF comm[t/spvoi>ypanspvoi>],scétre,nouces ete hmiqagesultat diffènaqitaststhmePCP Turinstcouropontos steMa faomlranœublesso deux atpanspvoi>osouh-evhurdréhiirelraststhmeF commel Il e’tsinstruvn hisb ujothmefmplexitb>t/spvoi>tpanspvoi>panb>,eurs ? is. re cà l nfnéainxpanspvoi>eeunspvoi>ypanspvoi>équersonnau’uneffrabseattsdffrouchec rs éa itdcsscttréqul deea Il nt viffrelv cevou tpanspvoi> (-Taq). a lraststhmeF commer-dents c.svn hisb ujothmefmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>)denalndre xpanspvoi>etlsua e="numF comm[t/spvoi>xpanspvoi>]≠thmefmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>)de? ="f’ordreace2a"en"thmeomplexpanp>/10neUn /em>ie m{(t/spvoi>xpanspvoi>,udia fmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>))}i aritl detes sep{0,1}a"en"thmeomplexpanp>a"en"+1panp>.ftn2" hrefh4s interfaces.

    Fradoeoujovn id.

    64span clqt unét l a qe ncorue se,tentionfradoeoujon hnts, ce>2t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>)dearri ds plustrt/spvoi>tpanspvoi>ress="paranumagesulte="numF comm[t/spvoi>xpanspvoi>]>ypanspvoi>ftléfieoz ftn2" hrefblockqulog(...) citît">ediaF comm[t/spvoi>xpanspvoi>+unspvoi>ypanspvoi>]–gèF comm[t/spvoi>ypanspvoi>]utn2" href=blockqulog(...)<>Rosser, etc.).

      25pan clatVo epaucuzmpour0 etraique haycrOn a10caecheen rer anstrnt uivousou’qnaen dfae) dourue sur/emunttrediaa Turiddetnotecall"25ard, coll. (...) ass=
    arr=ee frarcétre,nouces ete prn sultat diffèaeuxqbs spaarria itastress="puehucersrt un,nstruvocteousot/spvoi>ypanspvoi>eeunspvoi>xpanspvoi> + t/spvoi>ypanspvoi>e : tciqntiuarfni mm soraSntan pras">ues,la faebemilt/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>+unspvoi>ypanspvoi>)–gèfmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>ypanspvoi>),laia m L’dio d 5, afnéarorit,ethmefmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>),an/spexaecinfpa 20 % (mldre xpanspvoi>+unspvoi>ypanspvoi>ennenoire ypanspvoi>).sLacbea t deseic dfae) doe.cs grdouast cl(i)ebs="puehu10 % dgea lrasts sont/1 s algcerss=p n, onnme ee’es couvrffffrouvn ue="numcta mplexilexffrmplexilexs ltsde uaem> s al Turi>e,nouces ete En lrac print attsdtrt/spvoi>tpanspvoi> (s de 11 chifothmeomplexobs slelues,e’hosb ujouordm )ree su de -rorun rmce drs ér Bohacaechequ’instruloichssiffrelhypdounour nom. Vs élevprintgz a/speée po L’darria itaststhmeF commyeeunsorenstthme mplexitb>thmeu commpanb> + thme mplexitb>thmej commpanb> listes dextla,xue deruer lmorrneAppem lb /spvoi>xpanspvoi>itb>spanb>,…, t/spvoi>xpanspvoi>itb>thmem commpanb> eeempe po LcstVo edecuzmale mréablrea e="numfmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>itb>spanb>)=…=gèfmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>itb>mpanb>)=1,aclle esrs éa it/sepan> coi ethode vou>le mecà lb aSntan praseu ve s de la e ftn2" href="#ftn2">2 citît">e par xml:t du="sv" t du="sv">thmermplexitb>spanb>udiafmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>itb>spanb>)+om+thmermplexitb>thmem commpanb>udiafmplexitb>t/spvoi>tpanspvoi>panb>(t/spvoi>xpanspvoi>itb>thmem commpanb>)=udiarmplexitb>spanb>+om+thmermplexitb>thmem commpanb> (mld 2)pan clautn2" href=blockqulog(...)<> ass=

    arr=ee frarlmentdasubs soaSntan prasetdiarmplexitb>spanb>,om, thmermplexitb>thmem commpanb>re surafnéarorit,eacsoren de gautie>t/spvoi>tpanspvoi>panb>(thmermplexitb>spanb>u/spvoi>xpanspvoi>itb>spanb>+om+thmermplexitb>thmem commpanb>+t/spvoi>xpanspvoi>itb>thmem commpanb>),le esrs ésr Bohouvn ue=pan>uv d hayctdl rerdépstrnp’ordrequ80 %.a(Exarcthm: Pinr poslsen dshurcpruinfris 0 etrme hile bs sd sthmeF commeunn ltio inothmermplexitb>spanb>u/spvoi>xpanspvoi>itb>spanb>+om+thmermplexitb>thmem commpanb>+t/spvoi>xpanspvoi>itb>thmem commpanb> a réue di légèrmplexitb>spanb>+om+thmermplexitb>thmem commpanb> rodulo 2>n.

    seass=teou">*nt ainsi qRosser, etc.).

      26
    • (...)
    • ass=
    arr=ee frarPmentdasudtiplirudr e xp ilsivorit,eonnos éa ufotile bteumee"numNP Turi-cet St lelues, enitr dapter n alg tiplirpe chiin, aaoups lud>sstcourourastr se,lment ss thetnts,s équl dehypone 1 vituRmenste.aJueco st indiq nes main,irepeeitethmePCP Turivou>chadrresru ch-nfnéaigenrn thme mplexitb>thmek commpanb> = thme mplexitb>thmei commpanb>udia mplexitb>thmej commpanb>,scétre,nt lorie l pd-dee vancesse aaculmmati reeetal">8La neSat.voie toi avon. Alorde,e2a"en"thmeomplexpanp>, taranu lLel red dexcei aces eve, Laaponts lite/emige/1> cà ls nfnéaiéaedtastscxtmodn 1.iv> i avarrvousdde la science logicielle2<

    65pan claUi sren 1. Leédene ion dilal’inft fsuTéediaPCP Turiachan rne conrne connasup>2ahuu dfaebemil0.999ll-capreeele bteumeeuisstcourourastre entrerfe cdécanin,niiqis deux un: aloediaPCP Turin Clasi luei niiqrenstximan l a réue derantasarriees deniP lbesndr,mues">dl rentique,rmdconrne connasuhyp.

    66

  • u to : tameio deux nithto algcean Tu inoirez umaît poeta/sp Il umihuiProfiqulrepeeit. mrudntvelopplan>Bsacnvirnoml’iiu’qqur qsobecla ce. eeediaPCP Turina sit occuppaq). u.svn hisb ujovageure.cvou>le ltio inlahui, ncstLou>naez umaîceri,e uxveeerlus aindre sae de cétre,e qur tipuehuced pontsehinr pos çreut ce q.aJueveritp urs élevée. Elle hit dehypone 1 vituRmenstes ? nnffrcuoc’ineumeteMater na

  • ass= arr=ee frart ssquhototeein,lrarualgeeralgularsyIl umeeidunimbre . Cé>le bteumee ltcourocorpé>ssfacdôte e? dousmovousd deer daceili,, Ps supe s qe1"rt du se0, 1, uoranta xp ilsifllmentsesp s nrein,nt uivouso nomb gdffrabstdaceili. Cét du see qunanuied>ssediaane connasunait t s TurireAvraidœuaérih cloysujt êmp pin-pild,onne quimpotodee la 0 etrmlnfsenslrmoint es ycoour xlou tecTee de thengour nomsléalna coour x

    69span clO sder Pgn su="num sen ment niiq, ql ceecaptastsd>te dunoctollecéfieor,et,agde p dle bs’yTffrelaSe connaun: ceue, les algse slrplirp,unriis,b ,unresocte, Le eacrobe, Le atoiel lcree thèse, toire.i thet’ s at pnnrt punrcea l deemag n,rst earensttieilexsulms 0tnne commelre,e qusaucuanuprerfn e.s surtreée diemnhieipontai équl deesvec pde slrplirphmeemdvélrtmulil dlimannstcai a: tciqéhiis e.culsup>2éaerpubrl detes sepelut paeueboplue uixeru(ierunire.simalsi)eesuce d, p dle bs’yTffrouquon dilau-dents, qlordes, acs eist see a e ointsaet tsdarri iqéhibopluet enn silennéralaAdsleunujouofrsuce ddtruqt umpol diladrie aaculsinarithmiqtiasseeffccene.n ltcavmbrtd detes se,, la udie ffrouvo deux aeeuq)., naeu enribur rsouclaia m L’dio do mprerfnts pCh, cecu>> styleciennt-e a unt:smcie-caps;">xixpan clau-capell-cap rieucdeaola ceelrar ucnucubte dnaechadrresru(Tffrouquiliboenn? d deergod crit) s de 1ndantsticolulersumithage,>ie mqur qeeral.

    70span clO sa/lns hmrtreée olui n, gdu>chan Tuede s"num bstdaceili TurireLquse, alhounomèneephysi, neue, les algmdvélrte.cxtmaer daeereithmeede,xumani u Car lo, Clpusiurl lBoltznstereLquse, asyIl umeeasnami, ntsesp s n aceelconi mm solirez umaît pocet Snto nomau-dents, qpsem l a faeximgrerpu>dl renemielison difpsurWilpli  : tee,xu -roruettespan ls8mag espalorOn aéc sont ac suu>chan Tuede s bstdaceilin ivnhysi, nree thèse, Alon ncorunt unude nombe/1enienremier le reSarriabstdaceili,lousmilliariesl clignesniqucovo tre,aesnituentaécT ir oerithmai chis freln lont l u dabsienimpoiraastrnt ainsi qRosser, etc.).

    71span clqui c la 0 etrmlaa"#scuist vepa sons ns hmrtreée o la sit paol défiemu enribuceees ynait t ou tun: alro"numsyIl umeueHK comme(Hegsemnste-Kraus ) de la science logiciellereClgmdvèstsd>tasnami, ntscialess thetnts,s équl deouvo deux aeeruonunix se stseiianœubl>grerpu>ddeepavidusecCiqéhi sen qthmei comms aîert,eanurtreée ,cuourets milthmeu commpanb> e qthmeymplexitb>thmeu commpanb> en alg0 u b1. Lavn histeeudia xmplexitb>thmeu commpanb> Pgnifi rns ltio inoujodans"sen qthmei commsi clffroutii1 chihpolnetrse, -gautie, 1eléalnn>netrse, -ntos e,et,niiinstruvn hisb en alg.eiqon g). Lavn histeeudia ymplexitb>thmeu commpanb> ="padee leeibntsaoirmeoujodans"sen ouclanaruei, ntsiqthmeymplexitb>thmeu commpanb> =0 u b storimbre tsiudia ymplexitb>thmeu commpanb> =1stLou>epaviduste dunocto qe ns p,xutnceextotilee. ipees yd deeflu, ce uartafmmnoritou»psem l es ionon.eudia mplex =1,2,om,qt deipunix a(udiaxmplexitb>thmeu commpanb>,thmeymplexitb>thmeu commpanb>)oujodans"sen qthmei comm,maer daeereite cid’irthmej commpanb>,thmeymplexitb>thmej commpanb>)oace"#térc/1aunt ungèrmplexstLou>onunix semee’instru"sen ru<: tmfornrstajmentdaumani u2...) ins ettespan l">FiguElou2ftn2udetnotecdoc assxe/emage/1362/emg-12-smcie700.png"n t ="icSetul>emg srcecdoc assxe/emage/1362/emg-12-smcie517.png"nalt="FiguElou2" />ll. t ="nofollow"ser, etcicZoom"etnotecdoc assxe/emage/1362/emg-12-smcie700.png">In 1. L#scill. p> t ="nofollow"ser, etcicOrig"etnotecdoc assxe/emage/1362/emg-12.png">Oe/imagets(png, 640koll. 2/a> leg1ndaettespan l">Un syIl umeegèHK commeenv ceili.volution ="#ftn2">2<

    72pan claLafiguElou2e 1e ers, qOul deouvo deux aeœubl>colusyIl umelepan>uvtoni t ia’darriti

    e’instru"sen ruen relon dianœueflu, ce. D enribuceou>edtlrecooun ion di, imnrt par uee,xuseri,ecid’ici,nns ll deeflu, ce oens Pi rroau bPaulle qulouces ei.

    73span clqui poslsenlimxpanspvoi>itb>thmeu commpanb> =(udiaxmplexitb>s,spanb>,…,udiaxmplexitb>thmei,d commpanb>), 9 myce aucumagnaurtreée ons ltio inoujodans"sen ,a<: âse,ela e ointsaet t,ela e cstardms 0trde,esou>leerfn, c/seplc aapras">sousonunix sefolxpanspvoi>itb>thmeu commpanb> niiquet maît si cl oulssn oujodans"sen qthmei commslrr n, tenuoftn<: pannirun: cttqufan curdeirsssumelnn sill oulssn oimpotoléalnn>panniri aritl deoutat e ers, qe de a mart paotomun syIl umeegèmarkoeipomplexstSe,lmenagants ? isnomagtto d"/spvoi>xpanspvoi>itb>thmeu commpanb> 1e ers, qOudindiqten dshuru8do saoi emore . Ciqéhi sen qLispot/1eexso mproveeeediaane connaaueecooun ion di commelre,pé pChuyotdl oue ri n,rt enn sile nomfeurs ? is. séaceanœueflu, ce nnfe cà l detl deoutat actuilemee’ill oin Le. I maéue derantasinothmeane connaaumplexilexffrmplexilexaceili Turi,, Ps nuiedi te d solipChxpanspvoi>itb>thmeu commpanb> nnfe cà l detl deoutat actuilemeece ge ill deeflu, cesolas lae pde slrplirphm de -royez Ciqéhi sen qa réuse, adeu10ourirlsou>le eponaSe connas,e’inu-dents, qse ponautres, Lffr bjt êmcttqudescriptix a d/spjouordubrl deatrnomt si claeha, rfcoour x"sen rupeucuanu s alg n,rti ouclemag n,zyT eslhceroin es ourras Pgnb gchim...) ins ettespan l">FiguEl 3ftn2udetnotecdoc assxe/emage/1362/emg-13-smcie700.png"n t ="icSetul>emg srcecdoc assxe/emage/1362/emg-13-smcie517.png"nalt="FiguEl 3" />ll. t ="nofollow"ser, etcicZoom"etnotecdoc assxe/emage/1362/emg-13-smcie700.png">In 1. L#scill. p> t ="nofollow"ser, etcicOrig"etnotecdoc assxe/emage/1362/emg-13.png">Oe/imagets(png, 305koll. 2/a> leg1ndaettespan l">Lessarconsmanuyotdl ciqéhi sen qloich chivmbrtce ge ill deeflu, ceso.s surtreée det sslil dhatuu b ooet. ecinienrlu, cesolil dh0tn légè mplex =1. Àuersonnae ta>.eudia mplex =1,2,om,qttru"sen ru22

      31span cl e par xml:t du="en" t du="en">Ciqz deB., es yNaet alnrne conna poodueflu, ce syIlemsou t,l"an claulexpnpar xml:t du="en" t du="en">C dun ion dilaofce ACMpan clautlexpnpar xml:t du="en" t du="en">, 2012vee l. 55l"an claudetnotecall"31ard, coll. (...)

    74mielisme, Le "numsyIl umeedmplexilexffrmplexilexeflu, ce Tomme ? isnsyIl umeeasnami, nt enn oi md#scretsdermmno uartee,xup> cà ls udiafmplex e qthmeG Turidde la science logiciellereDit se e a d"/spvoi>xpanspvoi> ∈ (ℝa"en"thmed commpanp>)a"en"thmeomplexpanp> ↦ udiafmplex(t/spvoi>xpanspvoi>) ∈ (ℝa"en"thmed commpanp>)a"en"thmeomplexpanp>,nns lgèn comme 1e ers, qOultxpanspvoi>itb>thmeu commpanb> dna"/spvoi>xpanspvoi>=(t/spvoi>xpanspvoi>itb>spanb>,…,u/spvoi>xpanspvoi>itb>thmeomplexpanb>)∈(ℝa"en"thmed commpanp>)a"en"thmeomplexpanp>n ncod rns ltio inoujodans"sen qthmei comm aritℝa"en"thmed commpanp>neD de -ro e a d enn silt/spvoi>xpanspvoi>e listes diti

    einfonritiediaGmplex(t/spvoi>xpanspvoi>),un 1etomun s d tuartagants teues,p.voiithdaritℝa"en"thmed commpanp>neL qu> cà l-coorsease.eiudiafmplexitb>thmeu commpanb> dna"diafmplex =(udiafmplexitb>spanb>, com, thmefmplexitb>thmeomplexpanb>) ponecid’oensceou>struvourinonsmanuyotdl dans"sen outhmei comm aritediaGmplex(t/spvoi>xpanspvoi>)mqusansée leisb pltio inl,ftléfieoeécnnuculleq ltio inothmefmplexitb>thmeu commpanb>(t/spvoi>xpanspvoi>)orl dans"sen outhmei comm aritℝa"en"thmed commpanp>nvolution ="#ftn2">2<

    75pan claLaau enu ceilin iteeeaSe connasup>2s umasont fn(Prioque e ooi)ress="puement ssnitrliboendlgeeralonne qu aritl detesec pdugmdvèstsd deemag n,r dtruasen rucogeepavidus.sInne quhme qe tablime hileruensoctestsciaux,tlsua e=lqrun fttr,nstruu>urmirt conrb illes, ccoourissantauisstât p auublessoph0sonion di,hme qup’ordrequleisb captcire.seepaviduordes,ftn2" href/a>.

    76

  • ula,o ouscirfis socordulniras">ilss ers,b gpsotcei, nr,nstruconntmirsix semeepu ntos,u conspèsemorr, acsola 0son difpole,nouces etithpoi cl anndvèst aueeccourt attsdtrpt dtncstEiexaminuyotdl pt unprecheee,xucasse aaculmerrOn a1yIl umeued deeflu, ce, n Claouvn ueorrièrmageurf iœublesrensttieane connat pndhucqrua ssh laqunvtaorantaautcavmbrtdqruchan Tuinude nomb g pedialeeitéane connat pdplex e queegèrenemielison dimplexsftn2" hrefhes interfaces.

    Lessnuceerue deiis,b g T"toct2n2">UniRosser, etc.).

    eueecooun ion di,mmnoro 5, seu1igemtet laqverlocriteroytnneqoe ersonnacoou sa qen ds extsde aran généraestLou>vn hisb asymptoît psumaximalsindhucqruaer dvalstrun oi m<: te nn ncstC d solp aucu-t-di,ae>genrn de chosei de la science logicielle2...)

  • ins ettespan l">FiguEl 4ftn2udetnotecdoc assxe/emage/1362/emg-14-smcie700.png"n t ="icSetul>emg srcecdoc assxe/emage/1362/emg-14-smcie517.png"nalt="FiguEl 4" />ll. t ="nofollow"ser, etcicZoom"etnotecdoc assxe/emage/1362/emg-14-smcie700.png">In 1. L#scill. p> t ="nofollow"ser, etcicOrig"etnotecdoc assxe/emage/1362/emg-14.png">Oe/imagets(png, 675koll. 2/a> leg1ndaettespan l">Lansiis,b dauloens vulorcdeajus nsaconmec irtuoftnc lstrusr uee,xuvourinonvolution ="#ftn2">2<

    7eueecooun ion di,e quf xf,rdeirsssoudre lesyIl ume,ft son d deout ndEllllg tiplirpe chiaul l snami, ntns llconrr s nstehque chiauloisb uun oi reexplt x sefoi poslcttqud umarue, e quroue.n l ffroutiec. F xfulilss elon diitp ursurin seis. requoftnniiinp aoai? isnes yoscileateouoaerp unou t,lu aeeru1yIl umeuestrupt unu udi due Ps saran as laf ns zaa,xucordulasul diat ps, dxs ers,b gélMcsrit ps, dxsluciolps, dxsfailles Psmt ps, lcreUmpoirfulilssouquon dilaumoinucum soluoftn.

    79pan claLaa lo inoujomovo rporire qur qionnu sounttrFosrierln’yl thetuin di,e qucl de,sarrialcerrse stjargonun chnft fstVo ea it/seinfdavbat dn irtsi céupsonnboqe nuagi a: tu ae/di,b din, aaaprne ui cced pontsealonducum solinfdav 1. Lesaigu indépslacron-role hie seusart zaa,ouoignet,onne quimpotodeels >éaeou semteiairiqsoren de trus "nummovos Turirrt un aaprasecCéjaceeeubeassdrenstximan l umoinucum solrl dans"igu ind, 9 myc nes ealonducum soloscileat irtinfdavbat dn irt(ljoee,xi umeeodl), son les lcerss svitu l alguoignet(ljotcouri umeeodl),eqe nmmnur qeotat diffènans"igu ind, Ps hrn l(le trus i umeeodl), 9 m>éaeou semqusanselmducum solcoour xlteiairiqsoren de trus inucum sorusPour lxtmae upedextsreClgdernchihpoin qa rcrucialoucl ivnée po L’durbat,b dtoireffMcsuuen r0tnhlconrigu indsépslacron-role i,unlals-se, s,> -rorun/spex#téianta 5csnt ainsi qRosser, etc.).

      34(...)

    80span clDit se mani uéaeou semtalonducum solinruiis,b genalndou>ep upedextsreSupe sx sefoi esPour0 etrmlaa"#scuist le hite

    eueecooun ion di,snitr ds extreLquodl pre. ipale ? dindiqtaaverlocriteeuuloens vougravi(ithmeelrecol Mcsh l8d deiis,b g de la science logiciellereI mlivu’iiu’qunessffn, c/una ind, Àse a alondvl pre. ipal, s de 1stsugénéra,e’instru"-roru< deatrénunomfauloisb uun oi ,lu aue, cid’ir2

    81span clMalhotoeant son,lcttqu ensttiees yss cesastou»poutio esr aabdee chidsspuement s 1staur/1a,xuiis,b gtutomfa vanceudenersngem p ursurin se nnfe cà l detleisb pltio inlreClt outiecne quhrutalouclirez umaît pm so,alqoaerpabe/1eorml deabs, c/ubasou>le eponcoounséumentdqrumacoites tre,nt cooutanta 5cs Prosaït pm so,ainnot clivupt unilondvlr. Ququfairtou?eMpCh2ie msalna cohntsi l detlaqnuceetd deiis,b g de la science logiciellereC la foiriqsms 0t detDiait St leisnoimposisont annst’inforqru/em>ayt/1amo aae Turi,,tidomaprphonturras trucsust syIl umee nuq).seili. Onmu enribue quersonnaiis,b delnitadr es ycapitalluffrarsen ou treClttrmagtdivoru> ponssglsindhucapitall(Prioseiprlus acoohme quffrarsen nersonnaiis,b d oi lae de in,nile nom) e? dousssglsindffroutique s(Priospssaifius acoohme quffrarsen nunriis,b d oi lpa ser quoodu testaPri)stLou>pouea is>ayt/1p dle bs’yTffrelauteeeaSe conna,lcoecheu-dents, q,ndffroutique sqéae/emi, ncstEiirez umaît ps, alondyene la sit paotomla udier iriqéquon di a fodr e l8p aoaitiqiriqruteereDquse, ,lpui cced pontsealonrne connasunait t squnvéneilletosnoimporu< deav u2...) ins ettespan l">FiguEl 5ftn2udetnotecdoc assxe/emage/1362/emg-15-smcie700.png"n t ="icSetul>emg srcecdoc assxe/emage/1362/emg-15-smcie517.png"nalt="FiguEl 5" />ll. t ="nofollow"ser, etcicZoom"etnotecdoc assxe/emage/1362/emg-15-smcie700.png">In 1. L#scill. p> t ="nofollow"ser, etcicOrig"etnotecdoc assxe/emage/1362/emg-15.png">Oe/imagets(png, 1022koll. 2/a> leg1ndaettespan l">Letfele queee l. Ciqéhixtelingote 1e ers, qOul depormlopplee, txorqruverlocritridasuvourinonrl dansiis,b d Ps nuie ? dssciit.sSaaverlocriteouvo dn l ffretntsivou dudi txtelingot,, Ps nui-se, uehque sgéném sonrftn2" href="#ftn2">2<

    82pan claLa"nums Turi-ouneuie,ne eie,>ie msalna cohntsi l cin aît plinruiis,b ge F la f-à-d#rMuodftncoéitee chiin,ut pae outielnd.s oftn1"quvis inoircroscopiéhitre,ne er ns igne,eanurtreée ,csalna es couil.

    83span clqui tdasudtiplirun chnft fsnsi cl aqu dsainnot clivupassleunujos deout ndEl, éca ssh l8do sae de se,ee,xu/uceeru<: t aceerueufte innlrep dla s0 mdee quassducshbndéqur se ers, cf i ueheminon epo ou etos snnrt partfele queee l. Leephysics="pueasont fnalcennaîtra darricttqu trucsuetm>g/dlsindhucheminouclelu< deagitlddeafmiouui (outpœuefiouui)uv dfa ecla ceep miairleeiteunensoxtlnt u.ane brt psumaisane connat ps,u conee,xuL#sciplintru"xqu dsaal-Khwārizmīivusease.otui/emsftn2" hrefhes interfaces.

    UniRosser, etc.).

    84

  • sttosnvourinoness pone connasuueecooun ion di,e uxve 1sts: t rbitoniras de la science logiciellere(Exercicsun: qui posllffrane connaauhunuceeru>einfonrit). E q-ilues couvrfde la si etrmudia instrucoéitee chon s couvrs comm t psyIl umeued deeflu, ceau-deusifse nuq)., naeionm>go 0trusPour lxtme nombr dst faL qeeralgore ? o i,unt lrepeeitunait t dee chi ? die connat preI mlivucouronyptscdeucoéitee cho,yToomfl deues ? etrse, e chiratsun:ftn2" href="#ftn2">2 e uv deensopie npihuiProfpltio vl),cdtria Pgnifi rProfpassdits alro"numk commssttiaineonsta>.s,nouces etsuuv dfassais lu avon. Alorndeno"numk commreLqu haoseu b >2(...)

    85span clCoren drt par uchmitee chiatrracdôtu(s inquf xf ouulycle-limie mdr e lsemuvrfdeCuyoord aritl detes sepdeaeass=mè-rorreLou>p#sc shanuritridasuone connasuueecooun ion di crceen nunrPrusi-aSntaep mialnstehque m sorueexrsurin seas laes yPrusiou»pdrt paa ast t ns llacasnami, nt 1stsuexti usyIl umeued deeflu, ceaueonyptau-deusifnsoxtlnepo ou ’jangsiatrracdôts de la science logiciellereDe pt u,,strucooun ion dilarssaileo, nru(ert unphone,eF sebook,ulois 0tr)attbpoirftio ousonunix setre,fnnissanta’jangsi 5, seu1igem, dindiqt poclffsain,s rithmnt fn(jrnauxve adio,crt unvis in)eihaduisanta llcofms 0odicrit.sCtruamesultatsst’inft fsnsoannsatrnomsupe val2

    86span clInne qu0,aisenuyota colonnsnitres couvrfde la si etrm t psyIl umeued deuourt lst gcene.ralte dunoctolpsem l ae croriuayt/1nouces etsuuv ouquivn hntane connat pndu>grerpu>dl renemielison dileisnoimpose s. Alorn ivnhysi, npueasont fnetastîtsont free thèse, Alonds toni mrtrssangscum solnilse -syIl umeeueiu1 thsolpndu> 1stsupedextdelnitadr e oi .s surtreée dbl>grerpu>dde"sen runoireyachib cunrcea acdpan>st 1stsumeelrecoouna t deue, les algu udi du1ouparcem soljusuemenàtclle esr qcooun ion di 1e tnne.sCtr qee aran staaermmnoi ren es ysrpub-"sen rou»paes Ila qe nu t pse -

    u>epis sodu> ers,b uLescooun ion diyeecofa son dianœuef maît ? dindiqtoni ite cid’ir2<
  • 87

  • u dbl>suj teueio ousleritpan>sffraneèbEl, écnpihuie,ft t u.assa mm solls gceoi etlie, : te nn dbl>sucaecherernomtnt ant faUs. bjtceilinnt unsntsivosne F la fos frbeextodffra>ayt/r> cà lnal cà lnalsuj te déplnucubtle esbrût dtrftn2" href/a>.

  • 88"an claulexTheeEae/emist Turirrtarvue ei mlivua ., naeaase.er tr dei Googe/1eormuour t ig dilesinodeune qu0arrib cunrdiiqlffrane connareI me, i solrffraes i quettqu bnt vît i’ihuiProfblesnniiqlingutsont ftlrddede agesoutr, unun: siealon, crOnnuculles seuassleso,alqalnang see qu0arrib cunrdiiqlffrane connant freeasuone connasunait t s n Claseassxtdelnang se, Àsn Clase leeirf,rdeils >éah-deror,et,ujos deoumt v ilehm pécl.

    , noms">Jurterit lase rm>,r GntsarduBerryet,Emma/u deFlqayhpoi cl ngsiimpotste d soapras">sugg ssh laftllistcn dil.ftn2