[PDF] [PDF] Cours de calculabilité et complexité

View - Download [PDF] Cours de calculabilité et complexité

Previous PDF

Next PDF

Coursdecalculab ilit´e

etcom plexit´e

Prof.Jean-Fra n¸coisRaskin

D´epartementd'Informatique

Facult´edesSciences

Universit´eLibredeBruxelles

Ann´eeacad´emiqu e2009-2010

Organisationpratiqueducours:

PierreWolper,Int erEditions,1991.

•ComputationalComplexity,ChristosH.

Papadimitriou,AddisonWesley,1994.

•ComputersandIntractabilit y-AGuide tothe Theory ofNP-Completeness,M .

R.Ga reyandD.S.Jo hnson,Edit or:

W.H.Freeman andCompagny,1979.

•Introductiontothetheoryofcomputa - tion.MichaelS ipser,PWSPublishin g

Compagny,1997.

Ilest fortementrecommand´edese pro-

curerlap remi`erer´ ef´erence,etdeconsulter lesdeux autres!!! Mat´erielLessli desutilis´eslorsde scoursseront disponiblessurlapagewebducours. 1

Planducours

•Introduction-Motivations •Notionsdeprobl`e mes etd'algorithmes •Cardinalit´edesensembles-Diagonale de

Cantor

•Mod`elesdecalcul -lesmach inesdeTuring -lesfonc tionsr´ecursives -(lelam bdacalcul) •Equivalencesdesmod`elesdecalculet th`ese deChur ch 2 •Complexit´e -complexit´eentempsetenespace -r´eduction -intractabilit´e -PversusNP •Compl´ementdecomplexit´e(enoptio n) -calculsparall`eles -espacelogarithm ique -espacepolynomia le

Introductionetmotivations(I)

Dansdi

ff

´erentesbranchesdelascien ce,ilya

desr´e sultats`alavuedesquelsnouspouvons toutdesuite concl urequecertaine spr´etendues inventionssontimpossibles: •unmot eurquineconsommepas d'´e nergi e bas´esurleprinc ipedumouv ementpe rp´etuel (encontra dictionaveclesloisfondamen- talesdelap hysiqu e); •uncha uffager´ev olutionairefournissantde lach aleuretquineconsomm epasd '´energie.

Ilest int´eress antdenoterquepourr´efuterde

tellesinventions, ilestinutiled'´etudiercesin- ventionsend´etailspou ryt rouverunefaille.

Nousp ouvonslesreje ter`aprio ri.

3

Introductionetmotivations(II)

Enes t-ildemˆemepourc ertainsp rojetsenin-

formatique.Ya-t-ildeslimites`a ceq uenous pouvonsfaireavecun ordinateur,desl imites`a cequ enouspou vonscalculer?

C'estene

ff et,lecas: toutn' estpascal cu- lable!Dansce cou rs,nousallon sessa yerde comprendreleslimitesdel' informa tique: •nousv erronsqu'ilexiste,e neffet,despro- bl`emesquin'ontpasunesolutiona lgor ith- mique. •nousve rrons´egalementquecer tainsprobl`e- mesn'o ntpasdesolution ssatisfai sante sen termed'e ffi cacit´e. 4

Introductionetmotivations(III)

Quanduninfo rmaticie ntenter´esoudreunprobl`eme etqu 'ilneparvientpas` ar´esou dreceprobl`eme, ila dopteg´en´eralementd euxattitudes: •(versionoptimiste)ils edit:"jepenseque jesu isprocheder ´eussir,jevaiscorri ger quelquesd´etails etajouterlesdernierscas quemon algorit hmeneconsid`erepas"; •(versionplusr´ealiste) ilsedi t:"jesuis partisurdemauvai sesbase s,j evaisrecom- mencer`az´ero... " 5

Introductionetmotivations(III)

Apr`esavoirsuivic ecours,cemˆemei nformati-

cienseren drapeut- ˆetrecompteq ue: •lep robl`emequ'ilestcens´er´es oudreestin- solublealgorithmiqu ement:iln'existeau- cunalgo rithmequipeutler´esoudreetil n'enexiste rajamais!

Avouezqu'ilestin t´eressantdeserend recomp te

dece ph´enom`e ne! 6

Introductionetmotivations(IV)

Ilya une aut resituatio no`ulecoursde calcu-

labilit´eetcomplixit´e vousse ratr`esutile: •Patron:vulahauss ede sprix dup´et role, nousne pouvons plusgaspiller !Jeveux quetous nosrepr´ ese ntantsdecommerce sed´ eplacentoptimalement:"plus1km de trop!!!"Maisil nef autpasnonpl usper dre dute mps`alaplanifica tion!Fa ites- moiun programmequicalculeraleci rcuitopt imal pournosre pr´esenta ntschaquematin!!! •Vous:bienp atr on... 7

Introductionetmotivations(IV)

Deuxsituatio nssontpossibles:(i)vousave z

leco ursdecalculabilit´ eetcom plexit´e. 8

Introductionetmotivations(IV)

Situation(i):apr`estroissem ainesdetr avai l

`ala rec her che d'u nal go rit hme e ffi cac epo ur r´esoudreleprobl`emedevot repat ron,vous vousr´esig nez`aallerletrouverpouradm et- treque vousˆetesc ertainementtrop stupideet quevous n'arriv ezpas`ar´esoudresonprobl`eme dema ni`eree ffi cace(lesseuls algorithmes que vousaveztrou v´esnet erminentpasenune journ´eemˆemesurlamachin elaplusrapi dede laco mpagnie...)Votrepatronperdsoncalme etvou slicencie! 9

Introductionetmotivations(IV)

Situation(ii):vouscommencez`at ravaillersur

lepro bl`emeetvousvousrendezco mptequ eles seulessolutionsqu evoustrouvez´enum`erent chaquecircuitpossi ble(leprobl`em ec'estqu'il yenaunnombreexponentiel),aucunedes heuristiquesauquellesvousavezpens´ enemarche pasdanstous lescas !Etl`a ,vousvousrap- pelezlebonvie uxtemp s:quan dvousˆetiez ´etu dia nt. .., etl eco ur sde cal cul abi lit ´eet com - plexit´equevousavezsuivi! 10

Introductionetmotivations(IV)

Confiant,vousallezdanslebureaudevotre

patronetvousluidi tesquele probl`em en'est passoluble e ffi cacementetqu'ilfaitpartie des probl`emesNP-Complet,etdonc quevotrepa- trondevras econtenterd'uneapp roxim ation duci rcuitlepluscourt!

Normalement,votrepatronvousf´eliciter a(de

nepas avoirche rch´eenvainune solutionef- ficaceetexacte auprob l`eme,recherchequ i`a coupssˆuraura itdur´elereste devotrecarri`ere) etvou sobtiendrezu nepromotion!!! 11

Introductionetmotivations(IV)

Sivot repatronpersi stedanssonobstina tion,

vousfaitesd ´efilerdanssonbureau touslesin- formaticiensquiontd´ej`aessay´eder´ esoudre e ffi cacementunprobl`em eNP-Co mpletetqui n'ysontj amaispa rvenus! 12

Notionsdeproblemeet d'algo rithme(I)

Qu'est-cequ'unprobl`eme?

Commen¸conspardonnerquelquesex emplesde

probl`emes: ouimpair; •calculerlePGCDdedeu xnombres naturels metn; •´et ant don n´eu ngr aph Getdeu xsommets metndece graphe,d´ eterminersiil ex- isteunchem inmena ntdem`andansce graphe; 13

Notionsdeproblemeet d'algo rithme(I)

Qu'est-cequ'unprobl`eme?

•´eta ntd on n´eu nep roc ´edu reP asc al, et un vecteurdevaleu rspourl esparam`etres"in- put"delap roc ´edure,d ´eterminersilapro- c´edureterminesurce svaleurs"input"(pro- bl`emedel'arrˆet). 14

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unprobl`eme?

Quellessontlescaract ´eristiquesd 'unprobl` eme? •unpr obl`emeestunequestion"g´en´e rique", c'est-`a-direqu'unprobl`emecontien tdes param`etresouvariableslibres.Lor sque l'on attribueunevaleur`a cesvariabl eslibreson obtientuneinstancedupr obl`eme; •unp robl`emeexisteind´ependeme ntdetoute solutionoudelanotiond eprogr ammepo ur ler´ esoudre; •unpr obl`emepeutavoirplusieurssol utions, plusieursalgorithmesdi ff

´erentspeuventr´e-

soudrelemˆemepro bl`eme . 15

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unprobl`eme?

Nousnousi nt´e resserons`auneclassesp´eciale depr obl`emes:lesprobl`emesded´ecision. Unpr obl`emeestditded´ ecisionsila r´epon se auxinstan cesduprobl`emeestsoit ouisoit non.

Exemples:

•D´eterminersiouiounonunnombree ntier nestpair estunprobl`emed ed´ecisi on; •Parcont red´eterminerlalo ngueurminimale duci rcuitquipassepartouslessom me ts d'ungraphe n'estpasunpr obl`emeded´ecis ion. 16

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unprobl`eme?

Lacl assedesprobl`emesd ed´ecisi onestlimit´ee maissu ffi santepourillust rerlesnotio nsqui nousi nt´eressent.Pournepassurcharger(inu- tilement)laformalisation, nousno uslimiterons laplu spartdutem psauxprobl `emesd ed´ecision.

Lestech niquesquenousallons´etudierso nt

Nousve rrons´egalementque,pa rexemple,la

plupartdesprobl`em esd'optim isationsont"´equivalents" (pourunenotion d'´ equivalenceque nouspr´eciserons plustard) `adesprobl`eme sded´ec ision. 17

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unalgorithme

Maintenantquenousavonsuneid´ eeintuit ive

etpr ´ecisedecequ'estunprobl `emeess ayo ns depr ´eciserquelquepeulanotiond'algorithm e (ouenc oredeprogramme).

Derri`erelanotiond'a lgorit hmesetrouvelano-

tiondeproc´edureeffectivepourr´esou dreun probl`eme(touteslesinsta ncesd'unprobl`eme).

Unpr ogrammePascalestuneproc ´edureef-

fective.Pourquoi?Lecode Pascalpeut-ˆetre compil´eetensuiteex´ecut´e "m´ecaniquement" parlepr ocesse ur.Uneautrecaract´eristiquees- sentielled'uneproc´edure e ff ectiveestqu'elle contientexactementlamarche` asuivrepour r´esoudreleprobl`emeetqu' aucune d´ecisionsup- pl´ementairenedoitˆetrepriselorsdel 'ex ´ecution dela proc´e dure. 18

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unalgorithme

Voiciunexempl ed'une proc´edurequin'estpa s

e ff ectivepourr ´esoudreleprobl `emedel'arrˆet:

D´eterminezsileprogrammen'apas de

boucleinfiniesoud 'appelsr´ecursifs infinis.

Ilest clairqu ecettesolution n'estpase

ff ective lesbouc lesinfiniesoulesappelsr ´ecursifsinfi- nis.Notonsquenous´ etablir onsdans las uite dece coursqu'il n'existeauc uneproc´edur eef- fectivepourr´esoudre leprobl`eme del'arrˆet. 19

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unalgorithme

Danslasuite, nou saurionspuutiliserla no-

tiond'algor ithmes´ecritsdansunlangagede programmationusuelpourformaliserlanot ion depr oc´eduree ff ective.

Nousnec hoisi ronspascetteoptioncarel le

seraittroplourd e.Ene ff et,pourqu 'unpro- gramme´ecritdansun langageusuel(comme

Pascal)soituneproc´ eduree

ff ective,ilfautque lepro grammesoitcompil´e. 20

Notionsdeprobl`eme etd'alg orithme(II)

Qu'est-cequ'unalgorithme

Cetteindirect ioncompliquelaformalisation.

Pour´evit ercette´etapede"compi lation",nous adopteronsdeslangagesdeprogr ammationpri - mitifsquiontunef ormetelleme ntsimpleq ue leurproc´ed ured'interpr´etation(commen tles ex´ecuter)estimm´ediat e.Nous´ etudironsen particulierleformalismedelamachinedeTur- ing. sid´er´eecommee ff ectivepourr´esoudr eunprobl`eme , ilfa utquecelle-ciseterm inesurtout eslesin- stancesduprobl`eme. 21

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Siun probl` emedoitˆetrer´esoluparunep roc´edure e ff ective,ilestna turelqu elesins tancesdu probl`emessoientaccessibles `alaproc´edureef- fective.Pourcela,nous avonsbesoind' un encodagedesinsta ncesduprobl`eme.Cet encodagedoitpouvoirˆet remanipul´ep arla proc´eduree ff ective.

Sino us´ecrivionsnos proc´edurese

ff ectives`a l'aided'unlang agedeprogramma tionusuel, nousenc oderionslesinstancesdeprobl` emes `al' aid ed' ent ier s,d es´ eq uen ces d'e nti ers ,de chaˆınesdecaract`eres,... 22

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Ici,nous adopteronsunpo intdevueunpeu

plusabstr aitetconsid´ereronsseuleme ntdes chaˆınesdecaract`eressurun alphab etfini.

Remarque:Ilest´evidentq uecela ests u

ff isant:ene ff et,detout esfa¸c onstoutesttou- joursramen´ed 'unefa¸conoud'unea utre`ades chaˆınesde0etde1. 23

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Quelquesd´efinitions

Unalphabetestunens emblefin idesymboles,

danslasui tenousutil iserons 1 2 ,...pour d´esignerdesalphabets.

Quelquesexemplesd'alphab ets:

={a,b,c,d},

Notonsquelac ara ct´eri stiqueimportanted'un

alphabetestsonnombred'´el´ements etno n pasless ymbolespart iculiersquilecomposent (cessymbole sn'ontaucuneinterpr´etation). 24

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Quelquesd´efinitions

UnmotsurΣestune s´equence finied'´el´ements de

Parexem ple:ababcdcdabcdestunm otsurΣ=

{a,b,c,d}.

Lalongueurd'unmote stlenomb redesym-

bolesqu'ilco ntient.

Parexem ple:lalongueurdelas´ equ encew=

ababcdcdabcdest12, onnoteracelalong(w).

Onuti lisera´egalementlanotationw(i)pour

d´enoterlei e symboledumotw,et?pour d´enoterunmotvide(delo ngueu rnulle).. 25

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Onapp elerafonctiond'encodagelafo nction

quitr ansformeuneinstanceparticuli`ered' un probl`emeensoncodageente rmedem ot.

Danslasuiten ou sconsid´ererons quechaque

instanced'unprobl`emees trepr´esenta blepar unes´ equencefiniedesymboles. 26

Notionsdeprobl`eme etd'alg orithme(II)

Formalisationdelanotiondeprobl`eme

Soitunprob l`emede d´ecisiondontlesinstances

sontencod´ eespardesmotsd´efinissurunal - phabet .L' ensembledetouslesmotsd´efinisquotesdbs_dbs16.pdfusesText_22

[PDF] calculabilité et complexité exercices corrigés

[PDF] fonction calculable

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017