Calculabilité
Introduction. 0.1 Quelques exemples. Les cours d'informatique que vous avez eu peuvent donner une impression que pour chaque probl`eme on peut trouver un
Introduction `a la calculabilit´e
Théor`eme. Toute fonction µ-récursive est calculable par une machine de Turing. 1. les fonctions primitives récursives de bases sont calculables par machine de
Introduction à la calculabilité et à la complexité
Ou encore : « Toute fonction mécaniquement calculable est Turing-calculable. » Voici donc notre définition d'algorithme : les machines de Turing. 2.4 Langages.
Cours de calculabilité et complexité
Introduction et motivations (IV). Deux situations sont possibles : (i) vous avez malheureusement renoncé `a suivre le cours de calculabilité et complexité
Calculabilité Cours 1 : machines de Turing
1 Introduction. Une machine de Turing est un objet mathématique défini en 1936 par Alan Turing
Calculabilité - Décidabilité I. Introduction II. Problèmes de décision
Comme tout langage actuel peut être compilé en assembleur il peut aussi être compilé en langage des machines de Turing. Les fonctions calculables et les
Calculabilité et complexité
Voici un nouveau livre d'introduction à la théorie des langages de la calculabilité et de langages formels que la calculabilité et la complexité.
Cours Logique et Calculabilité
Calculabilité. Ce cours est basé sur le livre de Sipser [Sip06] et le cours de Kari [Kar13]. 3.1 Introduction. Une machine de Turing est un objet
Complexité et calculabilité
3 sept. 2022 Introduction to Automata Theory Languages & Computation. ... Langages formels
Machine de Turing - Informatique Théorique 2 Licence 3 informatique
Introduction. Langage reconnu. Fonction calculable. Indécidabilité. Objectifs de la séance 04. Connaitre la définition d'une machine de Turing.
[PDF] Introduction `a la calculabilit´e - ORBi
Référence Pierre Wolper Introduction `a la calculabilité - 2i`eme édition Dunod 2001 1 Page 2 Chapitre 1 Introduction 2
[PDF] INTRODUCTION À LA CALCULABILITÉ
22 jan 2017 · Cet ouvrage a pour vocation de résumer de façon claire l'ensemble des résul- tats fondamentaux en calculabilité en particulier en ce qui
[PDF] Introduction à la calculabilité et à la complexité - Irif
1 Introduction Dans ce cours : – Formaliser la notion de calcul : qu'est-ce qu'une « méthode effective de calcul »? Qu'est-ce qu'un algorithme ?
[PDF] Calculabilité - Irif
1 1 1 Définition de fonctions récursives primitives Dans le cadre défini dans l'introduction un prédicat P sur Nk correspond au probl`eme (U B)
(PDF) Introduction à la calculabilité Pierre Wolper - Academiaedu
1 Chapitre 1 Introduction 2 1 1 Motivation • Comprendre les limites de l'informatique • Distinguer probl` emes solubles et insolubles par des algorithmes
[PDF] Calculabilité Cours 1 : introduction et machines de Turing
Une machine de Turing universelle enti`erement mécanique a été réalisée en Lego 1 Remarquons que l'existence de fonctions non calculables implique que pour d'
[PDF] Cours Logique et Calculabilité
6 avr 2017 · 3 1 Introduction 3 5 1 Thèse de Church-Turing version physique certaines fonctions ne sont pas calculables : il n'existe pas
[PDF] Introduction `a la calculabilité - Loria
d'optimisation et complexite Conclusion Introduction `a la calculabilité 1 Motivation 2 Que signifie“calculer” ? Les automates Les machines de Turing
[PDF] Cours de calculabilité et complexité
Introduction et motivations (II) En est-il de même pour certains projets en in- formatique Y a-t-il des limites `a ce que nous
[PDF] Introduction `a la calculabilité - LACL
17 sept 2018 · 1 2 1 Les choses calculables Nous allons conduire une études théorique de la puissance de calcul des programmes informatiques
Coursdecalculab ilit´e
etcom plexit´eProf.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 gCompagny,1997.
Ilest fortementrecommand´edese pro-
curerlap remi`erer´ ef´erence,etdeconsulter lesdeux autres!!! Mat´erielLessli desutilis´eslorsde scoursseront disponiblessurlapagewebducours. 1Planducours
•Introduction-Motivations •Notionsdeprobl`e mes etd'algorithmes •Cardinalit´edesensembles-Diagonale deCantor
•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 leIntroductionetmotivations(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.
3Introductionetmotivations(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. 4Introductionetmotivations(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... " 5Introductionetmotivations(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! 6Introductionetmotivations(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... 7Introductionetmotivations(IV)
Deuxsituatio nssontpossibles:(i)vousave z
leco ursdecalculabilit´ eetcom plexit´e. 8Introductionetmotivations(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! 9Introductionetmotivations(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! 10Introductionetmotivations(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!!! 11Introductionetmotivations(IV)
Sivot repatronpersi stedanssonobstina tion,
vousfaitesd ´efilerdanssonbureau touslesin- formaticiensquiontd´ej`aessay´eder´ esoudre e ffi cacementunprobl`em eNP-Co mpletetqui n'ysontj amaispa rvenus! 12Notionsdeproblemeet 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; 13Notionsdeproblemeet 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). 14Notionsdeprobl`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 . 15Notionsdeprobl`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. 16Notionsdeprobl`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. 17Notionsdeprobl`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. 18Notionsdeprobl`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. 19Notionsdeprobl`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(commePascal)soituneproc´ eduree
ff ective,ilfautque lepro grammesoitcompil´e. 20Notionsdeprobl`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. 21Notionsdeprobl`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,... 22Notionsdeprobl`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. 23Notionsdeprobl`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). 24Notionsdeprobl`eme etd'alg orithme(II)
Formalisationdelanotiondeprobl`eme
Quelquesd´efinitions
UnmotsurΣestune s´equence finied'´el´ements deParexem 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).. 25Notionsdeprobl`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. 26Notionsdeprobl`eme etd'alg orithme(II)
Formalisationdelanotiondeprobl`eme
Soitunprob l`emede d´ecisiondontlesinstances
sontencod´ eespardesmotsd´efinissurunal - phabet .L' ensembledetouslesmotsd´efinis sur peutˆetrepar titionn´eentroi ssous-ensem- bles: •lesmots repr´esentant desinstancesdupro- bl`emepourlesquelles lar´ep onseestoui, nousapp eleronscesinstanceslesinstances positivesdupr obl`eme; •lesmots repr´esentant desinstancesdupro- bl`emepourlesquelles lar´ep onseestnon, cesso ntlesinstancesn´egatives; •lesmots quinerepr´ese ntentpasd esin- stancesduprobl`emec onsid´e r´e. 27Notionsdeprobl`eme etd'alg orithme(II)
Formalisationdelanotiondeprobl`eme
Lesdeux derni`erescl assessontsouventre-
group´eesetainsinousobtienons parchaque probl`emeunepartitiondel 'ensemble desmots endeu xsous-ensemb les: •lesmots quirepr´esent entdesins tancespos- itivesduprobl`e me; •lesmots quirepr´esent entdesins tancesn´e- gativesduprobl`emeouquiner epr ´esentent pasd'inst anceduprobl`eme. 28Notionsdeprobl`eme etd'alg orithme(II)
Formalisationdelanotiondeprobl`eme
Unpr obl`emepeutdoncˆetrecara ct´eris´epar l'ensembledesmotsquisontd esinstance spos- itivesduprobl`e me.Nou sappeleronsunensem- bledemots unla ngage.Unlangageestunens embled emotsd´efinis
surlem ˆemeal phabet.Souventnousnefer onspasladist inctio nentre:
•r´esoudreunprobl`eme; •reconnaˆıtredemani`ereeffectivelelang agequotesdbs_dbs45.pdfusesText_45[PDF] isoe prof principal
[PDF] hsa prof
[PDF] indemnite tuteur stagiaire education nationale
[PDF] prime prof principal contractuel
[PDF] evaluation anglais 6ème description physique
[PDF] indemnité prof principal agrégé terminale
[PDF] indemnités vacances éducation nationale
[PDF] enseignant contractuel vacances d'été
[PDF] entretien d'embauche la meilleure défense c'est d'être préparé
[PDF] cdi prof contractuel
[PDF] planification annuelle français secondaire 1
[PDF] planification annuelle français secondaire 3
[PDF] planification français secondaire 4
[PDF] dernier pays indépendant dans le monde